Premium
A latency tolerant hybrid sparse solver using incomplete Cholesky factorization
Author(s) -
Raghavan Padma,
Teranishi Keita,
Ng Esmond G.
Publication year - 2003
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.327
Subject(s) - cholesky decomposition , incomplete cholesky factorization , incomplete lu factorization , preconditioner , conjugate gradient method , computer science , scalability , sparse matrix , minimum degree algorithm , solver , parallel computing , linear system , factorization , generalized minimal residual method , matrix decomposition , algorithm , mathematics , mathematical optimization , iterative method , eigenvalues and eigenvectors , mathematical analysis , physics , quantum mechanics , database , gaussian
Consider the solution of large sparse symmetric positive definite linear systems using the preconditioned conjugate gradient method. On sequential architectures, incomplete Cholesky factorizations provide effective preconditioning for systems from a variety of application domains, some of which may have widely differing preconditioning requirements. However, incomplete factorization based preconditioners are not considered suitable for multiprocessors. This is primarily because the triangular solution step required to apply the preconditioner (at each iteration) does not scale well due to the large latency of inter‐processor communication. We propose a new approach to overcome this performance bottleneck by coupling incomplete factorization with a selective inversion scheme to replace triangular solutions by scalable matrix–vector multiplications. We discuss our algorithm, analyze its communication latency for model sparse linear systems, and provide empirical results on its performance and scalability. Copyright © 2003 John Wiley & Sons, Ltd.