Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Adaptive wavelet methods for elliptic operator equations: Convergence rates

Authors: Albert Cohen, Wolfgang Dahmen and Ronald DeVore
Journal: Math. Comp. 70 (2001), 27-75
MSC (2000): Primary 41A25, 41A46, 65F99, 65N12, 65N55
Published electronically: May 23, 2000
MathSciNet review: 1803124
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information


This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution $u$ of the equation by a linear combination of $N$ wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to $u$by an arbitrary linear combination of $N$ wavelets (so called $N$-term approximation), which would be obtained by keeping the $N$largest wavelet coefficients of the real solution (which of course is unknown). The main result of the paper is the construction of an adaptive scheme which produces an approximation to $u$ with error $O(N^{-s})$ in the energy norm, whenever such a rate is possible by $N$-term approximation. The range of $s>0$ for which this holds is only limited by the approximation properties of the wavelets together with their ability to compress the elliptic operator. Moreover, it is shown that the number of arithmetic operations needed to compute the approximate solution stays proportional to $N$. The adaptive algorithm applies to a wide class of elliptic problems and wavelet bases. The analysis in this paper puts forward new techniques for treating elliptic problems as well as the linear systems of equations that arise from the wavelet discretization.

References [Enhancements On Off] (What's this?)

  • 1. A. Averbuch, G. Beylkin, R. Coifman, and M. Israeli, Multiscale inversion of elliptic operators, in: Signal and Image Representation in Combined Spaces, J. Zeevi, R. Coifman (eds.), Academic Press, 1998, pp. 341-359. MR 99a:65162
  • 2. I. Babuska and A. Miller, A feedback finite element method with a-posteriori error estimation: Part I. The finite element method and some basic properties of the a-posteriori error estimator, Comput. Methods Appl. Mech. Engrg. 61 (1987), 1-40. MR 88d:73036
  • 3. I. Babuska and W.C. Rheinboldt, Error estimates for adaptive finite element computations, SIAM J. Numer. Anal. 15 (1978), 736-754. MR 58:3400
  • 4. R.E. Bank, A.H. Sherman and A. Weiser, Refinement algorithms and data structures for regular local mesh refinement, in: R. Stepleman et al. (eds.), Scientific Computing, Amsterdam: IMACS, North- Holland, 1983, 3-17. MR 85i:00014
  • 5. R.E. Bank and A. Weiser, Some a posteriori error estimates for elliptic partial differential equations, Math. Comp., 44 (1985), 283-301. MR 86g:65207
  • 6. A. Barinka, T. Barsch, P. Charton, A. Cohen, S. Dahlke, W. Dahmen, K. Urban, Adaptive wavelet schemes for elliptic problems--implementation and numerical experiments, IGPM Report # 173, RWTH Aachen, June 1999.
  • 7. S. Bertoluzza, A-posteriori error estimates for wavelet Galerkin methods, Appl Math. Lett., 8 (1995), 1-6. MR 96e:65053
  • 8. S. Bertoluzza, An adaptive collocation method based on interpolating wavelets, in: Multiscale Wavelet Methods for PDEs, W. Dahmen, A. J. Kurdila, P. Oswald (eds.), Academic Press, San Diego, 1997, 109-135. MR 98d:65149
  • 9. S. Bertoluzza, Wavelet stabilization of the Lagrange multiplier method, to appear in Numer. Math.
  • 10. S. Bertoluzza, C. Canuto, K. Urban, On the adaptive computation of integrals of wavelets, Preprint No. 1129, Istituto di Analisi Numerica del C.N.R. Pavia, 1999, to appear in Appl. Numer. Anal.
  • 11. G. Beylkin, R. R. Coifman, and V. Rokhlin, Fast wavelet transforms and numerical algorithms I, Comm. Pure and Appl. Math., 44 (1991), 141-183. MR 92c:65061
  • 12. G. Beylkin and J. M. Keiser, An adaptive pseudo-wavelet approach for solving nonlinear partial differential equations, in: Multiscale Wavelet Methods for PDEs, W. Dahmen, A. J. Kurdila, P. Oswald (eds.), Academic Press, San Diego, 1997, 137-197. MR 98i:65124
  • 13. F. Bornemann, B. Erdmann, and R. Kornhuber, A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal., 33 (1996), 1188-1204. MR 98a:65161
  • 14. D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, 1997. MR 98f:65002
  • 15. S. Brenner and L.R. Scott, The mathematical theory of finite element methods, Springer Verlag, New York, 1994. MR 95f:65001
  • 16. C. Canuto and I. Cravero, Wavelet-based adaptive methods for advection-diffusion problems, Preprint, University of Torino, 1996.
  • 17. A. Cohen, Wavelet methods in Numerical Analysis, to appear in the Handbook of Numerical Analysis, vol. VII, 1998.
  • 18. A. Cohen and R. Masson, Wavelet adaptive methods for elliptic equations - Preconditioning and adaptivity, Preprint, LAN, Université Pierre et Marie Curie, Paris, 1997, to appear in SIAM J. Sci. Comp.
  • 19. S. Dahlke, W. Dahmen, and R. DeVore, Nonlinear approximation and adaptive techniques for solving elliptic equations, in: Multiscale Techniques for PDEs, W. Dahmen, A. Kurdila, and P. Oswald (eds), Academic Press, 1997, San Diego, 237-284. MR 99a:65001
  • 20. S. Dahlke, W. Dahmen, R. Hochmuth, and R. Schneider, Stable multiscale bases and local error estimation for elliptic problems, Applied Numerical Mathematics, 23 (1997), 21-47. MR 98a:65075
  • 21. S. Dahlke and R. DeVore, Besov regularity for elliptic boundary value problems, Communications in PDEs, 22(1997), 1-16. MR 97k:35047
  • 22. S. Dahlke, R. Hochmuth, K. Urban, Adaptive wavelet methods for saddle point problems, IGPM Report # 170, RWTH Aachen, Feb. 1999.
  • 23. W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Numerica 6, Cambridge University Press, 1997, 55-228. MR 98m:65102
  • 24. W. Dahmen, A. Kunoth, R. Schneider, Wavelet least squares methods for boundary value problems, IGPM Report # 175, RWTH Aachen, Sep. 1999.
  • 25. W. Dahmen, S. Müller, and T. Schlinkmann, Multigrid and multiscale decompositions, in: Large-Scale Scientific Computations of Engineering and Environmental Problems, M. Griebel, O.P. Iliev, S.D. Margenov, and P.S. Vassilevski, eds., Notes on Numerical Fluid Mechanics, Vol. 62, Vieweg, Braunschweig/Wiesbaden, 1998, 18-41. MR 2000b:65228
  • 26. W. Dahmen, S. Prößdorf, and R. Schneider, Multiscale methods for pseudo-differential equations on smooth manifolds, in: Proceedings of the International Conference on Wavelets: Theory, Algorithms, and Applications, C.K. Chui, L. Montefusco, and L. Puccio (eds.), Academic Press, 1994, 385-424. MR 96c:65208
  • 27. W. Dahmen and R. Schneider, Wavelets on manifolds I, Construction and domain decomposition, IGPM-Report # 149, RWTH Aachen, Jan 1998.
  • 28. W. Dahmen and R. Schneider, Wavelets on manifolds II, Application to boundary integral equations, in preparation.
  • 29. W. Dahmen, R. Stevenson, Element-by-element construction of wavelets--stability and moment conditions, IGPM-Report # 145, RWTH Aachen, Dec. 1997.
  • 30. I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61, SIAM Philadelphia, 1988. MR 93e:42045
  • 31. R. DeVore, Nonlinear approximation, Acta Numerica 7, Campbridge University Press, 1998, 51-150. CMP 99:16
  • 32. R. DeVore, B. Jawerth and V. Popov, Compression of wavelet decompositions, Amer. J. Math., 114 (1992), 737-785. MR 94a:42045
  • 33. R. DeVore, V. Popov, Interpolation spaces and nonlinear approximation, in: Function Spaces and Approximation, M. Cwikel et al, eds., Lecture Notes in Mathematics, vol.1302, 1998, Springer, 191-205. MR 89d:41035
  • 34. R. DeVore and V. Temlyakov, Some remarks on greedy algorithms, Advances in Computational Math., 5 (1996), 173-187. MR 97g:41029
  • 35. W. Dörfler, A convergent adaptive algorithm for Poisson's equation, SIAM J. Numer. Anal., 33 (1996), 1106-1124. MR 97e:65139
  • 36. K. Eriksson, D. Estep, P. Hansbo, and C. Johnson, Introduction to adaptive methods for differential equations, Acta Numerica 4, Cambridge University Press, (1995), 105-158. MR 96k:65057
  • 37. M. Frazier, B. Jawerth, and G. Weiss, Littlewood-Paley theory and the study of function spaces, CBMS Conference Lecture Notes 79, (AMS, Providence, RI), 1991. MR 92m:42021
  • 38. Y. Meyer, Ondelettes et Operateurs, Vol 1 and 2, Hermann, Paris, 1990. MR 93i:42002; MR 93i:42003
  • 39. E. Novak, On the power of adaptation, J. Complexity, 12(1996), 199-237.
  • 40. T. von Petersdorff, and C. Schwab, Fully discrete multiscale Galerkin BEM, in: Multiscale Wavelet Methods for PDEs, W. Dahmen, A. Kurdila, and P. Oswald (eds.), Academic Press, San Diego, 1997, 287-346. MR 99a:65158
  • 41. R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme, Habilitationsschrift, Technische Hochschule, Darmstadt, 1995.
  • 42. P. Tchamitchian, Wavelets, Functions, and Operators, in: Wavelets: Theory and Applications, G. Erlebacher, M.Y. Hussaini, and L. Jameson (eds.), ICASE/LaRC Series in Computational Science and Engineering, Oxford University Press, 1996, 83-181.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A25, 41A46, 65F99, 65N12, 65N55

Retrieve articles in all journals with MSC (2000): 41A25, 41A46, 65F99, 65N12, 65N55

Additional Information

Albert Cohen
Affiliation: Laboratoire d’Analyse Numerique, Universite Pierre et Marie Curie, 4 Place Jussieu, 75252 Paris cedex 05, France

Wolfgang Dahmen
Affiliation: Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, 52056 Aachen, Germany

Ronald DeVore
Affiliation: Department of Mathematics, University of South Carolina, Columbia, SC 29208

Keywords: Elliptic operator equations, quasi-sparse matrices and vectors, best $N$-term approximation, fast matrix vector multiplication, thresholding, adaptive space refinement, convergence rates
Received by editor(s): December 16, 1998
Published electronically: May 23, 2000
Additional Notes: This work has been supported in part by the Deutsche Forschungsgemeinschaft grants Da 117/8–2, the Office of Naval Research Contract N0014-91-J1343, the Army Research Office Contract DAAG 55-98-1-D002, and the TMR network “Wavelets in Numerical Simulation".
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society