The problem of solving a large sparse linear system Ax = b is central in scientific computing. It is a real challenge, if the dimension is very large (e.g. > 100000). Such systems occur, for instance, in the numerical solution of partial differential equations. To solve them robustly and efficiently one has to exploit their special structure. Of particular interest in this context are sparse systems, i.e. systems where the number of non-zero entries in A is relatively small.
Roughly speaking, there are two approaches to solve sparse linear systems: the direct and the iterative. In the direct approach, one picks an appropriate direct method (like Gaussian elimination) and adapts it to the sparsity structure of A. Assuming exact arithmetic the direct methods produce the exact solution in finitely many steps. In contrast to this, the iterative methods generate a sequence of approximate solutions x_k and essentially involve the matrix A only in the context of matrix-vector multiplication. The evaluation of an iterative method invariably focuses on how quickly the iterates x_k converge.
In particular, the following topics will be covered:
References.