A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor

DOI10.1016/0167-8191(88)90039-7MaRDI QIDQ1108738zbMATH OpenOpenAlexFDO

Authors Earl Zmijewski, J. R. Gilbert

Publication date 1988

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(88)90039-7

zbMATH Keywords

complexityelimination forestslarge sparse symmetric positive definite matrixmessage-passing hypercube multiprocessorparallel algorithmparallel symbolic Cholesky factorization algorithm

Mathematics Subject Classification ID

Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05)

Review text

Consider a system of linear algebraic equations \(Ax=b\), where A is an \(n\times n\) large sparse symmetric positive definite matrix. Solving it for x the Cholesky factor L of A is computed first and then the systems \(Ly=b\) and \(L^ Tx=y\) are solved, where L is the lower triangular matrix such that \(A=LL^ T\). A parallel algorithm is developed for computing elimination forests and its correctness is proved. Using this algorithm a new parallel symbolic Cholesky factorization algorithm is presented for a message-passing hypercube multiprocessor and its complexity is discussed.

Recommendations

• Parallel sparse Cholesky factorization on a shared memory multiprocessor
• scientific article; zbMATH DE number 833696
• Parallel Cholesky factorization on a shared-memory multiprocessor
• A Mapping Algorithm for Parallel Sparse Cholesky Factorization
• Efficient Sparse Cholesky Factorization on a Massively Parallel SIMD Computer
• Parallel Cholesky factorization on orthogonal multiprocessors
• Highly Parallel Sparse Cholesky Factorization
• scientific article; zbMATH DE number 1760069
• scientific article; zbMATH DE number 833702
• Parallel symbolic factorization of sparse linear systems

Cited in

(12)

• A survey of the advances in the exploitation of the sparsity in the solution of large problems
• A parallel graph partitioning algorithm for a message-passing multiprocessor
• A parallel algorithm for elimination tree computation and symbolic factorization
• Supernodal symbolic Cholesky factorization on a local-memory multiprocessor
• A parallel Cholesky algorithm for the solution of symmetric linear systems
• Sparse Cholesky Factorization on a Local-Memory Multiprocessor
• scientific article; zbMATH DE number 4076453 (Why is no real title available?)
• A Mapping Algorithm for Parallel Sparse Cholesky Factorization
• Efficient Sparse Cholesky Factorization on a Massively Parallel SIMD Computer
• A survey of direct methods for sparse linear systems
• Task scheduling for parallel sparse Cholesky factorization
• Parallel symbolic factorization of sparse linear systems

This page was built for publication: A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108738)