Scalable parallel algorithm for sparse Cholesky factorization

Anshul Gupta, Vipin Kumar

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations

Abstract

In this paper, we describe a scalable parallel algorithm for sparse Cholesky factorization, analyze its performance and scalability, and present experimental results of its implementation on a 1024-processor nCUBE2 parallel computer. Through our analysis and experimental results, we demonstrate that our algorithm improves the state of the art in parallel direct solution of sparse linear systems by an order of magnitude - both in terms of speedups and the number of processors that can be utilized effectively for a given problem size. This algorithm incurs strictly less communication overhead and is more scalable than any known parallel formulation of sparse matrix factorization. We show that our algorithm is optimally scalable on hypercube and mesh architectures and that its asymptotic scalability is the same as that of dense matrix factorization for a wide class of sparse linear systems, including those arising in all two- and three- dimensional finite element problems.

Original languageEnglish (US)
Pages (from-to)793-802
Number of pages10
JournalProceedings of the ACM/IEEE Supercomputing Conference
DOIs
StatePublished - Jan 1 1994
EventProceedings of the 1994 Supercomputing Conference - Washington, DC, USA
Duration: Nov 14 1994Nov 18 1994

Fingerprint Dive into the research topics of 'Scalable parallel algorithm for sparse Cholesky factorization'. Together they form a unique fingerprint.

Cite this