{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:39Z","timestamp":1787337219274,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>In this article we introduce approximation spaces, especially suited for the approximation of solutions of parabolic problems, which are based on the tensor product construction of a multiscale basis in space and a multiscale basis in time. Proper truncation then leads to so-called space-time sparse grid spaces. For a uniform discretization of the spatial space of dimension d with O(Nd) degrees of freedom, these spaces involve for d &gt; 1 also only O(Nd) degrees of freedom for the discretization of the whole space-time problem. But they provide the same approximation rate as classical space-time finite element spaces which need O(Nd+1) degrees of freedoms. This makes these approximation spaces well suited for conventional parabolic and time-dependent optimization problems. We analyze the approximation properties and the dimension of these sparse grid space-time spaces for general stable multiscale bases. We then restrict ourselves to an interpolatory multiscale basis, i.e., a hierarchical basis. Here, to be able to handle also complicated spatial domains Omega, we construct the hierarchical basis from a given spatial finite element basis as follows: First we determine coarse grid points recursively over the levels by the coarsening step of the algebraic multigrid method. Then, we derive interpolatory prolongation operators between the respective coarse and fine grid points by a least squares approach. This way we obtain an algebraic hierarchical basis for the spatial domain which we then use in our space-time sparse grid approach. We give numerical results on the convergence rate of the interpolation error of these spaces for various space-time problems with two spatial dimensions. Implementational issues, data structures, and questions of adaptivity also are addressed to some extent.<\/jats:p>","DOI":"10.1137\/050629252","type":"journal-article","created":{"date-parts":[[2008,2,6]],"date-time":"2008-02-06T16:45:19Z","timestamp":1202316319000},"page":"701-727","source":"Crossref","is-referenced-by-count":14,"title":["Space-Time Approximation with Sparse Grids"],"prefix":"10.1137","volume":"28","author":[{"given":"Michael","family":"Griebel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Oeltz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panayot","family":"Vassilevski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0715049"},{"key":"R2","unstructured":"R. Balder,\n                      Adaptive Verfahren f\u00fcr elliptische und parabolische Differentialgleichungen\n                      , Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen, Munich, Germany, 1994."},{"key":"R3","unstructured":"D. Braess,\n                      Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics\n                      , Cambridge University Press, Cambridge, UK, 2001."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90095-0"},{"key":"R5","unstructured":"A. Brandt, S. F. McCormick, and J. W. Ruge,\n                      Algebraic Multigrid for Automatic Multigrid Solutions with Application to Geodetic Computations\n                      , Technical report, Institute for Computational Studies, Fort Collins, CO, 1982."},{"key":"R6","unstructured":"A. Brandt, S. F. McCormick, and J. W. Ruge,\n                      Algebraic multigrid for sparse matrix equations\n                      , in Sparsity and Its Applications, D. J. Evans, ed., Cambridge University Press, Cambridge, UK, 1984."},{"key":"R7","unstructured":"H.\u2010J. Bungartz,\n                      D\u00fcnne Gitter und deren Anwendung bei der adaptiven L\u00f6sung der drei\u2010 dimensionalen Poisson\u2010Gleichung\n                      , Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen, Munich, Germany, 1992."},{"key":"R8","unstructured":"H.\u2010J. Bungartz,\n                      Finite Elements of Higher Order on Sparse Grids\n                      , Shaker Verlag, Aachen, Germany, 1998."},{"key":"R9","unstructured":"H.\u2010J. Bungartz, T. Dornseifer, and C. Zenger,\n                      Tensor product approximation spaces for the efficient numerical solution of partial differential equations\n                      , in Proceedings of the International Workshop on Scientific Computations, Konya, Turkey, 1996, Nova Science Publishers, Hauppauge, NY, 1997."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0499"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492904000182"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(92)90120-D"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719208"},{"key":"R14","volume-title":"Numerical analysis of wavelet methods","author":"Cohen Albert","year":"2003"},{"key":"R15","unstructured":"A. Cohen, L. M. Echeverry, and Q. Sun,\n                      Finite element wavelets\n                      , Technical report, Laboratoire d\u2019Analyse Num\u00e9rique, Universit\u00e9 Pierre et Marie Curie, Paris, 2000."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Stephan Dahlke, Wolfgang Dahmen, Ronald DeVore, Nonlinear approximation and adaptive techniques for solving elliptic operator equations, Wavelet Anal. Appl., Vol. 6, Academic Press, San Diego, CA, 1997, 237\u201328399a:65001","DOI":"10.1016\/S1874-608X(97)80008-8"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(96)00060-8"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta Numer., Vol. 6, Cambridge Univ. Press, Cambridge, 1997, 55\u201322898m:65102","DOI":"10.1017\/S0962492900002713"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142997330949"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160410705"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01450912"},{"key":"R22","unstructured":"T. Gerstner,\n                      Adaptive hierarchical methods for landscape representation and analysis\n                      , in Process Modelling and Landform Evolution, Lecture Notes in Earth Sci. 78, Springer\u2010Verlag, 1999."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019129717644"},{"key":"R24","unstructured":"G. H. Gonnet and R. Baeza\u2010Yates,\n                      Handbook of Algorithmsand Data Structures\n                      , 2nd ed., Addison\u2013Wesley, Reading, MA, 1991."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(96)00062-1"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684411"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/s003650010010"},{"key":"R28","unstructured":"M. Griebel and D. Oeltz,\n                      A sparse grid space\u2010time discretization scheme for parabolic problems\n                      , to be submitted."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02123478"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050450"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1080\/10556789208805505"},{"key":"R32","volume-title":"Perspectives in flow control and optimization","author":"Gunzburger Max","year":"2003"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011417305739"},{"key":"R34","unstructured":"F. Koster,\n                      Multiskalen\u2010basierte Finite\u2010Differenzen\u2010Verfahren auf adaptiven d\u00fcnnen Gittern\n                      , Ph.D. thesis, Rheinische Friedrich\u2010Hilhelms\u2010Universit\u00e4t, Bonn, Germany, 2002."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/s002110100282"},{"key":"R36","unstructured":"O. A. Ladyzenskaja, V. A. Solonnikov, and N. N. Ural\u2019ceva,\n                      Linear and Quasilinear Equations of Parabolic Type\n                      , Trans. Math. Monogr. 23, American Mathematical Society, Providence, RI, 1988."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-86786-5"},{"key":"R38","unstructured":"J. Ruge, K. St\u00fcben, Efficient solution of finite difference and finite element equations, Inst. Math. Appl. Conf. Ser. New Ser., Vol. 3, Oxford Univ. Press, New York, 1985, 169\u201321287i:65047"},{"key":"R39","unstructured":"T. Schiekofer,\n                      Die Methode der Finiten Differenzen auf D\u00fcnnen Gittern\n                      , Ph.D. thesis, Rheinische Friedrich\u2010Hilhelms\u2010Universit\u00e4t, Bonn, Germany, 1998."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"P. Schr\u00f6der and W. Sweldens, Spherical wavelets: Efficiently representing functions on the sphere, in Computer Graphics Proceedings (SIGGRAPH 95), 1995, pp. 161\u2013172.","DOI":"10.1145\/218380.218439"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-003-0545-2"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/S0036141095289051"},{"key":"R43","unstructured":"Alexander Andrianov, Nonlinear Haar approximation of functions with bounded mixed derivative, Lecture Notes in Pure and Appl. Math., Vol. 212, Dekker, New York, 2000, 27\u2013472001j:42027"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1004"},{"key":"R45","volume-title":"Multigrid","author":"Trottenberg U.","year":"2001"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238511"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/040618205"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389538"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"Harry Yserentant, Hierarchical bases in the numerical solution of parabolic problems, Progr. Sci. Comput., Vol. 7, Birkh\u00e4user Boston, Boston, MA, 1987, 22\u20133688i:65140","DOI":"10.1007\/978-1-4684-6754-3_2"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050629252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:16Z","timestamp":1787334616000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050629252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/050629252"],"URL":"https:\/\/doi.org\/10.1137\/050629252","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}