Parallel Fast Gauss Transform
Parallel Fast Gauss Transform
复制标题
并行快速高斯变换
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Veerapaneni
中科院分区：
文献类型：
--
作者：
R. Sampath;H. Sundar;S. Veerapaneni
我们提出快速自适应并行算法来计算 N 个点处的 N 高斯之和。直接顺序计算该总和将花费 $O(N^2)$ 时间。我们算法的并行时间复杂度估计为 $O(N/np)$（对于均匀点分布）和 $O(N/np log N/np + nplognp)$（对于使用 np CPU 的非均匀分布）。我们结合了高斯核的平面波表示，它允许“对角线平移”。我们使用并行八叉树和一种新的平面波转换方案来有效地处理非均匀分布。使用橡树岭国家实验室 Jaguar 超级计算机上的 4096 个内核，以 1200 亿个点计算出六位数精度的变换大约需要 140 秒。我们的实现是独立于内核的，即使在内核的显式分析表达式未知的情况下，也可以处理其他“高斯型”内核。这些算法形成了一类新的核心计算机制，用于在大规模并行架构上求解抛物线偏微分方程。
We present fast adaptive parallel algorithms to compute the sum of N Gaussians at N points. Direct sequential computation of this sum would take $O(N^2)$ time. The parallel time complexity estimates for our algorithms are $O(N/np)$ for uniform point distributions and $O(N/np log N/np + nplognp)$ for nonuniform distributions using np CPUs. We incorporate a planewave representation of the Gaussian kernel which permits “diagonal translation”. We use parallel octrees and a new scheme for translating the plane-waves to efficiently handle nonuniform distributions. Computing the transform to six-digit accuracy at 120 billion points took approximately 140 seconds using 4096 cores on the Jaguar supercomputer at the Oak Ridge National Laboratory. Our implementation is kernel-independent and can handle other “Gaussian-type” kernels even when an explicit analytic expression for the kernel is not known. These algorithms form a new class of core computational machinery for solving parabolic PDEs on massively parallel architectures.
影响因子：
4.6
作者：
J. Xu
通讯作者：
J. Xu