当前位置： 文江博客话题详情

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

发布于 2024-07-16 03:32:59 字数 333 浏览 7 评论 0原文

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

最佳算法的复杂度是多少？

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

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

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

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

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

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

原文

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

What is the complexity of the best algorithms?

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?

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?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（8）

那一片橙海， 2024-07-23 03:32:59

大多数特征值计算算法都扩展到 big-Oh(n^3)，其中 n 是（对称和方）矩阵的行/列维度。

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

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

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

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

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.

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

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.

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

回复 原文
那片花海 2024-07-23 03:32:59

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

规范算法是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

With big matrices you usually don't want all the eigenvalues. You just want the top few to do (say) a dimension reduction.

The canonical algorithm is the Arnoldi-Lanczos iterative algorithm implemented in ARPACK:

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

There is a matlab interface in eigs:

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.

And there is now an R interface as well:

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

回复 原文
演出会有结束 2024-07-23 03:32:59

我认为如果矩阵是有帮助的
稀疏？

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

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

I assume it helps if the matrix is
sparse?

Yes, there are algorithms, that perform well on sparse matrices.

See for example: http://www.cise.ufl.edu/research/sparse/

回复 原文
别再吹冷风 2024-07-23 03:32:59

实践中可能需要多长时间
我有一个 1000x1000 矩阵？

MATLAB（基于 LAPACK）在双核 1.83 GHz 机器上在大约 5 秒内计算 1000x1000 随机的所有特征值。 当矩阵对称时，计算速度可以明显加快，并且只需要大约 1 秒。

How long might it take in practice if
I have a 1000x1000 matrix?

MATLAB (based on LAPACK) computes on a dual-core 1.83 GHz machine all eigenvalues of a 1000x1000 random in roughly 5 seconds. When the matrix is symmetric, the computation can be done significantly faster and requires only about 1 second.

回复 原文
因为看清所以看轻 2024-07-23 03:32:59

我会看一下特征值算法，它链接到许多不同的方法。 它们都有不同的特征，希望其中一个能适合您的目的。

I would take a look at Eigenvalue algorithms, which link to a number of different methods. They'll all have different characteristics, and hopefully one will be suitable for your purposes.

回复 原文
╰◇生如夏花灿烂 2024-07-23 03:32:59

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

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.)
#### 
您可以使用 CRAN< 中的 GuessCompx 包/a> 估计特征值计算的经验复杂度并预测完整的运行时间（尽管在您的示例中它仍然很小）。   您需要一个小辅助函数，因为拟合过程仅对行进行子集化，因此您必须将矩阵设为平方：

TIME COMPLEXITY RESULTS`
#### 
您可以使用 CRAN< 中的 GuessCompx 包/a> 估计特征值计算的经验复杂度并预测完整的运行时间（尽管在您的示例中它仍然很小）。   您需要一个小辅助函数，因为拟合过程仅对行进行子集化，因此您必须将矩阵设为平方：

TIME COMPLEXITY RESULTS`$best.model
#### [1] "CUBIC"
#### 
您可以使用 CRAN< 中的 GuessCompx 包/a> 估计特征值计算的经验复杂度并预测完整的运行时间（尽管在您的示例中它仍然很小）。   您需要一个小辅助函数，因为拟合过程仅对行进行子集化，因此您必须将矩阵设为平方：

TIME COMPLEXITY RESULTS`$computation.time.on.full.dataset
#### [1] "5.23S"
#### 
您可以使用 CRAN< 中的 GuessCompx 包/a> 估计特征值计算的经验复杂度并预测完整的运行时间（尽管在您的示例中它仍然很小）。   您需要一个小辅助函数，因为拟合过程仅对行进行子集化，因此您必须将矩阵设为平方：

TIME COMPLEXITY RESULTS`$p.value.model.significance
#### [1] 1.784406e-34

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

输入图片此处描述

You can use the GuessCompx package from CRAN to estimate the empirical complexity of your eigenvalues computation and predict the full running time (although it's still small in your example). You need a little helper function because the fitting process only subsets the rows, so you must make the matrix square:

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.)
#### 
You can use the GuessCompx package from CRAN to estimate the empirical complexity of your eigenvalues computation and predict the full running time (although it's still small in your example). You need a little helper function because the fitting process only subsets the rows, so you must make the matrix square:

TIME COMPLEXITY RESULTS`
#### 
You can use the GuessCompx package from CRAN to estimate the empirical complexity of your eigenvalues computation and predict the full running time (although it's still small in your example). You need a little helper function because the fitting process only subsets the rows, so you must make the matrix square:

TIME COMPLEXITY RESULTS`$best.model
#### [1] "CUBIC"
#### 
You can use the GuessCompx package from CRAN to estimate the empirical complexity of your eigenvalues computation and predict the full running time (although it's still small in your example). You need a little helper function because the fitting process only subsets the rows, so you must make the matrix square:

TIME COMPLEXITY RESULTS`$computation.time.on.full.dataset
#### [1] "5.23S"
#### 
You can use the GuessCompx package from CRAN to estimate the empirical complexity of your eigenvalues computation and predict the full running time (although it's still small in your example). You need a little helper function because the fitting process only subsets the rows, so you must make the matrix square:

TIME COMPLEXITY RESULTS`$p.value.model.significance
#### [1] 1.784406e-34

You get a cubic complexity for time, and a Nlog(N) complexity for memory usage of the R base eigen() function. It takes 5.2 secs and 37Mb to run the whole computation.

enter image description here

回复 原文
冰之心 2024-07-23 03:32:59

Apache Mahout 是一个基于 map-reduce 构建的开源框架（即它适用于非常非常大的矩阵） 。 请注意，对于很多矩阵内容，问题不是“big-o 运行时是什么”，而是“它的并行性如何？” Mahout 说他们使用 Lanczos，它本质上可以在尽可能多的处理器上并行运行你关心给它。

Apache Mahout is an open-source framework built on map-reduce (i.e. it works for really really big matrices). Note that for a lot of matrix stuff the question isn't "whats the big-o runtime" but rather "how parallelizable is it?" Mahout says they use Lanczos, which can essentially be run in parallel on as many processors as you care to give it.

回复 原文
So要识趣 2024-07-23 03:32:59

它使用 QR 算法。 请参阅 Wilkinson, JH (1965) 代数特征值问题。 克拉伦登出版社，牛津。 它不利用稀疏性。

It uses the QR algo. See Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford. It does not exploit sparsity.

回复 原文
~没有更多了~

关于作者

街角迷惘

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

1CH1MKgiKxn9p

文章 0 评论 0

ゞ记忆︶ㄣ

文章 0 评论 0

JackDx

文章 0 评论 0

信远

文章 0 评论 0

yaoduoduo1995

文章 0 评论 0

霞映澄塘

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文