Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout

Riko Jacob

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

We consider a new hierarchization algorithm for sparse grids of high dimension and low level. The algorithm is inspired by the theory of memory efficient algorithms. It is based on a cache-friendly layout of a compact data storage, and the idea of rearranging the data for the different phases of the algorithm. The core steps of the algorithm can be phrased as multiplying the input vector with two sparse matrices. A generalized counting makes it possible to create (or apply) the matrices in constant time per row. The algorithm is implemented as a proof of concept and first experiments show that it performs well in comparison with the previous implementation SG++, in particular for the case of high dimensions and low level.
Original languageEnglish
Title of host publicationSparse Grids and Applications - Munich 2012
Number of pages24
Volume97
PublisherSpringer
Publication date2012
Pages195-219
ISBN (Print)978-3-319-04536-8
ISBN (Electronic)978-3-319-04537-5
DOIs
Publication statusPublished - 2012
Externally publishedYes
EventSparse Grids and Applications - Munich, Germany
Duration: 2 Jul 20126 Jul 2012
Conference number: 2

Conference

ConferenceSparse Grids and Applications
Number2
Country/TerritoryGermany
CityMunich
Period02/07/201206/07/2012
SeriesLecture Notes in Computational Science and Engineering
Volume97
ISSN1439-7358

Keywords

  • Hierarchization algorithm
  • Sparse grids
  • High dimension
  • Cache-friendly
  • Sparse matrices

Fingerprint

Dive into the research topics of 'Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout'. Together they form a unique fingerprint.

Cite this