计算矩阵的特征值有多昂贵？
最佳算法的复杂度是多少？
如果我有一个 1000 x 1000 的矩阵，实际需要多长时间？我认为如果矩阵稀疏会有帮助吗？
是否存在特征值计算不会终止的情况？
在R中，我可以计算特征值，如下面的玩具示例所示：
m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14 3
有谁知道它使用什么算法？
是否有任何其他（开源）包可以计算特征值？
Frank
问问题
29307 次
8 回答
26
大多数用于特征值计算的算法都可以扩展到 big-Oh(n^3)，其中 n 是（对称和方形）矩阵的行/列维度。
要了解迄今为止最佳算法的时间复杂度，您必须参考科学计算/数值方法中的最新研究论文。
但即使您假设最坏的情况，对于 1000x1000 矩阵，您仍然需要至少 1000^3 次操作。
R 默认使用 LAPACK 例程的（DSYEVR、DGEEV、ZHEEV 和 ZGEEV）实现。但是，您可以指定 EISPACK=TRUE 作为参数来使用 EISPACK 的 RS、RG、CH 和 CG 例程。
用于特征值计算的最流行和最优秀的开源包是 LAPACK 和 EISPACK。
于 2009-04-03T15:05:37.607 回答
20
对于大矩阵，您通常不需要所有特征值。你只希望前几个做（比如说）降维。
规范算法是在 ARPACK 中实现的 Arnoldi-Lanczos 迭代算法：
www.caam.rice.edu/software/ARPACK/
eigs中有一个matlab接口：
eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.
现在还有一个 R 接口：
于 2009-04-17T20:41:02.613 回答
12
于 2009-04-03T14:29:51.280 回答
8
如果我有一个 1000x1000 矩阵，实际需要多长时间？
MATLAB（基于 LAPACK）在双核 1.83 GHz 机器上在大约 5 秒内计算 1000x1000 随机数的所有特征值。当矩阵是对称的时，计算可以明显更快地完成，并且只需要大约 1 秒。
于 2009-04-06T18:19:57.677 回答
5
我会看一下特征值算法，它链接到许多不同的方法。它们都有不同的特征，希望有一个适合您的目的。
于 2009-04-03T13:26:52.990 回答
5
您可以使用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
您会得到time 的三次复杂度，以及R 基函数的内存使用的 Nlog(N) 复杂度。eigen()运行整个计算需要 5.2 秒和 37Mb。
于 2019-04-29T09:04:37.270 回答
2
Apache Mahout是一个基于 map-reduce 的开源框架（即它适用于非常大的矩阵）。请注意，对于很多矩阵的东西，问题不是“什么是 big-o 运行时”，而是“它的可并行性如何？” Mahout说他们使用 Lanczos，它基本上可以在您愿意提供的任意数量的处理器上并行运行。
于 2010-05-27T21:55:43.637 回答
0
它使用 QR 算法。参见 Wilkinson, JH (1965) 代数特征值问题。克拉伦登出版社，牛津。它不利用稀疏性。
于 2012-03-30T07:21:55.783 回答