Closed-Form Multigrid Smoothing Factors for Lexicographic Gauss-Seidel

Abstract: 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 Möbius 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. 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 and a special case of the convection-diffusion equation. We show that 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 in particular for certain model convection-diffusion equations with high mesh Reynolds numbers.