×

zbMATH — the first resource for mathematics

Fast matrix-vector multiplication in the sparse-grid Galerkin method. (English) Zbl 1231.65224
Summary: Sparse grid discretization of higher dimensional partial differential equations is a means to break the curse of dimensionality. For classical sparse grids based on the one-dimensional hierarchical basis, a sophisticated algorithm has been devised to calculate the application of a vector to the Galerkin matrix in linear complexity, despite the fact that the matrix is not sparse. However more general sparse grid constructions have been recently introduced, e.g. based on multilevel finite elements, where the specified algorithms only have a log-linear scaling. This article extends the idea of the linear scaling algorithm to more general sparse grid spaces. This is achieved by abstracting the algorithm given by R. Balder and Ch. Zenger [SIAM J. Sci. Comput. 17, No. 3, 631–646 (1996; Zbl 0855.65111)] from specific bases, thereby identifying the prerequisites for performing the algorithm. In this way one can easily adapt the algorithm to specific discretizations, leading for example to an optimal linear scaling algorithm in the case of multilevel finite element frames.

MSC:
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balder, R., Zenger, C.: The solution of multidimensional real Helmholtz equations on sparse grids. SIAM J. Sci. Comput. 17(3), 631–646 (1996) · Zbl 0855.65111
[2] Bungartz, H.J.: Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung. Ph.D. thesis, TU München (1992)
[3] Bungartz, H.J.: A multigrid algorithm for higher order finite elements on sparse grids. ETNA Electron. Trans. Numer. Anal. 6, 63–77 (1997) · Zbl 0903.65087
[4] Bungartz, H.J.: Finite elements of higher order on sparse grids. Habilitationsschrift, Fakultät für Informatik, TU München (1998)
[5] Bungartz, H.J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004) · Zbl 1118.65388
[6] Chernov, A., Schwab, C.: Sparse p-version BEM for first kind boundary integral equations with random loading. Appl. Numer. Math. 59(11), 2698–2712 (2009). doi: 10.1016/j.apnum.2008.12.023 · Zbl 1177.65191
[7] Griebel, M., Oeltz, D.: A sparse grid space-time discretization scheme for parabolic problems. Computing 81(1), 1–34 (2007) · Zbl 1132.35387
[8] Harbrecht, H., Schneider, R., Schwab, C.: Multilevel frames for sparse tensor product spaces. Numer. Math. 110(2), 199–220 (2008) · Zbl 1151.65010
[9] Niedermeier, A.: Implementational aspects of prewavelet sparse grid methods. In: Lai, C.H., Bjoerstad, P., Cross, M., Widlund, O. (eds.) Eleventh International Conference of Domain Decomposition Methods (1999)
[10] Schwab, C., Todor, R.A.: Sparse finite elements for elliptic problems with stochastic loading. Numer. Math. 95(4), 707–734 (2003) · Zbl 1044.65085
[11] Weidmann, J.: Linear Operators in Hilbert Spaces. Springer, New York (1980) · Zbl 0434.47001
[12] Yserentant, H.: On the multi-level splitting of finite element spaces. Numer. Math. 49, 379–412 (1986) · Zbl 0608.65065
[13] Zenger, C.: Sparse grids. In: Hachbusch, W. (ed.) Parallel Algorithms for Partial Differential Equations. Notes on Numerical Fluid Mechanics, vol. 31, pp. 241–251. Vieweg, Wiesbaden (1990) · Zbl 0763.65091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.