Fourier Analysis of Multigrid Methods on Hexagonal Grids

This paper applies local Fourier analysis to multigrid methods on hexagonal grids. Using oblique coordinates to express the grids and a dual basis for the Fourier modes, the analysis proceeds essentially the same as for rectangular grids. The framework for one- and two-grid analyses is given and then applied to analyze the performance of multigrid methods for the Poisson problem on a hexagonal grid. Numerical results confirm the analysis. Uniform hexagonal grids provide an approximation to spherical geodesic grids; numerical results for the latter show similar performance. While the analysis is similar to that for rectangular grids, the results differ somewhat: full weighting is superior to injection for restriction, Jacobi relaxation performs about as well as Gauss-Seidel relaxation, and underrelaxation is not required for good performance. Also, coarse-fine or four-color ordering (both analogues of red-black ordering on the rectangular grid) improves the performance of Jacobi relaxation, with the latter achieving a smoothing factor of approximately 0.25. An especially simple compact fourth-order discretization works well, and the full multigrid algorithm produces the solution to the level of truncation error in work proportional to the number of unknowns.