Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout

Riko Jacob

doi:10.1007/978-3-319-04537-5_8

Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout

Riko Jacob

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-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 language	English
Title of host publication	Sparse Grids and Applications - Munich 2012
Number of pages	24
Volume	97
Publisher	Springer
Publication date	2012
Pages	195-219
ISBN (Print)	978-3-319-04536-8
ISBN (Electronic)	978-3-319-04537-5
DOIs	https://doi.org/10.1007/978-3-319-04537-5_8
Publication status	Published - 2012
Externally published	Yes
Event	Sparse Grids and Applications - Munich, Germany Duration: 2 Jul 2012 → 6 Jul 2012 Conference number: 2

Conference

Conference	Sparse Grids and Applications
Number	2
Country/Territory	Germany
City	Munich
Period	02/07/2012 → 06/07/2012

Series	Lecture Notes in Computational Science and Engineering
Volume	97
ISSN	1439-7358

Access to Document

10.1007/978-3-319-04537-5_8

Cite this

@inproceedings{b2986ec3657b424cb1b6c8157325932b,

title = "Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout",

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.",

author = "Riko Jacob",

year = "2012",

doi = "10.1007/978-3-319-04537-5_8",

language = "English",

isbn = "978-3-319-04536-8",

volume = "97",

series = "Lecture Notes in Computational Science and Engineering",

publisher = "Springer",

pages = "195--219",

booktitle = "Sparse Grids and Applications - Munich 2012",

address = "Germany",

note = "Sparse Grids and Applications, SGA 2012 ; Conference date: 02-07-2012 Through 06-07-2012",

}

TY - GEN

T1 - Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout

AU - Jacob, Riko

N1 - Conference code: 2

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-04537-5_8

DO - 10.1007/978-3-319-04537-5_8

M3 - Article in proceedings

SN - 978-3-319-04536-8

VL - 97

T3 - Lecture Notes in Computational Science and Engineering

SP - 195

EP - 219

BT - Sparse Grids and Applications - Munich 2012

PB - Springer

T2 - Sparse Grids and Applications

Y2 - 2 July 2012 through 6 July 2012

ER -

Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout

Abstract

Conference

Access to Document

Fingerprint

Cite this