稀疏矩阵转置的乘法速度慢。

Question

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

我的代码中矩阵 A 为：

501×501 SparseMatrixCSC{Float64, Integer}，存储了1501个条目

以下是用随机生成的 f0 = rand(Float64,501,1) 进行乘法运算得到的结果： 方法1 A_tr = transpose(A) @benchmark A_tr*f BenchmarkTools.Trial: 10000次样本测试，1次评估。

范围 (min … max)： 350.083 μs … 9.066 ms ┊ GC (min … max)： 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。 方法2 A_tr = Matrix(transpose(A)) @benchmark A_tr*f BenchmarkTools.Trial: 10000次样本测试，1次评估。

范围 (min … max)： 87.375 μs … 210.875 μs ┊ GC (min … max)： 0.00% … 0.00%

时间中位数： 88.542 μs ┊ GC 中位数： 0.00%

时间（平均值±σ）：89.286 μs ± 3.266 μs ┊ 垃圾回收（平均值±σ）：0.00% ± 0.00%

内存预估：4.06 KiB ，分配预估：1。

方法3

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

@benchmark A_tr*f

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

范围（最小值...最大值）：2.102μs…1.017ms ┊ 垃圾回收（最小值...最大值）：0.00%…99.40%

时间（中位数）：2.477μs ┊ 垃圾回收（中位数）：0.00%

时间（平均值±σ）：2.725μs ± 13.428μs ┊ 垃圾回收（平均值±σ）：6.92% ± 1.41%

内存预估：4.06 KiB ，分配预估：1。

为什么方法1不能产生类似于方法3的性能？我可能缺少一些基本知识。

感谢您的帮助！

- andresdrenik

---

不是答案，但转置稀疏矩阵并不是一项简单的操作。一旦计算出转置，乘法应该会很快。因此，您可能希望计时各个步骤，并查看时间花在哪里。如果可以避免进行转置，那将有所帮助。 - StefanKarpinski

如果我没记错的话，transpose(A) 通过 LinearAlgebra 创建了 A 的一个视图，这需要为每次访问翻译坐标。我不认为快速进行 MV 数学运算的方法会通过该接口起作用。将转置转换为矩阵对象而不是尝试通过视图进行数学运算更快，这并不让我感到惊讶。 - CJR

Answer 1

1501个存储条目的501×501 SparseMatrixCSC{Float64, Integer}

Integer是一个抽象类型。这正是导致代码变慢的原因。请参考性能提示。

- SGJ

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

据我所知，通过LinearAlgebra转置（transpose）A会创建一个视图，这需要为每个访问翻译坐标。我不认为快速进行MV数学运算的方法能够通过该接口工作。将转置转换为矩阵对象而不是尝试通过视图进行数学运算比较快，这并不令人惊讶。

transpose(A)产生Transpose(A)，其中Transpose是一个懒惰的转置包装器。对于稀疏矩阵-密集向量乘法，有专门的方法，不需要对A进行任何变异。

- Martin Möddel

---

谢谢Martin！我是Julia的新手，我没有意识到这一点。事实上，我将矩阵A定义为SparseMatrixCSC {Float64，Integer}。我的直觉是，在怀疑时，更通用的类型应该更好。再次感谢，我从你那里学到了新东西！ - andresdrenik