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

点击翻译按钮获取中文摘要

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.