Using Symbolic Methods to Analyze Convergence Properties of Multigrid Methods

Dr. Stefan Takacs

April 12, 2011, 2 p.m. HS 14

Local Fourier analysis (or local mode analysis) is a widely-used tool to analyze numerical methods for solving discretized systems of partial differential equations. We use this technique to analyze all-at-once multigrid methods for some classes of saddle point problems, namely optimality systems characterizing the solution of optimal control problems. The convergence (or smoothing) rates that can be computed with local Fourier analysis are typically the supremum of some rational function. Typically, either non-sharp bounds were derived for this supremum or the supremum was approximated numerically. We show that the supremum can be resolved exactly using cylindrical algebraic decomposition, which is a well established method in symbolic computation. Using this approach, the computed bounds for the convergence (or smoothing) rates are sharp and moreover show explicitly the dependence of these rates on the choice of some problem and/or numerical parameters.