计算矩阵的特征值有多昂贵? [英] How expensive is it to compute the eigenvalues of a matrix?

问题描述

计算矩阵的特征值多少钱?

How expensive is it to compute the eigenvalues of a matrix?

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

What is the complexity of the best algorithms?

如果我有1000 x 1000的矩阵，实际上需要多长时间?我认为矩阵稀疏会有所帮助吗?

How long might it take in practice if I have a 1000 x 1000 matrix? I assume it helps if the matrix is sparse?

在任何情况下特征值计算都不会终止吗?

Are there any cases where the eigenvalue computation would not terminate?

在R中，我可以像下面的玩具示例中那样计算特征值:

In R, I can compute the eigenvalues as in the following toy example:

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

有人知道它使用什么算法吗?

Does anyone know what algorithm it uses?

还有其他用于计算特征值的(开源)软件包吗?

Are there any other (open-source) packages that compute the eigenvalue?

推荐答案

本征值计算的大多数算法都缩放为big-Oh(n ^ 3)，其中n是(对称和平方) 矩阵.

Most of the algorithms for eigen value computations scale to big-Oh(n^3), where n is the row/col dimension of the (symmetric and square) matrix.

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

For knowing the time complexity of the best algorithm till date you would have to refer to the latest research papers in Scientific Computing/Numerical Methods.

但是，即使您假设情况更糟，对于1000x1000矩阵，您仍然至少需要进行1000 ^ 3次操作.

But even if you assume the worse case, you would still need at least 1000^3 operations for a 1000x1000 matrix.

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

R uses the LAPACK routine's (DSYEVR, DGEEV, ZHEEV and ZGEEV) implementation by default. However you could specify the EISPACK=TRUE as a parameter to use a EISPACK's RS, RG, CH and CG routines.

用于特征值计算的最流行，最优秀的开源软件包是LAPACK和EISPACK.

The most popular and good open source packages for eigenvalue computation are LAPACK and EISPACK.

这篇关于计算矩阵的特征值有多昂贵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！