Preliminary list of abstracts

Note: We are using the fantastic MathJax JavaScript library to typeset the mathematics on this web page. You can right-click on a formula to zoom in or to select the rendering engine you like (all under 'Settings'). Under Firefox the default renderer turns out to be MathML (which is quick), but you might prefer the HTML-CSS renderer for more faithful LaTeX rendering. If you encounter any problems with this setup: then please email us!

Click here to go back to the list of abstracts.

A multigrid method for PDEs on spatially adaptive sparse grids
Keywords: sparse grids; PDE; multigrid
Mon, 09:25--09:50
  • Peherstorfer, Benjamin (Department of Informatics, Technische Universität München, Germany)
  • Bungartz, Hans-Joachim (Department of Informatics, Technische Universität München, Germany)
  • Zenger, Christoph (Department of Informatics, Technische Universität München, Germany)

To solve a PDE on spatially adaptive sparse grids with the FE method, we need a matrix-vector product to apply a vector to the system matrix. Numerous work has been published on how to best compute this product in order to obtain the solution of the system of linear equations efficiently, see e.g. [1,4]. However, only very limited or specialized multigrid approaches have been presented.

We present a multigrid method which relies on a dimension-wise (i.e. ANOVA-like) decomposition of the hierarchically lower parts of the function. Note that the natural relationship between sparse grids and such decompositions has been shown in e.g. [3,2]. Whereas the algorithm in [1] needs $\mathcal{O}(2^d)$ recursive calls to compute the bilinear form corresponding to the hierarchically lower and higher parts of the function, we simply store these hierarchically lower parts. Representing the function in the nodal point basis on the current grid, no hierarchically higher parts of the function exist. An extra benefit besides the method's multigrid performance is that its dimension-wise decomposition of the hierarchically lower parts gives us some knowledge concerning the importance of the different dimensions.

We present first numerical experiments for elliptic PDEs in moderately high dimensions which confirm the expected multigrid performance. Both regular and spatially adaptive sparse grids are used. These examples further demonstrate that the additional amount of storage required for the hierarchically lower parts can be kept under control if only non-zero values are stored. Finally, we show that the components of the dimension-wise decomposition do indeed reflect the characteristics of the solution to some extent.

[1] Robert Balder and Christoph Zenger. The solution of multidimensional real helmholtz equations on sparse grids. SIAM Journal on Scientific Computing, 17(3):631–646, 1996.
[2] Christian Feuersänger. Sparse Grid Methods for Higher Dimensional Approximation. PhD thesis, September 2010.
[3] M. Griebel. Sparse grids and related approximation schemes for higher dimensional problems. In L. Pardo, A. Pinkus, E. Suli, and M.J. Todd, editors, Foundations of Computational Mathematics (FoCM05), Santander, pages 106–161. Cambridge University Press, 2006.
[4] Christoph Schwab and Radu-Alexandru Todor. Sparse finite elements for elliptic problems with stochastic loading. Numerische Mathematik, 95(4):707–734, October 2003.