Massively parallel preconditioners for symmetric positive definite linear systems

In this paper, we address the problem of solving sparse symmetric linear systems on parallel computers. With further restrictive assumptions on the matrix (e.g., bidiagonal or tridiagonal structure), several direct methods may be used. These methods give ideas for constructing efficient data parallel preconditioners for general positive definite symmetric matrices. We describe two examples of such preconditioners for which the factorization (i.e., the construction of the preconditioning matrix) turns out to be parallel. This revised version was published online in June 2006 with corrections to the Cover Date.