julia - 稀疏矩阵对角化的快速方法（julia）：为什么 arpack 这么慢？

Question

对于我的问题，我只对稀疏实对称矩阵 A 的几个特征态（具有最小特征值）感兴趣。据我所知，arpack 使用不同的方法，并且应该比 LinearAlgebra 包的完全对角化快得多。为什么在我的示例中速度要慢得多？

using LinearAlgebra, SparseArrays, Arpack    
A = sprand(5000,4995,0.01) # Matrix with 5-dimensional nullspace
H = sparse(Hermitian(A*A'))
@time E, v  = eigen(Matrix(H))
@time E, v  = eigs(H, nev=10, which=:SM)

> 12.059152 seconds (27 allocations: 764.733 MiB, 0.72% gc time)
> 37.628222 seconds (680 allocations: 1.424 GiB, 0.47% gc time)

Answer 1

当用 计算最小特征值时eigs，有必要在算法的每次迭代中计算(H - λ*I)\x一些移位。λ在我们的实现中，eigs这会导致H - λ*I每次迭代的稀疏分解，这是昂贵的。此外，与计算大值相比，计算最小值有时需要多次迭代，但我怀疑稀疏分解的成本占主导地位。which=:LM您可以通过计算而不是:SM因为前者只需要矩阵向量乘法来了解成本。