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

Question

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

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

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

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

在R中，我可以计算特征值，如下面的玩具示例所示：

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

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

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

Answer 1

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

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

但即使您假设最坏的情况，对于1000x1000矩阵，您仍然需要至少1000 ^ 3次操作。

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

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

Answer 2

对于大矩阵，您通常不需要所有特征值。你只想让前几个人做（比方说）降维。

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

呜呜呜.擦啊摹.rice.额度/software/AR pack/

假发中有一个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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

我会看看Eigenvalue algorithms，它链接到许多不同的方法。他们都有不同的特点，希望有一个适合你的目的。

Answer 6

您可以使用GuessCompx的CRAN软件包来估算特征值计算的经验复杂性并预测完整的运行时间（尽管在您的示例中它仍然很小）。您需要一个小辅助函数，因为拟合过程仅对行进行子集，因此您必须使矩阵成为正方形：

library(GuessCompx)
m = matrix(rnorm(1e6), ncol=1000, nrow=1000)
# custom function  to subset the increasing-size matrix to a square one:
eigen. = function(m) eigen(as.matrix(m[, 1:nrow(m)]))
CompEst(m, eigen.)
#### $`TIME COMPLEXITY RESULTS`
#### $`TIME COMPLEXITY RESULTS`$best.model
#### [1] "CUBIC"
#### $`TIME COMPLEXITY RESULTS`$computation.time.on.full.dataset
#### [1] "5.23S"
#### $`TIME COMPLEXITY RESULTS`$p.value.model.significance
#### [1] 1.784406e-34

你得到时间的立方复杂度，以及R base eigen()函数的内存使用的Nlog（N）复杂度。运行整个计算需要5.2秒和37Mb。

Answer 7

Apache Mahout是一个基于map-reduce的开源框架（即它适用于真正非常大的矩阵）。请注意，对于很多矩阵问题，问题不是“什么是大运行时”，而是“它是如何并行化的？” Mahout says他们使用Lanczos，它基本上可以在你想要的多个处理器上并行运行。

Answer 8

它使用QR算法。参见Wilkinson，J.H。（1965）The Algebraic Eigenvalue Problem。 Clarendon Press，牛津。它没有利用稀疏性。