Matrix Algorithms: Basic Decompositions v. 1 [Paperback]

Please be warned that this book is heavily designed toward matrix theory, rather than the algorithm itself. Therefore, if you are math-averse, you'd better look for other books that offers much lighter theory such as Numerical Recipes. However, if you are not deterred by Greek letters or complicated formulas and eager to learn the theories behind all of the algorithms, this book is for you. Although the author claims that the intended audience is "nonspecialist", I find that this book is most suitable to scientists or grad students, rather than common programmers.

The author explicitly assumes that you know some programming and some linear algebra. Although chapter 1 explains basic matrix theories, you'll need to possess strong basic matrix knowledge -- such as matrix additions, substractions, transpositions, determinants, inverses -- as the author glosses over those on the very first few pages. Still on chapter 1, the author builds up the theories a lot, both matrix theory and linear algebra. He explains many terms such as rank, norms, decompositions, singularity, etc. He also give some proofs on some theorems. These advanced theories will be developed in corresponding later chapters.

Chapter 2 discusses keywords and notations used in the algorithm, such as "for", "if", etc. The pseudocode looks like Pascal. Here, he also give some samples of "easier" algorithms, such as forward substitution and inversion of triangular matrix. He also explains the classical Big O notation briefly and use the sample algorithms as examples on how to compute the Big O notation out. Then, followed by how matrices are stored in the memory and how to optimize the algorithm based on how we store the matrix in the memory. Then, he discuses, quite elaborately, on how to compute rounding error on algorithms and numerical stability of a given algorithm. This last section of chapter 2 is extremely important for those who demands accuracy. This numerical issues will be thoroughly discussed in the later chapters too.

Chapter 3 discusses Gaussian Elimination, LU Decomposition, Cholesky decompositions and their respective variants. The author explains all theory behind them, complete with proofs, discussion on accuracy / rounding error, and Big-O theoretical performance. The algorithms are presented in Pascal-like pseudocode, whose notation described in chapter 2. The author also discuss how certain variants are more beneficial than others (in terms of speed, numerical stability, etc), again, often complete with proofs (or left as an "exercise" for the reader). Theories from chapter 1 are also revisited and expanded as needed.

Chapter 4 discusses QR decomposition and its variants. Complete with background theory, proofs, discussion on accuracy, etc. Just like in chapter 3. It also discusses updating issues and how to adapt QR to linear solutions.

Chapter 5 discusses rank-reducing decompositions. Modifications of previous decompositions to suit this rank-reducing needs, QLP decompositions, and variants of UTV decompositions. Theories, proofs, and discussion of accuracies are all in, as usual.

Speaking of the theory, it's great. It's thorough and the proofs are there even when I think it's not that necessary. By studying this book, one will understand all the theory behind all the decompositions discussed. Numerical issues are discussed very thoroughly, which in itself justifies the price of this book.

However, my main qualms are:

1. Dearth of real examples

Many examples discussed in the book are way too abstract. Sometimes there are no examples at all. For example: There are no examples in doing Cholesky decomposition. The author only gives an example when the pivoting is necessary (and thus leads to small modification of the algorithm). What about the one that doesn't require any pivoting? Even with the one that requires pivoting, the examples are not given as step-by-step run through. The reader is assumed to know which several steps of the algorithms have already taken place from one matrix to another. In the case of Hessenberg matrix, there are no examples at all. This book is certainly not intended for "nonspecialists".

2. Way too much theory and proofs

I'm inclined to say that there are way too much theory than it is necessary. I'm not math-averse at all. I was hoping that this book is more practical as the author claims.

3. BLAS acronym

Maybe this one is a small annoyance. The author uses BLAS acronym a lot. Such as "xeuib" that stands for "X Equals U^(-1) times B". I'm not familiar with BLAS and I have to keep refering to Figure 2.2 to figure one out.

That being said, this is a solid book for explaining theories behind basic decomposition. Treatment on the programming and pragmatic side is rather lacking. Definitely not for the faint-hearted.