JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
45.68k stars 5.48k forks source link

Slow matrix vector product (adjoint dense * SparseCSC) #32402

Closed davidbp closed 5 years ago

davidbp commented 5 years ago

When multiplying Dense matrices by sparse vectors the speed seems to degrade too much if the dense matrix is an adjoint.

percent_nonzeros =  0.01
W = rand(15000, 2);
x_sp = sprand(15000, percent_nonzeros);
Wt = copy(W') 

@btime W'*x_sp
  285.560 μs (6 allocations: 304 bytes)

@btime Wt*x_sp
  522.068 ns (1 allocation: 96 bytes)

This seems to be related with #32195 but this is not matrix-matrix multiply. This is matrix-vector multiply

dkarrasch commented 5 years ago

Yes, the corresponding method for Adjoints is missing, but the one for Transposes exists:

julia> Wt = copy(transpose(W));

julia> @btime Wt*x_sp;
  501.161 ns (1 allocation: 96 bytes)

julia> @btime transpose(W)*x_sp;
  462.653 ns (3 allocations: 128 bytes)

I started translating the transpose method to adjoints, PR is coming soonish...