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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Sparse Grids and Applications - Munich 2012
Antal sider	24
Vol/bind	97
Forlag	Springer
Publikationsdato	2012
Sider	195-219
ISBN (Trykt)	978-3-319-04536-8
ISBN (Elektronisk)	978-3-319-04537-5
DOI	https://doi.org/10.1007/978-3-319-04537-5_8
Status	Udgivet - 2012
Udgivet eksternt	Ja
Begivenhed	Sparse Grids and Applications - Munich, Tyskland Varighed: 2 jul. 2012 → 6 jul. 2012 Konferencens nummer: 2

Konference

Konference	Sparse Grids and Applications
Nummer	2
Land/Område	Tyskland
By	Munich
Periode	02/07/2012 → 06/07/2012

Navn	Lecture Notes in Computational Science and Engineering
Vol/bind	97
ISSN	1439-7358

Emneord

Hierarchization algorithm
Sparse grids
High dimension
Cache-friendly
Sparse matrices

Adgang til dokumentet

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

Citationsformater

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

keywords = "Hierarchization algorithm, Sparse grids, High dimension, Cache-friendly, Sparse matrices, Hierarchization algorithm, Sparse grids, High dimension, Cache-friendly, Sparse matrices",

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

}

Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout. / Jacob, Riko.
Sparse Grids and Applications - Munich 2012. Bind 97 Springer, 2012. s. 195-219 (Lecture Notes in Computational Science and Engineering, Bind 97).

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

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.

KW - Hierarchization algorithm

KW - Sparse grids

KW - High dimension

KW - Cache-friendly

KW - Sparse matrices

KW - Hierarchization algorithm

KW - Sparse grids

KW - High dimension

KW - Cache-friendly

KW - Sparse matrices

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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater