Abstract
Sparse tensor product spaces provide an efficient tool to discretize higher dimensional operator equations. The direct Galerkin method in such ansatz spaces may employ hierarchical bases, interpolets, wavelets or multilevel frames. Besides, an alternative approach is provided by the so-called combination technique. It properly combines the Galerkin solutions of the underlying problem on certain full (but small) tensor product spaces. So far, however, the combination technique has been analyzed only for special model problems. In the present paper, we provide now the analysis of the combination technique for quite general operator equations in sparse tensor product spaces. We prove that the combination technique produces the same order of convergence as the Galerkin approximation with respect to the sparse tensor product space. Furthermore, the order of the cost complexity is the same as for the Galerkin approach in the sparse tensor product space. Our theoretical findings are validated by numerical experiments.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
H.-J. Bungartz, M. Griebel, A note on the complexity of solving Poisson’s equation for spaces of bounded mixed derivatives. J. Complex. 15(2), 167–199 (1999)
H.-J. Bungartz, M. Griebel, Sparse grids. Acta Numer. 13, 147–269 (2004)
H. Bungartz, M. Griebel, D. Röschke, C. Zenger, A proof of convergence for the combination technique for the Laplace equation using tools of symbolic computation. Math. Comput. Simul. 42(4–6), 595–605 (1996)
D. Cioranescu, A. Damlamian, G. Griso, The periodic unfolding method in homogenization. SIAM J. Math. Anal. 40(4), 1585–1620 (2008)
W. Dahmen, Wavelet and multiscale methods for operator equations. Acta Numer. 6, 55–228 (1997)
F.-J. Delvos, d-variate Boolean interpolation. J. Approx. Theory 34(2), 99–114 (1982)
F.-J. Delvos, Boolean methods for double integration. Math. Comput. 55(192), 683–692 (1990)
F.-J. Delvos, W. Schempp, Boolean Methods in Interpolation and Approximation. Pitman Research Notes in Mathematics Series, vol. 230 (Longman Scientific & Technical, Harlow, 1989)
M. Griebel, Multilevelmethoden als Iterationsverfahren über Erzeugendensystemen. Teubner Skripten zur Numerik (B.G. Teubner, Stuttgart, 1994)
M. Griebel, H. Harbrecht, On the construction of sparse tensor product spaces. Math. Comput. 82(282), 975–994 (2013)
M. Griebel, H. Harbrecht, A note on the construction of L-fold sparse tensor product spaces. Constr. Approx. 38(2), 235–251 (2013)
M. Griebel, P. Oswald, On additive Schwarz preconditioners for sparse grid discretizations. Numer. Math. 66, 449–463 (1994)
M. Griebel, P. Oswald, T. Schiekofer, Sparse grids for boundary integral equations. Numer. Math. 83(2), 279–312 (1999)
M. Griebel, M. Schneider, C. Zenger, A combination technique for the solution of sparse grid problems, in Iterative Methods in Linear Algebra, ed. by P. de Groen, R. Beauwens. IMACS (Elsevier, North Holland, 1992), pp. 263–281
H. Harbrecht, A finite element method for elliptic problems with stochastic input data. Appl. Numer. Math. 60(3), 227–244 (2010).
H. Harbrecht, R. Schneider, C. Schwab, Sparse second moment analysis for elliptic problems in stochastic domains. Numer. Math. 109(3), 385–414 (2008)
H. Harbrecht, R. Schneider, C. Schwab, Multilevel frames for sparse tensor product spaces. Numer. Math. 110(2), 199–220 (2008)
H. Harbrecht, M. Peters, M. Siebenmorgen, Combination technique based k-th moment analysis of elliptic problems with random diffusion. J. Comput. Phys. 252, 128–141 (2013)
M. Hegland, J. Garcke, V. Challis, The combination technique and some generalisations. Linear Algebra Appl. 420(2–3), 249–275 (2007)
V.H. Hoang, C. Schwab, High-dimensional finite elements for elliptic problems with multiple scales. Multiscale Model. Simul. 3(1), 168–194 (2004/2005)
C. Pflaum, Convergence of the combination technique for second-order elliptic differential equation. SIAM J. Numer. Anal. 34, 2431–2455 (1997)
C. Pflaum, A. Zhou, Error analysis of the combination technique. Numer. Math. 84, 327–350 (1999)
C. Reisinger, Analysis of linear difference schemes in the sparse grid combination technique. IMA J. Numer. Anal. 33(2), 544–581 (2013)
C. Schwab, R.-A. Todor, Sparse finite elements for elliptic problems with stochastic loading. Numer. Math. 95(4), 707–734 (2003)
Y. Xu, A. Zhou, Fast Boolean approximation methods for solving integral equations in high dimensions. J. Integral Equ. Appl. 16(1), 83–110 (2004)
C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations. Proceedings of 6th GAMM-Seminar, Kiel/Germany 1990, ed. by W. Hackbusch. Notes on Numerical Fluid Mechanics, vol. 31 (Vieweg, Braunschweig, 1991), pp. 241–251
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Griebel, M., Harbrecht, H. (2014). On the Convergence of the Combination Technique. In: Garcke, J., Pflüger, D. (eds) Sparse Grids and Applications - Munich 2012. Lecture Notes in Computational Science and Engineering, vol 97. Springer, Cham. https://doi.org/10.1007/978-3-319-04537-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-04537-5_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04536-8
Online ISBN: 978-3-319-04537-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)