Algebraic multigrid method
The algebraic multigrid (AMG) is a numerical method for solving systems of linear equations with , for example, from the discretization of elliptic partial differential equations can be derived. It is a modification of classic multigrid methods .
Differences to the conventional multi-grid method
The main difference to the conventional multigrid method is that it can be applied directly to linear systems of equations without using geometric properties.
The basic building blocks such as smoother and grid operators are also available at AMG, but the concepts are implemented differently: The grids are replaced by subgraphs of the matrix . The smoother is selected in advance, the interpolation or restriction operator must first be constructed (in contrast to the usual multi-grid method).
AMG needs a preparatory phase to calculate coarser grids and interpolation operators, so that it is usually slower compared to the classic multi-grid method. However, the main benefit of AMG lies in the fact that problems can be dealt with that cannot be easily solved with classic multigrid methods.
Problems considered
AMG aims, for example, at problems with complicated geometries, where classic multi-lattice methods are difficult to apply. It can then be difficult or impossible to find coarser grids. AMG does not have this problem, as the coarsening is defined differently and has no geometric background.
A given interpolation operator can also give poor results, but since the interpolation is selected in AMG, this method also gives better results. Furthermore, AMG can of course also solve problems that are not geometrically motivated at all.
literature
- William L. Briggs, Van Emden Henson, and Steve F. McCormick: A Multigrid Tutorial , 2nd Edition, SIAM, 2000, ISBN 0-89871-462-1
- Stephen F. McCormick: Multigrid Methods , SIAM, 1987, ISBN 0-89871-214-9