Algebraic Multigrid based on Graph Coarsening

Ulrich Langer
Ferdinand Kickinger
University Linz Austria


In the numerical simulation of industrial problems fast solvers are needed, especially when dealing with complicated geometries in 3D arising from real-life problems. Multigrid (MG) Methods are quite useful in this context, because of their optimal time complexity. One of the major problems caused by the use of MG, is the sequence of nested meshes needed. This sequence is often not available or reconstructible in a natural manner. To overcome this crucial point, we generalize some Algebraic Multigrid Method (AMG) for scalar elliptic equations to systems of equations. This method is based on a graph coarsening algorithm acting on the stiffness pattern, and therefore, it is cheap. From this point of view, the standard MG with Galerkin projection turns out to be some special case of our algebraic algorithm.

Industrial problems often cause further trouble based on some bad scaled property. Therefor, engineers use the so-called Global Extraction Element-by-Element (GE-EBE) Methods, The authors propose to use the GE-EBE methods and their patch counterpart (GE-PBP) either as smoothers, especially, in their multiplicative version, or as preconditioners in their multilevel additive version. The GE-PBP smoother is especially suited for the use in Algebraic Multigrid Methods based on graph coarsening strategies. The numerical results presented confirm the good smoothing properties of GE-PBP smoothers as well as the preconditioning properties of multilevel additive GE-PBP preconditioners. Finally, the authors discuss Algebraic Multigrid Methods for the Stokes Problem using Uzawa typed methods.