Parallel algorithms for sparse triangular system solution

DOI10.1016/0167-8191(93)90048-PMaRDI QIDQ1208515zbMATH OpenFDO

Authors S. Singh, P. Sreenivasa Kumar, M. Kishore Kumar, A. Basu

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)90048-P

zbMATH Keywords

Cholesky factorizationcomputation resultselimination treemulti- transputer local memory multiprocessor systemparallel algorithmsPARAMperformancesparse matricessparse triangular system

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10) Complexity and performance of numerical algorithms (65Y20)

Review text

The elimination tree is used to enhance the forward and backward substitutions for the Cholesky factorization. The authors generalize the technique of \textit{G. Li} and \textit{T. F. Coleman} [SIAM J. Sci. Stat. Comput. 9, No. 3, 485-502 (1988; Zbl 0644.65020)] to sparse matrices. First graph theoretic results associated with the elemination tree are given. This is followed by the new parallel algorithms. The paper concludes with implementation details and computation results on PARAM, a multi-transputer local memory multiprocessor system using 4, 8 and 16 processors. These results indicate a significant enhancement in the overall performance.

Recommendations

• scientific article; zbMATH DE number 4076453
• Optimal Parallel Solution of Sparse Triangular Systems
• scientific article; zbMATH DE number 4184919
• scientific article; zbMATH DE number 4113848
• scientific article; zbMATH DE number 554768

Cited in

(13)

• Parallel algorithms for solving linear systems with sparse triangular matrices
• A parallel algorithm for elimination tree computation and symbolic factorization
• Fast implementation of partial Gram-Schmidt algorithm using tree data structure with sequential row pointers data structure to solve structural problems (PGS)
• On designing optimal parallel triangular solvers.
• Aggregation Methods for Solving Sparse Triangular Systems on Multiprocessors
• scientific article; zbMATH DE number 434542 (Why is no real title available?)
• The Role of Elimination Trees in Sparse Factorization
• A Fast Reordering Algorithm for Parallel Sparse Triangular Solution
• A LINEAR ARRAY FOR LARGE SPARSE MATRIX OPERATIONS – II TRIANGULAR SYSTEM SOLVERS AND MATRIX MULTIPLICATION
• scientific article; zbMATH DE number 554768 (Why is no real title available?)
• Efficient parallel Gauss-Doolittle matrix triangulation
• Theww^Tfactorization of dense and sparse matrices
• A survey of direct methods for sparse linear systems

This page was built for publication: Parallel algorithms for sparse triangular system solution

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