Efficient preconditioning scheme for block partitioned matrices with structured sparsity

An efficient preconditioning algorithm is presented for solving linear syst ems 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 transf ormation are proportional to the identity-the most block-diagonally dominan t member is determined. The diagonal blocks of this new matrix are then tak en as the preconditioner. Constructing the preconditioner is computationall y inexpensive, and fully parallelizable. Moreover, the sparsity pattern is preserved under the transformation, and for the scattering applications ari sing in molecular and chemical physics, it is shown that most of the comput ation need be performed only once for a large number of linear system solve s. Results are summarized for two such systems, for which the total CPU eff ort was reduced by almost two orders of magnitude. Copyright (C) 2000 John Wiley & Sons, Ltd.