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

如果人们可以帮助我找到一种有效的方法（可能是低内存算法）来解决以下问题，我将不胜感激。如何找到给定特征值1的特征向量，最大限度地减少内存使用

我需要找到转换矩阵P的平稳分布x。转移矩阵是一个非常大的，极其稀疏矩阵，构造为使得由于固定分布由等式给出Px = x所有列总和为1，然后x是一个简单的与P特征值有关的特征向量1.

我目前使用GNU Octave来生成转换矩阵，找到平稳分布并绘制结果。我使用函数eigs()来计算特征值和特征向量，并且有可能返回一个特征向量，其中特征值是1（为了防止错误，我实际上必须指定1.1）。转换矩阵（使用稀疏矩阵）的构造相当快，但是当我增加尺寸时发现特征向量变得越来越慢，并且在我能够检查即使是中等大小的问题之前，内存耗尽。

我当前的代码是

既然我知道1是本征值，我想知道是否有可以是一个更好的方法来计算的特征向量，或者使更有效地使用一种方法内存，因为我并不真的需要一个中等大型的密集矩阵。我天真地尝试

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

这失败，因为Q是单数（定义）。

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

作为这个问题的背景，我正在求解一个随机SIR模型中牛群感染数量的均衡分布。不幸的是，即使是中等大小的牛群，转换矩阵也非常大。例如：在平均20个人（95％的时间人口在12和28个人之间）的SIR模型中，P是21169到21169，其中20340个非零值（即0.0005％密度），并且用完321 Kb（这个尺寸的全矩阵将是3.3 Gb），而对于大约50个人，P使用3 Mb。 x本身应该很小。我怀疑eigs()在某个地方有一个密集的矩阵，这会导致我用完内存，所以如果我可以避免使用完整矩阵，我应该没问题。

来源

2014-04-09 spaceLem

功率迭代是找到矩阵的主要特征值的标准方法。你选择一个随机矢量v，然后重复用P重复它，直到你不再看到它变化非常多。你想定期将v除以sqrt(v^T v)以使其正常化。

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

有很多方法可以做到这一点（“PageRank”在这里搜索是一件好事），可以提高真正巨大的稀疏矩阵的速度，但我不知道它们在这里是必要的还是有用的。

来源

2014-04-09 17:38:40 tmyklebu

谢谢，我正在尝试它（忽略我以前的评论，我意识到即使我已经得到了特征值，它仍然可以是有用的，因为我确信最大的特征值已经是1）。现在我开始我的初始'x'作为'ones（n，1）/ n'（其中'P'是n乘n），并且重复乘以'P'，所以内存需求不会气球（如果我尝试了“P”来获得某种力量，那么非零元素的数量会迅速增加）。如果它比以前更好，我会报告回来。 – spaceLem

当然，对于一个小案例来说，最大的几个特征值是1，.9927，.9818，.9676 ......所以收敛可能需要一段时间。 – spaceLem

最大特征值HAS为1（除了数值误差），或者平衡分布将爆炸至无穷大或消失至零。请参阅本文中“融合速度”一节：http://en.wikipedia.org/wiki/Markov_chain – Peter