Sparse matrix technology. (English) Zbl 0536.65019

London - Orlando, Florida etc.: Academic Press (Harcourt Brace Jovanovich, Publishers). XIII, 321 p. £32.50; $ 55.00 (1984).
This book is concerned with the direct solution of sparse linear algebraic equations, solution of sparse standard and generalized eigenvalue problems, and sparse matrix algebra. The concepts and the methods used are described at a fairly elementary level. A variety of computational algorithms in Fortran are given. In many sections, a survey of the relevant literature is included. A matrix is assumed to be sparse when it is advantageous to exploit the existence of many zero elements. In such a case, the number of operations performed by the computer during the execution of a sparse matrix algorithm is proportional to the numbers of nonzeros, rather than the total number of elements of the coefficient matrix. A good sparse matrix algorithm tries to preserve sparsity by keeping the fill-in as low as possible. Towards this goal only nonzeros are stored and operated on in such a manner that sparsity is preserved. The author begins the book with a description of structures and internal representations used for storing lists of numbers, graphs, and various types of sparse matrices and sparse block-partitioned matrices. Symbolic and numerical processing of sparse matrices and dynamic storage allocation are examined. Then both the Gaussian elimination and orthogonal factorization are introduced and a table of operation counts is given. Numerical errors in sparse factorization are discussed and nicely tabulated. It is pointed out that the existing procedures are heuristic and usually attempt to find the orderings for which the fill-in and the operations count are low, without guaranteeing a true minimum. Orderings for symmetric and general sparse matrix Gaussian elimination are discussed in two separate chapters. The eigenvalue analysis of \(Ax=\lambda x\) is restricted to the case of real symmetric A and real symmetric positive definite B. Elementary operations of sparse matrix algebra are summarized in a separate chapter. Special techniques are given for mesh problems that arise in the finite element methods. The final chapter consists of a variety of ideas for writing and implementation of algorithms for problems in sparse matrix technology. This is an excellent book on sparse matrices. The author has been quite sucessful in including the most useful and well known results in this area. This reviewer would have liked to see some more discussion of hybrid methods where \(A=LU+E\), where E has most of the non-critical fill- in.
Reviewer: R.P.Tewarson


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
68Q25 Analysis of algorithms and problem complexity
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15-04 Software, source code, etc. for problems pertaining to linear algebra
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs