# Slow sparse matrix-vector product with symmetric matrices

**URL:** <https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968>\
**Category:** General Usage\
**Created:** [May 29, 2017, 5:21am UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968 "2017-05-29T05:21:37Z")\
**Posts on this page:** 15\
**Page:** 2

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 29, 2017, 2:20pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/21 "2017-05-29T14:20:35Z")

</div>

> [@kristoffer.carlsson](#):
>
> I don’t think you can assume that A.data is symmetric.

You’re right, I forgot about that. If you only call `Symmetric(A)` if `A` is already symmetric in the first place, it works, but that would cripple the functionality.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [May 29, 2017, 6:44pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/22 "2017-05-29T18:44:38Z")

</div>

Here’s an implementation: [https://gist.github.com/481b0c03dd08d26af342573df98ddc21](https://gist.github.com/481b0c03dd08d26af342573df98ddc21)

Timings:

```julia
julia> include("symmetric_matvec.jl")
A_mul_B! (generic function with 92 methods)

julia> using MatrixMarket

julia> A = MatrixMarket.mmread("af_shell8.mtx");

julia> size(A)
(504855,504855)

julia> nnz(A)
17579155

julia> B = Symmetric(A);

julia> b = ones(A.n);

julia> using BenchmarkTools

julia> @benchmark B * b
BenchmarkTools.Trial: 
  memory estimate: 3.85 MiB
  allocs estimate: 2
  --------------
  minimum time: 22.198 ms (0.00% GC)
  median time: 26.073 ms (0.00% GC)
  mean time: 26.232 ms (0.87% GC)
  maximum time: 40.818 ms (0.00% GC)
  --------------
  samples: 191
  evals/sample: 1

julia> @benchmark A * b
BenchmarkTools.Trial: 
  memory estimate: 3.85 MiB
  allocs estimate: 2
  --------------
  minimum time: 21.040 ms (0.00% GC)
  median time: 23.167 ms (0.00% GC)
  mean time: 23.644 ms (1.27% GC)
  maximum time: 29.607 ms (6.07% GC)
  --------------
  samples: 211
  evals/sample: 1

```

---

<div class="post-metadata">

**Author:** ![jebej](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jebej/32/1784_2.png) [@jebej](https://discourse.julialang.org/u/jebej)\
**Post date:** [May 29, 2017, 6:52pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/23 "2017-05-29T18:52:55Z")

</div>

> [@DNF](#):
>
> since At\_mul\_B! is faster than A\_mul\_B!,

huh, I wonder why that’s the case…

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 29, 2017, 6:58pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/24 "2017-05-29T18:58:28Z")

</div>

I guess because you can more naturally traverse the matrix in column order instead of in row order when performing the multiplication. Just write out the product as a sum over the indices to see why.

I presume that BLAS may have some tricks up its sleeve to optimize memory access in any case, but at least the naive implementation of `At_mul_B!` should be faster than `A_mul_B!`.

---

<div class="post-metadata">

**Author:** ![jebej](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jebej/32/1784_2.png) [@jebej](https://discourse.julialang.org/u/jebej)\
**Post date:** [May 29, 2017, 7:03pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/25 "2017-05-29T19:03:42Z")

</div>

> [@DNF](#):
>
> I guess because you can more naturally traverse the matrix in column order instead of in row order when performing the multiplication. Just write out the product as a sum over the indices to see why.

You can just as well traverse the matrix in column order, multiplying the first element of the vector with the first column, and then the second element with the second column.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 29, 2017, 7:18pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/26 "2017-05-29T19:18:40Z")

</div>

Yeah, but then the result of each of those multiplications go into separate entries in the output vector, instead of each column-vector product accumulating into a single element in the output vector.

But no matter, I don’t really know how BLAS optimizes this stuff. I have just observed that `At_mul_B!` is faster by some significant amount, and that it seems easier to optimize it in a naive way.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [May 29, 2017, 8:11pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/27 "2017-05-29T20:11:38Z")

</div>

Yes `At_mul_B` is faster for CSC while it is the opposite for CSR.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [May 29, 2017, 10:06pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/28 "2017-05-29T22:06:56Z")

</div>

@kristoffer.carlsson Can the above implementation be improved in your opinion? What would be missing for a PR? All [this stuff](https://github.com/JuliaLang/julia/blob/master/base/sparse/linalg.jl#L46)?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [May 30, 2017, 7:07am UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/29 "2017-05-30T07:07:03Z")

</div>

It is tricky. I’m not sure it is so good to extract the triangular part using `triu` and `tril` directly when calling `Symmetric` because I think the expectation is that `Symmetric` is just a wrapper and doesn’t modify the data in anyway. On the other hand, having to extract the triangular part every time a matvec is done will be expensive so that is not really good either.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [May 30, 2017, 12:24pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/30 "2017-05-30T12:24:26Z")

</div>

I would think `Symmetric` is handy in that you can assemble only one triangle and claim it contains all the information of a symmetric operator. It’s often the case for matrices from the UFL collection, or in applications (e.g., Hessians in optimization). I’ll see if I can scan only one triangle efficiently without calling `tril()` or `triu()`.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [June 1, 2017, 3:28am UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/31 "2017-06-01T03:28:19Z")

</div>

I posted two other variants at the gist above along with benchmark results. The variants are:

1. `Symmetric()` calls `tril()` or `triu()` and `A_mul_B!()` is straightforward;
2. `Symmetric()` does not modify `A`, and `A_mul_B!()` skip irrelevant indices;
3. `Symmetric()` does not modify `A` but builds an index of relevant indices (corresponding to either the upper or lower triangle), and `A_mul_B!()` relies on that index.

Variant 1 has the disadvantage of modifying `A`. However, it seems to me that one of the reasons for using `Symmetric` is to save storage. This allows users to only assemble one triangle (e.g., in FEM or optimization). In addition, the sparse symmetric factorization packages I know only access one triangle. One could imagine _requiring_ the input `A` to be triangular when calling `Symmetric()`.

Variant 2 has the advantage of not modifying `A` and not requiring extra storage. Strangely, multiplying with the lower triangle by scanning row indices backward is slower than multiplying with the upper triangle (and scanning forward). Perhaps this can be improved?! The performance of the product with the upper triangle is basically the same as that of Variant 1.

Variant 3 costs an extra array of length `n` (the number of columns of `A`) that gives the initial/final index for each column. The performance is basically the same as that of Variant 1.

Comments?

---

<div class="post-metadata">

**Author:** ![andreasnoack](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andreasnoack/32/27_2.png) [@andreasnoack](https://discourse.julialang.org/u/andreasnoack)\
**Post date:** [June 1, 2017, 4:59pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/32 "2017-06-01T16:59:23Z")

</div>

Option 2. sounds like the right approach. It would be great with a PR.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [January 15, 2018, 3:35pm UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/33 "2018-01-15T15:35:18Z")

</div>

Any update on this? I can still confirm that `Symmetric` slows down the matrix-vector multiplication by a factor of 100 on my machine.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [July 28, 2019, 5:04am UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/34 "2019-07-28T05:04:04Z")

</div>

This issue should be solved in julia version 1.2 since a while. Please look at [#30018](https://github.com/JuliaLang/julia/pull/30018) and [#32689](https://github.com/JuliaLang/julia/issues/32689.%5Bdef%5D)

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [July 28, 2019, 7:19am UTC](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968/35 "2019-07-28T07:19:02Z")

</div>

Cool, that’s awesome! Thanks for your efforts.

[Previous page](https://discourse.julialang.org/t/slow-sparse-matrix-vector-product-with-symmetric-matrices/3968.md?page=1)
