Data-driven Construction of Hierarchical Matrices with Nested Bases

DOI10.1137/22M1500848arXiv2206.01885MaRDI QIDQ6401097FDOQ6401097

Authors: Difeng Cai, Hua Huang, Edmond Chow, Yuanzhe Xi 

Publication date: 3 June 2022

Abstract: Hierarchical matrices provide a powerful representation for significantly reducing the computational complexity associated with dense kernel matrices. 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 with $O(n)$ complexity for the memory-efficient construction of hierarchical matrices with nested bases where $n$ is the number of data points. HiDR aims to reduce the given data in a hierarchical way so as to obtain $O(1)$ representations for all nearfield and farfield interactions. Based on HiDR, a linear complexity $mathcal{H}^2$ matrix 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. Though the method is not optimized for any special kernel, benchmark experiments for the Coulomb kernel show that the proposed general-purpose algorithm offers competitive performance for hierarchical matrix construction compared to several state-of-the-art algorithms for the Coulomb kernel.

Mathematics Subject Classification ID

Approximation algorithms (68W25) Numerical approximation of high-dimensional functions; sparse grids (65D40)

Cited In (1)

• An adaptive factorized Nyström preconditioner for regularized kernel matrices

This page was built for publication: Data-driven Construction of Hierarchical Matrices with Nested Bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401097)