Vectorization of the preconditioner solve     Next: Parallelizing the preconditioner Up: Point incomplete factorizations Previous: Modified incomplete factorizations

### Vectorization of the preconditioner solve

At first it may appear that the sequential time of solving a factorization is of the order of the number of variables, but things are not quite that bad. Consider the special case of central differences on a regular domain of points. The variables Figure: Wavefront solution of from a central difference problem on a domain of points.

on any diagonal in the domain, that is, in locations with , depend only on those on the previous diagonal, that is, with . Therefore it is possible to process the operations on such a diagonal, or `wavefront'  , in parallel (see figure ), or have a vector computer pipeline them; see Van der Vorst .

Another way of vectorizing the solution of the triangular factors is to use some form of expansion of the inverses of the factors. Consider for a moment a lower triangular matrix, normalized to the form where is strictly lower triangular). Its inverse can be given as either of the following two series: (The first series is called a ``Neumann expansion'', the second an ``Euler expansion''. Both series are finite, but their length prohibits practical use of this fact.) Parallel or vectorizable preconditioners can be derived from an incomplete factorization by taking a small number of terms in either series. Experiments indicate that a small number of terms, while giving high execution rates, yields almost the full precision of the more recursive triangular solution (see Axelsson and Eijkhout  and Van der Vorst ).

There are some practical considerations in implementing these expansion algorithms. For instance, because of the normalization the in equation ( ) is not . Rather, if we have a preconditioner (as described in section ) described by then we write Now we can choose whether or not to store the product . Doing so doubles the storage requirements for the matrix, not doing so means that separate multiplications by and have to be performed in the expansion. Figure: Preconditioning step algorithm for a Neumann expansion of an incomplete factorization .

Suppose then that the products and have been stored. We then define by and replace solving a system for by computing . This algorithm is given in figure .     Next: Parallelizing the preconditioner Up: Point incomplete factorizations Previous: Modified incomplete factorizations

Jack Dongarra
Mon Nov 20 08:52:54 EST 1995