Space-time adaptive wavelet methods for parabolic evolution problems

Schwab, Christoph; Stevenson, Rob

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

Space-time adaptive wavelet methods for parabolic evolution problems
HTML articles powered by AMS MathViewer

by Christoph Schwab and Rob Stevenson PDF

Math. Comp. 78 (2009), 1293-1318 Request permission

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

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, DOI 10.1016/j.jcp.2005.10.009
Ivo Babuška, Error-bounds for finite element method, Numer. Math. 16 (1970/71), 322–333. MR 288971, DOI 10.1007/BF02165003
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, DOI 10.1051/m2an/1992260707931
A. Barinka. Fast Evaluation Tools for Adaptive Wavelet Schemes. Ph.D. thesis, RTWH Aachen, March 2005.
Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. MR 2249147, DOI 10.1017/S0962492904000182
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
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, DOI 10.1090/S0025-5718-00-01252-7
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, DOI 10.1007/s102080010027
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. MR 2047083, DOI 10.1090/S0025-5718-04-01634-5
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
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, DOI 10.1093/imanum/drl035
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, DOI 10.1137/S0036141094276160
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, DOI 10.1137/S0036141096313112
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, DOI 10.1016/j.jcp.2007.11.046
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, DOI 10.1006/acha.1998.0247
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, DOI 10.1007/978-3-642-58090-1
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, DOI 10.1007/BF03322055
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, DOI 10.1137/S0036141098333451
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.
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, DOI 10.1137/0728003
Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. II. Optimal error estimates in $L_\infty L_2$ and $L_\infty L_\infty$, SIAM J. Numer. Anal. 32 (1995), no. 3, 706–740. MR 1335652, DOI 10.1137/0732033
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, DOI 10.1051/m2an/1985190406111
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, DOI 10.1016/j.cam.2006.11.013
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, DOI 10.1090/S0025-5718-06-01917-X
Tsogtgerel Gantumur and Rob Stevenson, Computation of differential operators in wavelet coordinates, Math. Comp. 75 (2006), no. 254, 697–709. MR 2196987, DOI 10.1090/S0025-5718-05-01807-7
T. Gantumur and R. P. Stevenson, Computation of singular integral operators in wavelet coordinates, Computing 76 (2006), no. 1-2, 77–107. MR 2174673, DOI 10.1007/s00607-005-0135-1
M. Griebel and S. Knapek, Optimized tensor-product approximation spaces, Constr. Approx. 16 (2000), no. 4, 525–540. MR 1771694, DOI 10.1007/s003650010010
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, DOI 10.1007/BF02123478
M. Griebel and D. Oeltz, A sparse grid space-time discretization scheme for parabolic problems, Computing 81 (2007), no. 1, 1–34. MR 2369419, DOI 10.1007/s00607-007-0241-3
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.
Helmut Harbrecht and Rob Stevenson, Wavelets with patchwise cancellation properties, Math. Comp. 75 (2006), no. 256, 1871–1889. MR 2240639, DOI 10.1090/S0025-5718-06-01867-9
Angela Kunoth and Jan Sahner, Wavelets on manifolds: an optimized construction, Math. Comp. 75 (2006), no. 255, 1319–1349. MR 2219031, DOI 10.1090/S0025-5718-06-01828-X
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, DOI 10.1007/978-3-662-04484-1
A. Metselaar. Handling Wavelet Expansions in Numerical Methods. Ph.D. thesis, University of Twente, 2002.
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, DOI 10.1007/s10915-006-9102-z
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, DOI 10.1090/S0025-5718-1983-0717689-8
Marco Picasso, Adaptive finite elements for a linear parabolic problem, Comput. Methods Appl. Mech. Engrg. 167 (1998), no. 3-4, 223–237. MR 1673951, DOI 10.1016/S0045-7825(98)00121-2
M. Primbs. Stabile biorthogonale Spline-Waveletbasen auf dem Intervall. Ph.D. thesis, Universität Duisburg, 2006.
T. Raasch. Adaptive Wavelet and Frame Schemes for Elliptic and Parabolic Equations. Ph.D. thesis, Philipps-Universität Marburg, 2007.
N. Reich. Wavelet Compression of Anisotropic Integrodifferential Operators on Sparse Grids, Ph.D. Dissertation, ETH Zürich, 2008.
Christoph Schwab and Rob Stevenson, Adaptive wavelet algorithms for elliptic PDE’s on product domains, Math. Comp. 77 (2008), no. 261, 71–92. MR 2353944, DOI 10.1090/S0025-5718-07-02019-4
Rob Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074–1100. MR 2005196, DOI 10.1137/S0036142902407988
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
R. Verfürth. A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques. Wiley-Teubner, Chichester, 1996.
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, DOI 10.1051/m2an:2004005
Joseph Wloka, Partielle Differentialgleichungen, Mathematische Leitfäden. [Mathematical Textbooks], B. G. Teubner, Stuttgart, 1982 (German). Sobolevräume und Randwertaufgaben. [Sobolev spaces and boundary value problems]. MR 652934