H2Pack is a library that provides linear-scaling storage and
linear-scaling matrix-vector multiplication for dense kernel matrices.
This is accomplished by storing the kernel matrices in the
hierarchical block low-rank representation. It can be used for
Gaussian processes, solving integral equations, Brownian dynamics,
and other applications.
The main strength of H2Pack is its ability to efficiently construct
matrices
in linear time for kernel functions used in Gaussian processes (up
to 3-D data) by using a new proxy point method. Kernel functions from
computational physics, e.g., Coulomb, Stokes, can also be used. H2Pack is
optimized for shared-memory multicore architectures, including the use
of vectorization for evaluating kernel functions. H2Pack provides C/C++
and Python interfaces.
Notes
-
H2Pack is designed for general kernel functions, including the Gaussian, Matern, and other kernels used in statistics and machine learning. For these kernels, H2Pack computes the
representation much faster, and with linear complexity, compared to algebraic approaches that rely on rank-revealing matrix decompositions.
-
For standard kernel functions from potential theory, e.g., Coulomb, Stokes, H2Pack using the proxy point method constructs a more efficient representation than approaches based on analytic expansions, like the fast multipole method (FMM), and thus has faster matrix-vector multiplication than FMM. Note that H2Pack requires a preprocessing step to construct the
representation, while FMM does not need a preprocessing step. However, FMM cannot handle general kernel functions.
-
The proxy points only need to be computed once for a given kernel function, domain, and requested accuracy. These proxy points can be reused for different sets of points or data. Constructing the
matrix with these proxy points only requires linear time. Alternatively, the proxy points could be selected on a surface, which corresponds to the proxy surface method that can be useful for kernel functions from potential theory.
Other Features
- Users can provide a function that defines the kernel function or use kernels that are already built into H2Pack. Vector wrapper functions are provided to help users optimize the evaluation of their own kernel functions.
- HSS hierarchical block low-rank representations are also available, including ULV decomposition and solve.
- A Matlab version of H2Pack is available in this repo.
Limitations
- Kernel functions up to 3-dimensions
- Symmetric, translationally-invariant, non-oscillatory kernel functions
- H2Pack currently only supports kernel matrices defined by a single set of points (i.e., square, symmetric matrices)
Main Functions
matrix representation construction for a kernel matrix with O(N) complexity for an N-by-N matrix
matrix-vector multiplication with O(N) complexity
matrix-matrix multiplication with O(N) complexity
References
- H. Huang, X. Xing, and E. Chow, H2Pack: High-performance H2 matrix package for kernel matrices using the proxy point method, ACM Transactions on Mathematical Software, 47(1), Article 3 (2020).
- X. Xing and E. Chow, Interpolative decomposition via proxy points for kernel matrices, SIAM Journal on Matrix Analysis and Applications, 41(1), 221โ243 (2020).
- Installing H2Pack
- Basic Application Interface
- Using and Writing Kernel Functions
- Two Running Modes for H2Pack
- HSS-Related Computations
- Bi-Kernel Matvec (BKM) Functions
- Vector Wrapper Functions for Kernel Evaluations
- Proxy Points and their Reuse
- Python Interface
- H2 Matrix File Storage Scheme (draft)
- Using H2 Matrix File Storage