A semi-algebraic approach that enables the design of inter-grid operators to optimize multigrid convergence

Abstract

We study the effect of inter-grid operators—the interpolation and restriction operators—on the convergence of two-grid algorithms for linear models. We show how a modal analysis of linear systems, along with some assumptions on the normal modes of the system, allows us to understand the role of inter-grid operators in the speed and accuracy of a full-multigrid step. We state an assumption that generalizes local Fourier analysis (LFA) by means of a precise description of aliasing effects on the system. This assumption condenses, in a single algebraic property called the harmonic aliasing property, all the information needed from the geometry of the discretization and the structure of the system’s eigenvectors. We first state a harmonic aliasing property based on the standard coarsening strategies of 1D problems. Then, we extend this property to a more aggressive coarsening typically used in 2D problems with the help of additional assumptions on the structure of the system matrix. Under our general assumptions, we determine the exact rates at which groups of modal components of the error evolve and interact. With this knowledge, we are then able to design inter-grid operators that optimize the two-grid algorithm convergence. By different choices of operators, we verify the classic heuristics based on Fourier harmonic analysis, show a trade-off between the rate of convergence and the number of computations required per iteration, and show how our analysis differs from LFA.