next up previous
Next: About this document ...

Marco, M Donatelli
An algebraic generalization of the local Fourier analysis

Universita' dell'Insubria - sede di Como
Dipartimento di Fisica e Matematica
via Valleggio
11 - 22100 Como (ITALY)
marco.donatelli@uninsubria.it

The Local Fourier analysis (LFA) is a classic tool to prove convergence results for multigrid methods (MGMs). In particular, we are interested in optimality that is a convergence speed independent of the size of the involved matrices. For elliptic partial differential equations (PDEs), a well known optimality result requires that the sum of the orders of the grid transfer operators is not lower than the order of the PDE to be solved. Analogously, when dealing with MGMs for Toeplitz matrices in the literature an optimality condition on the position and on the order of the zeros of the symbols of the grid transfer operators has been found. In this work we show that in the case of elliptic PDEs with constant coefficients, the two different approaches lead to an equivalent condition. We argue that the analysis for Toeplitz matrices is an algebraic generalization of the LFA, which allows to deal not only with differential problems, but also, for instance, with integral problems. We give also a class of grid transfer operators related to the B-spline refinement equation and we study their geometric properties. This analysis suggests further links between wavelets and multigrid methods. A numerical experimentation confirms the correctness of the proposed analysis.




next up previous
Next: About this document ...
Marian 2009-02-04