Handbook of Linear Algebra, 2nd Edition

Chapter 54

Iterative Solution Methods for Linear Systems

Anne Greenbaum

University of Washington

Given an n by n nonsingular matrix A and an n-vector b, the linear system Ax = b can always be solved for x by Gaussian elimination. The work required is approximately 2n3/3 operations (additions, subtractions, multiplications, and divisions), and, in general, n2 words of storage are required. This is often acceptable if n is of moderate size, say n ≤ 1000, but for much larger values of n, say, n ≈ 106, both the work and storage for Gaussian elimination may become prohibitive.

Where do such large linear systems arise? They may occur in many different areas, but one important source is the numerical solution of partial differential equations (PDEs). ...