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

Question

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

我需要找到一个转移矩阵x的平稳分布P。过渡矩阵是一个非常大、极稀疏的矩阵，它的构造使得所有的列之和为1。由于平稳分布是由方程Px = x给出的，所以x就是与特征值1相关联的P的特征向量。

我目前正在使用generate来生成转换矩阵，找出平稳分布，并绘制结果。我使用函数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乘21169,20340个非零值(即0.0005%的密度)，消耗321KB(这个大小的完整矩阵将为3.3GB)，而对于大约50个个体，P使用3 Mb。x本身应该非常小。我怀疑eigs()在某个地方有一个密集的矩阵，这导致我的内存耗尽，所以我应该可以避免使用完整的矩阵。

Answer 1

幂迭代是求矩阵主特征值的一种标准方法。选择一个随机向量v，然后重复使用P，直到不再看到它发生很大变化。您希望周期性地将v除以sqrt(v^T v)来规范它。

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

有一些更时髦的方法可以做到这一点("PageRank“是在这里搜索的一件好事)，它们提高了非常庞大的稀疏矩阵的速度，但我不知道它们在这里是否必要或有用。

Answer 2

你的方法看上去不错。然而，你所称的x，如果它支持稀疏矩阵，那么Q.null(Q)的空空间就能工作，但它不支持。网络上有很多东西用来查找稀疏矩阵的空空间。例如：

thread/249467

http://www.mathworks.com/matlabcentral/fileexchange/42922-null-space-for-sparse-matrix/content/nulls.m

http://www.mathworks.com/matlabcentral/fileexchange/11120-null-space-of-a-sparse-matrix

Answer 3

按照tmyklebu的建议，最好的解决方案似乎是使用Power迭代方法。

方法是迭代x = Px; x /= sum(x)，直到x收敛。如果连续迭代之间的d1范数小于1e-5，我假设收敛，因为这似乎给出了很好的结果。

收敛可能需要一段时间，因为最大的两个特征值相当接近(收敛所需的迭代次数可能有很大差异，取决于所使用的模型和人口规模，从200到2000不等，但最终会达到)。然而，内存需求很低，而且很容易实现。