Ebook: Computer Algorithms for Solving Linear Algebraic Equations: The State of the Art

The NATO Advanced Study Institute on "Computer algorithms for solving linear algebraic equations: the state of the art" was held September 9-21, 1990, at II Ciocco, Barga, Italy. It was attended by 68 students (among them many well known specialists in related fields!) from the following countries: Belgium, Brazil, Canada, Czechoslovakia, Denmark, France, Germany, Greece, Holland, Hungary, Italy, Portugal, Spain, Turkey, UK, USA, USSR, Yugoslavia. Solving linear equations is a fundamental task in most of computational mathematics. Linear systems which are now encountered in practice may be of very large dimension and their solution can still be a challenge in terms of the requirements of accuracy or reasonable computational time. With the advent of supercomputers with vector and parallel features, algorithms which were previously formulated in a framework of sequential operations often need a completely new formulation, and algorithms that were not recommended in a sequential framework may become the best choice. The aim of the ASI was to present the state of the art in this field. While not all important aspects could be covered (for instance there is no presentation of methods using interval arithmetic or symbolic computation), we believe that most important topics were considered, many of them by leading specialists who have contributed substantially to the developments in these fields.

---

This volume presents the lectures given by fourteen specialists in algorithms for linear algebraic systems during a NATO Advanced Study Institute held at Il Ciocco, Barga, Italy, September 1990. The lectures give an up-to-date and fairly complete coverage of this fundamental field in numerical mathematics. Topics related to sequential formulation include a review of classical methods with some new proofs, and extensive presentations of complexity results, of algorithms for linear least squares, of the recently developed ABS methods, of multigrid methods, of preconditioned conjugate gradient methods for H-matrices, of domain decomposition methods, of hierarchical basis methods, and of splitting type methods. With reference to implementations on multiprocessors, topics include algorithms for general sparse systems, factorization methods for dense matrices, Gaussian elimination on systolic arrays, and methods for linear systems arising in optimization problems. The book will be useful as an introduction to a field still in rapid growth and as a reference to the most recent results in the field.

---

This volume presents the lectures given by fourteen specialists in algorithms for linear algebraic systems during a NATO Advanced Study Institute held at Il Ciocco, Barga, Italy, September 1990. The lectures give an up-to-date and fairly complete coverage of this fundamental field in numerical mathematics. Topics related to sequential formulation include a review of classical methods with some new proofs, and extensive presentations of complexity results, of algorithms for linear least squares, of the recently developed ABS methods, of multigrid methods, of preconditioned conjugate gradient methods for H-matrices, of domain decomposition methods, of hierarchical basis methods, and of splitting type methods. With reference to implementations on multiprocessors, topics include algorithms for general sparse systems, factorization methods for dense matrices, Gaussian elimination on systolic arrays, and methods for linear systems arising in optimization problems. The book will be useful as an introduction to a field still in rapid growth and as a reference to the most recent results in the field.
Content:
Front Matter....Pages I-VIII
Classical Methods for Linear Equations....Pages 1-26
Complexity of Algorithms for Linear Systems of Equations....Pages 27-56
Algorithms for Linear Least Squares Problems....Pages 57-92
Abs Algorithms for General Linear Systems....Pages 93-110
ABS Algorithms for Sparse Linear Systems....Pages 111-131
Multi-Grid Algorithms....Pages 133-160
Two Multi-Level Methods for Nonuniformly Refined Grids....Pages 161-167
Preconditioning methods for block H-matrices....Pages 169-184
Domain Decomposition methods for solving large sparse linear systems....Pages 185-206
A Splitting Method for Large Sparse Linear Systems on a Multivector Computer....Pages 207-215
Scheduling Parallel Factorization Algorithms on a Shared Memory Computer....Pages 217-252
Gaussian elimination on distributed memory architectures....Pages 253-276
Parallel Algorithms for General Sparse Systems....Pages 277-297
The Solution of Partially Separable Linear Equations on Parallel Processing Systems....Pages 299-338
Back Matter....Pages 339-356

---

This volume presents the lectures given by fourteen specialists in algorithms for linear algebraic systems during a NATO Advanced Study Institute held at Il Ciocco, Barga, Italy, September 1990. The lectures give an up-to-date and fairly complete coverage of this fundamental field in numerical mathematics. Topics related to sequential formulation include a review of classical methods with some new proofs, and extensive presentations of complexity results, of algorithms for linear least squares, of the recently developed ABS methods, of multigrid methods, of preconditioned conjugate gradient methods for H-matrices, of domain decomposition methods, of hierarchical basis methods, and of splitting type methods. With reference to implementations on multiprocessors, topics include algorithms for general sparse systems, factorization methods for dense matrices, Gaussian elimination on systolic arrays, and methods for linear systems arising in optimization problems. The book will be useful as an introduction to a field still in rapid growth and as a reference to the most recent results in the field.
Content:
Front Matter....Pages I-VIII
Classical Methods for Linear Equations....Pages 1-26
Complexity of Algorithms for Linear Systems of Equations....Pages 27-56
Algorithms for Linear Least Squares Problems....Pages 57-92
Abs Algorithms for General Linear Systems....Pages 93-110
ABS Algorithms for Sparse Linear Systems....Pages 111-131
Multi-Grid Algorithms....Pages 133-160
Two Multi-Level Methods for Nonuniformly Refined Grids....Pages 161-167
Preconditioning methods for block H-matrices....Pages 169-184
Domain Decomposition methods for solving large sparse linear systems....Pages 185-206
A Splitting Method for Large Sparse Linear Systems on a Multivector Computer....Pages 207-215
Scheduling Parallel Factorization Algorithms on a Shared Memory Computer....Pages 217-252
Gaussian elimination on distributed memory architectures....Pages 253-276
Parallel Algorithms for General Sparse Systems....Pages 277-297
The Solution of Partially Separable Linear Equations on Parallel Processing Systems....Pages 299-338
Back Matter....Pages 339-356
....