%0 Conference Paper %1 10.1007/978-3-030-81362-8_4 %A Holzmüller, David %A Pflüger, Dirk %B Sparse Grids and Applications - Munich 2018 %C Cham %D 2021 %E Bungartz, Hans-Joachim %E Garcke, Jochen %E Pflüger, Dirk %I Springer International Publishing %K %P 69--100 %T Fast Sparse Grid Operations Using the Unidirectional Principle: A Generalized and Unified Framework %X Sparse grids enable accurate function approximation in higher-dimensional settings with a moderate number of grid points. In this paper, we introduce generalized versions of various efficient sparse grid algorithms in a unified notation: For local basis functions, transformations between function values at grid points and interpolation coefficients can be efficiently realized using the well-known unidirectional principle (Balder and Zenger, SIAM Journal on Scientific Computing, 17(3):631--646, May 1996; Bungartz, Finite Elements of Higher Order on Sparse Grids, Universität München, Aachen, November 1998). For general basis functions without spatial adaptivity, Avila and Carrington show in (The Journal of Chemical Physics, 143(21):214108, 2015) and follow-up work that the unidirectional principle can instead be applied to an equivalent incremental basis, and we show that a second application of the unidirectional principle can be used to compute interpolation coefficients for the original, non-incremental basis. Our Open Source implementation for the latter case is able to compute interpolation coefficients for up to 20 million sparse grid points in one second on a single CPU core. We also discuss the efficient application of linear operators occurring in derivative evaluations of interpolants and in the solution of partial differential equations on sparse grids with finite elements, e.g., using the UpDown scheme (Bungartz, Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung, PhD thesis, Technische Universität München, 1992; Pflüger, Spatially Adaptive Sparse Grids for High-Dimensional Problems, Verlag Dr. Hut, München, February 2010; Zeiser, Journal of Scientific Computing, 47(3):328--346, 2011; Bungartz et al., Journal of Computational and Applied Mathematics, 236(15):3741--3750, 2012). %@ 978-3-030-81362-8

@inproceedings{10.1007/978-3-030-81362-8_4, abstract = {Sparse grids enable accurate function approximation in higher-dimensional settings with a moderate number of grid points. In this paper, we introduce generalized versions of various efficient sparse grid algorithms in a unified notation: For local basis functions, transformations between function values at grid points and interpolation coefficients can be efficiently realized using the well-known unidirectional principle (Balder and Zenger, SIAM Journal on Scientific Computing, 17(3):631--646, May 1996; Bungartz, Finite Elements of Higher Order on Sparse Grids, Universit{\"a}t M{\"u}nchen, Aachen, November 1998). For general basis functions without spatial adaptivity, Avila and Carrington show in (The Journal of Chemical Physics, 143(21):214108, 2015) and follow-up work that the unidirectional principle can instead be applied to an equivalent incremental basis, and we show that a second application of the unidirectional principle can be used to compute interpolation coefficients for the original, non-incremental basis. Our Open Source implementation for the latter case is able to compute interpolation coefficients for up to 20 million sparse grid points in one second on a single CPU core. We also discuss the efficient application of linear operators occurring in derivative evaluations of interpolants and in the solution of partial differential equations on sparse grids with finite elements, e.g., using the UpDown scheme (Bungartz, D{\"u}nne Gitter und deren Anwendung bei der adaptiven L{\"o}sung der dreidimensionalen Poisson-Gleichung, PhD thesis, Technische Universit{\"a}t M{\"u}nchen, 1992; Pfl{\"u}ger, Spatially Adaptive Sparse Grids for High-Dimensional Problems, Verlag Dr. Hut, M{\"u}nchen, February 2010; Zeiser, Journal of Scientific Computing, 47(3):328--346, 2011; Bungartz et al., Journal of Computational and Applied Mathematics, 236(15):3741--3750, 2012).}, added-at = {2023-10-12T12:10:40.000+0200}, address = {Cham}, author = {Holzm{\"u}ller, David and Pfl{\"u}ger, Dirk}, biburl = {https://puma.ub.uni-stuttgart.de/bibtex/28ec97c3d2425a1399cde9df27c0a9add/davidholzmller}, booktitle = {Sparse Grids and Applications - Munich 2018}, editor = {Bungartz, Hans-Joachim and Garcke, Jochen and Pfl{\"u}ger, Dirk}, interhash = {291453abea2da18bc0cb8598039ca4ba}, intrahash = {8ec97c3d2425a1399cde9df27c0a9add}, isbn = {978-3-030-81362-8}, keywords = {}, pages = {69--100}, publisher = {Springer International Publishing}, timestamp = {2023-10-12T10:10:40.000+0200}, title = {Fast Sparse Grid Operations Using the Unidirectional Principle: A Generalized and Unified Framework}, year = 2021 }