稀疏矩阵转置的缓慢乘法

Question

我在将稀疏矩阵的转置与列向量相乘时遇到速度问题。

在我的代码中，矩阵 A 是

501×501 SparseMatrixCSC{Float64, Integer} with 1501 stored entries:

⠻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣦⠀⢸

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

这些是我用 f0 = rand(Float64,501,1):

乘法得到的结果

方法一

A_tr = transpose(A)

@benchmark A_tr*f

BenchmarkTools.Trial：10000 个样本，1 次评估。

范围（最小…最大）：350.083 μs…9.066 ms┊GC（最小…最大）：0.00%…95.44%

时间（中值）：361.208 μs ┊ GC（中值）：0.00%

时间（平均值±σ）：380.269μs±355.997μs┊GC（平均值±σ）：4.06%±4.15%

内存估计：218.70 KiB，分配估计：11736。

方法二

A_tr = Matrix(transpose(A))

@benchmark A_tr*f

BenchmarkTools.Trial：10000 个样本，1 次评估。

范围（最小...最大）：87.375 μs ...210.875 μs ┊ GC（最小...最大）：0.00% ...0.00%

时间（中值）：88.542 μs ┊ GC（中值）：0.00%

时间（平均值±σ）：89.286μs±3.266μs┊GC（平均值±σ）：0.00%±0.00%

内存估计：4.06 KiB，分配估计：1.

方法三

A_tr = sparse(Matrix(transpose(A)))

@benchmark A_tr*f

BenchmarkTools.Trial：10000 个样本，9 次评估。

范围（最小...最大）：2.102 μs ...1.017 ms ┊ GC（最小...最大）：0.00% ...99.40%

时间（中值）：2.477 μs ┊ GC（中值）：0.00%

时间（平均值±σ）：2.725μs±13.428μs┊GC（平均值±σ）：6.92%±1.41%

内存估计：4.06 KiB，分配估计：1.

为什么方法 1 不能产生与方法 3 相似的性能？我可能在这里遗漏了一些基本的东西。

感谢您的帮助！

Answer 1

501×501 SparseMatrixCSC{Float64, Integer} with 1501 stored entries

Integer 是抽象类型。这就是减慢代码速度的原因。见 performance tips.

Answer 2

使用以下 MWE

using LinearAlgebra, BenchmarkTools, SparseArrays

A = sprand(501,501,0.005)
At1 = transpose(A)
At2 = sparse(Matrix(transpose(A)))
f = rand(Float64,501,1)

你会发现

之间没有显着的性能差异

@benchmark $At1*$f

和

@benchmark $At2*$f

正如@SGJ 所指出的，诀窍是使用基本类型作为容器的参数，即 SparseMatrixCSC{Float64, Int64} 而不是 SparseMatrixCSC{Float64, Integer}，这是 sprand(501,501,0.005) 生成的。

@CRJ

IIRC, transpose(A) makes a view of A through LinearAlgebra, which requires translating coordinates for every access. I don't think the fast ways of doing MV math will work through that interface. I'm not surprised that converting your transpose to a matrix object instead of trying to do math through the view is faster.

transpose(A) 产生 Transpose(A)，其中 Transpose 是惰性转置包装器。对于 sparse-matrix-dense-vector 乘法有 tailored methods，不需要 A.

的任何突变

稀疏矩阵转置的缓慢乘法

Slow multiplication of transpose of sparse matrix

sparse-matrix

julia