Mathematics of Computation

Author(s): M. Griebel; S. Knapek.
Journal: Math. Comp. 78 (2009), 2223-2257.
MSC (2000): Primary 41A17, 41A25, 41A30, 41A65, 45L10, 65D99, 65N12, 65N30, 65N38, 65N55
Posted: April 23, 2009
Retrieve article in: PDF

Abstract: 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 is $O(2^{J})$ independent of the dimension

of the problem, compared to $O(2^{Jn})$ 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.

1.: R. Adams, Sobolev spaces, Academic Press, New York, 1975. MR 0450957 (56:9247)
2.: P. Auscher, Wavelets with boundary conditions on the interval, in C. Chui (editor), Wavelets: A tutorial in theory and applications, Wavelet Anal. Appl., vol. 2, Acad. Press, Boston, 217-236, 1992. MR 1161253 (93c:42029)
3.: H.-J. Bungartz, Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung, Dissertation, TU München, Institut für Informatik, 1992.
4.: H.-J. Bungartz, Finite elements of higher order on sparse grids, Habilitation, TU München, Institut für Informatik, 1998.
5.: H.-J. Bungartz, M. Griebel, A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives, J. Complexity, 15:167-199, 1999. MR 1693892 (2000d:65254)
6.: H.-J. Bungartz, M. Griebel, Sparse grids, Acta Numerica, 13:1-123, 2004. MR 2249147 (2007e:65102)
7.: C. Chui, J. Wang, On compactly supported spline wavelets, Trans. Amer. Math. Soc., 330:903-915, 1992. MR 1076613 (92f:41020)
8.: A. Cohen, I. Daubechies, P. Vial, Wavelets on the interval and fast wavelet transforms, Appl. Comput. Harmon. Anal., 1:54-81, 1993. MR 1256527 (94m:42074)
9.: W. Dahmen, Stability of multiscale transformations, Journal of Fourier Analysis and Applications, 2:341-361, 1996. MR 1395769 (97i:46133)
10.: W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Numerica, 6:55-228, 1997. MR 1489256 (98m:65102)
11.: W. Dahmen, H. Harbrecht, R. Schneider, Adaptive methods for boundary integral equations: Complexity and convergence estimates, Math. Comp., 76:1243-1274, 2007. MR 2299773 (2008c:65360)
12.: W. Dahmen, A. Kunoth, Multilevel preconditioning, Numer. Math., 63:315-344, 1992. MR 1186345 (93j:65065)
13.: W. Dahmen, S. Prößdorf, R. Schneider, Wavelet approximation methods for pseudodifferential equations II: Matrix compression and fast solution, Advances in Computational Mathematics, 1:259-335, 1993. MR 1242378 (95g:65149)
14.: R. DeVore, Nonlinear approximation, Acta Numerica, 7:51-150, 1998. MR 1689432 (2001a:41034)
15.: R. DeVore, B. Jawerth, V. Popov, Compression of wavelet decompositions, Amer. J. Math., 114:737-785, 1992. MR 1175690 (94a:42045)
16.: K. Frank, S. Heinrich, S. Pereverzev, Information complexity of multivariate Fredholm equations in Sobolev classes, J. Complexity, 12:17-34, 1996. MR 1386591 (97h:65167)
17.: C. Feuersänger, Dünngitterverfahren für hochdimensionale elliptische partielle Differentialgleichungen, Diplomarbeit, Institut für Numerische Simulation, Universität Bonn, 2005.
18.: M. Griebel, A parallelizable and vectorizable multi-level algorithm on sparse grids, Parallel Algorithms for Partial Differential Equations, Notes on Numer. Fluid Mech. 31, W. Hackbusch (editor), Vieweg, Braunschweig, 1991. MR 1167870
19.: M. Griebel, Multilevelmethoden als Iterationsverfahren über Erzeugendensystemen, Teubner Skripten zur Numerik, Teubner, Stuttgart, 1994. MR 1312162 (95k:65004)
20.: M. Griebel, Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing, 61(2):151-179, 1998. MR 1650985 (99j:65184)
21.: M. Griebel, Sparse grids and related approximation schemes for higher dimensional problems, In Foundations of Computational Mathematics, L. Pardo, A. Pinkus, E. Suli, M. Todd (editors), London Math. Soc. Lecture Note Ser. 331, Cambridge University Press, Cambridge, 2006. MR 2277104 (2007k:65206)
22.: M. Griebel, J. Hamaekers, Sparse grids for the Schrödinger equation, Mathematical Modeling and Numerical Analysis, 41(2):215-247, 2007. MR 2339626 (2008h:81042)
23.: M. Griebel, J. Hamaekers, A wavelet based sparse grid method for the electronic Schrödinger equation, in M. Sanz-Solé, J. Soria, J. Varona, J. Verdera (editors), Proceedings of the International Congress of Mathematicians, volume III, 1473-1506, Madrid, Spain, 22.-30. August 2006, European Mathematical Society. MR 2275738 (2008a:65269)
24.: M. Griebel, S. Knapek, Optimized approximation spaces for operator equations, Technical Report 568, SFB 256, Univ. Bonn, 1999.
25.: M. Griebel, S. Knapek, Optimized tensor-product approximation spaces, Constructive Approximation, 16(4):525-540, 2000. MR 1771694 (2001g:41025)
26.: M. Griebel, D. Oeltz, A sparse grid space-time discretization scheme for parabolic problems, Computing, 81(1):1-34, 2007. MR 2369419
27.: M. Griebel, P. Oswald, Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Advances in Computational Mathematics, 4:171-206, 1995. MR 1338900 (96e:65069)
28.: M. Griebel, P. Oswald, T. Schiekofer, Sparse grids for boundary integral equations, Numer. Mathematik, 83(2):279-312, 1999. MR 1712687 (2000h:65195)
29.: M. Griebel, M. Schneider, C. Zenger, A combination technique for the solution of sparse grid problems, in Iterative Methods in Linear Algebra, P. de Groen, R. Beauwens (editors), Elsevier, Amsterdam, 263-281, 1992. MR 1159736
30.: R. Hochmuth, S. Knapek, G. Zumbusch, Tensor products of Sobolev spaces and applications, Technical Report 685, SFB 256, Univ. Bonn, 2000.
31.: S. Jaffard, Wavelet methods for fast resolution of elliptic equations, SIAM J. Numer. Anal., 29:965-986, 1992. MR 1173180 (93i:35042)
32.: S. Knapek, Hyperbolic cross approximation of integral operators with smooth kernel, Technical Report 665, SFB 256, Univ. Bonn, 2000.
33.: S. Knapek, Compression of anisotropic tensor-product discretizations, Technical Report 0200, Institut für Numerische Simulation, Universität Bonn, 2002.
34.: S. Knapek, F. Koster, Integral operators on sparse grids, SIAM J. Numer. Anal., 39(5):1794-1809, 2002. MR 1885717 (2003e:42054)
35.: L. Kronsjö, G. Dahlquist, On the design of nested iteration for elliptic differential equations, BIT, 12:63-71, 1972. MR 0312754 (47:1309)
36.: S. Martello, P. Toth, Knapsack problems: Algorithms and computer implementations, John Wiley & Sons, Chichester, 1990. MR 1086874 (92a:90006)
37.: P. Nitsche, Sparse approximation of singularity functions, Constructive Approximation, 21:63-81, 2004. MR 2105391 (2005h:41038)
38.: 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-214, 1992.
39.: 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-444, 2001.
40.: S. Pereverzev, On the complexity of finding solutions of Fredholm equations of the second kind with differentiable kernels II, Ukrain. Mat. Zh., 41:169-173, 1989. MR 992820 (90i:65245)
41.: D. Röschke, Über eine Kombinationstechnik zur Lösung partieller Differentialgleichungen, Diplomarbeit, Institut für Informatik, TU München, 1991.
42.: H.-J. Schmeisser, H. Triebel, Topics in Fourier analysis and function spaces, John Wiley, Chichester, 1987. MR 891189 (88k:42015b)
43.: R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme, Advances in Numerical Analysis, Teubner, Stuttgart, 1998. MR 1623209 (99f:65067)
44.: I. Sloan, H. Wozniakowski, When are Quasi-Monte Carlo algorithms efficient for high dimensional problems, Journal of Complexity, 14:1-33, 1998. MR 1617765 (99d:65384)
45.: I. Sloan, H. Wozniakowski, Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces, Journal of Complexity, 18:479-499, 2002. MR 1919445 (2003e:46119)
46.: S. Smoljak, Quadrature and interpolation formulae for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR, 148:1042-1045, 1963. MR 0147825 (26:5338)
47.: R. Stevenson, On the compressibility of operators in wavelet coordinates, SIAM J. Math. Anal., 35(5):1110-1132, 2004. MR 2050194 (2005e:42128)
48.: J. Traub, G. Wasilkowski, H. Wozniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
49.: J. Weidmann, Linear operators in Hilbert spaces, Springer, New York, 1980. MR 566954 (81e:47001)
50.: A. Werschulz, The computational complexity of differential and integral equations, An information-based approach, Oxford University Press, The Clarendon Press, New York, 1991. MR 1144521 (93a:68061)
51.: A. Werschulz, The complexity of the Poisson problem for spaces of bounded mixed derivatives, Technical Report CUCS-016-95, 1995. MR 1421372 (98g:65113)
52.: C. Zenger, Sparse grids, In W. Hackbusch (editor), Parallel Algorithms for Partial Differential Equations, Notes on Numer. Fluid Mech. 31, Vieweg, Braunschweig, 1991. MR 1167882

M. Griebel
Affiliation: Institut für Numerische Simulation, Universität Bonn, D-53115 Bonn, Germany
Email: griebel@ins.uni-bonn.de

S. Knapek
Affiliation: Institut für Numerische Simulation, Universität Bonn, D-53115 Bonn, Germany

DOI: 10.1090/S0025-5718-09-02248-0
PII: S 0025-5718(09)02248-0
Received by editor(s): April 10, 2008
Received by editor(s) in revised form: December 4, 2008
Posted: April 23, 2009
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS