This paper is concerned with the construction of optimized sparse grid approximation spaces for elliptic pseudodifferential operators of arbitrary order. Based on the framework of tensor-product biorthogonal wavelet bases and stable subspace splittings, we construct operator-adapted subspaces with a dimension smaller than that of the standard full grid spaces but which have the same approximation order as the standard full grid spaces, provided that certain additional regularity assumptions on the solution are fulfilled. Specifically for operators of positive order, their dimension isO<\/mml:mi>(<\/mml:mo>2<\/mml:mn>J<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow>O(2^{J})<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>independent of the dimensionn<\/mml:mi>n<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>of the problem, compared toO<\/mml:mi>(<\/mml:mo>2<\/mml:mn>J<\/mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow>O(2^{Jn})<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>for the full grid space. Also, for operators of negative order the overall cost is significantly in favor of the new approximation spaces. We give cost estimates for the case of continuous linear information. We show these results in a constructive manner by proposing a Galerkin method together with optimal preconditioning. The theory covers elliptic boundary value problems as well as boundary integral equations.<\/p>","DOI":"10.1090\/s0025-5718-09-02248-0","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T14:39:02Z","timestamp":1246372742000},"page":"2223-2257","source":"Crossref","is-referenced-by-count":50,"title":["Optimized general sparse grid approximation spaces for operator equations"],"prefix":"10.1090","volume":"78","author":[{"given":"M.","family":"Griebel","sequence":"first","affiliation":[]},{"given":"S.","family":"Knapek","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"1","series-title":"Pure and Applied Mathematics, Vol. 65","volume-title":"Sobolev spaces","author":"Adams, Robert A.","year":"1975"},{"key":"2","first-page":"217","article-title":"Wavelets with boundary conditions on the interval","author":"Auscher, Pascal","year":"1992"},{"key":"3","unstructured":"H.-J. Bungartz, D\u00fcnne Gitter und deren Anwendung bei der adaptiven L\u00f6sung der dreidimensionalen Poisson-Gleichung, Dissertation, TU M\u00fcnchen, Institut f\u00fcr Informatik, 1992."},{"key":"4","unstructured":"H.-J. Bungartz, Finite elements of higher order on sparse grids, Habilitation, TU M\u00fcnchen, Institut f\u00fcr Informatik, 1998."},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/jcom.1999.0499","article-title":"A note on the complexity of solving Poisson\u2019s equation for spaces of bounded mixed derivatives","volume":"15","author":"Bungartz, Hans-Joachim","year":"1999","journal-title":"J. Complexity","ISSN":"http:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","article-title":"Sparse grids","volume":"13","author":"Bungartz, Hans-Joachim","year":"2004","journal-title":"Acta Numer.","ISSN":"http:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"903","DOI":"10.2307\/2153941","article-title":"On compactly supported spline wavelets and a duality principle","volume":"330","author":"Chui, Charles K.","year":"1992","journal-title":"Trans. Amer. Math. Soc.","ISSN":"http:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/acha.1993.1005","article-title":"Wavelets on the interval and fast wavelet transforms","volume":"1","author":"Cohen, Albert","year":"1993","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"4","key":"9","first-page":"341","article-title":"Stability of multiscale transformations","volume":"2","author":"Dahmen, Wolfgang","year":"1996","journal-title":"J. Fourier Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/1069-5869","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1017\/S0962492900002713","article-title":"Wavelet and multiscale methods for operator equations","author":"Dahmen, Wolfgang","year":"1997"},{"issue":"259","key":"11","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1090\/S0025-5718-07-01970-9","article-title":"Adaptive methods for boundary integral equations: complexity and convergence estimates","volume":"76","author":"Dahmen, Wolfgang","year":"2007","journal-title":"Math. Comp.","ISSN":"http:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01385864","article-title":"Multilevel preconditioning","volume":"63","author":"Dahmen, Wolfgang","year":"1992","journal-title":"Numer. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3-4","key":"13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF02072014","article-title":"Wavelet approximation methods for pseudodifferential equations. II. Matrix compression and fast solution","volume":"1","author":"Dahmen, W.","year":"1993","journal-title":"Adv. Comput. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/1019-7168","issn-type":"print"},{"key":"14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1017\/S0962492900002816","article-title":"Nonlinear approximation","author":"DeVore, Ronald A.","year":"1998"},{"issue":"4","key":"15","doi-asserted-by":"publisher","first-page":"737","DOI":"10.2307\/2374796","article-title":"Compression of wavelet decompositions","volume":"114","author":"DeVore, Ronald A.","year":"1992","journal-title":"Amer. J. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/jcom.1996.0004","article-title":"Information complexity of multivariate Fredholm integral equations in Sobolev classes","volume":"12","author":"Frank, Karin","year":"1996","journal-title":"J. Complexity","ISSN":"http:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"17","unstructured":"C. Feuers\u00e4nger, D\u00fcnngitterverfahren f\u00fcr hochdimensionale elliptische partielle Differentialgleichungen, Diplomarbeit, Institut f\u00fcr Numerische Simulation, Universit\u00e4t Bonn, 2005."},{"key":"18","first-page":"94","article-title":"A parallelizable and vectorizable multi-level algorithm on sparse grids","author":"Griebel, M.","year":"1991"},{"key":"19","series-title":"Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-89224-9","volume-title":"Multilevelmethoden als Iterationsverfahren \\\"{u}ber Erzeugendensystemen","author":"Griebel, Michael","year":"1994","ISBN":"http:\/\/id.crossref.org\/isbn\/3519027186"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02684411","article-title":"Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences","volume":"61","author":"Griebel, M.","year":"1998","journal-title":"Computing","ISSN":"http:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"21","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1017\/CBO9780511721571.004","article-title":"Sparse grids and related approximation schemes for higher dimensional problems","author":"Griebel, Michael","year":"2006"},{"issue":"2","key":"22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1051\/m2an:2007015","article-title":"Sparse grids for the Schr\u00f6dinger equation","volume":"41","author":"Griebel, Michael","year":"2007","journal-title":"M2AN Math. Model. Numer. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0764-583X","issn-type":"print"},{"key":"23","first-page":"1473","article-title":"A wavelet based sparse grid method for the electronic Schr\u00f6dinger equation","author":"Griebel, Michael","year":"2006"},{"key":"24","unstructured":"M. Griebel, S. Knapek, Optimized approximation spaces for operator equations, Technical Report 568, SFB 256, Univ. Bonn, 1999."},{"issue":"4","key":"25","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s003650010010","article-title":"Optimized tensor-product approximation spaces","volume":"16","author":"Griebel, M.","year":"2000","journal-title":"Constr. Approx.","ISSN":"http:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"issue":"1","key":"26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00607-007-0241-3","article-title":"A sparse grid space-time discretization scheme for parabolic problems","volume":"81","author":"Griebel, M.","year":"2007","journal-title":"Computing","ISSN":"http:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"1-2","key":"27","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02123478","article-title":"Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems","volume":"4","author":"Griebel, M.","year":"1995","journal-title":"Adv. Comput. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/1019-7168","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s002110050450","article-title":"Sparse grids for boundary integral equations","volume":"83","author":"Griebel, M.","year":"1999","journal-title":"Numer. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"29","first-page":"263","article-title":"A combination technique for the solution of sparse grid problems","author":"Griebel, Michael","year":"1992"},{"key":"30","unstructured":"R. Hochmuth, S. Knapek, G. Zumbusch, Tensor products of Sobolev spaces and applications, Technical Report 685, SFB 256, Univ. Bonn, 2000."},{"issue":"4","key":"31","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1137\/0729059","article-title":"Wavelet methods for fast resolution of elliptic problems","volume":"29","author":"Jaffard, St\u00e9phane","year":"1992","journal-title":"SIAM J. Numer. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"32","unstructured":"S. Knapek, Hyperbolic cross approximation of integral operators with smooth kernel, Technical Report 665, SFB 256, Univ. Bonn, 2000."},{"key":"33","unstructured":"S. Knapek, Compression of anisotropic tensor-product discretizations, Technical Report 0200, Institut f\u00fcr Numerische Simulation, Universit\u00e4t Bonn, 2002."},{"issue":"5","key":"34","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0036142900375426","article-title":"Integral operators on sparse grids","volume":"39","author":"Knapek, S.","year":"2001","journal-title":"SIAM J. Numer. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"35","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/bf01932674","article-title":"On the design of nested iterations for elliptic difference equations","volume":"12","author":"Kronsj\u00f6, Lydia","year":"1972","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"http:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"key":"36","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","isbn-type":"print","volume-title":"Knapsack problems","author":"Martello, Silvano","year":"1990","ISBN":"http:\/\/id.crossref.org\/isbn\/0471924202"},{"issue":"1","key":"37","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00365-004-0559-4","article-title":"Sparse approximation of singularity functions","volume":"21","author":"Nitsche, P\u00e1l-Andrej","year":"2005","journal-title":"Constr. Approx.","ISSN":"http:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"key":"38","unstructured":"P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, in: Constructive Theory of Functions, K.G. Ivanov, P. Petrushev, B. Sendov (editors), Proc. Int. Conf. Varna, 1991, Bulg. Acad. Sci., Sofia, 203\u2013214, 1992."},{"key":"39","unstructured":"P. Oswald, Best N-term capacitance approximation on sparse grids, Proc. 12th Intern. Conf. on Domain Decomposition Methods in Science and Engineering, T. Chan et al. (editors), Chiba, 1999, 437\u2013444, 2001."},{"issue":"2","key":"40","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF01060382","article-title":"On the complexity of the problem of finding the solutions of Fredholm equations of the second kind with smooth kernels. II","volume":"41","author":"Pereverzev, S. V.","year":"1989","journal-title":"Ukrain. Mat. Zh.","ISSN":"http:\/\/id.crossref.org\/issn\/0041-6053","issn-type":"print"},{"key":"41","unstructured":"D. R\u00f6schke, \u00dcber eine Kombinationstechnik zur L\u00f6sung partieller Differentialgleichungen, Diplomarbeit, Institut f\u00fcr Informatik, TU M\u00fcnchen, 1991."},{"key":"42","series-title":"Mathematik und ihre Anwendungen in Physik und Technik [Mathematics and its Applications in Physics and Technology]","isbn-type":"print","volume-title":"Topics in Fourier analysis and function spaces","volume":"42","author":"Schmeisser, H.-J.","year":"1987","ISBN":"http:\/\/id.crossref.org\/isbn\/3321000016"},{"key":"43","series-title":"Advances in Numerical Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-10851-1","volume-title":"Multiskalen- und Wavelet-Matrixkompression","author":"Schneider, Reinhold","year":"1998","ISBN":"http:\/\/id.crossref.org\/isbn\/3519027399"},{"issue":"1","key":"44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcom.1997.0463","article-title":"When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?","volume":"14","author":"Sloan, Ian H.","year":"1998","journal-title":"J. Complexity","ISSN":"http:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"45","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1006\/jcom.2001.0626","article-title":"Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces","volume":"18","author":"Sloan, Ian H.","year":"2002","journal-title":"J. Complexity","ISSN":"http:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"46","first-page":"1042","article-title":"Quadrature and interpolation formulae on tensor products of certain function classes","volume":"148","author":"Smoljak, S. A.","year":"1963","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"http:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"issue":"5","key":"47","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/S0036141002411520","article-title":"On the compressibility operators in wavelet coordinates","volume":"35","author":"Stevenson, Rob","year":"2004","journal-title":"SIAM J. Math. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"key":"48","series-title":"Computer Science and Scientific Computing","isbn-type":"print","volume-title":"Information-based complexity","author":"Traub, J. F.","year":"1988","ISBN":"http:\/\/id.crossref.org\/isbn\/0126975450"},{"key":"49","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6027-1","volume-title":"Linear operators in Hilbert spaces","volume":"68","author":"Weidmann, Joachim","year":"1980","ISBN":"http:\/\/id.crossref.org\/isbn\/0387904271"},{"key":"50","series-title":"Oxford Mathematical Monographs","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198535898.001.0001","volume-title":"The computational complexity of differential and integral equations","author":"Werschulz, Arthur G.","year":"1991","ISBN":"http:\/\/id.crossref.org\/isbn\/0198535899"},{"key":"51","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1006\/jcom.1996.0027","article-title":"The complexity of the Poisson problem for spaces of bounded mixed derivatives","author":"Werschulz, Arthur G.","year":"1996"},{"key":"52","first-page":"241","article-title":"Sparse grids","author":"Zenger, Christoph","year":"1991"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02248-0\/S0025-5718-09-02248-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02248-0\/S0025-5718-09-02248-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T23:20:23Z","timestamp":1710458423000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-268\/S0025-5718-09-02248-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,23]]},"references-count":52,"journal-issue":{"issue":"268","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["S0025-5718-09-02248-0"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-09-02248-0","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,23]]}}}