Complexity of dense-linear-system solution on a multiprocessor ring

DOI10.1016/0024-3795(86)90169-2MaRDI QIDQ1072340zbMATH OpenOpenAlexFDO

Authors Ilse C. F. Ipsen, Martin H. Schultz, Y. 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)90169-2

zbMATH Keywords

complexitydense linear systemsGaussian eliminationmultiprocessor ring

Mathematics Subject Classification ID

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

Review text

Different algorithms, based on Gaussian elimination, for the solution of dense linear systems of equations are discussed for a multiprocessor ring. The number of processors is assumed not to exceed the problem size. A fairly general model for data transfer is proposed, and the algorithms are analyzed with respect to their requirements of arithmetic as well as communication times.

Recommendations

• scientific article; zbMATH DE number 3930228
• Numerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected Processors
• A parallel elimination algorithm for the solution of dense linear systems
• Fast and efficient parallel solution of dense linear systems
• On the cost of sequential and parallel algorithms for solving linear system of equations

Cites work

• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Data-flow algorithms for parallel matrix computation
• scientific article; zbMATH DE number 3994972 (Why is no real title available?)
• Multiple array processors for ocean acoustic problems
• On Stable Parallel Linear System Solvers
• On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
• Some Complexity Results for Matrix Computations on Parallel Processors
• The computation and communication complexity of a parallel banded system solver

Cited in

(11)

• Assignment and scheduling in parallel matrix factorization
• Communication complexity of the Gaussian elimination algorithm on multiprocessors
• Parallel solution of Fredholm integral equations of the second kind by orthogonal polynomial expansions
• Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods
• Parallel direct methods for solving banded linear systems
• Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors
• Numerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected Processors
• scientific article; zbMATH DE number 3930228 (Why is no real title available?)
• Adaptive blocking in the QR factorization
• A study of the performance of Neville elimination using two kinds of partitioning techniques
• Neville elimination: a study of the efficiency using checkerboard partitioning

This page was built for publication: Complexity of dense-linear-system solution on a multiprocessor ring

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