Parallel preconditioners for elliptic PDEs

Iterative schemes for solving sparse linear systems arising from elliptic PDEs are very suitable for efficient implementation on large scale multiprocessors. However, these methods rely heavily on effective preconditioners which must also be amenable to parallelization. In this paper, we present a novel method to obtain a preconditioned linear system which is solved using an iterative method. Each iteration comprises of a matrix-vector product with k sparse matrices (k < logn), and can be computed in O(n) opertions where n is the number of unknowns. The numerical convergence properties of our preconditioner are superior to the commonly used incomplete factorization preconditioners. Moreover, unlike the incomplete factorization preconditioners, our algorithm affords a higher degree of concurrency and doesn't require triangular system solves, thereby achieving the dual objective of good preconditioning and efficient parallel implementation. We describe our scheme for certain linear systems with symmetric positive definite or symmetric indefinite matrices and present an efficient parallel implementation along with an analysis of the parallel complexity. Results of the parallel implimentation of our algorithm will also be presented in the final version of this paper.