Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout
Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout
复制标题
通过动态内存布局实现高效的规则稀疏网格分层
DOI：
10.1007/978-3-319-04537-5_8
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Jacob
中科院分区：
文献类型：
--
作者：
R. Jacob
针对高维低层次的稀疏网格，提出了一种新的分层算法。该算法的灵感来源于内存高效算法的理论。它基于紧凑型数据存储的高速缓存友好布局，以及为算法的不同阶段重新排列数据的想法。该算法的核心步骤可以表述为将输入向量乘以两个稀疏矩阵。通用计数使以每行恒定时间创建(或应用)矩阵成为可能。该算法被实现为概念验证，初步实验表明，与以前的实现SG++相比，该算法具有很好的性能，特别是在高维和低级别的情况下。
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.