Solution Methods for Linear Algebraic Systems

In principle, the task of solving a linear algebraic systems seems trivial, as with Gauss elimination a solution method exists which allows one to solve a problem of dimension N (i.e. N equations with N unknowns) at a cost of O(N ) elementary operations [85]. Such solution methods which, apart from roundoff errors and machine accuracy, produce an exact solution of an equation system after a predetermined number of operations, are called direct solvers. However, for problems related to the solution of partial differential equations, direct solvers are usually very inefficient Methods such as Gauss elimination do not exploit a special feature of the coefficient matrices of the corresponding linear systems, namely that most of the entries are zero. Such sparse matrices are characteristic of problems originating from the discretization of partial or ordinary differential equations. As an example, consider the discretization of the one-dimensional Poisson equation 

In order to exploit the sparseness of the matrix, iterative solvers can be applied. The iterative procedure is initialized with a guess for the solution vector O. In 

The general structure of an iterative solution method for the linear system of Eq. (38) is given as 

The iteration scheme allows to compute an improved approximation 0 j given a previous approximation as an input. If after a number of iterations 0 j 0  

In CED, a number of different iterative solvers for linear algebraic systems have been applied. Two of the most successful and most widely used methods are conjugate gradient and multigrid methods. The basic idea of the conjugate gradient method is to transform the linear equation system Eq. (38) into a minimization problem 

---

An iterative solution method for linear algebraic systems which damps the shortwave components of the iteration error very fast and, after a few iterations, leaves predominantly long-wave components. The Gauss-Seidel method [85] could be chosen as a suitable solver in this context. 

---