# What is the correct order to use factorization matrices in multiplication?

**URL:** <https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194>\
**Category:** General Usage\
**Tags:** question\
**Created:** [August 2, 2022, 8:41pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194 "2022-08-02T20:41:31Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 2, 2022, 8:41pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/1 "2022-08-02T20:41:32Z")

</div>

I tried to have the result of `` but it gave error. So, I tried `adj_factor.L*adj_factor.U*adj_factor.F*V` but it gave different result with `adj*V`.  
Could you please tell me what is the correct order of `L,U,P` to have the same result between?

```julia
using SparseArrays, LinearAlgebra, KLU

adj = sparse([1.0 0 0 0 0; 0 1 0 -1 0; 0 -1 1 0 0; 1 0 0 0 -1; 1 -1 0 0 0]);
V = [4,5,6,7,8];
adj_factor = klu(adj);

julia> adj*V
5-element Vector{Float64}:
  4.0
 -2.0
  1.0
 -4.0
 -1.0

julia> adj_factor*V
ERROR: MethodError: no method matching *(::KLU.KLUFactorization{Float64, Int64}, ::Vector{Int64})

julia> adj_factor.L*adj_factor.U*adj_factor.F*V
5-element Vector{Float64}:
 -8.0
 -7.0
 -7.0
 -8.0
  0.0

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 4, 2022, 2:26pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/3 "2022-08-04T14:26:56Z")

</div>

> [@Amro](#):
>
> `adj_factor*V`

What operation are you trying to perform here?

You normally use LU factors to _solve_ systems, i.e. you do `x = adj_factor \ V` to find the solution `x` of `adj * x = V`.

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [August 4, 2022, 2:43pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/4 "2022-08-04T14:43:18Z")

</div>

If it helps, the following holds

```julia
(adj_factor.L * adj_factor.U + adj_factor.F)==diagm(adj_factor.Rs)\adj[adj_factor.p,adj_factor.q] # true

```

Edit: as stevengj mentions, normally you decompose to solve a system, not to multiply the matrix with something (in that case you could directly use your matrix)

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 2:54pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/5 "2022-08-04T14:54:50Z")

</div>

My main goal is to find a way to accelerate the multiplication of two matrices (one or both are sparse/s). So, I though that factorizing one and multiplying it by the other can be faster.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 4, 2022, 3:01pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/6 "2022-08-04T15:01:56Z")

</div>

That will be significantly slower.

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 3:06pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/7 "2022-08-04T15:06:19Z")

</div>

Ok, is there a package in Julia for fast multiplication?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 4, 2022, 3:11pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/8 "2022-08-04T15:11:02Z")

</div>

Julia’s built in sparse matrix multiplication should already be pretty good. Is there a specific reason you think faster should be possible?

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 3:25pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/9 "2022-08-04T15:25:12Z")

</div>

I am profiling my code (takes 5 sec) against another program (coded in Fortran and takes 2.13 sec). It is a time loop simulation 1:25e-6:0.6.  
I found my code spends 1.5 sec at the line of multiplication (as in my first post). So, I started to think if there is a faster way to do the multiplication. I tried to use “MKLSparse.jl” but no gain. I am not sure if it is activated correctly in my julia.

```julia
julia> BLAS.lbt_get_config()
LinearAlgebra.BLAS.LBTConfig
Libraries:
└ [ILP64] mkl_rt.2.dll

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 4, 2022, 3:29pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/10 "2022-08-04T15:29:06Z")

</div>

How long is the Fortran spending in each part? The Fortran is likely using the same libraries as Julia for the multiplication, so I would think the time difference would be in a different part.

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 3:31pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/11 "2022-08-04T15:31:24Z")

</div>

I cannot access the source code in Fortran. I can only see the execution time.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 4, 2022, 3:35pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/12 "2022-08-04T15:35:15Z")

</div>

Other than the matrix multiplication, what are the other 3.5 seconds spent on in Julia?

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 4:09pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/13 "2022-08-04T16:09:45Z")

</div>

The remaining time is for solution x =A\b, multiplication (other simple matrices), addition, and storing.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [August 4, 2022, 5:11pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/14 "2022-08-04T17:11:44Z")

</div>

I would suggest to describe the problem in detail. It is possible to find examples of poor performance when multiplying matrices, especially when mixing dense and sparse matrices.

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [August 4, 2022, 7:32pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/15 "2022-08-04T19:32:29Z")

</div>

> [@Amro](#):
>
> ime loop simulation 1:25e-6:0.6.

Thanks for your tip. Actually, I just want to find a way to accelerate the multiplication. Like new libraries or method.

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [September 26, 2022, 10:31pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/16 "2022-09-26T22:31:39Z")

</div>

For solving `Ax=b` by using KLU. I don not know how it works after this point (I could not isolate `x`):

```julia
A_factor = klu(A);
(A_factor.L * A_factor.U + A_factor.F)*x =diagm(A_factor.Rs)\b[A_factor.p,Aj_factor.q]

```

Could you please help me here?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 27, 2022, 11:18am UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/17 "2022-09-27T11:18:35Z")

</div>

> [@Amro](#):
>
> I cannot access the source code in Fortran. I can only see the execution time.

So it may be using a completely different algorithm? Hard to compare with, then…

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 27, 2022, 11:21am UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/18 "2022-09-27T11:21:26Z")

</div>

> [@Amro](#):
>
> For solving `Ax=b` by using KLU. I don not know how it works after this point (I could not isolate `x`):

Just do `x = A_factor \ b`. (This is the first example in the [KLU.jl README](https://github.com/JuliaSparse/KLU.jl).)

> [@Amro](#):
>
> So, I started to think if there is a faster way to do the multiplication.

Factoring matrices _loses_ sparsity, so it will slow down multiplication. The reason to factor matrices is to do other things, like solving Ax=b.

Before you can optimize your code, you’re really going to have to learn a bit about how sparse-matrix algorithms work, in order to get some sense of what is fast and what is slow.

---

<div class="post-metadata">

**Author:** ![Amro](https://avatars.discourse-cdn.com/v4/letter/a/4491bb/32.png) [@Amro](https://discourse.julialang.org/u/Amro)\
**Post date:** [September 27, 2022, 1:20pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/20 "2022-09-27T13:20:43Z")

</div>

Thanks for your help!

> [@stevengj](#):
>
> Just do `x = A_factor \ b`. (This is the first example in the [KLU.jl README](https://github.com/JuliaSparse/KLU.jl).)

Yes, I just wanted to know how to solve it based on the the factoring matrices. (similar to x=U(L\P.b) in LU factorization).

Is there a package to solve klu(A)x=b in parallel similar to [MKLPardisoSolver](https://github.com/JuliaSparse/Pardiso.jl)?

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [September 27, 2022, 2:06pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/21 "2022-09-27T14:06:44Z")

</div>

It’s good, but is it the best (feel free to send me a private message, if not helpful here)? I saw a new format, and Julia package for recently, and while I didn’t mean to interject, I thought it might be relevant to the user here; see on other question where I also posted:

> [@Block Sparse Matrix](https://discourse.julialang.org/t/block-sparse-matrix/81465/2):
>
> It took me a while to find this, I recalled the first package that I put at the top of the list (maybe none applies to you, but posting just in case, what I found while searching): [https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680)[https://discourse.julialang.org/t/ann-announcing-threadedsparsecsr-jl/71343](https://discourse.julialang.org/t/ann-announcing-threadedsparsecsr-jl/71343)[https://discourse.julialang.org/t/ann-announcing-threadedsparsecsr-jl/71343](https://discourse.julialang.org/t/ann-announcing-threadedsparsecsr-jl/71343)[https://discourse.julialang.org/t/best-way-to-use-cusparsematrixbsr/86075](https://discourse.julialang.org/t/best-way-to-use-cusparsematrixbsr/86075)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 27, 2022, 2:47pm UTC](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194/22 "2022-09-27T14:47:47Z")

</div>

> [@Amro](#):
>
> (similar to x=U(L\P.b) in LU factorization).

For you the LU factorization you should also generally do `F \ b` with `F = lu(A)` in Julia. This is mathematically equivalent to `U \ (L \ P*b)` but is easier and probably more efficient (because it uses specialized lower-level routines and tries to work more in-place with fewer temporary vectors).

[Next page](https://discourse.julialang.org/t/what-is-the-correct-order-to-use-factorization-matrices-in-multiplication/85194.md?page=2)