Parallel sparse Cholesky factorization on a shared memory multiprocessor

TitleParallel sparse Cholesky factorization on a shared memory multiprocessor
Publication TypeJournal Articles
Year of Publication1992
AuthorsZhang G, Elman H
JournalParallel Computing
Pagination1009 - 1022
Date Published1992/09//
ISBN Number0167-8191
Keywordslinear algebra, Parallel algorithms, shared memory multiprocessor, sparse Cholesky factorization

Parallel implementations of Cholesky factorization for sparse symmetric positive definite matrices are considered on a shared memory multiprocessor computer. Two column-oriented schemes, known as the column-Cholesky algorithm and the fan-in algorithm, along with enhancements of each, are implemented and discussed. High parallel efficiency of the column-Cholesky algorithm and its enhancement is demonstrated for test problems. A detailed investigation of the performance of the fan-in algorithm and its enhancement, the compute-ahead fan-in algorithm, is made to study the effects of overhead associated with the fan-in based schemes.