Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Space-time adaptive wavelet methods for parabolic evolution problems

Authors: Christoph Schwab and Rob Stevenson
Journal: Math. Comp. 78 (2009), 1293-1318
MSC (2000): Primary 35K10, 41A25, 46B28, 65N99, 65T60
Published electronically: November 25, 2008
MathSciNet review: 2501051
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: With respect to space-time tensor-product wavelet bases, parabolic initial boundary value problems are equivalently formulated as bi-infinite matrix problems. Adaptive wavelet methods are shown to yield sequences of approximate solutions which converge at the optimal rate. In case the spatial domain is of product type, the use of spatial tensor product wavelet bases is proved to overcome the so-called curse of dimensionality, i.e., the reduction of the convergence rate with increasing spatial dimension.

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

  • [AKV06] J. Alam, N. Kevlahan, and O. Vasilyev.
    Simultaneous space-time adaptive wavelet solution of nonlinear parabolic differential equations.
    J. Comput. Phys., 214(2):829-857, 2006. MR 2216616 (2006k:65242)
  • [Bab71] I. Babuška.
    Error-bounds for finite element method.
    Numer. Math., 16:322-333, 1970/1971. MR 0288971 (44:6166)
  • [BMP92] E. Bacry, S. Mallat, and G. Papanicolaou.
    A wavelet based space-time adaptive numerical method for partial differential equations
    RAIRO Model. Math. Anal. Numer. 26(7): 793-834, 1992. MR 1199314 (94f:65122)
  • [Bar05] A. Barinka.
    Fast Evaluation Tools for Adaptive Wavelet Schemes.
    Ph.D. thesis, RTWH Aachen, March 2005.
  • [BG04] H.J. Bungartz and M. Griebel.
    Sparse grids.
    Acta Numer., 13:147-269, 2004. MR 2249147 (2007e:65102)
  • [Bra01] D. Braess.
    Finite Elements.
    Cambridge University Press, 2001.
    Second edition. MR 1827293 (2001k:65002)
  • [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)
  • [CF04] Z. Chen and J. Feng.
    An adaptive finite element algorithm with reliable and efficient error control for linear parabolic problems.
    Math. Comp., 73(247):1167-1193 (electronic), 2004. MR 2047083 (2005e:65131)
  • [CQ92] Ch. Chui and E. Quak.
    Wavelets on a bounded interval.
    In Numerical methods in approximation theory, Vol. 9 (Oberwolfach, 1991), volume 105 of Internat. Ser. Numer. Math., pages 53-75. Birkhäuser, Basel, 1992. MR 1269355 (95b:42027)
  • [DFR+07] S. Dahlke, M. Fornasier, T. Raasch, R.P. Stevenson, and M. Werner.
    Adaptive frame methods for elliptic operator equations: The steepest descent approach.
    IMA J. Numer. Math., 27(4):717-740, 2007. MR 2371829 (2008i:65239)
  • [DGH96] G.C. Donovan, J.S. Geronimo, and D.P. Hardin.
    Intertwining multiresolution analyses and the construction of piecewise-polynomial wavelets.
    SIAM J. Math. Anal., 27(6):1791-1815, 1996. MR 1416519 (98c:42029)
  • [DGH99] G.C. Donovan, J.S. Geronimo, and D.P. Hardin.
    Orthogonal polynomials and the construction of piecewise polynomial smooth wavelets.
    SIAM J. Math. Anal., 30(5):1029-1056, 1999. MR 1709786 (2000j:41012)
  • [DGR+08] M.O. Domingues, S.M. Gomes, O. Roussel, and K. Schneider.
    An adaptive multiresolution scheme with local time stepping for evolutionary PDEs.
    J. Comp. Phys. 227(8): 3758-3780, 2008. MR 2403866
  • [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)
  • [DL92] R. Dautray and J.-L. Lions.
    Mathematical analysis and numerical methods for science and technology. Vol. 5.
    Springer-Verlag, Berlin, 1992.
    Evolution problems I. MR 1156075 (92k:00006)
  • [DS98] W. Dahmen and R. Schneider.
    Wavelets with complementary boundary conditions--function spaces on the cube.
    Results Math., 34(3-4):255-293, 1998. MR 1652724 (99h:42057)
  • [DS99] 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)
  • [DSS08] T J. Dijkema, Ch. Schwab, and R.P. Stevenson.
    An adaptive wavelet method for solving high-dimensional elliptic PDEs.
    Technical report, January 2008.
    To appear.
  • [EJ91] K. Eriksson and C. Johnson.
    Adaptive finite element methods for parabolic problems. I. A linear model problem.
    SIAM J. Numer. Anal., 28(1):43-77, 1991. MR 1083324 (91m:65274)
  • [EJ95] K. Eriksson and C. Johnson.
    Adaptive finite element methods for parabolic problems. II. Optimal error estimates in $ L\sb \infty L\sb 2$ and $ L\sb \infty L\sb \infty$.
    SIAM J. Numer. Anal., 32(3):706-740, 1995. MR 1335652 (96c:65162)
  • [EJT85] K. Eriksson, C. Johnson, and V. Thomée.
    Time discretization of parabolic problems by the discontinuous Galerkin method.
    RAIRO Modél. Math. Anal. Numér., 19(4):611-643, 1985. MR 826227 (87e:65073)
  • [Gan08] T. Gantumur.
    An optimal adaptive wavelet method for nonsymmetric and indefinite elliptic problems.
    J. Comput. Appl. Math., 211(1), 90-102, 2008. MR 2386831
  • [GHS07] T. Gantumur, H. Harbrecht, and R.P. Stevenson.
    An optimal adaptive wavelet method without coarsening of the iterands.
    Math. Comp., 77:615-629, 2007. MR 2291830 (2008i:65310)
  • [GS06a] T. Gantumur and R.P. Stevenson.
    Computation of differential operators in wavelet coordinates.
    Math. Comp., 75:697-709, 2006. MR 2196987 (2007h:65162)
  • [GS06b] T. Gantumur and R.P. Stevenson.
    Computation of singular integral operators in wavelet coordinates.
    Computing, 76:77-107, 2006. MR 2174673 (2006e:65051)
  • [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)
  • [GO07] M. Griebel and D. Oeltz.
    A Sparse Grid Space-Time Discretization Scheme for Parabolic Problems.
    Computing, 2007. MR 2369419
  • [Goo00] T.N.T. Goodman.
    Biorthogonal refinable spline functions.
    In A. Cohen, C. Rabut, and L.L. Schumaker, editors, Curve and Surface Fitting: Saint-Malo 1999, pages 1-8, Nashville, TN, 2000. Vanderbilt University Press.
  • [HS06] H. Harbrecht and R.P. Stevenson.
    Wavelets with patchwise cancellation properties.
    Math. Comp., 75(256):1871-1889, 2006. MR 2240639 (2007e:42042)
  • [KS06] A. Kunoth and J. Sahner.
    Wavelets on manifolds: An optimized construction.
    Math. Comp., 75:1319-1349, 2006. MR 2219031 (2007d:42076)
  • [Lan01] J. Lang.
    Adaptive multilevel solution of nonlinear parabolic PDE systems, volume 16 of Lecture Notes in Computational Science and Engineering.
    Springer-Verlag, Berlin, 2001.
    Theory, algorithm, and applications. MR 1801795 (2001i:65106)
  • [Met02] A. Metselaar.
    Handling Wavelet Expansions in Numerical Methods.
    Ph.D. thesis, University of Twente, 2002.
  • [MS07] S. Müller and Y. Stiriba.
    Fully adaptive multiscale schemes for conservation laws employing locally varying time stepping.
    J. Sci. Comput. 30: 493-531, 2007. MR 2295481 (2008d:65103)
  • [OS83] S. Osher and R. Sanders.
    Numerical approximations to nonlinear conservation laws with locally varying time and space grids.
    Math. Comp., 41: 321-336, 1983. MR 717689 (85i:65121)
  • [Pic98] M. Picasso.
    Adaptive finite elements for a linear parabolic problem.
    Comput. Methods Appl. Mech. Engrg., 167(3-4):223-237, 1998. MR 1673951 (2000b:65188)
  • [Pri06] M. Primbs.
    Stabile biorthogonale Spline-Waveletbasen auf dem Intervall.
    Ph.D. thesis, Universität Duisburg, 2006.
  • [Raa07] T. Raasch.
    Adaptive Wavelet and Frame Schemes for Elliptic and Parabolic Equations.
    Ph.D. thesis, Philipps-Universität Marburg, 2007.
  • [Rei08] N. Reich.
    Wavelet Compression of Anisotropic Integrodifferential Operators on Sparse Grids,
    Ph.D. Dissertation, ETH Zürich, 2008.
  • [SS08] Ch. Schwab and R.P. Stevenson.
    Adaptive wavelet algorithms for elliptic PDEs on product domains.
    Math. Comp., 77:71-92, 2008. MR 2353944
  • [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)
  • [Tho06] V. Thomée.
    Galerkin finite element methods for parabolic problems, volume 25 of Springer Series in Computational Mathematics.
    Springer-Verlag, Berlin, second edition, 2006. MR 2249024 (2007b:65003)
  • [Ver96] R. Verfürth.
    A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques.
    Wiley-Teubner, Chichester, 1996.
  • [vPS04] T. von Petersdorff and Ch. Schwab.
    Numerical solution of parabolic equations in high dimensions.
    M2AN Math. Model. Numer. Anal., 38(1):93-127, 2004. MR 2073932 (2005d:65169)
  • [Wlo82] J. Wloka.
    Partielle Differentialgleichungen.
    B.G. Teubner, Stuttgart, 1982.
    Sobolevräume und Randwertaufgaben. MR 652934 (84a:35002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 35K10, 41A25, 46B28, 65N99, 65T60

Retrieve articles in all journals with MSC (2000): 35K10, 41A25, 46B28, 65N99, 65T60

Additional Information

Christoph Schwab
Affiliation: Department of Mathematics, ETH Zürich, ETH Zentrum, HG G58.1, CH 8092 Zürich, Switzerland

Rob Stevenson
Affiliation: Korteweg-de Vries Institute for Mathematics, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands

Keywords: Parabolic differential equations, wavelets, adaptivity, optimal computational complexity, best $N$-term approximation, matrix compression
Received by editor(s): January 3, 2008
Received by editor(s) in revised form: July 23, 2008
Published electronically: November 25, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society