A local Fourier convergence analysis of a multigrid method using symbolic computation
Abstract.
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.
The accompanying notebooks containing the calculations for the symbolic Local Fourier
Analysis (sLFA) described in "A
local Fourier convergence analysis of a multigrid method using symbolic computation"
by Veronika Pillwein and Stefan Takacs are available here
for
These notebooks were created in Mathematica 8.0.4.0 and
show the full output of all calculations. They can also be opened without having Mathematica
installed using the Wolfram CDF Player.
