Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the construction of sparse tensor product spaces

Authors: Michael Griebel and Helmut Harbrecht
Journal: Math. Comp. 82 (2013), 975-994
MSC (2010): Primary 41A17, 41A25, 41A30, 41A65
Published electronically: August 9, 2012
MathSciNet review: 3008845
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. G. Allaire and M. Briane.
    Multiscale convergence and reiterated homogenisation.
    Proc. Roy. Soc. Edinburgh Sect. A, 126(2):297-342, 1996. MR 1386865 (97d:35014)
  • 2. Hans-Joachim Bungartz and Michael Griebel.
    Sparse grids.
    Acta Numer., 13:147-269, 2004. MR 2249147 (2007e:65102)
  • 3. Nabi Chegini and Rob Stevenson.
    Adaptive wavelet schemes for parabolic problems: sparse matrices and numerical results.
    SIAM J. Numer. Anal., 49(1):182-212, 2011. MR 2783222
  • 4. D. Cioranescu, A. Damlamian, and G. Griso.
    The periodic unfolding method in homogenization.
    SIAM J. Math. Anal., 40(4):1585-1620, 2008. MR 2466168 (2009m:35024)
  • 5. Wolfgang Dahmen.
    Wavelet and multiscale methods for operator equations.
    In Acta numerica, 1997, volume 6 of Acta Numer., pages 55-228. Cambridge Univ. Press, Cambridge, 1997. MR 1489256 (98m:65102)
  • 6. T. Gerstner and M. Griebel.
    Dimension-adaptive tensor-product quadrature.
    Computing, 71(1):65-87, 2003. MR 2009651 (2004k:65036)
  • 7. Thomas Gerstner and Michael Griebel.
    Numerical integration using sparse grids.
    Numer. Algorithms, 18(3-4):209-232, 1998. MR 1669959 (99m:65042)
  • 8. M. Griebel and S. Knapek.
    Optimized general sparse grid approximation spaces for operator equations.
    Math. Comp., 78(268):2223-2257, 2009. MR 2521287 (2010f:65255)
  • 9. M. Griebel and D. Oeltz.
    A sparse grid space-time discretization scheme for parabolic problems.
    Computing, 81(1):1-34, 2007. MR 2369419 (2009b:65252)
  • 10. M. Griebel, P. Oswald, and T. Schiekofer.
    Sparse grids for boundary integral equations.
    Numer. Math., 83(2):279-312, 1999. MR 1712687 (2000h:65195)
  • 11. Michael Griebel and Jan Hamaekers.
    Sparse grids for the Schrödinger equation.
    M2AN Math. Model. Numer. Anal., 41(2):215-247, 2007. MR 2339626 (2008h:81042)
  • 12. Helmut Harbrecht.
    A finite element method for elliptic problems with stochastic input data.
    Appl. Numer. Math., 60(3):227-244, 2010. MR 2602675 (2011c:65261)
  • 13. Helmut Harbrecht, Reinhold Schneider, and Christoph Schwab.
    Sparse second moment analysis for elliptic problems in stochastic domains.
    Numer. Math., 109(3):385-414, 2008. MR 2399150 (2009b:65012)
  • 14. Viet Ha Hoang and Christoph Schwab.
    High-dimensional finite elements for elliptic problems with multiple scales.
    Multiscale Model. Simul., 3(1):168-194, 2004/05. MR 2123115 (2005m:65267)
  • 15. A. Kolmogoroff.
    Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse.
    Ann. of Math. (2), 37(1):107-110, 1936. MR 1503273
  • 16. 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(1):193-209, 2008. MR 2462660 (2009j:91102)
  • 17. Dirk Pflüger, Benjamin Peherstorfer, and Hans-Joachim Bungartz.
    Spatially adaptive sparse grids for high-dimensional data-driven problems.
    J. Complexity, 26(5):508-522, 2010. MR 2719645 (2011i:65043)
  • 18. Christoph Reisinger and Gabriel Wittum.
    Efficient hierarchical approximation of high-dimensional option pricing problems.
    SIAM J. Sci. Comput., 29(1):440-458, 2007. MR 2285899 (2008b:65107)
  • 19. Christoph Schwab and Rob Stevenson.
    Space-time adaptive wavelet methods for parabolic evolution problems.
    Math. Comp., 78(267):1293-1318, 2009. MR 2501051 (2011a:65347)
  • 20. Christoph Schwab and Radu-Alexandru Todor.
    Sparse finite elements for elliptic problems with stochastic loading.
    Numer. Math., 95(4):707-734, 2003. MR 2013125 (2004j:65192)
  • 21. Tobias von Petersdorff and Christoph Schwab.
    Numerical solution of parabolic equations in high dimensions.
    M2AN Math. Model. Numer. Anal., 38(1):93-127, 2004. MR 2073932 (2005d:65169)
  • 22. Tobias von Petersdorff and Christoph Schwab.
    Sparse finite element methods for operator equations with stochastic data.
    Appl. Math., 51(2):145-180, 2006. MR 2212311 (2007g:65111)
  • 23. G. Widmer, R. Hiptmair, and Ch. Schwab.
    Sparse adaptive finite elements for radiative transfer.
    J. Comput. Phys., 227(12):6071-6105, 2008. MR 2418354 (2010c:85003)
  • 24. Christoph Zenger.
    Sparse grids.
    In Parallel algorithms for partial differential equations (Kiel, 1990), volume 31 of Notes Numer. Fluid Mech., pages 241-251. Vieweg, Braunschweig, 1991. MR 1167882

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A17, 41A25, 41A30, 41A65

Retrieve articles in all journals with MSC (2010): 41A17, 41A25, 41A30, 41A65

Additional Information

Michael Griebel
Affiliation: Institut für Numerische Simulation, Universität Bonn, Wegelerstr. 6, 53115 Bonn, Germany

Helmut Harbrecht
Affiliation: Mathematisches Institut, Universität Basel, Rheinsprung 21, 4051 Basel, Switzerland

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
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society