Asynchronous Parallel Methods with Overlapfor Google Matrices, Dynamics of Biomolecules,and Other Markov Chains Problems

0514489 Daniel B.SzyldTemple University Google矩阵、生物分子动力学和其他马尔可夫链问题的带重叠的异步并行方法本项目涉及奇异矩阵的计算问题，特别是表示马尔可夫链的计算问题。两个重要的应用推动了这项调查。其中第一个是表示万维网中网页之间的互连的随机矩阵。这种表示方式有几种，据报道，谷歌使用的PageRank算法就是其中之一。该矩阵的零空间的基被适当地归一化，给出了搜索引擎所使用的网页的排序。提出了用并行块迭代方法来求解这类奇异线性系统。由于使用了重叠变量，Schwarz方法在非奇异情况下被证明是非常有效的。这些想法将应用于奇异系统和Google型矩阵。为此将开发的计算工具之一是一种新的组合和代数算法，以确定适当的变量块(包括重叠变量)，以便并行迭代方法能够很好地工作。异步方法也将在这方面进行研究。第二个重要的应用来自中型生物分子的动力学，包括某些病毒，如艾滋病毒。这些分子有不同的平衡状态，从一种状态到另一种状态的概率模型产生了奇异矩阵。某些变量块代表了这些生物分子的亚稳态构型，而拟议的项目涉及到寻找这些亚稳态构型的新算法。

ABSTRACT0514489Daniel B. SzyldTemple UniversityAsynchronous Parallel Methods with Overlap for Google Matrices, Dynamics of Biomolecules, and Other Markov Chains ProblemsThis project relates to computational problems with singular matrices, and in particular with those representing Markov chains. Two important applications drive this investigation. The first of these are the stochastic matrices representing the interconnections between web pages in the World Wide Web. This representation can be done in several ways, one of which is by the PageRank algorithm reportedly used by Google. A basis for the null space of this matrix, appropriately normalized, gives the ranking of the web pages used by the search engines.It is proposed to solve such singular linear systems by parallel block iterative methods.Schwarz methods have been shown to be very effective in the nonsingular case, thanks to the use of overlapping variables. These ideas will be applied to singular systems and Google-type matrices.One of the computational tools to be developed to that end is a new combinatorial and algebraic algorithm to determine appropriate blocks of variables (with the inclusion of overlapping variables) so that the parallel iterative methods work well.Asynchronous methods will also be studied in this context. The second important application comes from the dynamics of medium-sized biomolecules, including certain viruses, such as HIV. These molecules have different equilibrium states, and the probability models to go from one state to another give rise to singular matrices. Certain blocks of variables represent metastable configurations of these biomolecules, andthe proposed project involves new algorithms to find these metastable configurations.