Handbook of Linear Algebra, 2nd Edition

Chapter 53

Sparse Matrix Methods

Esmond G. Ng

Lawrence Berkeley National Laboratory

53.1 Introduction

Let A be an n by n nonsingular matrix and b be an n-vector. Assume that A and b are given. As discussed in Chapter 51, the solution of the system of linear equations Ax = b using Gaussian elimination, where x is an unknown n-vector to be computed, requires O(n3) operations, which typically include additions, subtractions, multiplications, and divisions. Computing the solution also requires O(n2) words of storage. The computational complexity is based on the assumption that every element of the matrix has to be stored and operated on. However, linear systems that arise in many scientific and engineering applications can be large; that is, n can ...