Open Collections

A complex analysis based derivation of multigrid smoothing factors of lexicographic Gauss-Seidel

University of British Columbia

This thesis aims to present a unified framework for deriving analytical formulas for multigrid smoothing factors in arbitrary dimensions, under certain simplifying assumptions. To derive these expressions we rely on complex analysis and geometric considerations, using the maximum modulus principle and Mobius transformations. We restrict our attention to pointwise and block lexicographic Gauss-Seidel smoothers on a d-dimensional uniform mesh, where the computational molecule of the associated discrete operator forms a 2d+1 point star. In the pointwise case the effect of a relaxation parameter, as well as different choices of mesh ratio, are analyzed. The results apply to any number of spatial dimensions, and are applicable to high-dimensional versions of a few common model problems with constant coefficients, including the Poisson and anisotropic diffusion equations as well as the convection-diffusion equation. We show that in most cases our formulas, exact under the simplifying assumptions of Local Fourier Analysis, form tight upper bounds for the asymptotic convergence of geometric multigrid in practice. We also show that there are asymmetric cases where lexicographic Gauss-Seidel smoothing outperforms red-black Gauss-Seidel smoothing; this occurs for certain model convection-diffusion equations with high mesh Reynolds numbers.

Text

2011-08-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/37012

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/