#include <Multigrid.h>
Inheritance diagram for NestedMultigrid::
Public Methods | |
| NestedMultigrid (const MLSolver_prm &pm) | |
| ~NestedMultigrid () | |
| virtual String | description () const |
| virtual int | getWork (const PrecondWork work_tp) const |
| virtual bool | solve (StartVectorMode start) |
| virtual void | init () |
| virtual void | initRes (SpaceId i) |
NAME: NestedMultigrid - nested multigrid
DESCRIPTION:
Implements a nested multigrid cycle. Other names for the algorithm are full multigrid method (FMG) and cascadic multigrid. The idea is to use multigrid on coarser grids to create a good start vector for a multigrid cycle on the finest grid. The procedure is especially attractive for nonlinear problems, if the coarse grids are used as good start vectors for the nonlinear iterations.
If the right hand side vectors for all grids are valid, they will be used in the nested iteration. Missing vectors are computed by restricting (using "transfer") the fine grid vectors to the grid. Hence it is useful to compute all right hand sides (and flag them as valid) for the nested iteration considered as an iterative solver. The coarse right hand sides for preconditioners will be discarded, instead.
A fixed number of fine grid multigrid cycles should be sufficient to solve the system (up to discretization error), independent of the number of unknowns or the number of grids. The total number of operations per unknown is therefore fixed. The number of cycles can be chosen by the "nestedcycles" parameter of "MLSolver_prm". This parameter is by default 1. If one wants to have a dynamic control of the number of multigrid cycles, e.g. by the "ConvMonitor" mechanism, one should use the "Multigrid" class instead and write the nested-iteration-loop around it.
The different sub-domains here are the different grids. The grids themselves can be Lattice Grids, structured or unstructured grids, or adaptively refined grids. It can be used as a iterative solver, a preconditioner or a non-linear solver.
The coarse grid is number 1, the fine grid is number "getNoOfSpaces". The grids all cover the same geometric domain, but differ in the resolution or grid size. For standard applications the grids are nested and the grid sizes double form fine to coarse. However, in general the grids need not be nested.
The "Proj" operators will usually be used to implement the grid transfers for "transfer" of "MLSolverUDC". Only the transfers from i to i+1 (prolongation) and the adjoint transfers from i+1 to i (restriction) are used. These transfers can be implemented very efficiently for nested grids which grid sizes double. For non nested grids this transfers are more expensive.
The approximate solvers for the different grids usually are called smoothers. The solver for the coarsest grid number 1 can be exact, e.g. a direct solver, but does not have to be exact. It is not useful to use additional exact solvers for linear problems. Hence the other solvers are iterative solvers. Usually it is sufficient to use a small fixed number of iterations. Note that the optimal relaxation for over-relaxation iterations differs from the optimal value used for single-grid (standard) applications. If you want to use different procedures for pre- and post-smoothing, you will make use of the "MLSolverMode" flag in the "solveSubSystem" function of "MLSolverUDC". In the case of adaptively refined grids, the iteration can be restricted to the refined parts of the grid.
The "gamma" parameter of "MLSolver_prm" is used to choose the multigrid cycle type. "gamma"=1 is a V-cycle, which is one run from fine to coarse and reverse. "gamma"=2 is a W-cycle, which spends more operations on coarse grids. Higher "gamma" are defined recursively. If there are some convergence problems, which can not be overcome by improving the sub-domain solvers (or better transfer operators), it is usually a good idea to switch from a V-cycle to a W-cycle or even more expensive cycles. Note that using too expensive cycles ("gamma" too high) sacrifices the optimal complexity of the algorithm. This bound depends on the increase of points from one grid i to the finer grid i+1. It is independent of the number of nested cycles.
In the case you want to have a symmetric multigrid, take care that the transfers i to i+1 and i+1 to i are adjoint and that the pre-smoothing and the post-smoothing are adjoint, too. This can be useful for self-adjoint differential operators and symmetric solvers like "ConjGrad".
For further reading see e.g. chapters 5 and 9 of W. Hackbusch "Multigrid Methods and Applications", Springer Verlag, 1985.
|
|
See class "MLSolver". |
|
|
|
|
|
Reimplemented from Multigrid. |
|
|
estimate work. Estimates are compatible with estimates for linear solvers. Reimplemented from Multigrid. |
|
|
initializes the class. Reimplemented from Multigrid. |
|
|
|
|
|
solves the system. The function implements the algorithm and will probably never be called by the user directly. Data vectors have to be attached during initialization. The actual algorithm determines exactly, which vectors are needed and checks, whether they have been attached. The start vector is given by a value "StartVectorMode". Reimplemented from Multigrid. |