Local Fourier analysis (LFA) is a classical tool for proving convergence theorems for multigrid methods (MGMs). In particular, we are interested in optimal convergence, i.e. convergence rates that are independent of the problem size. 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 approximated. Analogously, when dealing with MGMs for Toeplitz matrices, a well-known optimality condition concerns the position and the order of the zeros of the symbols of the grid transfer operators. 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. The equivalence of the two approaches gives the possibility of using grid transfer operators with different orders also for MGMs for Toeplitz matrices. We give also a class of grid transfer operators related to the B-spline's refinement equation and study their geometric properties. Numerical experiments confirm the correctness of the proposed analysis.

An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices

DONATELLI, MARCO
2010-01-01

Abstract

Local Fourier analysis (LFA) is a classical tool for proving convergence theorems for multigrid methods (MGMs). In particular, we are interested in optimal convergence, i.e. convergence rates that are independent of the problem size. 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 approximated. Analogously, when dealing with MGMs for Toeplitz matrices, a well-known optimality condition concerns the position and the order of the zeros of the symbols of the grid transfer operators. 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. The equivalence of the two approaches gives the possibility of using grid transfer operators with different orders also for MGMs for Toeplitz matrices. We give also a class of grid transfer operators related to the B-spline's refinement equation and study their geometric properties. Numerical experiments confirm the correctness of the proposed analysis.
2010
http://onlinelibrary.wiley.com/doi/10.1002/nla.704/abstract
Donatelli, Marco
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/1717854
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 24
social impact