Bulk-synchronous parallel Gaussian elimination

DOI10.1023/A:1013588221172MaRDI QIDQ5959711zbMATH OpenFDO

Authors Alexander Tiskin

Publication date 14 April 2002

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1013588221172

zbMATH Keywords

algorithmsGaussian eliminationparallel computationpivotingsynchronization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05)

Review text

Two algorithms for bulk synchronous parallel Gaussian elimination are presented: one without pivoting and the other with a local pivoting scheme. Computational and theoretical arguments are utilized to show that both the algorithms are more efficient in terms of communications but not in synchronization. This fact is used to trade off, in a certain range, the costs of communication and synchronization to achieve optimal or near-optimal cost values at the extremes of this range. It is pointed out that for large problems, a communication-efficient algorithm may be preferable to a synchronization-efficient one.

Recommendations

• scientific article; zbMATH DE number 3999131
• scientific article; zbMATH DE number 4215247
• Publication:4734762
• Optimal scheduling algorithms for parallel Gaussian elimination
• Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods

Cited in

(7)

• scientific article; zbMATH DE number 3907653 (Why is no real title available?)
• scientific article; zbMATH DE number 1223727 (Why is no real title available?)
• Communication lower bounds and optimal algorithms for numerical linear algebra
• An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination
• scientific article; zbMATH DE number 1405674 (Why is no real title available?)
• Direct bulk-synchronous parallel algorithms
• Basic techniques for numerical linear algebra on bulk synchronous parallel computers

This page was built for publication: Bulk-synchronous parallel Gaussian elimination

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