Using Symbolic Methods to Analyze Convergence Properties of Multigrid Methods

Dr. Stefan Takacs

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

Local Fourier analysis (or local mode analysis) is a widely-used tool to ana-
lyze numerical methods for solving discretized systems of partial di erential
equations. We use this technique to analyze all-at-once multigrid methods for
some classes of saddle point problems, namely optimality systems characteri-
zing the solution of optimal control problems. The convergence (or smoothing)
rates that can be computed with local Fourier analysis are typically the supre-
mum of some rational function. Typically, either non-sharp bounds were derved
for this supremum or the supremum was approximated numerically. We show
that the supremum can be resolved exactly using cylindrical algebraic decom-
position, 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.