Parallel preconditioning for sparse linear equations

Abstract

A popular class of preconditioners is known as incomplete factorizations. They can be thought of as approximating the exact LU factorization of a given matrix A (e.g. computed via Gaussian elimination) by disallowing certain ll-ins. As opposed to other PDE-based preconditioners such asmultigrid and domain decomposition, this class of preconditioners are primarily algebraic in nature and can in principle be applied to any sparse matrices. In this paper we will discuss some new viewpoints for the construction of eective preconditioners. In particular, we will discuss parallelization aspects, including re-ordering, series expansion and domain decomposition techniques. Generally, this class of preconditioner does not possess a high degree of parallelism in its original form. Re-ordering and approximations by truncating certain series expansion will increase the parallelism, but usually with a deterioration in convergence rate. Domain decomposition oers a compromise.