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

bus architecturemultiprocessorsnearest 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) Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25)

Review text

The author analyses the effects of data movement delays in parallel Gaussian elimination algorithms on multiprocessors. Three types of architectures are considered: a bus architecture, a nearest neighbour ring network, and a nearest neighbor grid network. It is shown that for the bus and the ring architectures, the minimum communication time is \(O(N^ 2)\), independent of processors, while for the grid it is reduced to \(O(K^{-1/2}N^ 2)+O(K^{1/2})\) for a lock step Gaussian elimination algorithm, and to \(O(K^{1/2}N^ 2)+O(K^{1/2})\) for any pipelined Gaussian elimination algorithm, where K is the total number of processors. The practical implications of these bounds are discussed.

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

(15)

• Parallel solution of Fredholm integral equations of the second kind by orthogonal polynomial expansions
• On the communication complexity of Lipschitzian optimization for the coordinated model of computation
• 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
• The implementation of a generalized cross validation algorithm using deflation techniques for linear systems
• Impact of communications of the complexity of the parallel Gaussian elimination
• An optimal schedule for Gaussian elimination on an MIMD architecture
• scientific article; zbMATH DE number 425387 (Why is no real title available?)
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
• Communication analysis of the PIE and QIF algorithms on distributed memory architecture
• scientific article; zbMATH DE number 3999131 (Why is no real title available?)
• scientific article; zbMATH DE number 4121427 (Why is no real title available?)
• PARALLEL BLOCK METHODS FOR SOLVING LINEAR SYSTEMS
• scientific article; zbMATH DE number 4189171 (Why is no real title available?)

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)