Space-time adaptive wavelet methods for parabolic evolution problems

Schwab, Christoph; Stevenson, Rob

doi:10.1090/S0025-5718-08-02205-9

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: 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.

[AKV06] Jahrul M. Alam, Nicholas K.-R. Kevlahan, and Oleg V. Vasilyev, Simultaneous space-time adaptive wavelet solution of nonlinear parabolic differential equations, J. Comput. Phys. 214 (2006), no. 2, 829–857. MR 2216616 (2006k:65242), http://dx.doi.org/10.1016/j.jcp.2005.10.009
[Bab71] Ivo Babuška, Error-bounds for finite element method, Numer. Math. 16 (1970/1971), 322–333. 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 Modél. Math. Anal. Numér. 26 (1992), no. 7, 793–834 (English, with English and French summaries). MR 1199314 (94f:65122)
[Bar05] A. Barinka.
Fast Evaluation Tools for Adaptive Wavelet Schemes.
Ph.D. thesis, RTWH Aachen, March 2005.
[BG04] Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. MR 2249147 (2007e:65102), http://dx.doi.org/10.1017/S0962492904000182
[Bra01] Dietrich Braess, Finite elements, 2nd ed., Cambridge University Press, Cambridge, 2001. Theory, fast solvers, and applications in solid mechanics; Translated from the 1992 German edition by Larry L. Schumaker. MR 1827293 (2001k:65002)
[CDD01] Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27–75. MR 1803124 (2002h:65201), http://dx.doi.org/10.1090/S0025-5718-00-01252-7
[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 (2003f:65212), http://dx.doi.org/10.1007/s102080010027
[CF04] Zhiming Chen and Jia Feng, An adaptive finite element algorithm with reliable and efficient error control for linear parabolic problems, Math. Comp. 73 (2004), no. 247, 1167–1193 (electronic). MR 2047083 (2005e:65131), http://dx.doi.org/10.1090/S0025-5718-04-01634-5
[CQ92] Charles K. Chui and Ewald Quak, Wavelets on a bounded interval, Numerical methods in approximation theory, Vol. 9 (Oberwolfach, 1991), Internat. Ser. Numer. Math., vol. 105, Birkhäuser, Basel, 1992, pp. 53–75. MR 1269355 (95b:42027)
[DFR+07] Stephan Dahlke, Thorsten Raasch, Manuel Werner, Massimo Fornasier, and Rob Stevenson, Adaptive frame methods for elliptic operator equations: the steepest descent approach, IMA J. Numer. Anal. 27 (2007), no. 4, 717–740. MR 2371829 (2008i:65239), http://dx.doi.org/10.1093/imanum/drl035
[DGH96] George C. Donovan, Jeffrey S. Geronimo, and Douglas P. Hardin, Intertwining multiresolution analyses and the construction of piecewise-polynomial wavelets, SIAM J. Math. Anal. 27 (1996), no. 6, 1791–1815. MR 1416519 (98c:42029), http://dx.doi.org/10.1137/S0036141094276160
[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 (1999), no. 5, 1029–1056. MR 1709786 (2000j:41012), http://dx.doi.org/10.1137/S0036141096313112
[DGR+08] Margarete O. Domingues, Sônia M. Gomes, Olivier Roussel, and Kai Schneider, An adaptive multiresolution scheme with local time stepping for evolutionary PDEs, J. Comput. Phys. 227 (2008), no. 8, 3758–3780. MR 2403866 (2009b:65204), http://dx.doi.org/10.1016/j.jcp.2007.11.046
[DKU99] Wolfgang Dahmen, Angela Kunoth, and Karsten Urban, Biorthogonal spline wavelets on the interval—stability and moment conditions, Appl. Comput. Harmon. Anal. 6 (1999), no. 2, 132–196. MR 1676771 (99m:42046), http://dx.doi.org/10.1006/acha.1998.0247
[DL92] Robert Dautray and Jacques-Louis Lions, Mathematical analysis and numerical methods for science and technology. Vol. 5, Springer-Verlag, Berlin, 1992. Evolution problems. I; With the collaboration of Michel Artola, Michel Cessenat and Hélène Lanchon; Translated from the French by Alan Craig. MR 1156075 (92k:00006)
[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 (99h:42057)
[DS99] 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 (2000k:65242), http://dx.doi.org/10.1137/S0036141098333451
[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] Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. I. A linear model problem, SIAM J. Numer. Anal. 28 (1991), no. 1, 43–77. MR 1083324 (91m:65274), http://dx.doi.org/10.1137/0728003
[EJ95] Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. II. Optimal error estimates in 𝐿_{∞}𝐿₂ and 𝐿_{∞}𝐿_{∞}, SIAM J. Numer. Anal. 32 (1995), no. 3, 706–740. MR 1335652 (96c:65162), http://dx.doi.org/10.1137/0732033
[EJT85] Kenneth Eriksson, Claes Johnson, and Vidar Thomée, Time discretization of parabolic problems by the discontinuous Galerkin method, RAIRO Modél. Math. Anal. Numér. 19 (1985), no. 4, 611–643 (English, with French summary). MR 826227 (87e:65073)
[Gan08] Tsogtgerel Gantumur, An optimal adaptive wavelet method for nonsymmetric and indefinite elliptic problems, J. Comput. Appl. Math. 211 (2008), no. 1, 90–102. MR 2386831 (2008m:65317), http://dx.doi.org/10.1016/j.cam.2006.11.013
[GHS07] Tsogtgerel Gantumur, Helmut Harbrecht, and Rob Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Math. Comp. 76 (2007), no. 258, 615–629. MR 2291830 (2008i:65310), http://dx.doi.org/10.1090/S0025-5718-06-01917-X
[GS06a] Tsogtgerel Gantumur and Rob Stevenson, Computation of differential operators in wavelet coordinates, Math. Comp. 75 (2006), no. 254, 697–709. MR 2196987 (2007h:65162), http://dx.doi.org/10.1090/S0025-5718-05-01807-7
[GS06b] T. Gantumur and R. P. Stevenson, Computation of singular integral operators in wavelet coordinates, Computing 76 (2006), no. 1-2, 77–107. MR 2174673 (2006e:65051), http://dx.doi.org/10.1007/s00607-005-0135-1
[GK00] M. Griebel and S. Knapek, Optimized tensor-product approximation spaces, Constr. Approx. 16 (2000), no. 4, 525–540. MR 1771694 (2001g:41025), http://dx.doi.org/10.1007/s003650010010
[GO95] M. Griebel and P. Oswald, Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Adv. Comput. Math. 4 (1995), no. 1-2, 171–206. MR 1338900 (96e:65069), http://dx.doi.org/10.1007/BF02123478
[GO07] M. Griebel and D. Oeltz, A sparse grid space-time discretization scheme for parabolic problems, Computing 81 (2007), no. 1, 1–34. MR 2369419 (2009b:65252), http://dx.doi.org/10.1007/s00607-007-0241-3
[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] Helmut Harbrecht and Rob Stevenson, Wavelets with patchwise cancellation properties, Math. Comp. 75 (2006), no. 256, 1871–1889 (electronic). MR 2240639 (2007e:42042), http://dx.doi.org/10.1090/S0025-5718-06-01867-9
[KS06] Angela Kunoth and Jan Sahner, Wavelets on manifolds: an optimized construction, Math. Comp. 75 (2006), no. 255, 1319–1349 (electronic). MR 2219031 (2007d:42076), http://dx.doi.org/10.1090/S0025-5718-06-01828-X
[Lan01] Jens Lang, Adaptive multilevel solution of nonlinear parabolic PDE systems, Lecture Notes in Computational Science and Engineering, vol. 16, 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] Siegfried Müller and Youssef Stiriba, Fully adaptive multiscale schemes for conservation laws employing locally varying time stepping, J. Sci. Comput. 30 (2007), no. 3, 493–531. MR 2295481 (2008d:65103), http://dx.doi.org/10.1007/s10915-006-9102-z
[OS83] Stanley Osher and Richard Sanders, Numerical approximations to nonlinear conservation laws with locally varying time and space grids, Math. Comp. 41 (1983), no. 164, 321–336. MR 717689 (85i:65121), http://dx.doi.org/10.1090/S0025-5718-1983-0717689-8
[Pic98] Marco Picasso, Adaptive finite elements for a linear parabolic problem, Comput. Methods Appl. Mech. Engrg. 167 (1998), no. 3-4, 223–237. MR 1673951 (2000b:65188), http://dx.doi.org/10.1016/S0045-7825(98)00121-2
[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] Christoph Schwab and Rob Stevenson, Adaptive wavelet algorithms for elliptic PDE’s on product domains, Math. Comp. 77 (2008), no. 261, 71–92 (electronic). MR 2353944 (2009a:41024), http://dx.doi.org/10.1090/S0025-5718-07-02019-4
[Ste03] Rob Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074–1100. MR 2005196 (2004e:42062), http://dx.doi.org/10.1137/S0036142902407988
[Tho06] Vidar Thomée, Galerkin finite element methods for parabolic problems, 2nd ed., Springer Series in Computational Mathematics, vol. 25, Springer-Verlag, Berlin, 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] Tobias von Petersdorff and Christoph Schwab, Numerical solution of parabolic equations in high dimensions, M2AN Math. Model. Numer. Anal. 38 (2004), no. 1, 93–127. MR 2073932 (2005d:65169), http://dx.doi.org/10.1051/m2an:2004005
[Wlo82] Joseph Wloka, Partielle Differentialgleichungen, B. G. Teubner, Stuttgart, 1982 (German). Sobolevräume und Randwertaufgaben. [Sobolev spaces and boundary value problems]; Mathematische Leitfäden. [Mathematical Textbooks]. MR 652934 (84a:35002)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|