Closed-form multigrid smoothing factors for lexicographic Gauss-Seidel

This paper aims to present a unified framework for deriving analytical formulas for 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 is analysed. Our 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 a special case of 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.