Chapter 28: Matrix Operations

Operations on matrices are at the heart of scientific computing. Efficient algorithms for working with matrices are therefore of considerable practical interest. This chapter provides a brief introduction to matrix theory and matrix operations, emphasizing the problems of multiplying matrices and solving sets of simultaneous linear equations.

After Section 28.1 introduces basic matrix concepts and notations, Section 28.2 presents Strassen's surprising algorithm for multiplying two n × n matrices in Θ(n^{lg 7}) = O(n^2.81) time. Section 28.3 shows how to solve a set of linear equations using LUP decompositions. Then, Section 28.4 explores the close relationship between the problem of multiplying matrices and the problem of inverting a matrix. Finally, Section 28.5 discusses the important class of symmetric positive-definite matrices and shows how they can be used to find a least-squares solution to an overdetermined set of linear equations.

One important issue that arises in practice is numerical stability. Due to the limited precision of floating-point representations in actual computers, round-off errors in numerical computations may become amplified over the course of a computation, leading to incorrect results; such computations are numerically unstable. Although we shall briefly consider numerical stability on occasion, we do not focus on it in this chapter. We refer the reader to the excellent book by Golub and Van Loan [125] for a thorough discussion of stability issues.