Communication complexity of the Gaussian elimination algorithm on multiprocessors

DOI10.1016/0024-3795(86)90174-6MaRDI QIDQ1077125zbMATH OpenOpenAlexFDO

Authors Y. Saad

Publication date 1986

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0024-3795(86)90174-6

zbMATH Keywords

multiprocessorsbus architecturenearest neighbor grid networknearest neighbour ring networkparallel Gaussian elimination algorithmspipelined Gaussian eliminationring architectures

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Recommendations

• Publication:4734762
• scientific article; zbMATH DE number 3999131
• Impact of communications of the complexity of the parallel Gaussian elimination
• The communication complexity of several problems in matrix computation
• scientific article; zbMATH DE number 1333604
• scientific article; zbMATH DE number 1943028
• On the parallel complexity of Gaussian elimination with pivoting
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms

Cites work

• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Complexity of dense-linear-system solution on a multiprocessor ring
• Data-flow algorithms for parallel matrix computation
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
• Parallel direct methods for solving banded linear systems
• Some Complexity Results for Matrix Computations on Parallel Processors
• The computation and communication complexity of a parallel banded system solver

Cited in

(14)

• scientific article; zbMATH DE number 3999131 (Why is no real title available?)
• scientific article; zbMATH DE number 4121427 (Why is no real title available?)
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
• Parallel direct methods for solving banded linear systems
• On the communication complexity of Lipschitzian optimization for the coordinated model of computation
• The implementation of a generalized cross validation algorithm using deflation techniques for linear systems
• An optimal schedule for Gaussian elimination on an MIMD architecture
• scientific article; zbMATH DE number 4189171 (Why is no real title available?)
• Optimal scheduling algorithms for parallel Gaussian elimination
• Parallel solution of Fredholm integral equations of the second kind by orthogonal polynomial expansions
• Impact of communications of the complexity of the parallel Gaussian elimination
• scientific article; zbMATH DE number 425387 (Why is no real title available?)
• PARALLEL BLOCK METHODS FOR SOLVING LINEAR SYSTEMS
• Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors

This page was built for publication: Communication complexity of the Gaussian elimination algorithm on multiprocessors

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