Geometry-Oblivious FMM for Compressing Dense SPD Matrices
Geometry-Oblivious FMM for Compressing Dense SPD Matrices
复制标题
用于压缩密集 SPD 矩阵的几何忽略 FMM
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
Chenhan D. Yu;James Levitt;Severin Reiz;G. Biros
我们提出了GOFMM(几何无关的FMM)，这是一种新的方法，它创建了任意稠密对称正定(SPD)矩阵的分层低阶近似或“压缩”。对于许多应用程序，GOFMM支持在N logN甚至N次内进行近似矩阵-向量乘法，其中N是矩阵大小。压缩需要N个logN存储和工作。总的来说，我们的方案属于分层矩阵逼近方法家族。特别是，它将快速多极子方法(FMM)推广到纯代数设置，只需要采样矩阵条目的能力。既不需要几何信息(即点坐标)，也不需要知道矩阵条目是如何生成的，因此术语“几何模糊”。此外，我们还介绍了一种用于分层矩阵计算的共享内存并行方案，该方案减少了同步障碍。我们给出了关于Intel Knight Landing和Haswell体系结构以及各种矩阵的NVIDIA Pascal体系结构的结果。CCS概念·计算理论$\right tarrow$数值近似算法；草图和采样；·计算数学$\right tarrow$数学软件性能；内核密度估计器；·计算方法$\right tarrow$线性代数算法；并行算法；内核方法；·计算机系统组织$\right tarrow$多核体系结构；异质(混合)系统；
We present GOFMM (geometry-oblivious FMM), a novel method that creates a hierarchical low-rank approximation, or “compression,” of an arbitrary dense symmetric positive definite (SPD) matrix. For many applications, GOFMM enables an approximate matrix-vector multiplication in N logN or even N time, where N is the matrix size. Compression requires N logN storage and work. In general, our scheme belongs to the family of hierarchical matrix approximation methods. In particular, it generalizes the fast multipole method (FMM) to a purely algebraic setting by only requiring the ability to sample matrix entries. Neither geometric information (i.e., point coordinates) nor knowledge of how the matrix entries have been generated is required, thus the term “geometry-obliclious.” Also, we introduce a shared-memory parallel scheme for hierarchical matrix computations that reduces synchronization barriers. We present results on the Intel Knights Landing and Haswell architectures, and on the NVIDIA Pascal architecture for a variety of matrices.CCS CONCEPTS• Theory of computation $\rightarrow$ Numeric approximation algorithms; Sketching and sampling; • Mathematics of computing $\rightarrow$ Mathematical software performance; Kernel density estimators; • Computing methodologies $\rightarrow$ Linear algebra algorithms; Parallel algorithms; Kernel methods; • Computer systems organization $\rightarrow$Multicore architectures; Heterogeneous (hybrid) systems;