R. Cook
C. Phillips
University of Newcastle upon Tyne. 1994
We are concerned here with the solution of the system of linear equations Ax = b, (1) with A an n x n matrix and x and b conforming n-vectors. Of particular interest is the situation in which n is large (of the order of 1000's) and A is sparse; linear systems with such properties arise from, for example, 'the discretisation' of elliptic partial differential equations using finite difference or finite element techniques. (see [1] for a review of numerical methods for partial differential equations on vector and parallel computers and a discussion of application areas.) It is theoretically possible to solve systems of this form using direct methods based on elimination techniques (see [2] for a parallel implementation in the case that A is symmetric and positive definite and [3] for a more general discussion) but this approach can be very expensive both in terms of storage requirements and computation. This is a direct consequence of the fill-in that may occur. An alternative, and frequently used, approach which avoids these drawbacks is based on the use of iteration, leading to a family of (Krylov subspace) methods which cover the various particular forms that A may take.