A local Fourier convergence analysis of a multigrid method using symbolic computation

Cylindrical algebraic decomposition (CAD) is a standard tool in symbolic computation. In this paper we use it to compute a bound for the convergence rate for a numerical method that usually is merely resolved by numerical interpolation. Applying CAD allows us to determine an exact bound, but the given formula is too large to be simply plugged in. Hence a combination of reformulating, guess and prove and splitting into subproblems is necessary. In this paper we work out the details of a symbolic local Fourier analysis for a particular multigrid solver applied to a particular optimization problem constrained to a partial differential equation (PDE-constrained optimization problem), even though the proposed approach is applicable to different kinds of problems and different kinds of solvers. The approach is based on local Fourier analysis (or local mode analysis), a widely-used straight-forward method to analyze the convergence of numerical methods for solving discretized systems of partial differential equations (PDEs). Such an analysis requires to determine the supremum of some rational function, for which we apply CAD.