Fourier Analysis of Periodic Stencils in Multigrid Methods

Many applications require the numerical solution of a partial differential equation (PDE), leading to large and sparse linear systems. Often a multigrid method can solve these systems efficiently. To adapt a multigrid method to a given problem, local Fourier analysis (LFA) can be used. It provides quantitative predictions about the behavior of the components of a multigrid method. In this paper we generalize LFA to handle what we call periodic stencils. An operator given by a periodic stencil has a block Fourier symbol representation. It gives a way to compute the spectral radius and norm of the operator. Furthermore block Fourier symbols can be used to find out how an operator acts on smooth/oscillatory input and whether its output will be smooth/oscillatory. This information can then be used to construct efficient smoothers and coarse grid corrections. We consider a particular PDE with jumping coefficients and show that it leads to a periodic stencil. LFA shows that the Jacobi method is a suitable smoot...