Massively parallel preconditioners for symmetric positive definite linear systems (Q1370332)

The inverse of an \(n\times n\) bidiagonal matrix \(I-E\) with diagonal \(I\) can be expressed as a product of \(\log n\) matrices of the form \(I+ E^p\) with \(p\) powers of 2. This remains true for more general ``irregular diagonal'' matrices \(E\) like general subdiagonals. The paper proposes a preconditioning technique where the preconditioner is a product of matrices \(I- E_k\) with \(E_k\) ``irregular'' diagonal matrices corresponding to some a priori chosen pattern. The computation of the preconditioner may be viewed as a sequence of incomplete factorizations of the form \(A\leftarrow (I- E_k)A(I- E_k)^T\). A similar version with \(A\) replaced by \(A^{-1}\) is also investigated. In a data parallel environment, solving systems with the preconditioner amounts to multiplications with the powers of the \(E_k\) which can be done efficiently. An analysis of the proposed preconditioners is not given, but numerical experiments on a connection machine CM5 with 32 processors for 2D discrete elliptic problems on a uniform mesh show the advantage of the proposed method over diagonal and polynomial preconditioners.