A Multiscale Filter to Accelerate Multigrid Methods

 

Haim Waisman, Jacob Fish

Department of Civil Engineering
Rensselaer Polytechnic Institute, Troy, NY 12180

 

 

Ray Tuminaro

Sandia National Laboratories
PO Box 969, MS 9159, Livermore, CA 94551

 

 

John Shadid

Sandia National Laboratories
PO Box 5800, MS 1111, Albuquerque, NM 87185

 


Abstract

We present the Generalized Global-Basis (GGB) method aimed at enhancing performance of multigrid solvers for difficult systems such as those arising from indefinite and nonsymmetric matrices. The GGB method is a multiscale filter that constructs an auxiliary coarse model from the largest eigenvalues of the iteration matrix. It projects these modes which would cause slow convergence to a coarse problem which is then used to eliminate  these modes. 

For nonlinear problems the filter is modified (MGGB) to selectively reuse the same prolongation and thus reduce the amount of eigensolver calculations. This selection criteria is based on principal angles between subspaces spanned between the previous and current prolongation operators. 

Numerical examples show that best performance is obtained when GGB is accelerated by GMRES and used for problems with multiple right hand sides. In addition it is demonstrated that GGB can enhance restarted GMRES strategies by retention of important subspace information. For nonlinear problems, MGGB scheme indicate significant time savings.

 

 

References

H. Waisman, J. Fish, R. S. Tuminaro and J. Shadid, The Generalized Global Basis (GGB) Method, International Journal for Numerical Methods in Engineering 61 (8):1243-1269, October 2004.


H. Waisman, J. Fish, R. S. Tuminaro and J. Shadid, Acceleration of the Generalized Global Basis method for nonlinear problem, Submitted to  Journal of Computational Physics.