matrix-dense-vector multiplication faster for symmetric/hermitian matrices using adjoint

[jamblejoe]

As Julia is for now exclusively using CSC storage format, the matrix-dense-vector multiplication is faster for symmetric/hermitian matrix A if one computes A' * v instead of A * v. A simple example script hinting this is the following:

julia> let
       for D in [10^3, 10^4, 10^5, 10^6]
           A = sprand(D,D,1/D)
           A = A+A'
           v = rand(D)
           w = similar(v)
           @btime mul!($w, $A, $v)
           @btime mul!($w,$A',$v)
       end
       end
  3.500 μs (0 allocations: 0 bytes)
  1.540 μs (0 allocations: 0 bytes)
  23.100 μs (0 allocations: 0 bytes)
  14.100 μs (0 allocations: 0 bytes)
  305.400 μs (0 allocations: 0 bytes)
  206.300 μs (0 allocations: 0 bytes)
  13.283 ms (0 allocations: 0 bytes)
  4.167 ms (0 allocations: 0 bytes)

On

Julia Version 1.7.0
Commit 3bf9d17731 (2021-11-30 12:12 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

and MKLSparse v1.1.0.

Should MKLSparse detect this with ishermitian ?

[amontoison]

We should add a better dispatch if the sparse matrix is wrapped in Symmetric or Hermitian. I remember that they have a dedicated routine for symmetric matrices (sparse_symv). It should be even faster than A' * v.