This book, Basic Decompositions, is the first volume in a projected five-volume series entitled Matrix Algorithms. The other four volumes will treat eigensystems, iterative methods for linear systems, sparse direct methods, and special topics, including fast algorithms for structured matrices.
My intended audience is the nonspecialist whose needs cannot be satisfied by black boxes. It seems to me that these people will be chiefly interested in the methods themselves— how they are derived and how they can be adapted to particular problems. Consequently, the focus of the series is on algorithms, with such topics as roundingerror analysis and perturbation theory introduced impromptu as needed. My aim is to bring the reader to the point where he or she can go to the research literature to augment what is in the series.
The series is self-contained. The reader is assumed to have a knowledge of elementary analysis and linear algebra and a reasonable amount of programming experience— about what you would expect from a beginning graduate engineer or an undergraduate in an honors program. Although strictly speaking the individual volumes are not textbooks, they are intended to teach, and my guiding principle has been that if something is worth explaining it is worth explaining fully. This has necessarily restricted the scope of the series, but I hope the selection of topics will give the reader a sound basis for further study.
The focus of this and part of the next volume will be the computation of matrix decompositions—that is, the factorization of matrices into products of simpler ones. This decompositional approach to matrix computations is relatively new: it achieved its definitive form in the early 1960s, thanks to the pioneering work of Alston Householder and James Wilkinson. Before then, matrix algorithms were addressed to specific problems—the solution of linear systems, for example — and were presented at the scalar level in computational tableaus. The decompositional approach has two advantages.
First, by working at the matrix level it facilitates the derivation and analysis of matrix algorithms. Second, by deemphasizing specific problems, the approach turns the decomposition into a computational platform from which a variety of problems can be solved. Thus the initial cost of computing a decomposition can pay for itself many times over.