Efficient Multigrid Methods based on Improved Coarse Grid Correction Techniques

Efficient Multigrid Methods based on Improved Coarse Grid Correction Techniques

Bin Zubair, H.

Oosterlee, C.W. (promotor)

Electrical Engineering, Mathematics and Computer Science

Applied mathematics

2009-09-01

Multigrid efficiency often suffers from inadequate coarse grid correction in different prototypic situations. We select a few problems, where coarse grid correction issues arise because of anisotropic coefficients, non-equidistant or non-uniform grid stretching, or inherent indefiniteness in the partial differential equation. Most of the work in this thesis can be classified as an attempt to increase multigrid efficiency by analysing and developing novel grid coarsening techniques that ensure sufficient coarse grid correction for the multigrid algorithm. Anisotropy in discrete systems can stem from various continuous and discrete features of the problem and has to have its negative effects countered before a successful multigrid solution can be brought about. We select multidimensional stationary diffusion equation as the first important problem to be treated in this context. The work for dimensions higher than three, is aimed at developing grid coarsening strategies for discretization on rectangular hyper-grids that differ greatly in their dimensions, and thus induce the so-called grid-aligned anisotropies in the system. Coarse grids formed through standard coarsening fail to provide sufficient coarse grid correction, and alternative block relaxation techniques are expensive in high dimensions. We also investigate and test coarsening strategies with the aim that their use would allow point based relaxation to stay effective in this non-equidistant multigrid scenario. Through local Fourier analysis we also analyze w-RB Jacobi, and implement a computer program through which we compute the optimal relaxation parameters. There are three important inferences in this regard. (1) Partial (and grid dependent) coarsening strategies allow the successful use of point relaxation methods for this problem. (2) Quadrupling along a few dimensions is a very attractive partial coarsening choice. (3) Optimal relaxation parameters have a significant enhancement effect on multigrid convergence in high dimensions. The efficient solution of time-dependent multidimensional equations (discretized with implicit time-integration schemes) is also a challenge. We first use the sparse grid technique to reduce the exponential complexity of the discrete problem, and then use the d-dimensional multigrid techniques to solve the sparse grid sub problems. In this situation, i.e., with a multitude of different non equidistant grids, evaluating and using optimal relaxation parameters on the fly is not an option any more. As a multigrid solver in high dimensions depends on optimal attributes to quite a large extent, we employ the method as a preconditioner, instead of a solver. This results in a very robust and efficient multigrid preconditioned Bi-CGSTAB solver. Another coarsening strategy that we develop in this thesis is aimed at two-dimensional grids that are non-uniformly stretched. We investigated different experimental coarsening strategies. A strategy based on improving individual mesh aspect ratios of grid cells proves successful both theoretically as well as experimentally. It is based on adaptive coarsening so that on each successive coarsening step the grid cells become more square. We can also successfully use point relaxation methods with the proposed technique and get nice multigrid convergence in this case. This bit of work also has consequence for locally refined grids. Efficient multigrid techniques for the indefinite Helmholtz equation form a separate research theme included in the thesis. We employ the complex shifted operator preconditioning technique for model problems that stem from quantum mechanics applications. These model problems have strongly varying wave-numbers which perturbs the solution. The mesh size requirement in the region of this perturbation is quite demanding. This requirement can be eased by saturating the grid in that area. We find that standard coarsening in this situation works well. This is in contrast to the existing strategies where coarsening is only done in the region of refinement, until the grid is regularized. We discretize the model problems both on equidistant and also on locally refined grids, and the efficiency of the multigrid preconditioner is tested in both these situations. Experiments point to the fact that existing techniques for the indefinite Helmholtz are still not satisfactory and must be enhanced. Some conclusions and outlook mark the end of the thesis.

multigrid
d-multigrid
sparse grids
multidimensional partial differential equations
multigrid preconditioned Krylov methods
grid-stretching
indefinite Helmholtz
adaptive mesh-refinement

http://resolver.tudelft.nl/uuid:e0b43b38-ad07-4076-baf1-aa02579c397f

9789090243986

Institutional Repository

doctoral thesis

(c) 2009 bin Zubair, H.