为何1000×1000矩阵下scipy.sparse.linalg.eigs比linalg.eigvals更慢？

Great question—this counterintuitive performance result makes total sense once you dig into how these two functions work under the hood. Let's break down the key reasons:

1. Algorithmic Complexity Tradeoffs #

eigs relies on iterative methods (typically ARPACK) built to find a small subset of eigenvalues from large sparse matrices. Its true strength shines when k (the number of eigenvalues you're requesting) is much smaller than N (matrix size)—like k=10 or 20 for a 1000x1000 matrix.

But when you set k=500 (half the size of your matrix), the iterative approach loses all its advantages:

• ARPACK needs to run far more iterations to converge on 500 eigenvalues, and each iteration involves sparse matrix-vector multiplications that add up quickly.
• In contrast, scipy.linalg.eigvals uses direct dense solvers (from LAPACK) optimized for full eigenvalue decomposition. These solvers have an O(N³) complexity, but for k close to N, the iterative method's effective complexity often ends up being comparable or even worse than the direct approach—especially with the overhead of managing sparse data structures.

2. Optimization and Hardware Efficiency #

• Dense matrix operations (like those in eigvals) are heavily optimized for modern CPUs: they leverage multi-threaded BLAS libraries (e.g., OpenBLAS, MKL) and are cache-friendly, maximizing memory bandwidth and CPU utilization.
• Sparse matrix operations in eigs have more inherent overhead: even though your matrix is sparse, the irregular memory access patterns of sparse multiplications don't play as nicely with CPU caches. Plus, ARPACK may not utilize multi-threading as effectively as the dense LAPACK solvers by default.

3. Parameter Choices Impacting Runtime #

Your eigs call uses tol=0.0001 and targets the largest real part eigenvalues (which='LR'):

• A tighter tolerance means ARPACK runs more iterations to meet the precision requirement.
• Finding LR eigenvalues can sometimes require more convergence checks than other subsets (like magnitude-based eigenvalues), adding extra runtime.

Recommendations #

• Use eigs only when k is a small fraction of N (e.g., k < 10% of N). For k > ~30% of N, direct dense solvers will almost always be faster.
• If you need to stick with sparse methods, try loosening the tol parameter (if your use case allows lower precision) or experimenting with other solvers like scipy.sparse.linalg.eigsh (though this only helps for symmetric matrices—your random matrix isn't, so this may not apply here).
• Verify your BLAS/LAPACK configuration: ensure you're using a multi-threaded implementation (like MKL or OpenBLAS) to maximize dense solver performance.

Your Original Code and Results #

import scipy as sp
import scipy.sparse.linalg as lg
N = 1000
m = sp.sparse.random(N, N, density=0.05).tocsc()
a = m.A
%timeit lg.eigs(m, k=500, return_eigenvectors=False, which='LR', tol = 0.0001)
%timeit sp.linalg.eigvals(a)

eigs运行结果：3.62 s ± 520 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
eigvals运行结果：1.68 s ± 420 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

内容的提问来源于stack exchange，提问作者user566657