Hierarchical Tucker Low-Rank Matrices: Construction and Matrix-Vector Multiplication

2025/08/08 by Li, Yingzhou, Liu, Jingyu · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2508.05958

Abstract

In this paper, a hierarchical Tucker low-rank (HTLR) matrix is proposed to approximate non-oscillatory kernel functions in linear complexity. The HTLR matrix is based on the hierarchical matrix, with the low-rank blocks replaced by Tucker low-rank blocks. Using high-dimensional interpolation as well as tensor contractions, algorithms for the construction and matrix-vector multiplication of HTLR matrices are proposed admitting linear and quasi-linear complexities respectively. Numerical experiments demonstrate that the HTLR matrix performs well in both memory and runtime. Furthermore, the HTLR matrix can also be applied on quasi-uniform grids in addition to uniform grids, enhancing its versatility.

Citations

• A Linear-complexity Tensor Butterfly Algorithm for Compressing High-dimensional Oscillatory Integral Operators
• RTSMS: Randomized Tucker with single-mode sketching
• Distributed-memory H-matrix Algebra I: Data Distribution and Matrix-vector Multiplication
• Randomized algorithms for low-rank tensor decompositions in the Tucker\n format
• A parallel non-uniform fast Fourier transform library based on an\n "exponential of semicircle" kernel
• Hierarchical interpolative factorization for elliptic operators: integral equations
• An O(N) Direct Solver for Integral Equations on the Plane
• A direct solver with O(N) complexity for integral equations on\n one-dimensional domains
• Tensor Decompositions and Applications
• A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators

Cited by

• Parametric Hierarchical Matrix Approximations to Kernel Matrices

Related

• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• An efficient method for block low-rank approximations for kernel matrix systems
• Parametric kernel low-rank approximations using tensor train decomposition
• On the best approximation of the hierarchical matrix product
• Parametric Hierarchical Matrix Approximations to Kernel Matrices