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

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迭代算法:

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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 基函数的内存使用情况的 Nlog(N) 复杂度eigen()。运行整个计算需要 5.2 秒和 37Mb。