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

2025/08/08 by Yingzhou Li, J. Y. Liu, Li, Yingzhou +1 · 2 citations
Computer Science · Mathematics · #Cellular Automata and Applications #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.2508.05958

openalex publication_date 2025/08/08 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

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 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
• Parallel Sparse and Data-Sparse Factorization-based Linear Solvers

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