Previous: The why and how
Up: The why and how
Next: Theoretical prerequisites on preconditioners
Previous Page: The why and how
Next Page: Theoretical prerequisites on preconditioners
Since applying a preconditioner incurs some extra cost, both initially
and per iteration, there is a trade-off between the cost of
constructing and applying the preconditioner, and the gain in
convergence speed. Certain preconditioners need no construction phase
at all (for instance the SSOR preconditioner), but for others, such as
incomplete factorizations, there can be substantial work involved.
Although the work in scalar terms may be comparable to a single
iteration, the construction of the preconditioner may not be
vectorizable/parallelizable even if application of the preconditioner
is. In that case, the initial cost has to be amortized over the
iterations, or over repeated use of the same preconditioner in
multiple linear systems.
Most preconditioners take in their application an amount of work proportional to the number of variables. This implies that they multiply the work per iteration by a constant factor. On the other hand, the number of iterations as a function of the matrix size is usually only improved by a constant. Certain preconditioners are able to improve on this situation, most notably the modified incomplete factorizations and preconditioners based on multigrid techniques.
On parallel machines there is a further trade-off between the efficacy
of a preconditioner in the classical sense, and its parallel
efficiency. Many of the traditional preconditioners have a large
sequential component.