Computation of differential operators in wavelet coordinates

Authors:
Tsogtgerel Gantumur and Rob Stevenson

Journal:
Math. Comp. **75** (2006), 697-709

MSC (2000):
Primary 41A25, 47A20, 65F50, 65N30, 65D30

Published electronically:
December 8, 2005

MathSciNet review:
2196987

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In [*Found. Comput. Math.*, 2 (2002), pp. 203-245], Cohen, Dahmen, and DeVore proposed an adaptive wavelet algorithm for solving general operator equations. Assuming that the operator defines a boundedly invertible mapping between a Hilbert space and its dual, and that a Riesz basis of wavelet type for this Hilbert space is available, the operator equation is transformed into an equivalent well-posed infinite matrix-vector system. This system is solved by an iterative method, where each application of the infinite stiffness matrix is replaced by an adaptive approximation. It was shown that if the errors of the best linear combinations from the wavelet basis with terms are for some , which is determined by the Besov regularity of the solution and the order of the wavelet basis, then approximations yielded by the adaptive method with terms also have errors of . Moreover, their computation takes only operations, *provided* , with being a measure of how well the infinite stiffness matrix with respect to the wavelet basis can be approximated by computable sparse matrices. Under appropriate conditions on the wavelet basis, for both differential and singular integral operators and for the relevant range of , in [*SIAM J. Math. Anal.*, 35(5) (2004), pp. 1110-1132] we showed that , *assuming* that each entry of the stiffness matrix is exactly available at unit cost.

Generally these entries have to be approximated using numerical quadrature. In this paper, restricting ourselves to differential operators, we develop a numerical integration scheme that computes these entries giving an additional error that is consistent with the approximation error, whereas in each column the average computational cost per entry is . As a consequence, we can conclude that the adaptive wavelet algorithm has optimal computational complexity.

**[Bur98]**Victor I. Burenkov,*Sobolev spaces on domains*, Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], vol. 137, B. G. Teubner Verlagsgesellschaft mbH, Stuttgart, 1998. MR**1622690****[CDD02]**A. Cohen, W. Dahmen, and R. DeVore,*Adaptive wavelet methods. II. Beyond the elliptic case*, Found. Comput. Math.**2**(2002), no. 3, 203–245. MR**1907380**, 10.1007/s102080010027**[Coh00]**Albert Cohen,*Wavelet methods in numerical analysis*, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 417–711. MR**1804747****[CM00]**A. Cohen and R. Masson,*Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition*, Numer. Math.**86**(2000), no. 2, 193–238. MR**1777487**, 10.1007/PL00005404**[CTU99]**Claudio Canuto, Anita Tabacco, and Karsten Urban,*The wavelet element method. I. Construction and analysis*, Appl. Comput. Harmon. Anal.**6**(1999), no. 1, 1–52. MR**1664902**, 10.1006/acha.1997.0242**[Dah96]**Wolfgang Dahmen,*Stability of multiscale transformations*, J. Fourier Anal. Appl.**2**(1996), no. 4, 341–361. MR**1395769****[DeV98]**Ronald A. DeVore,*Nonlinear approximation*, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR**1689432**, 10.1017/S0962492900002816**[DL04]**S. Dekel and D. Leviatan,*The Bramble-Hilbert lemma for convex domains*, SIAM J. Math. Anal.**35**(2004), no. 5, 1203–1212. MR**2050198**, 10.1137/S0036141002417589**[DS98]**Wolfgang Dahmen and Reinhold Schneider,*Wavelets with complementary boundary conditions—function spaces on the cube*, Results Math.**34**(1998), no. 3-4, 255–293. MR**1652724**, 10.1007/BF03322055**[DS99a]**Wolfgang Dahmen and Reinhold Schneider,*Composite wavelet bases for operator equations*, Math. Comp.**68**(1999), no. 228, 1533–1567. MR**1648379**, 10.1090/S0025-5718-99-01092-3**[DS99b]**Wolfgang Dahmen and Reinhold Schneider,*Wavelets on manifolds. I. Construction and domain decomposition*, SIAM J. Math. Anal.**31**(1999), no. 1, 184–230. MR**1742299**, 10.1137/S0036141098333451**[DS99c]**Wolfgang Dahmen and Rob Stevenson,*Element-by-element construction of wavelets satisfying stability and moment conditions*, SIAM J. Numer. Anal.**37**(1999), no. 1, 319–352. MR**1742747**, 10.1137/S0036142997330949**[GS05]**T. Gantumur and R.P. Stevenson.

Computation of singular integral operators in wavelet coordinates.*Computing*, 76:77-107, 2006.**[Ste03]**Rob Stevenson,*Adaptive solution of operator equations using wavelet frames*, SIAM J. Numer. Anal.**41**(2003), no. 3, 1074–1100. MR**2005196**, 10.1137/S0036142902407988**[Ste04a]**Rob Stevenson,*On the compressibility operators in wavelet coordinates*, SIAM J. Math. Anal.**35**(2004), no. 5, 1110–1132 (electronic). MR**2050194**, 10.1137/S0036141002411520**[Ste04b]**R.P. Stevenson.

Composite wavelet bases with extended stability and cancellation properties.

Preprint 1304, Department of Mathematics, Utrecht University, 2004. Submitted.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
41A25,
47A20,
65F50,
65N30,
65D30

Retrieve articles in all journals with MSC (2000): 41A25, 47A20, 65F50, 65N30, 65D30

Additional Information

**Tsogtgerel Gantumur**

Affiliation:
Department of Mathematics, Utrecht University, P. O. Box 80.010, NL-3508 TA Utrecht, The Netherlands

Email:
gantumur@math.uu.nl

**Rob Stevenson**

Affiliation:
Department of Mathematics, Utrecht University, P. O. Box 80.010, NL-3508 TA Utrecht, The Netherlands

Email:
stevenson@math.uu.nl

DOI:
http://dx.doi.org/10.1090/S0025-5718-05-01807-7

Keywords:
Wavelets,
matrix compression,
differential operators,
adaptivity,
numerical integration

Received by editor(s):
August 30, 2004

Received by editor(s) in revised form:
February 22, 2005

Published electronically:
December 8, 2005

Additional Notes:
This work was supported by the Netherlands Organization for Scientific Research and by the EC-IHP project “Breaking Complexity”

Article copyright:
© Copyright 2005
American Mathematical Society