Communication complexity of the Gaussian elimination algorithm on multiprocessors

DOI10.1016/0024-3795(86)90174-6zbMath0594.65013OpenAlexW2086878177MaRDI QIDQ1077125

Yousef Saad

Publication date: 1986

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

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

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

Related Items

PARALLEL BLOCK METHODS FOR SOLVING LINEAR SYSTEMS, The implementation of a generalized cross validation algorithm using deflation techniques for linear systems, Parallel solution of Fredholm integral equations of the second kind by orthogonal polynomial expansions, Parallel direct methods for solving banded linear systems, Optimal scheduling algorithms for parallel Gaussian elimination, Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors, On the communication complexity of Lipschitzian optimization for the coordinated model of computation, An optimal schedule for Gaussian elimination on an MIMD architecture

Cites Work

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