Daniel B. Szyld Temple University
Asynchronous Parallel Methods with Overlap for Google Matrices, Dynamics of Biomolecules, and Other Markov Chains Problems
This 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, and the proposed project involves new algorithms to find these metastable configurations.
