Data-Driven Construction of Hierarchical Matrices With Nested Bases
Data-Driven Construction of Hierarchical Matrices With Nested Bases
复制标题
具有嵌套基的分层矩阵的数据驱动构建
DOI：
10.1137/22m1500848
复制
发表时间：
2023
影响因子：
3.1
通讯作者：
Xi, Yuanzhe
中科院分区：
文献类型：
--
作者：
Cai, Difeng;Huang, Hua;Chow, Edmond;Xi, Yuanzhe
层次矩阵提供了一个强大的表示显着降低计算复杂性与密集的核矩阵。例如，当核函数与经典椭圆偏微分方程的基本解相关时，快速多极子方法（FMM）及其变体是高效的。对于一般核函数，基于插值的方法被广泛用于构造层次矩阵。本文提出了一种快速层次数据约简（HiDR）方法，用于构造基为嵌套的层次矩阵，其复杂度为. HiDR旨在以分层的方式减少给定的数据，以便获得所有近场和远场相互作用的表示。提出了一种基于HiDR的线性复杂度矩阵构造算法。数据驱动方法的使用使得效率比其他通用方法更高，并且在不访问内核函数的情况下实现了灵活的计算。实验表明，显着提高内存效率的建议数据驱动的方法相比，插值为基础的方法在广泛的内核。对于库仑核，所提出的通用算法提供了竞争力的性能相比，FMM及其变种，如PVFMM。数据驱动的方法不仅适用于一般的内核，而且与PVFMM相比，它的预计算成本要小得多。
Hierarchical matrices provide a powerful representation for significantly reducing the computational complexity associated with dense kernel matrices. For example, the fast multipole method (FMM) and its variants are highly efficient when the kernel function is related to fundamental solutions of classical elliptic PDEs. For general kernel functions, interpolation-based methods are widely used for the efficient construction of hierarchical matrices. In this paper, we present a fast hierarchical data reduction (HiDR) procedure withcomplexity for the memory-efficient construction of hierarchical matrices with nested bases whereis the number of data points. HiDR aims to reduce the given data in a hierarchical way so as to obtainrepresentations for all nearfield and farfield interactions. Based on HiDR, a linear complexitymatrix construction algorithm is proposed. The use of data-driven methods enables better efficiency than other general-purpose methods and flexible computation without accessing the kernel function. Experiments demonstrate significantly improved memory efficiency of the proposed data-driven method compared to interpolation-based methods over a wide range of kernels. For the Coulomb kernel, the proposed general-purpose algorithm offers competitive performance compared to FMM and its variants, such as PVFMM. The data-driven approach not only works for general kernels but also leads to much smaller precomputation costs compared to PVFMM.