highly scalable parallel algorithms for sparse matrix factorization精编.pdfVIP

Highly Scalable Parallel Algorithms for Sparse Matrix Factorization∗ Anshul Gupta George Karypis and Vipin Kumar IBM T. J. Watson Research Center Department of Computer Science P.O. Box 218 University of Minnesota Yorktown Heights, NY 10598 Minneapolis, MN 55455 anshul@ {karypis/kumar}@ Abstract In this paper, we describe scalable parallel algorithms for sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1024 processors on a Cray T3D parallel computer. Through our analysis and experimental r esults, we demonstrate that our algorithms substantially improve the state of the art in parallel direct solution of sparse linear systems—both in terms of scalability and overall performance. It is a well known fact that dense matrix factorization scales well and can be implemented efficiently on parallel computers. In this paper, we present the first algorithms to factor a wide class of sparse matrices (including those arising from two- and three-dimensional finite element problems) that are asymptotically as scalable as dense matrix factorization algorithms on a variety of parallel architectures. Our algorithms incur less communication overhead and are more scalable than any previously known parallel formulation of sparse matrix factorization. Although, in this paper, we discuss Cholesky factorization of symmetric positive definite matrices, the algori