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 ...

Get Handbook of Linear Algebra, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.