Parallel Algorithms for Numerical Linear Algebra (Advances in Parallel Computing)

This is the first in a new series of books presenting research results and developments concerning the theory and applications of parallel computers, including vector, pipeline, array, fifth/future generation computers, and neural computers. All aspects of high-speed computing fall within the scope of the series, e.g. algorithm design, applications, software engineering, networking, taxonomy, models and architectural trends, performance, peripheral devices. Papers in Volume One cover the main streams of parallel linear algebra: systolic array algorithms, message-passing systems.;Front Cover; Parallel Algorithms for Numerical Linear Algebra; Copyright Page; Table of Contents; Preface; Part 1: Systolic array algorithms; Chapter 1. A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues; 1. Introduction; 2. Parallel annihilators; the first step; 3. The effect of a complete sweep; 4. Numerical examples; 5. Conclusions; References; Chapter 2. A Jacobi-like algorithm for computing the generalized Schur form of a regular pencil; 1. Introduction; 2. Normal pencils; 3. Description of the method; 4. Global convergence. Front Cover Parallel Algorithms for Numerical Linear Algebra Copyright Page Table of Contents Preface Part 1: Systolic array algorithms Chapter 1. A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues 1. Introduction 2. Parallel annihilators the first step 3. The effect of a complete sweep 4. Numerical examples 5. Conclusions References Chapter 2. A Jacobi-like algorithm for computing the generalized Schur form of a regular pencil 1. Introduction 2. Normal pencils 3. Description of the method 4. Global convergence. 5. Ultimate convergence6. Numerical tests 7. Conclusion References Chapter 3. Canonical correlations and generalized SVD: applications and new algorithms 1. Introduction 2. Applications 3. SVD of products of three matrices 4. New algorithms 5. Final remarks Acknowledgements References Chapter 4. From Bareiss' algorithm to the stable computation of partial correlations 1. Introduction 2. The Generalized Bareiss algorithm 3. Cybenko's algorithm 4. The Hyperbolic Cholesky algorithm 5. Application to the computation of certain sample partial correlations. 6. Computation of arbitrary partial correlations7. Conclusions Acknowledgement References Part 2: Message-passing systems Chapter 5. A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors 1. Introduction 2. The LU decomposition algorithm 3. Solution of tridiagonal systems using prefix algorithms 4. Parallel prefix algorithms on hypercube multiprocessors 5. Estimated speedup and efficiency 6. Experimental results and conclusions References Chapter 6. Least squares modifications with inverse factorizations: parallel implications. 1. Introduction2. Updating R-1 3. Downdating R-1 4. Summary and parallel implications Acknowledgements References Chapter 7. Solution of sparse positive definite systems on a hypercube 1. Introduction 2. Solution of sparse symmetric positive definite systems 3. Parallel Cholesky factorization 4. Symbolic factorization 5. Sparse triangular solution 6. Ordering 7. Some experiments and concluding remarks References Chapter 8. Some aspects of parallel implementation of the finite-element method on message passing architectures 1. Introduction. 2. The model problem and finite-element discretization3. Overview of computations 4. Cost analysis 5. Numerical experiments 6. Conclusions Appendix References Part 3: Algorithms for parallel shared-memory systems Chapter 9. An overview of parallel algorithms for the singular value and symmetric eigenvalue problems 1. Introduction 2. Jacobi methods 3. Reduction to tridiagonal form and multisectioning 4. Performance of eigensolvers 5. Singular value decomposition 6. Performance of SVD algorithms 7. Conclusions Acknowledgements References. This is the first in a new series of books presenting research results and developments concerning the theory and applications of parallel computers, including vector, pipeline, array, fifth/future generation computers, and neural computers.

All aspects of high-speed computing fall within the scope of the series, e.g. algorithm design, applications, software engineering, networking, taxonomy, models and architectural trends, performance, peripheral devices.

Papers in Volume One cover the main streams of parallel linear algebra: systolic array algorithms, message-passing systems, algorithms for parallel shared-memory systems, and the design of fast algorithms and implementations for vector supercomputers.

This is the first in a new series of books presenting research results and developments concerning the theory and applications of parallel computers, including vector, pipeline, array, fifth/future generation computers, and neural computers. All aspects of high-speed computing fall within the scope of the series, e.g. algorithm design, applications, software engineering, networking, taxonomy, models and architectural trends, performance, peripheral devices. Papers in Volume One cover the main streams of parallel linear algebra: systolic array algorithms, message-passing systems, algorithms for parallel shared-memory systems, and the design of fast algorithms and implementations for vector supercomputers