These are the approaches towards parallel preconditioning
taken in the packages under review here.
- Direct approximations of the inverse
- SPAI
(section 3.13) is the only package that provides
a direct approximation method to the inverse of the coefficient
matrix. Since such an approximation is applied directly, using
a matrix-vector product, it is trivially parallel. The SPAI
preconditioner is in addition also generated fully in parallel.
- Block Jacobi
- Each processor solves its own subsystem,
and there is no communication between the processors.
Since this strategy neglects the global/implicit properties
of the linear system, only a limited improvement in the number
of iterations can result. On the other hand, this type of method
is very parallel.
All parallel preconditioner packages provide some form of
Block Jacobi method.
- Additive Schwarz
- As in the Block Jacobi method, each processor
solves a local subsystem. However, the local system is now augmented
to include bordering variables, which belong to other processors.
A certain amount of communication is now necessary, and the convergence
improvement can by much higher.
This method is available in Aztec (3.1),
Petsc (3.10),
ParPre (3.8),
PSparselib (3.12).
- Multicolour factorisations
- It is possible to perform global
incomplete factorisation if the domain is not only split over
the processors, but is also augmented with a multicolour structure.
Under the reasonable assumption that each processor has variables
of every colour, both the factorisation and the solution with
a system thus ordered are parallel. The number of synchronisation
points is equal to the number of colours.
This is the method supplied in BlockSolve95 (3.2);
it is also
available in ParPre (3.8).
- Block factorisation
- It is possible to implement
block SSOR or ILU methods, with the subblocks corresponding
to the local systems (with overlap, this gives the Multiplicative
Schwarz method). Such factorisations are necessarily
more sequential than Block Jacobi or Additive Schwarz methods,
but they are also more accurate. With an appropriately chosen
processor ordering (e.g., multicolour instead of sequential)
the solution time is only a small multiple times that of
Block Jacobi and Additive Schwarz methods.
Such block factorisations are available in Parpre (3.8);
PSparselib (3.12)
has the Multiplicative Schwarz method, under
the name `multicolour SOR'.
- Multilevel methods
- Petsc (3.10)
and ParPre (3.8)
are the only packages supplying
variants of (algebraic) multigrid methods in parallel.
- Schur complement methods
- ParPre (3.8)
and PSparselib (3.12)
contain Schur complement domain decomposition methods.
