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 Free Access

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?)

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