Discovering parallelism in sequential preconditioners.



next up previous contents index
Next: More parallel variants Up: Preconditioning Previous: Preconditioning

Discovering parallelism in sequential preconditioners.

Certain preconditioners were not developed with parallelism in mind, but they can be executed in parallel. Some examples are domain decomposition methods (see §gif), which provide a high degree of coarse grained parallelism, and polynomial preconditioners (see §gif), which have the same parallelism as the matrix-vector product.

Incomplete factorization preconditioners are usually much harder to parallelize: using wavefronts of independent computations (see for instance Paolini and Radicati di Brozolo [170]) a modest amount of parallelism can be attained, but the implementation is complicated. For instance, a central difference discretization on regular grids gives wavefronts that are hyperplanes (see Van der Vorst [205][203]).



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