Adaptive Fourier-Galerkin methods

Canuto, C.; Nochetto, R.; Verani, M.

doi:10.1090/S0025-5718-2013-02781-0

Adaptive Fourier-Galerkin methods
HTML articles powered by AMS MathViewer

by C. Canuto, R. H. Nochetto and M. Verani PDF

Math. Comp. 83 (2014), 1645-1687 Request permission

Abstract:

We study the performance of adaptive Fourier-Galerkin methods in a periodic box in $\mathbb {R}^d$ with dimension $d\ge 1$. These methods offer unlimited approximation power only restricted by solution and data regularity. They are of intrinsic interest but are also a first step towards understanding adaptivity for the $hp$-FEM. We examine two nonlinear approximation classes, one classical corresponding to algebraic decay of Fourier coefficients and another associated with exponential decay typical of spectral approximation. We investigate the natural sparsity class for the operator range and find that the exponential class is not preserved, thus in contrast with the algebraic class. This entails a striking different behavior of the feasible residuals that lead to practical algorithms, influencing the overall optimality. The sparsity degradation for the exponential class is partially compensated with coarsening. We present several feasible adaptive Fourier algorithms, prove their contraction properties, and examine the cardinality of the activated sets. The Galerkin approximations at the end of each iteration are quasi-optimal for both classes, but inner loops or intermediate approximations are sub-optimal for the exponential class.

References

Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods, SIAM J. Math. Anal. 43 (2011), no. 3, 1457–1472. MR 2821591, DOI 10.1137/100795772
Peter Binev, Wolfgang Dahmen, and Ron DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219–268. MR 2050077, DOI 10.1007/s00211-003-0492-7
D. Bini, Personal communication.
A. Böttcher and B. Silbermann, Introduction to large truncated Toeplitz matrices, Springer-Verlag, New York, 1999.
C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral methods, Scientific Computation, Springer-Verlag, Berlin, 2006. Fundamentals in single domains. MR 2223552, DOI 10.1007/978-3-540-30726-6
J. Manuel Cascon, Christian Kreuzer, Ricardo H. Nochetto, and Kunibert G. Siebert, Quasi-optimal convergence rate for an adaptive finite element method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2524–2550. MR 2421046, DOI 10.1137/07069047X
Albert Cohen, Numerical analysis of wavelet methods, Studies in Mathematics and its Applications, vol. 32, North-Holland Publishing Co., Amsterdam, 2003. MR 1990555
Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27–75. MR 1803124, DOI 10.1090/S0025-5718-00-01252-7
Albert Cohen, Ronald DeVore, and Ricardo H. Nochetto, Convergence rates of AFEM with $H^{-1}$ data, Found. Comput. Math. 12 (2012), no. 5, 671–718. MR 2970853, DOI 10.1007/s10208-012-9120-1
Stephan Dahlke, Massimo Fornasier, and Karlheinz Gröchenig, Optimal adaptive computations in the Jaffard algebra and localized frames, J. Approx. Theory 162 (2010), no. 1, 153–185. MR 2565831, DOI 10.1016/j.jat.2009.04.001
Stephan Dahlke, Massimo Fornasier, and Thorsten Raasch, Adaptive frame methods for elliptic operator equations, Adv. Comput. Math. 27 (2007), no. 1, 27–63. MR 2317920, DOI 10.1007/s10444-005-7501-6
Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI 10.1017/S0962492900002816
R. A. DeVore and V. N. Temlyakov, Nonlinear approximation by trigonometric sums, J. Fourier Anal. Appl. 2 (1995), no. 1, 29–48. MR 1361541, DOI 10.1007/s00041-001-4021-8
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
C. Foias and R. Temam, Gevrey class regularity for the solutions of the Navier-Stokes equations, J. Funct. Anal. 87 (1989), no. 2, 359–369. MR 1026858, DOI 10.1016/0022-1236(89)90015-3
Tsogtgerel Gantumur, Helmut Harbrecht, and Rob Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Math. Comp. 76 (2007), no. 258, 615–629. MR 2291830, DOI 10.1090/S0025-5718-06-01917-X
S. Jaffard, Propriétés des matrices “bien localisées” près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré C Anal. Non Linéaire 7 (1990), no. 5, 461–476 (French, with English summary). MR 1138533, DOI 10.1016/S0294-1449(16)30287-6
Yitzhak Katznelson, An introduction to harmonic analysis, 3rd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2004. MR 2039503, DOI 10.1017/CBO9781139165372
Pedro Morin, Ricardo H. Nochetto, and Kunibert G. Siebert, Data oscillation and convergence of adaptive FEM, SIAM J. Numer. Anal. 38 (2000), no. 2, 466–488. MR 1770058, DOI 10.1137/S0036142999360044
Ricardo H. Nochetto, Kunibert G. Siebert, and Andreas Veeser, Theory of adaptive finite element methods: an introduction, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 409–542. MR 2648380, DOI 10.1007/978-3-642-03413-8_{1}2
Ch. Schwab, $p$- and $hp$-finite element methods, Numerical Mathematics and Scientific Computation, The Clarendon Press, Oxford University Press, New York, 1998. Theory and applications in solid and fluid mechanics. MR 1695813
Rob Stevenson, Optimality of a standard adaptive finite element method, Found. Comput. Math. 7 (2007), no. 2, 245–269. MR 2324418, DOI 10.1007/s10208-005-0183-0
Rob Stevenson, Adaptive wavelet methods for solving operator equations: an overview, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 543–597. MR 2648381, DOI 10.1007/978-3-642-03413-8_{1}3