Parallel Gaussian elimination on an MIMD computer

DOI10.1016/0167-8191(88)90070-1MaRDI QIDQ1096997zbMATH OpenOpenAlexFDO

Authors Yves Robert, Michel Cosnard, Mounir Marrakchi, Denis Trystram

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)90070-1

zbMATH Keywords

asymptotic performancescomputational complexityGaussian eliminationMIMD computerparallel algorithmsparallel Gaussian-like triangularization algorithmstask graph models

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25)

Review text

This paper introduces a graph-theoretic approach to analyse the performances of several parallel Gaussian-like triangularization algorithms on an MIMD computer. We show that the SAXPY, GAXPY and DOT algorithms of \textit{J. J. Dongarra}, \textit{F. G. Gustavson} and \textit{A. Karp} [SIAM Rev. 26, 91-112 (1984; Zbl 0539.65009)], as well as parallel versions of the \(LDM^ t\), \(LDL^ t\), Doolittle and Cholesky algorithms, can be classified into four task graph models. We derive new complexity results and compare the asymptotic performances of these parallel versions.

Recommendations

• scientific article; zbMATH DE number 3984455
• Optimal algorithms for Gaussian elimination on an MIMD computer
• scientific article; zbMATH DE number 3999131
• Impact of communications of the complexity of the parallel Gaussian elimination
• scientific article; zbMATH DE number 3876585

Cited in

(22)

• Comparisons of Gaussian elimination algorithms on a Cray Y-MP
• Minimizing the schedule length for a parallel 3D-grid precedence graph
• Practical task-oriented parallelism for Gaussian elimination in distributed memory
• A parallel continuation algorithm for nonlinear eigenvalue problems
• Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors
• Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
• Applying abstraction and formal specification in numerical software design
• A complex structure-preserving algorithm for split quaternion matrix \textit{LDU} decomposition In split quaternion mechanics
• A complex structure-preserving algorithm for the full rank decomposition of quaternion matrices and its applications
• ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems
• An optimal schedule for Gaussian elimination on an MIMD architecture
• scientific article; zbMATH DE number 3845037 (Why is no real title available?)
• scientific article; zbMATH DE number 3876585 (Why is no real title available?)
• Systolic algorithm for the solution of dense linear equations
• scientific article; zbMATH DE number 3984455 (Why is no real title available?)
• A parallel gaussian elimination method for general linear systems
• scientific article; zbMATH DE number 4121427 (Why is no real title available?)
• PARALLEL BLOCK METHODS FOR SOLVING LINEAR SYSTEMS
• Optimal parallelization of a recursive algorithm for triangular matrix inversion on MIMD computers
• Implementing stochastic control software on supercomputing machines
• A new presentation of the conjugate direction algorithm
• Optimal algorithms for Gaussian elimination on an MIMD computer

This page was built for publication: Parallel Gaussian elimination on an MIMD computer

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