On the construction of sparse tensor product spaces
HTML articles powered by AMS MathViewer
- by Michael Griebel and Helmut Harbrecht PDF
- Math. Comp. 82 (2013), 975-994 Request permission
Abstract:
Let $\Omega _1\subset \mathbb {R}^{n_1}$ and $\Omega _2\subset \mathbb {R}^{n_2}$ be two given domains and consider on each domain a multiscale sequence of ansatz spaces of polynomial exactness $r_1$ and $r_2$, respectively. In this paper, we study the optimal construction of sparse tensor products made from these spaces. In particular, we derive the resulting cost complexities to approximate functions with anisotropic and isotropic smoothness on the tensor product domain $\Omega _1\times \Omega _2$. Numerical results validate our theoretical findings.References
- G. Allaire and M. Briane, Multiscale convergence and reiterated homogenisation, Proc. Roy. Soc. Edinburgh Sect. A 126 (1996), no. 2, 297–342. MR 1386865, DOI 10.1017/S0308210500022757
- Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. MR 2249147, DOI 10.1017/S0962492904000182
- Nabi Chegini and Rob Stevenson, Adaptive wavelet schemes for parabolic problems: sparse matrices and numerical results, SIAM J. Numer. Anal. 49 (2011), no. 1, 182–212. MR 2783222, DOI 10.1137/100800555
- D. Cioranescu, A. Damlamian, and G. Griso, The periodic unfolding method in homogenization, SIAM J. Math. Anal. 40 (2008), no. 4, 1585–1620. MR 2466168, DOI 10.1137/080713148
- Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
- T. Gerstner and M. Griebel, Dimension-adaptive tensor-product quadrature, Computing 71 (2003), no. 1, 65–87. MR 2009651, DOI 10.1007/s00607-003-0015-5
- Thomas Gerstner and Michael Griebel, Numerical integration using sparse grids, Numer. Algorithms 18 (1998), no. 3-4, 209–232. MR 1669959, DOI 10.1023/A:1019129717644
- M. Griebel and S. Knapek, Optimized general sparse grid approximation spaces for operator equations, Math. Comp. 78 (2009), no. 268, 2223–2257. MR 2521287, DOI 10.1090/S0025-5718-09-02248-0
- 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
- M. Griebel, P. Oswald, and T. Schiekofer, Sparse grids for boundary integral equations, Numer. Math. 83 (1999), no. 2, 279–312. MR 1712687, DOI 10.1007/s002110050450
- Michael Griebel and Jan Hamaekers, Sparse grids for the Schrödinger equation, M2AN Math. Model. Numer. Anal. 41 (2007), no. 2, 215–247. MR 2339626, DOI 10.1051/m2an:2007015
- Helmut Harbrecht, A finite element method for elliptic problems with stochastic input data, Appl. Numer. Math. 60 (2010), no. 3, 227–244. MR 2602675, DOI 10.1016/j.apnum.2009.12.002
- Helmut Harbrecht, Reinhold Schneider, and Christoph Schwab, Sparse second moment analysis for elliptic problems in stochastic domains, Numer. Math. 109 (2008), no. 3, 385–414. MR 2399150, DOI 10.1007/s00211-008-0147-9
- Viet Ha Hoang and Christoph Schwab, High-dimensional finite elements for elliptic problems with multiple scales, Multiscale Model. Simul. 3 (2004/05), no. 1, 168–194. MR 2123115, DOI 10.1137/030601077
- A. Kolmogoroff, Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse, Ann. of Math. (2) 37 (1936), no. 1, 107–110 (German). MR 1503273, DOI 10.2307/1968691
- C. C. W. Leentvaar and C. W. Oosterlee, On coordinate transformation and grid stretching for sparse grid pricing of basket options, J. Comput. Appl. Math. 222 (2008), no. 1, 193–209. MR 2462660, DOI 10.1016/j.cam.2007.10.015
- Dirk Pflüger, Benjamin Peherstorfer, and Hans-Joachim Bungartz, Spatially adaptive sparse grids for high-dimensional data-driven problems, J. Complexity 26 (2010), no. 5, 508–522. MR 2719645, DOI 10.1016/j.jco.2010.04.001
- Christoph Reisinger and Gabriel Wittum, Efficient hierarchical approximation of high-dimensional option pricing problems, SIAM J. Sci. Comput. 29 (2007), no. 1, 440–458. MR 2285899, DOI 10.1137/060649616
- Christoph Schwab and Rob Stevenson, Space-time adaptive wavelet methods for parabolic evolution problems, Math. Comp. 78 (2009), no. 267, 1293–1318. MR 2501051, DOI 10.1090/S0025-5718-08-02205-9
- Christoph Schwab and Radu-Alexandru Todor, Sparse finite elements for elliptic problems with stochastic loading, Numer. Math. 95 (2003), no. 4, 707–734. MR 2013125, DOI 10.1007/s00211-003-0455-z
- 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
- Tobias von Petersdorff and Christoph Schwab, Sparse finite element methods for operator equations with stochastic data, Appl. Math. 51 (2006), no. 2, 145–180. MR 2212311, DOI 10.1007/s10492-006-0010-1
- G. Widmer, R. Hiptmair, and Ch. Schwab, Sparse adaptive finite elements for radiative transfer, J. Comput. Phys. 227 (2008), no. 12, 6071–6105. MR 2418354, DOI 10.1016/j.jcp.2008.02.025
- Christoph Zenger, Sparse grids, Parallel algorithms for partial differential equations (Kiel, 1990) Notes Numer. Fluid Mech., vol. 31, Friedr. Vieweg, Braunschweig, 1991, pp. 241–251. MR 1167882
Additional Information
- Michael Griebel
- Affiliation: Institut für Numerische Simulation, Universität Bonn, Wegelerstr. 6, 53115 Bonn, Germany
- MR Author ID: 270664
- Email: griebel@ins.uni-bonn.de
- Helmut Harbrecht
- Affiliation: Mathematisches Institut, Universität Basel, Rheinsprung 21, 4051 Basel, Switzerland
- Email: helmut.harbrecht@unibas.ch
- Received by editor(s): May 27, 2011
- Received by editor(s) in revised form: September 26, 2011, and October 15, 2011
- Published electronically: August 9, 2012
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 82 (2013), 975-994
- MSC (2010): Primary 41A17, 41A25, 41A30, 41A65
- DOI: https://doi.org/10.1090/S0025-5718-2012-02638-X
- MathSciNet review: 3008845