提问人：AncientSpark 提问时间：8/3/2023 更新时间：8/4/2023 访问量：29
稀疏矩阵中的特征值减慢
Eigenvalue Slowdown in Sparse Matrices
问：
矩阵的结构或内容是否存在可能导致特征值计算显著减慢的条件（除了稀疏性）？例如在 Matlab 中的 eig 或 eigs 中。
我正在尝试运行一种算法，其速度的主要瓶颈是在大型稀疏矩阵上进行多个特征值计算。当我在算法给出的示例矩阵（13309x13309 矩阵）上运行该算法时，运行时速度与预期一样快（例如，eigs 在 0.014287 秒内运行）。
我尝试在我自己的较小矩阵（3087x3087 矩阵）上进行相同的特征值测试。然而，运行时间要长得多（eigs 为 0.79211 秒，其他特征值计算（如 eig）的运行时间也增加了类似）。尽管矩阵的稀疏程度明显降低（0.11% 非零条目，而不是最初的 0.027% 非零条目），但它仍然非常稀疏，所以我不确定问题是否出在特征值的接近程度或一些类似的度量上。
答：
3赞
Cris Luengo
8/4/2023
#1
计算特征值可能或多或少复杂，具体取决于矩阵的结构，不仅仅是零的数量，还有它们的位置。MATLAB 可以根据结构选择不同的算法，但即使使用固定算法，某些结构的工作量也比其他结构少得多。明显的例子是对角线矩阵，其中特征值直接是对角线元素，根本不需要计算。
下面是一个包含完整矩阵的示例（矩阵的预期结果类似）：sparse
A = randn(1000);
tic
eig(A);
toc
A = tril(A);
tic
eig(A);
toc
A = toeplitz([5, 6, 2, zeros(1, 997)]);
tic
eig(A);
toc
A = diag(randn(1, 1000));
tic
eig(A);
toc
输出：
Elapsed time is 0.682568 seconds.
Elapsed time is 0.039816 seconds.
Elapsed time is 0.133101 seconds.
Elapsed time is 0.002881 seconds.
[请注意，/ 是衡量此类短时间的糟糕方法，我们真的应该在这里使用。tictoctimeit
请注意，Toeplitz 矩阵只有 4994 个非零元素，但计算时间比下三角矩阵长得多，后者有五十万个非零元素。
评论