Efficient preconditioning scheme for block partitioned matrices with structured sparsity

An efficient preconditioning algorithm is presented for solving linear systems for which the matrix exhibits a certain sparse block structure, such as PDEs in two or more dimensions. From the set of all matrices orthogonally similar to the original - subject to the constraint that blocks of the transformation are proportional to the identity - the most block-diagonally dominant member is determined. The diagonal blocks of this new matrix are then taken as the preconditioner. Constructing the preconditioner is computationally inexpensive, and fully parallelizable. Moreover, the sparsity pattern is preserved under the transformation, and for the scattering applications arising in molecular and chemical physics, it is shown that most of the computation need be performed only once for a large number of linear system solves. Results are summarized for two such systems, for which the total CPU effort was reduced by almost two orders of magnitude.