稀疏特徵值：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構造我的方程組的雅可比行列式的緻密基質和calc_pde_analytic_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

對於足夠大和稀疏的矩陣，稀疏求解器應該更快。我跑下面的片段爲N的範圍（150，550，50）和N = 1000：

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。