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.
1. Classical Methods for Linear Equations.- 2. Complexity of Algorithms for Linear Systems of Equations.- 3. Algorithms for Linear Least Squares Problems.- 4. ABS Algorithms for General Linear Systems.- 5. ABS Algorithms for Sparse Linear Systems.- 6. Multi-Grid Algorithms. Introduction, Survey and Convergence Analysis.- 7. Two Multi-Level Methods for Nonuniformly Refined Grids.- 8. Preconditioning Methods for Block H-Matrices.- 9. Domain Decomposition Methods for Solving Large Sparse Linear Systems.- 10. A Splitting Method for Large Sparse Linear Systems on a Multivector Computer.- 11. Scheduling Parallel Factorization Algorithms on a Shared Memory Computer.- 12. Gaussian Elimination on Distributed Memory Architectures.- 13. Parallel Algorithms for General Sparse Systems.- 14. The Solution of Partially Separable Linear Equations on Parallel Processing Systems.- Author Index.- List of Participants.