Prolongation Smoothing for Nonsymmetric and Indefinite Matrices

Applying algebraic multigrid techniques to nonsymmetric or indefinite matrices is currently one of the most difficult tasks confronting the algebraic multigrid community. Algebraic multigrid is built around the complementary relationship between relaxation and interpolation. In classic multigrid, this complementary relationship is usually defined with the matrix inner-product and induced norm. However when the matrix becomes nonsymmetric or indefinite, it becomes unclear how to define this complementary relationship, or the relaxation and interpolation techniques that would enforce such a relationship. Our goal is to develop robust prolongation smoothers for indefinite or nonsymmetric matrices. For the complementary relationship, we look to the A*A-norm, although the normal equations are never explicitly formed.

Currently, we are utilizing Krylov methods to minimize the energy of the prolongator in a constraint space. This research has already provided the CGNR-based prolongation smoother that is used in the smoothed aggregation preconditioner for indefinite Helmholtz problems discussed here. In the future, we plan to explore other Krylov or Krylov-like methods operating in a constraint space as possible prolongation smoothers.

In the below image, a sample scattered wave for the indefinite Helmholtz problem is shown. The above mentioned CGNR-based prolongation smoother was used to generate the multilevel preconditioner.

Last updated September, 2009