memory - 如何在给定特征值 1 的情况下找到特征向量，最大限度地减少内存使用

Question

如果人们能帮助我找到一种有效的方法(可能是低内存算法)来解决以下问题，我将不胜感激。

我需要找到转换矩阵P的平稳分布x。转移矩阵是一个非常大、非常稀疏的矩阵，其构造使得所有列的总和为 1。由于平稳分布由方程 Px = x 给出，因此 x 只是与特征值 1 相关的 P 特征向量。

我目前正在使用 GNU Octave 来生成转换矩阵、找到平稳分布并绘制结果。我正在使用函数 eigs()，它计算特征值和特征向量，并且可以仅返回一个特征向量，其中特征值为 1(实际上我必须指定 1.1，以防止错误)。构建转换矩阵(使用稀疏矩阵)相当快，但随着大小的增加，寻找特征向量变得越来越慢，而且在检查中等大小的问题之前，我的内存就已经耗尽了。

我当前的代码是

[v l] = eigs(P, 1, 1.01);
x = v / sum(v);

鉴于我知道 1 是特征值，我想知道是否有更好的方法来计算特征向量，或者是否有一种方法可以更有效地利用内存，因为我并不真正需要中间大的密集矩阵。我天真地尝试过

n = size(P,1);       % number of states
Q = P - speye(n,n);
x = Q\zeros(n,1);    % solve (P-I)x = 0

失败了，因为 Q 是单数(根据定义)。

如果有人对我应该如何处理这个问题有任何想法，我将非常感激，因为这是一个我必须执行多次的计算，如果可能的话，我想在更大、更复杂的模型上尝试它.

作为这个问题的背景，我正在用随机 SIR 模型求解牛群中感染者数量的平衡分布。不幸的是，即使对于中等规模的牛群来说，转移矩阵也非常大。例如:在平均有 20 个个体的 SIR 模型中(95% 的情况下种群数量在 12 到 28 个个体之间)，P 为 21169 x 21169，其中有 20340 个非零值(即 0.0005) % 密集)，并使用 321 Kb(该大小的完整矩阵为 3.3 Gb)，而对于大约 50 个个体 P 使用 3 Mb。 x 本身应该非常小。我怀疑 eigs() 在某处有一个密集矩阵，这导致我内存不足，所以如果我可以避免使用完整矩阵，我应该没问题。

Answer 1

幂迭代是查找矩阵主特征值的标准方法。您选择一个随机向量 v，然后用 P 反复点击它，直到您不再看到它发生太大变化。您需要定期将 v 除以 sqrt(v^T v) 以对其进行标准化。

这里的收敛速度与最大特征值和第二大特征值之间的间隔成正比。每次迭代只需要几次矩阵乘法。

有一些更奇特的方法可以做到这一点(“PageRank”是在这里搜索的一件好事)，可以提高真正巨大的稀疏矩阵的速度，但我不知道它们在这里是否必要或有用。