Impact of communications of the complexity of the parallel Gaussian elimination

DOI10.1016/S0167-8191(05)80017-1MaRDI QIDQ2277765zbMATH OpenFDO

Authors Evripidis Bampis, Jean-Claude König, Denis Trystram

Publication date 1991

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-8191(05)80017-1

zbMATH Keywords

complexityGaussian eliminationMIMD computersparallel algorithmsscheduling algorithmshared-memory system

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Review text

From authors' summary: This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. The new scheduling algorithm that we have proposed in this paper reduces the overhead to only \(O(n^ 2)\).

Recommendations

• scientific article; zbMATH DE number 3999131
• Communication complexity of the Gaussian elimination algorithm on multiprocessors
• Publication:4734762
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
• On the parallel complexity of Gaussian elimination with pivoting
• scientific article; zbMATH DE number 1943028
• scientific article; zbMATH DE number 3876585
• scientific article; zbMATH DE number 1333604

Cited in

(10)

• Communication complexity of the Gaussian elimination algorithm on multiprocessors
• Parallel Gaussian elimination on an MIMD computer
• Minimizing the schedule length for a parallel 3D-grid precedence graph
• Modelling and analysis of communication overhead for parallel matrix algorithms
• Optimal scheduling algorithms for parallel Gaussian elimination
• An optimal schedule for Gaussian elimination on an MIMD architecture
• scientific article; zbMATH DE number 4155892 (Why is no real title available?)
• scientific article; zbMATH DE number 3999131 (Why is no real title available?)
• scientific article; zbMATH DE number 4121427 (Why is no real title available?)
• Some models for scheduling parallel programs with communication delays

This page was built for publication: Impact of communications of the complexity of the parallel Gaussian elimination

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