Space-time adaptive wavelet methods for parabolic evolution problems. (English) Zbl 1198.65249
Summary: 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.
MSC:
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
| 65T60 | Numerical methods for wavelets |
| 35K10 | Second-order parabolic equations |
| 41A25 | Rate of convergence, degree of approximation |
| 46B28 | Spaces of operators; tensor products; approximation properties |
Keywords:
parabolic differential equations; wavelets; adaptivity; optimal computational complexity; best \(N\)-term approximation; matrix compressionReferences:
| [1] | 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. · Zbl 1089.65103 · doi:10.1016/j.jcp.2005.10.009 |
| [2] | Ivo Babuška, Error-bounds for finite element method, Numer. Math. 16 (1970/1971), 322 – 333. · Zbl 0214.42001 · doi:10.1007/BF02165003 |
| [3] | 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). · Zbl 0768.65062 |
| [4] | A. Barinka. Fast Evaluation Tools for Adaptive Wavelet Schemes. Ph.D. thesis, RTWH Aachen, March 2005. |
| [5] | Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147 – 269. · Zbl 1118.65388 · doi:10.1017/S0962492904000182 |
| [6] | 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. · Zbl 0754.65084 |
| [7] | Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27 – 75. · Zbl 0980.65130 |
| [8] | A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203 – 245. · Zbl 1025.65056 · doi:10.1007/s102080010027 |
| [9] | 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. · Zbl 1052.65091 |
| [10] | 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. · Zbl 0815.42016 |
| [11] | 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. · Zbl 1153.65050 · doi:10.1093/imanum/drl035 |
| [12] | 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. · Zbl 0857.42023 · doi:10.1137/S0036141094276160 |
| [13] | 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. · Zbl 0932.42021 · doi:10.1137/S0036141096313112 |
| [14] | 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. · Zbl 1139.65060 · doi:10.1016/j.jcp.2007.11.046 |
| [15] | 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. · Zbl 0922.42021 · doi:10.1006/acha.1998.0247 |
| [16] | 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. · Zbl 0755.35001 |
| [17] | Wolfgang Dahmen and Reinhold Schneider, Wavelets with complementary boundary conditions — function spaces on the cube, Results Math. 34 (1998), no. 3-4, 255 – 293. · Zbl 0931.46006 · doi:10.1007/BF03322055 |
| [18] | Wolfgang Dahmen and Reinhold Schneider, Wavelets on manifolds. I. Construction and domain decomposition, SIAM J. Math. Anal. 31 (1999), no. 1, 184 – 230. · Zbl 0955.42025 · doi:10.1137/S0036141098333451 |
| [19] | 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. · Zbl 1205.65313 |
| [20] | 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. · Zbl 0732.65093 · doi:10.1137/0728003 |
| [21] | Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. II. Optimal error estimates in \?_{\infty }\?\(_{2}\) and \?_{\infty }\?_{\infty }, SIAM J. Numer. Anal. 32 (1995), no. 3, 706 – 740. · Zbl 0830.65094 · doi:10.1137/0732033 |
| [22] | 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). · Zbl 0589.65070 |
| [23] | Tsogtgerel Gantumur, An optimal adaptive wavelet method for nonsymmetric and indefinite elliptic problems, J. Comput. Appl. Math. 211 (2008), no. 1, 90 – 102. · Zbl 1193.65199 · doi:10.1016/j.cam.2006.11.013 |
| [24] | 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. · Zbl 1115.41023 |
| [25] | Tsogtgerel Gantumur and Rob Stevenson, Computation of differential operators in wavelet coordinates, Math. Comp. 75 (2006), no. 254, 697 – 709. · Zbl 1158.65355 |
| [26] | T. Gantumur and R. P. Stevenson, Computation of singular integral operators in wavelet coordinates, Computing 76 (2006), no. 1-2, 77 – 107. · Zbl 1087.65120 · doi:10.1007/s00607-005-0135-1 |
| [27] | M. Griebel and S. Knapek, Optimized tensor-product approximation spaces, Constr. Approx. 16 (2000), no. 4, 525 – 540. · Zbl 0969.65107 · doi:10.1007/s003650010010 |
| [28] | 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. · Zbl 0826.65099 · doi:10.1007/BF02123478 |
| [29] | M. Griebel and D. Oeltz, A sparse grid space-time discretization scheme for parabolic problems, Computing 81 (2007), no. 1, 1 – 34. · Zbl 1132.35387 · doi:10.1007/s00607-007-0241-3 |
| [30] | 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. |
| [31] | Helmut Harbrecht and Rob Stevenson, Wavelets with patchwise cancellation properties, Math. Comp. 75 (2006), no. 256, 1871 – 1889. · Zbl 1112.46012 |
| [32] | Angela Kunoth and Jan Sahner, Wavelets on manifolds: an optimized construction, Math. Comp. 75 (2006), no. 255, 1319 – 1349. · Zbl 1113.65127 |
| [33] | 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. · Zbl 0963.65102 |
| [34] | A. Metselaar. Handling Wavelet Expansions in Numerical Methods. Ph.D. thesis, University of Twente, 2002. |
| [35] | 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. · Zbl 1110.76037 · doi:10.1007/s10915-006-9102-z |
| [36] | 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. · Zbl 0592.65068 |
| [37] | Marco Picasso, Adaptive finite elements for a linear parabolic problem, Comput. Methods Appl. Mech. Engrg. 167 (1998), no. 3-4, 223 – 237. · Zbl 0935.65105 · doi:10.1016/S0045-7825(98)00121-2 |
| [38] | M. Primbs. Stabile biorthogonale Spline-Waveletbasen auf dem Intervall. Ph.D. thesis, Universität Duisburg, 2006. · Zbl 1196.65015 |
| [39] | T. Raasch. Adaptive Wavelet and Frame Schemes for Elliptic and Parabolic Equations. Ph.D. thesis, Philipps-Universität Marburg, 2007. · Zbl 1189.65008 |
| [40] | N. Reich. Wavelet Compression of Anisotropic Integrodifferential Operators on Sparse Grids, Ph.D. Dissertation, ETH Zürich, 2008. |
| [41] | Christoph Schwab and Rob Stevenson, Adaptive wavelet algorithms for elliptic PDE’s on product domains, Math. Comp. 77 (2008), no. 261, 71 – 92. · Zbl 1127.41009 |
| [42] | Rob Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074 – 1100. · Zbl 1057.41010 · doi:10.1137/S0036142902407988 |
| [43] | Vidar Thomée, Galerkin finite element methods for parabolic problems, 2nd ed., Springer Series in Computational Mathematics, vol. 25, Springer-Verlag, Berlin, 2006. · Zbl 1105.65102 |
| [44] | R. Verfürth. A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques. Wiley-Teubner, Chichester, 1996. · Zbl 0853.65108 |
| [45] | 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. · Zbl 1083.65095 · doi:10.1051/m2an:2004005 |
| [46] | 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]. · Zbl 0482.35001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
