Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleA local Fourier convergence analysis of a multigrid method using symbolic computation
Author(s) Veronika Pillwein, Stefan Takacs
TypeArticle in Journal
AbstractAbstract 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.
KeywordsCylindrical decomposition, Multigrid methods
URL http://www.sciencedirect.com/science/article/pii/S0747717113001752
JournalJournal of Symbolic Computation
Pages1 - 20
Translation No
Refereed No