Premium
Efficient preconditioning scheme for block partitioned matrices with structured sparsity
Author(s) -
Poirier Bill
Publication year - 2000
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/1099-1506(200010/12)7:7/8<715::aid-nla220>3.0.co;2-r
Subject(s) - preconditioner , parallelizable manifold , block matrix , mathematics , block (permutation group theory) , diagonal , linear system , sparse matrix , transformation (genetics) , matrix (chemical analysis) , algorithm , computation , eigenvalues and eigenvectors , identity matrix , iterative method , combinatorics , mathematical analysis , geometry , gene , composite material , gaussian , biochemistry , physics , chemistry , materials science , quantum mechanics
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. Copyright © 2000 John Wiley & Sons, Ltd.