In many application areas, including information retrieval and networking systems, finding the steady-state distribution vector of an irreducible Markov chain is of interest and it is often difficult to compute efficiently. The steady-state vector is the solution to a nonsymmetric eigenproblem with known eigenvalue, B x = x, subject to probability constraints ||x||1 = 1 Vert{bf x}Vert _1 = 1 and x > 0, where B is column stochastic, that is, B ≥ O and 1 t B = 1 t . Recently, scalable methods involving Smoothed Aggregation (SA) and Algebraic Multigrid (AMG) were proposed to solve such eigenvalue problems. These methods use multiplicative iterate updates versus the additive error corrections that are typically used in nonsingular linear solvers. This paper discusses an outer iteration that accelerates convergence of multiplicative update methods, similar in principle to a preconditioned flexible Krylov wrapper applied to an additive iteration for a nonsingular linear problem. The acceleration is performed by selecting a linear combination of old iterates to minimize a functional within the space of probability vectors. Two different implementations of this idea are considered and the effectiveness of these approaches is demonstrated with representative examples.
展开▼
机译：在包括信息检索和网络系统在内的许多应用领域中，寻找不可还原的马尔可夫链的稳态分布矢量是令人感兴趣的，并且通常难以有效地进行计算。稳态矢量是具有已知特征值B x = x的非对称特征问题的解，服从概率约束|| x || 1 = 1 Vert {bf x} Vert _1 = 1并且x> 0，其中B是列随机的，即B≥O且1 t B = 1 t 。最近，提出了涉及平滑聚合（SA）和代数多重网格（AMG）的可扩展方法来解决此类特征值问题。这些方法使用乘法迭代更新，而不是通常在非奇异线性求解器中使用的附加误差校正。本文讨论了一个外部迭代，该迭代可加快乘法更新方法的收敛速度，其原理类似于应用于非奇异线性问题的加性迭代的预处理柔性Krylov包装器。通过选择旧迭代的线性组合来执行加速，以最小化概率矢量空间内的函数。考虑了此想法的两种不同实现，并通过代表性示例演示了这些方法的有效性。
展开▼
