High Performance Algorithms for Structured Matrix Problems

Abstract

Edited by: Peter Arbenz, Marcin Paprzycki, Ahmed Sameh and Vivek Sarin 
Nova Science Publishers, Commack, NY, 1998, 197 pp. 
ISBN 1-56072-594-X, $79.95

The book is a well-organized comprehensive collection of algorithms and ideas in the area of high performance solutions for structured linear systems, eigenvalue and singular value problems. The content of this text is impressive, not only summarizing the state of the art in the area, but also discussing many detailed implementation issues with supporting examples on numerous parallel and distributed architectures from vector computers, shared and distributed memory multiprocessors to cluster of workstations. Hence, this book is an excellent reference for the working professionals in scientific and engineering computing with application areas.

The book's targets can be mainly classified into four categories, namely linear system solver, eigenvalue problems, matrices with special structure and parallel computation.

In the first part, linear system solver, direct solution techniques have been discussed mainly in term of performance and stability for large and sparse linear systems with a certain structure inherent in the problems. The effectiveness of different approaches is demonstrated by extensive experiments carried out on different architectures from vector computer, shared and distributed memory parallel computers to workstations.

In the second part, eigenvalue problems, several approaches are highlighted for computing eigenvalues and singular values of structured matrices. They are presented by, either reducing banded matrices to bidiagonal and tridiagonal form by numerically stable and efficient orthogonal transformations, or improving bisection and divide-and-conquer algorithms, on parallel architectures. The theoretical considerations are verified by experimental results on vector and distributed memory computers.

In the third part, matrices with special structures, some special structured matrices such as Hankel, Toeplitz systems from many applications, for example, signal processing, are treated. The authors propose several fast algorithms for the solution of such linear systems by considering the special properties of the structure and the numerical stability constraints.

In the last part, parallel computation, the issues related to the question how to efficiently implement the existing algorithms for structured matrices are covered; ranging from load balance to optimized implementation.

In summary, this book addresses a variety of algorithm design issues by either comprehensive survey or in-depth discussions for structured matrices. The only small disappointment is that the discussions on iterative methods for parallel and distributed architectures should be touched as well. Overall, this text would be a very valuable reference to professionals or to students working on structured matrix related problems.

Laurence Tianruo Yang
St. Francis Xavier University