Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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 $ N$ terms are $ \mathcal{O}(N^{-s})$ for some $ s>0$, 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 $ N$ terms also have errors of $ \mathcal{O}(N^{-s})$. Moreover, their computation takes only $ \mathcal{O}(N)$ operations, provided $ s<s^*$, with $ s^*$ 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 $ s$, in [SIAM J. Math. Anal., 35(5) (2004), pp. 1110-1132] we showed that $ s^{\ast}>s$, 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 $ {\mathcal O}(1)$. As a consequence, we can conclude that the adaptive wavelet algorithm has optimal computational complexity.

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

  • [Bur98] V. I. Burenkov,
    Sobolev spaces on domains.
    Teubner Verlag, Stuttgart, Leipzig, 1998. MR 1622690 (99g:46040)
  • [CDD02] A. Cohen, W. Dahmen and R. DeVore.
    Adaptive wavelet methods II - Beyond the elliptic case.
    Found. Comput. Math., 2(3):203-245, 2002. MR 1907380 (2003f:65212)
  • [Coh00] A. Cohen.
    Wavelet methods in numerical analysis.
    in P.G. Ciarlet and J.L. Lions (eds.), Handbook of numerical analysis. Vol. VII, pp.417-711, North-Holland, Amsterdam, 2000. MR 1804747 (2002c:65252)
  • [CM00] A. Cohen and R. Masson.
    Wavelet adaptive method for second order elliptic problems: Boundary conditions and domain decomposition.
    Numer. Math., 86:193-238, 2000.MR 1777487 (2001j:65185)
  • [CTU99] C. Canuto, A. Tabacco and K. Urban.
    The wavelet element method part I: Construction and analysis.
    Appl. Comput. Harmon. Anal., 6:1-52, 1999. MR 1664902 (99k:42055)
  • [Dah96] W. Dahmen.
    Stability of multiscale transformations.
    J. Four. Anal. Appl., 4:341-362, 1996. MR 1395769 (97i:46133)
  • [DeV98] R. DeVore.
    Nonlinear approximation.
    Acta Numer., 7:51-150, 1998. MR 1689432 (2001a:41034)
  • [DL04] S. Dekel and D. Leviatan.
    The Bramble-Hilbert lemma for convex domains.
    SIAM J. Numer. Anal., 35(5):1203-1212, 2004. MR 2050198 (2005d:41010)
  • [DS98] W. Dahmen and R. Schneider.
    Wavelets with complementary boundary conditions - Function spaces on the cube.
    Results in Math., 34:255-293, 1998. MR 1652724 (99h:42057)
  • [DS99a] W. Dahmen and R. Schneider.
    Composite wavelet bases for operator equations.
    Math. Comput., 68:1533-1567, 1999. MR 1648379 (99m:65122)
  • [DS99b] W. Dahmen and R. Schneider.
    Wavelets on manifolds I: Construction and domain decomposition.
    SIAM J. Math. Anal., 31:184-230, 1999. MR 1742299 (2000k:65242)
  • [DS99c] W. Dahmen and R.P. Stevenson.
    Element-by-element construction of wavelets satisfying stability and moment conditions.
    SIAM J. Numer. Anal., 37(1):319-352, 1999. MR 1742747 (2001c:65144)
  • [GS05] T. Gantumur and R.P. Stevenson.
    Computation of singular integral operators in wavelet coordinates.
    Computing, 76:77-107, 2006.
  • [Ste03] R.P. Stevenson.
    Adaptive solution of operator equations using wavelet frames.
    SIAM J. Numer. Anal., 41(3):1074-1100, 2003. MR 2005196 (2004e:42062)
  • [Ste04a] R.P. Stevenson.
    On the compressibility of operators in wavelet coordinates.
    SIAM J. Math. Anal., 35(5):1110-1132, 2004. MR 2050194 (2005e:42128)
  • [Ste04b] R.P. Stevenson.
    Composite wavelet bases with extended stability and cancellation properties.
    Preprint 1304, Department of Mathematics, Utrecht University, 2004. Submitted.

Similar Articles

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

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

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

American Mathematical Society