Fast Matrix-Vector Multiplication in the Sparse-Grid Galerkin Method

Fast Matrix-Vector Multiplication in the Sparse-Grid Galerkin Method: "

Abstract

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 in (Balder and Zenger, SIAM J. Sci.
Comput. 17:631, 1996) 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.

• Content Type Journal Article
• DOI 10.1007/s10915-010-9438-2
• Authors
  
  
  • Andreas Zeiser, Sekretariat MA 3-3, Institut für Mathematik, TU Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
  
  

• Journal Journal of Scientific Computing
• Online ISSN 1573-7691
• Print ISSN 0885-7474

"