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

摘要0514489丹尼尔B。Szyld Temple 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. 两个重要的应用程序推动了这项调查。 其中第一个是随机矩阵表示在万维网网页之间的互连。 这种表示可以通过多种方式完成，其中之一是据报道Google使用的PageRank算法。 这个矩阵的零空间的基础，适当规范化，给出了搜索引擎使用的网页的排名。它提出了解决这种奇异线性系统的并行块迭代法。施瓦茨方法已被证明是非常有效的非奇异情况下，由于使用重叠变量。 这些思想将应用于奇异系统和Google型矩阵。为此目的开发的计算工具之一是一种新的组合和代数算法，以确定适当的变量块（包括重叠变量），从而使并行迭代方法工作良好。在这方面还将研究异步方法。 第二个重要的应用来自中等大小的生物分子的动力学，包括某些病毒，如HIV。这些分子有不同的平衡态，从一种状态到另一种状态的概率模型产生奇异矩阵。某些变量块代表这些生物分子的亚稳态构型，而拟议的项目涉及新的算法来找到这些亚稳态构型。

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.