**Previous:** The use of fast solvers

**Up:** Preconditioners from properties of the
differential equation

**Previous Page:** The use of fast solvers

**Next Page:** Related Issues

The Poisson differential operator can be split in a natural way as the sum of two operators:

Now let , be discretized representations of , . Based on the observation that , iterative schemes such as

with suitable choices of and have been proposed.

This * alternating direction implicit*, or * ADI*, method was first
proposed as a solution method for parabolic equations. The
are then approximations on subsequent time steps. However, it can also
be used for the steady state, that is, for solving elliptic equations.
In that case, the become subsequent iterates;
see D'Yakonov [79],
Fairweather, Gourlay and Mitchell [93],
Hadjidimos [118], and
Peaceman and Rachford [169].
Generalization
of this scheme to variable coefficients or fourth order elliptic
problems is relatively straightforward.

The above method is implicit since it requires systems solutions, and it alternates the and (and if necessary ) directions. It is attractive from a practical point of view (although mostly on tensor product grids), since solving a system with, for instance, a matrix entails only a number of uncoupled tridiagonal solutions. These need very little storage over that needed for the matrix, and they can be executed in parallel, or one can vectorize over them.

However, there is a problem of data distribution. For vector computers, either the system solution with or with will involve very large strides: if columns of variables in the grid are stored contiguously, only the solution with will involve contiguous data. For the the stride equals the number of variables in a column.

On parallel machines the same problem occurs, and it requires a global data transposition in between the and system solution.

A theoretical reason that ADI preconditioners are of interest is that they can be shown to be spectrally equivalent to the original coefficient matrix. Hence the number of iterations is bounded independent of the condition number.