我有一个大型稀疏矩阵，例如，128000×128000 SparseMatrixCSC{Complex{Float64},Int64}，其中包含1376000个存储条目。
如何快速获取稀疏矩阵的所有特征值？是否可能？
我尝试了使用eigs处理128000×128000和1376000个存储条目，但是计算机卡死了。
我使用16GB内存的MacBook Pro和在Jupyter Notebook上运行的Julia 1.3.1。
朱莉娅：大型稀疏矩阵的所有特征值
3
- yosuga
1个回答
5
据我所知（如果我的认识是错误的，我会非常高兴得到证明），没有一种有效的方法可以获取一般稀疏矩阵的所有特征值。
计算矩阵特征值的主要算法是QR算法。QR算法的第一步是将矩阵约化为Hessenberg形式（以便在O(n)时间内进行QR分解）。问题在于，将矩阵归约为Hessenberg形式会破坏稀疏性，你只会得到一个密集矩阵。
还有其他计算矩阵特征值的方法，例如(inverse) power iteration，只需要矩阵向量乘积和解线性系统，但是这些方法仅给出最大或最小特征值，并且当你想计算所有特征值时它们变得昂贵（需要存储"deflation"的特征向量）。
所以，这是一般情况，如果你的矩阵具有某些特殊结构，可能会有更好的替代方案。例如，如果你的矩阵对称，则其Hessenberg形式是三对角形式，你可以相当快地计算出所有特征值。
简而言之：总体来说，不可能。
附言：我尽量让回答简短，但如果你感兴趣，我可以在回答的任何部分给你更多细节。
计算矩阵特征值的主要算法是QR算法。QR算法的第一步是将矩阵约化为Hessenberg形式（以便在O(n)时间内进行QR分解）。问题在于，将矩阵归约为Hessenberg形式会破坏稀疏性，你只会得到一个密集矩阵。
还有其他计算矩阵特征值的方法，例如(inverse) power iteration，只需要矩阵向量乘积和解线性系统，但是这些方法仅给出最大或最小特征值，并且当你想计算所有特征值时它们变得昂贵（需要存储"deflation"的特征向量）。
所以，这是一般情况，如果你的矩阵具有某些特殊结构，可能会有更好的替代方案。例如，如果你的矩阵对称，则其Hessenberg形式是三对角形式，你可以相当快地计算出所有特征值。
简而言之：总体来说，不可能。
附言：我尽量让回答简短，但如果你感兴趣，我可以在回答的任何部分给你更多细节。
- Miguel
2
谢谢您的回答！我通常处理带状Toeplitz矩阵（一般来说，它是非厄米的）。在这种情况下，有没有一种有效的方法来获取所有特征值？ - yosuga
我的猜测是：可能是（正如这篇帖子所建议的 https://math.stackexchange.com/questions/1313115/explicit-calculation-of-eigenvalues-of-banded-toeplitz-matrix），但你可能需要自己实现它。出于好奇，你的带宽是多少？ - Miguel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接