计算矩阵的特征值有多贵？

计算矩阵的特征值有多贵？

最佳算法的复杂性是什么？

如果我有一个1000 x 1000的矩阵,在实践中需要多长时间？我认为如果矩阵稀疏会有帮助吗？

是否存在特征值计算不会终止的情况？

在R,我可以计算特征值,如下面的玩具示例所示:

m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14  3

有谁知道它使用什么算法？

是否还有其他(开源)软件包可以计算特征值？

1> amit-agrawal..：

---

大多数用于特征值计算的算法都缩放到大哦(n ^ 3),其中n是(对称和方形)矩阵的行/列维度.

要了解迄今为止最佳算法的时间复杂度,您必须参考科学计算/数值方法的最新研究论文.

但即使你假设情况更糟,对于1000x1000矩阵,你仍然需要至少1000 ^ 3次操作.

R默认使用LAPACK例程(DSYEVR,DGEEV,ZHEEV和ZGEEV)实现.但是,您可以将EISPACK = TRUE指定为使用EISPACK的RS,RG,CH和CG例程的参数.

用于特征值计算的最流行和最好的开源包是LAPACK和EISPACK.

---

`EISPACK`现已解散并被忽略.见http://stat.ethz.ch/R-manual/R-devel/library/base/html/eigen.html

2> ramanujan..：

---

对于大矩阵,您通常不需要所有特征值.你只想让前几个人做(比方说)降维.

规范算法是在ARPACK中实现的Arnoldi-Lanczos迭代算法:

www.caam.rice.edu/software/ARPACK/

eigs中有一个matlab接口:

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/eigs.html

eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.

现在还有一个R接口:

http://igraph.sourceforge.net/doc-0.5/R/arpack.html

3> vartec..：

---

我认为如果矩阵稀疏会有帮助吗？

是的,有些算法在稀疏矩阵上表现良好.

参见例如:http://www.cise.ufl.edu/research/sparse/

4> 小智..：

---

如果我有一个1000x1000矩阵,实践需要多长时间？

MATLAB(基于LAPACK)在双核1.83 GHz机器上计算1000x1000随机的所有特征值,大约5秒钟.当矩阵是对称的时,计算可以明显更快地完成并且仅需要大约1秒.

5> Brian Agnew..：

---

我将看看特征值算法,它连接到许多不同的方法.他们都有不同的特点,希望有一个适合你的目的.