Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Adaptive wavelet algorithms for elliptic PDE's on product domains

Authors: Christoph Schwab and Rob Stevenson
Journal: Math. Comp. 77 (2008), 71-92
MSC (2000): Primary 41A25, 41A46, 41A63, 65D32, 65N12, 65T60
Published electronically: May 14, 2007
MathSciNet review: 2353944
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: With standard isotropic approximation by (piecewise) polynomials of fixed order in a domain $ D\subset \mathbb{R}^d$, the convergence rate in terms of the number $ N$ of degrees of freedom is inversely proportional to the space dimension $ d$. This so-called curse of dimensionality can be circumvented by applying sparse tensor product approximation, when certain high order mixed derivatives of the approximated function happen to be bounded in $ L_2$. It was shown by Nitsche (2006) that this regularity constraint can be dramatically reduced by considering best $ N$-term approximation from tensor product wavelet bases. When the function is the solution of some well-posed operator equation, dimension independent approximation rates can be practically realized in linear complexity by adaptive wavelet algorithms, assuming that the infinite stiffness matrix of the operator with respect to such a basis is highly compressible. Applying piecewise smooth wavelets, we verify this compressibility for general, non-separable elliptic PDEs in tensor domains. Applications of the general theory developed include adaptive Galerkin discretizations of multiple scale homogenization problems and of anisotropic equations which are robust, i.e., independent of the scale parameters, resp. of the size of the anisotropy.

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

  • [AB96] G. Allaire and M. Briane.
    Multiscale convergence and reiterated homogenization.
    Proc. Roy. Soc. Edinburgh, 126A:297-342, 1996. MR 1386865 (97d:35014)
  • [All92] G. Allaire.
    Homogenization and two scale convergence.
    SIAM J. Applied Mathematics, 23:1482-1518, 1992. MR 1185639 (93k:35022)
  • [BLP78] A. Bensoussan, J.L. Lions, and G. Papanicolau.
    Asymptotic Analysis for Periodic Structures.
    North-Holland Publishing, Amsterdam, 1978. MR 0503330 (82h:35001)
  • [BSS04] S. Beuchler, R. Schneider, and Ch. Schwab.
    Multiresolution weighted norm equivalences and applications.
    Numer. Math., 98:67-97, 2004. MR 2076054 (2005g:65199)
  • [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)
  • [CDD01] A. Cohen, W. Dahmen, and R. DeVore.
    Adaptive wavelet methods for elliptic operator equations - Convergence rates.
    Math. Comp, 70:27-75, 2001. MR 1803124 (2002h:65201)
  • [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)
  • [Coh03] A. Cohen.
    Numerical Analysis of Wavelet Methods.
    Elsevier, Amsterdam, 2003. MR 1990555 (2004c:65178)
  • [DKU99] W. Dahmen, A. Kunoth, and K. Urban.
    Biorthogonal spline-wavelets on the interval - Stability and moment conditions.
    Appl. Comp. Harm. Anal., 6:132-196, 1999. MR 1676771 (99m:42046)
  • [DS99a] W. Dahmen and R. Schneider.
    Composite wavelet bases for operator equations.
    Math. Comp., 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)
  • [DeV98] R. DeVore.
    Nonlinear approximation.
    Acta Numer., 7:51-150, 1998. MR 1689432 (2001a:41034)
  • [Gan06] T. Gantumur.
    An optimal adaptive wavelet method for nonsymmetric and indefinite elliptic problems.
    Technical Report 1343, Utrecht University, January 2006.
  • [GHS05] T. Gantumur, H. Harbrecht, and R.P. Stevenson.
    An optimal adaptive wavelet method without coarsening of the iterands.
    Technical Report 1325, Utrecht University, March 2005.
    To appear in Math. Comp.
  • [GS04] T. Gantumur and R.P. Stevenson.
    Computation of differential operators in wavelet coordinates.
    Math. Comp., 75:697-709, 2006. MR 2196987
  • [GG98] T. Gerstner and M. Griebel.
    Numerical integration using sparse grids.
    Numer. Algorithms, 18:209-232, 1998. MR 1669959 (99m:65042)
  • [GK00] M. Griebel and S. Knapek.
    Optimized tensor-product approximation spaces.
    Constr. Approx., 16(4):525-540, 2000. MR 1771694 (2001g:41025)
  • [GO95] M. Griebel and P. Oswald.
    Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems.
    Adv. Comput. Math., 4(1-2):171-206, 1995. MR 1338900 (96e:65069)
  • [HS04] H. Harbrecht and R.P. Stevenson.
    Wavelets with patchwise cancellation properties.
    Math. Comp., 75:1871-1889, 2006. MR 2240639
  • [HMS05] N. Hilber, A.M. Matache, and Ch. Schwab.
    Sparse wavelet methods for option pricing under stochastic volatility.
    The Journal of Computational Finance, 8(4):1-42, 2005.
  • [HS05] V.H. Hoang and Ch. Schwab.
    High dimensional finite elements for elliptic problems with multiple scales.
    Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 3:168-194, 2005. MR 2123115 (2005m:65267)
  • [LC85] W. A. Light and E. W. Cheney.
    Approximation theory in tensor product spaces, volume 1169 of Lecture Notes in Mathematics.
    Springer-Verlag, Berlin, 1985. MR 817984 (87g:41064)
  • [Nit06] P. A. Nitsche.
    Best $ N$-term approximation spaces for tensor product wavelet bases.
    Const. Approx., 24(1), 49-70, 2006. MR 2217525 (2007a:41032)
  • [vPS04] T. von Petersdorff and Ch. Schwab.
    Numerical solution of parabolic problems in high dimensions.
    M2AN Mathematical Modelling and Numerical Analysis, 38:93-121, 2004. MR 2073932 (2005d:65169)
  • [vPS06] T. von Petersdorff and Ch. Schwab.
    Sparse finite element methods for operator equations with stochastic data.
    Applications of Mathematics, 45:145-180, 2006. MR 2212311
  • [Pri06] M. Primbs.
    Stabile biorthogonale Spline-Waveletbasen auf dem Intervall.
    Ph.D. thesis, Universität Duisburg, 2006.
  • [Smo63] S.A. Smolyak.
    Quadrature and interpolation formulas for tensor products of certain classes of functions.
    Dokl. Akad. Nauk SSSR, 4:240-243, 1963.
  • [Ste04] R.P. Stevenson.
    Composite wavelet bases with extended stability and cancellation properties.
    SIAM J. Numer. Anal., 45(2):133-162, 2007.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A25, 41A46, 41A63, 65D32, 65N12, 65T60

Retrieve articles in all journals with MSC (2000): 41A25, 41A46, 41A63, 65D32, 65N12, 65T60

Additional Information

Christoph Schwab
Affiliation: Seminar for Applied Mathematics, ETHZ HG G58.1, ETH Zürich, CH 8092 Zürich, Switzerland

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

Keywords: Elliptic PDE's on (high) dimensional product domains, multiple scale homogenization, tensor product approximation, sparse grids, wavelets, best $N$-term approximation, optimal computational complexity, matrix compression
Received by editor(s): May 8, 2006
Received by editor(s) in revised form: December 6, 2006
Published electronically: May 14, 2007
Additional Notes: This work was performed in part in the IHP network “Breaking Complexity” of the EC under contract HPRN-CT-2002-00286 and supported by the Netherlands Organization for Scientific Research and by the Swiss BBW under grant BBW 02.0418
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society