python - 稀疏特征值 : scipy. sparse.linalg.eigs 比 scipy.linalg.eigvals 慢

Question

我有一个奇怪的现象，虽然 scipy.sparse.linalg.eigs 对于稀疏矩阵应该更快，但我知道它运行得比正常的 eigvals 方法慢scipy:

In [4]: %timeit m.calc_pde_numerical_jacobian(m.initial_state)
10 loops, best of 3: 41.2 ms per loop

In [5]: %timeit m.calc_pde_analytic_jacobian(m.initial_state)
1000 loops, best of 3: 1.42 ms per loop

In [6]: %timeit m.calc_analytic_pde_eigs(m.initial_state)
1 loop, best of 3: 374 ms per loop

In [7]: %timeit m.calc_numeric_pde_eigs(m.initial_state)
1 loop, best of 3: 256 ms per loop 

所以方法 calc_pde_numerical_jacobian 构建了我的方程组的 Jacobian 的稠密矩阵，而 calc_pde_analytic_jacobian 正在解析地构建 Jacobian 的稀疏矩阵(csc 格式)。虽然分析方法在构造雅可比行列式的稀疏矩阵方面工作得更快，但是当使用 scipy 的特征值查找方法时，稀疏矩阵特征值方法更慢。我用来计算特征值的函数如下:

def calc_numeric_pde_eigs(self,state):
    return linalg.eigvals(self.calc_pde_numerical_jacobian(state))
def calc_analytic_pde_eigs(self,state):
    return sparse.linalg.eigs(self.calc_pde_analytic_jacobian(state),k=6,which='LR',return_eigenvectors=False)

有人知道这是怎么发生的吗？

Answer 1

对于足够大和稀疏的矩阵，稀疏求解器应该更快。我针对范围 (150, 550, 50) 和 N = 1000 中的 N 运行了以下代码段:

In [150]: from scipy import sparse

In [151]: from scipy import linalg

[...]

In [186]: N = 150

In [187]: m = sparse.random(N, N, density=0.05).tocsc()

In [188]: a = m.A

In [189]: %timeit sparse.linalg.eigs(m, k=6, which='LR', return_eigenvectors=False)
10 loops, best of 3: 20.2 ms per loop

In [190]: %timeit linalg.eigvals(a)
100 loops, best of 3: 9.66 ms per loop

并得到以下时间(以毫秒为单位):

N                    150   200   250   300   350   400   450   500   1000
sparse.linalg.eig   20.2  22.2  28.9  29.4  48.5  38.6  75.2   57.9   152
linalg.eigvals       9.7  17.0  24.5  37.0  52.7  63.3  82.5  105     482

在这种情况下，稀疏求解器具有竞争力的大小为 250-300。

时间可能取决于稀疏性(即矩阵的非零百分比)和非零元素的结构或模式。对于您的问题，在矩阵大于 512x512 之前，稀疏求解器可能不会更好。