用Python计算稀疏矩阵的N个最小特征值

Question

我想在Python中找到一个稀疏矩阵的N个最小特征值。我试过使用scipy.sparse.linalg.eigen.arpack这个包，但计算最小特征值的速度非常慢。我看到有提到一种叫做“移位反转”的模式，但当我尝试使用它时，系统给我发了个错误消息，告诉我这个模式还不支持。有没有什么建议我该怎么做呢？

Answer 1

SciPy版本

对比一下scipy.sparse.linalg.eigs在SciPy v0.9的文档和scipy.sparse.linalg.eigs在SciPy v0.10的文档，可以发现从v0.10开始，shift-invert模式已经实现并且可以正常使用。具体来说，v0.9的文档中提到的sigma参数没有实现，但v0.10的文档没有说明这一点。

如果你没有SciPy v0.10或更高版本，安装最新版本应该可以让你使用稀疏特征求解器的shift-invert模式。

寻找小特征值很慢

正如问题中提到的，可以使用ARPACK接口来寻找小特征值。这是通过在调用scipy.sparse.linalg.eigs时传入which='SM'来实现的。不过，正如问题所说，这个过程比较慢。在SciPy教程的使用ARPACK解决稀疏特征值问题的部分中也确认了这一点，内容如下：

请注意，ARPACK通常更擅长寻找极值特征值，也就是那些数值比较大的特征值。特别是，使用which = 'SM'可能会导致执行时间变慢和/或结果异常。更好的方法是使用shift-invert模式。

实验

我们来看看一些代码，尝试在SciPy的v0.9和v0.10中使用shift-invert模式。在这两种情况下，我们将使用以下代码。

from scipy.sparse import identity
from scipy.sparse.linalg import eigs

A = identity(10, format='csc')
A.setdiag(range(1, 11))
eigs(A, 3, sigma=0) # find three eigenvalues near zero using shift-invert mode

SciPy v0.9

在SciPy v0.9中运行这段代码会抛出一个异常。

NotImplementedError: shifted eigenproblem not supported yet

SciPy v0.10

在SciPy v0.10中运行这段代码会得到预期的结果。

(array([ 1.+0.j,  2.+0.j,  3.+0.j]),
 array([[ -1.00000000e+00+0.j,   5.96300068e-17+0.j,   9.95488924e-17+0.j],
       [  3.55591776e-17+0.j,   1.00000000e+00+0.j,  -4.88997616e-16+0.j],
       [ -3.79110898e-17+0.j,   1.16635626e-16+0.j,   1.00000000e+00+0.j],
       [ -1.08397454e-17+0.j,   1.23544164e-17+0.j,   1.78854096e-15+0.j],
       [  1.68486368e-17+0.j,  -9.37965967e-18+0.j,   2.05571432e-16+0.j],
       [ -2.97859557e-19+0.j,  -3.43100887e-18+0.j,   3.35947574e-17+0.j],
       [  1.89565432e-17+0.j,  -3.61479402e-17+0.j,  -1.33021453e-17+0.j],
       [ -1.40925577e-18+0.j,   3.16953070e-18+0.j,   7.91193025e-17+0.j],
       [  6.76947854e-19+0.j,  -3.75674631e-19+0.j,   3.61821551e-17+0.j],
       [ -3.07505146e-17+0.j,  -6.52050102e-17+0.j,  -8.57423599e-16+0.j]]))