Supernodal symbolic Cholesky factorization on a local-memory multiprocessor

DOI10.1016/0167-8191(93)90045-MMaRDI QIDQ1208511zbMATH OpenOpenAlexFDO

Authors Esmond G. Ng

Publication date 16 May 1993

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(93)90045-m

zbMATH Keywords

Cholesky factorizationIntel iPSC/2large sparse symmetric positive definite matrixlocal- memory multiprocessorparallel computationsparse matricessymbolic factorization algorithmtest problems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Symbolic computation and algebraic computation (68W30)

Review text

An improvement in the author's algorithm [(1) cf. \textit{A. George}, \textit{M. T. Heath}, \textit{E. Ng} and \textit{J. W-H. Liu} ibid. 5, 85-95 (1987; Zbl 0618.65023)] is described. First, a symbolic factorization algorithm for serial machines is presented. This is followed by a description of the parallel version of the sequential algorithm (1) and the proposed improvements. These improvements exploit the supernodal structure. The improved algorithm is compared with the original one using an Intel iPSC/2 on two sets of test problems. The programs are written in Fortran and compiled with optimization turned on. More than \(50\%\) improvement is observed for matrices of order greater than 5,000 on 16 or more processors.

Recommendations

• A Supernodal Cholesky Factorization Algorithm for Shared-Memory Multiprocessors
• Symbolic Cholesky factorization on a local-memory multiprocessor
• Sparse Cholesky Factorization on a Local-Memory Multiprocessor
• A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor
• Parallel Cholesky factorization on a shared-memory multiprocessor
• scientific article; zbMATH DE number 2087095
• Parallel sparse Cholesky factorization on a shared memory multiprocessor
• Parallel Cholesky factorization on orthogonal multiprocessors
• scientific article; zbMATH DE number 1424208
• Near optimal Cholesky factorization on orthogonal multiprocessors.

Cited in

(5)

• Hypermatrix oriented supernode amalgamation
• Symbolic Cholesky factorization on a local-memory multiprocessor
• A Supernodal Cholesky Factorization Algorithm for Shared-Memory Multiprocessors
• Theww^Tfactorization of dense and sparse matrices
• A survey of direct methods for sparse linear systems

This page was built for publication: Supernodal symbolic Cholesky factorization on a local-memory multiprocessor

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