pith. sign in

arxiv: 2604.09147 · v1 · submitted 2026-04-10 · 🧮 math.NA · cs.NA

Hybrid hierarchical matrices with adaptive mixed precision storage

Ritesh Khan , Erin Carson This is my paper

Pith reviewed 2026-05-10 16:53 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords hierarchical matricesmixed precisionadmissibility conditionsstorage reductionrounding errormatrix vector productadaptive precision
0
0 comments X

The pith

Hybrid hierarchical matrices use a mix of admissibility rules to allow low-precision storage in admissible blocks, reducing memory use by up to 11 times.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proposes H_h-matrices that combine standard admissibility for large blocks with weak admissibility for small blocks. The hybrid rule ensures dense blocks appear only along the diagonal. A rounding error analysis then shows that the low-rank admissible blocks can safely be stored using fewer bits than the working precision. An explicit rule picks the precision for each block to keep the overall error controlled. Tests demonstrate that the resulting mixed-precision matrices use far less storage than conventional double-precision hierarchical matrices while delivering the same accuracy in matrix-vector products.

Core claim

The paper establishes that under the hybrid admissibility condition, the admissible blocks of an H_h-matrix can be stored in reduced precision according to a derived selection rule, yielding a matrix approximation whose error is bounded similarly to the full-precision case, and whose matrix-vector product remains stable, with numerical evidence of storage savings reaching a factor of 11 compared to standard H-matrices.

What carries the argument

The hybrid admissibility condition, combining standard admissibility at coarse levels of the block cluster tree with weak admissibility at fine levels, which confines dense blocks to the diagonal and permits the use of an adaptive precision rule for low-rank blocks.

If this is right

  • The storage requirement for H_h-matrices is lower than for standard H-matrices when the provided criterion is met.
  • Admissible blocks can be represented in precision lower than double without increasing the overall approximation error beyond acceptable levels.
  • The matrix-vector product with the mixed-precision H_h-matrix maintains numerical stability equivalent to the full-precision version.
  • Practical implementations achieve storage reductions of up to 11 times on test problems while preserving accuracy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the hybrid structure generalizes well, similar mixed-precision ideas could apply to other hierarchical formats like H2-matrices.
  • The precision selection rule might be combined with dynamic precision in arithmetic operations beyond storage.
  • Such storage savings could enable larger-scale simulations in applications like boundary element methods where memory limits currently constrain problem size.

Load-bearing premise

The hybrid admissibility condition must confine all dense blocks to the diagonal so that reducing precision only in the admissible blocks does not increase the global approximation error.

What would settle it

Construct an H_h-matrix with the adaptive mixed precision rule and compare its approximation error or matvec accuracy to a standard full-double H-matrix on the same problem; if the hybrid version shows substantially larger error, the claim does not hold.

Figures

Figures reproduced from arXiv: 2604.09147 by Erin Carson, Ritesh Khan.

Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: c [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: a [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 4
Figure 4. Figure 4: b [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: a [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
read the original abstract

Hierarchical matrices are data-sparse approximations of dense matrices that are widely used for fast matrix computations. Hierarchical matrices are built using a tree data structure, with low-rank blocks identified by various admissibility conditions, such as standard admissibility and weak admissibility. This paper introduces a novel hierarchical matrix framework, namely $\mathcal{H}_h$, based on a hybrid admissibility condition: we use the standard admissibility at the coarser levels (larger blocks) and the weak admissibility at the finer levels (smaller blocks). This hybrid strategy confines dense blocks only along the diagonal. We provide a criterion that ensures lower storage cost for $\mathcal{H}_h$-matrices compared to $\mathcal{H}$-matrices under the standard admissibility condition. We carry out a rounding error analysis of $\mathcal{H}_h$-matrices and show that the admissible blocks of $\mathcal{H}_h$-matrices can be represented in low precision (precision lower than the working precision) without degrading the overall approximation quality. We provide an explicit rule for dynamically selecting the precision of a given admissible block, thereby proposing an adaptive mixed precision algorithm for constructing and storing $\mathcal{H}_h$-matrices. Furthermore, we show that the use of mixed precision does not compromise the numerical stability and accuracy of the resulting $\mathcal{H}_h$-matrix-vector product. We perform a range of numerical experiments to validate our theoretical findings. Our numerical results show that the proposed adaptive mixed precision $\mathcal{H}_h$-matrices achieve significant storage reductions (up to $11 \times$) compared with uniform double precision standard admissibility-based $\mathcal{H}$-matrices, without compromising accuracy.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces hybrid hierarchical matrices denoted H_h that employ a hybrid admissibility condition—standard admissibility at coarse levels and weak admissibility at fine levels—to confine dense blocks to the diagonal. It derives a storage-cost criterion guaranteeing lower memory use than standard-admissibility H-matrices, performs a rounding-error analysis justifying representation of admissible blocks in precision lower than working precision, supplies an explicit adaptive rule for choosing block precision, and proves that the resulting mixed-precision H_h matrix-vector product remains stable and accurate. Numerical experiments report storage reductions of up to 11× relative to uniform double-precision standard H-matrices while preserving accuracy.

Significance. If the rounding-error bounds hold for the full matvec, the work supplies a theoretically supported route to substantial memory reduction in hierarchical-matrix approximations, which is valuable for large-scale scientific computing. The combination of hybrid admissibility with an explicit mixed-precision rule, together with the reported storage gains and stability guarantees, represents a concrete advance over uniform-precision H-matrix constructions.

major comments (2)
  1. [§4 (Rounding Error Analysis)] §4 (Rounding Error Analysis): the per-block precision-selection rule is derived from local block size and distance, yet the forward-error bound for the hierarchical matvec does not explicitly propagate rounding errors from the increased number of low-precision admissible blocks admitted by weak admissibility at fine levels; accumulation across the tree could exceed the claimed tolerance without additional controls.
  2. [§5 (Numerical Experiments)] §5 (Numerical Experiments): the reported 11× storage reduction is measured against uniform double-precision standard H-matrices, but the experiments do not include a direct comparison of matvec forward error under the adaptive mixed-precision rule versus a uniform low-precision baseline, leaving open whether the observed accuracy preservation is due to the hybrid structure or simply to the chosen test problems.
minor comments (1)
  1. [§2] Notation for the hybrid admissibility condition should be introduced with a single compact definition rather than distributed across the introduction and §2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below, indicating where revisions will be made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§4 (Rounding Error Analysis)] the per-block precision-selection rule is derived from local block size and distance, yet the forward-error bound for the hierarchical matvec does not explicitly propagate rounding errors from the increased number of low-precision admissible blocks admitted by weak admissibility at fine levels; accumulation across the tree could exceed the claimed tolerance without additional controls.

    Authors: The forward-error analysis in §4 already sums local rounding errors over the full hierarchy, weighting each admissible block by its contribution to the matvec and accounting for the total number of blocks at each level (including those added by weak admissibility). The resulting bound therefore incorporates the effect of the larger number of low-precision blocks. To make the propagation explicit and address the referee’s concern, we will add a short paragraph in the revised §4 that isolates the accumulation factor across the tree and verifies that the adaptive precision rule keeps the total error below the target tolerance. revision: yes

  2. Referee: [§5 (Numerical Experiments)] the reported 11× storage reduction is measured against uniform double-precision standard H-matrices, but the experiments do not include a direct comparison of matvec forward error under the adaptive mixed-precision rule versus a uniform low-precision baseline, leaving open whether the observed accuracy preservation is due to the hybrid structure or simply to the chosen test problems.

    Authors: The storage comparison is deliberately made against uniform double-precision standard H-matrices, the conventional accuracy-preserving baseline. We agree that an explicit comparison against a uniform low-precision baseline would clarify the benefit of the adaptive rule. In the revised manuscript we will add, in §5, forward-error results for the adaptive mixed-precision H_h matvec together with the corresponding errors obtained from a uniform single-precision standard H-matrix on the same test problems. This will show that uniform low precision degrades accuracy while the adaptive selection preserves it. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central contributions—a hybrid admissibility condition (standard at coarse levels, weak at fine), a derived storage-cost criterion, an explicit rounding-error analysis for low-precision admissible blocks, and a dynamic precision-selection rule—are developed from first principles within the manuscript. These steps do not reduce by construction to fitted parameters, self-citations, or renamed inputs; the error bounds and selection rule are stated as derived quantities, and numerical experiments serve only as validation rather than as the source of the claims. No load-bearing self-citation chains or ansatzes smuggled via prior work appear in the provided text. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard properties of low-rank approximations and floating-point rounding but introduces no new free parameters or invented entities; the hybrid admissibility and precision rule are the primary additions.

axioms (2)
  • domain assumption Standard definitions and algebraic properties of hierarchical matrices and admissibility conditions
    Invoked throughout the construction of H_h and the storage comparison.
  • standard math Standard floating-point rounding error bounds for matrix operations
    Used to justify that lower precision in admissible blocks does not degrade overall quality.

pith-pipeline@v0.9.0 · 5593 in / 1452 out tokens · 72588 ms · 2026-05-10T16:53:47.208354+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Abdelf attah, H

    A. Abdelf attah, H. Anzt, E. G. Boman, E. Carson, T. Cojean, J. Dongarra, A. Fox, M. Gates, N. J. Higham, X. S. Li, et al. , A survey of numerical linear algebra meth- ods utilizing mixed-precision arithmetic, The International Journal of High Performance Computing Applications, 35 (2021), pp. 344–369

    work page 2021

  2. [2]

    Abdulah, Q

    S. Abdulah, Q. Cao, Y. Pei, G. Bosilca, J. Dongarra, M. G. Genton, D. E. Keyes, H. Ltaief, and Y. Sun , Accelerating geostatistical modeling and prediction with mixed- precision computations: A high-productivity approach with parsec, IEEE Transactions on Parallel and Distributed Systems, 33 (2021), pp. 964–976

    work page 2021

  3. [3]

    Ambikasaran and E

    S. Ambikasaran and E. Dar ve , An O (N log N ) fast direct solver for partial hierarchically semi-separable matrices, Journal of Scientific Computing, 57 (2013), pp. 477–501

    work page 2013

  4. [4]

    Ambikasaran, K

    S. Ambikasaran, K. R. Singh, and S. S. Sankaran , HODLRlib: A library for hierarchical matrices, Journal of Open Source Software, 4 (2019), p. 1167

    work page 2019

  5. [5]

    Amestoy, O

    P. Amestoy, O. Boiteau, A. Buttari, M. Gerest, F. Jézéquel, J.-Y. L’Excellent, and T. Mary , Mixed precision low-rank approximations and their application to block low-rank LU factorization, IMA Journal of Numerical Analysis, 43 (2023), pp. 2198–2227

    work page 2023

  6. [6]

    Amestoy, A

    P. Amestoy, A. Buttari, J.-Y. L’Excellent, and T. Mary , On the complexity of the block low-rank multifrontal factorization, SIAMJournalonScientificComputing, 39(2017), pp. A1710–A1740. 26 RITESH KHAN, ERIN CARSON

    work page 2017

  7. [7]

    Bebendorf, Hierarchical LU decomposition-based preconditioners for bem, Computing, 74 (2005), pp

    M. Bebendorf, Hierarchical LU decomposition-based preconditioners for bem, Computing, 74 (2005), pp. 225–247

    work page 2005

  8. [8]

    Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Springer, 2008

    M. Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Springer, 2008

    work page 2008

  9. [9]

    Börm, Construction of data-sparseH2-matrices by hierarchical compression, SIAM Journal on Scientific Computing, 31 (2009), pp

    S. Börm, Construction of data-sparseH2-matrices by hierarchical compression, SIAM Journal on Scientific Computing, 31 (2009), pp. 1820–1839

    work page 2009

  10. [10]

    S. Börm, L. Grasedyck, and W. Hackbusch , Hierarchical matrices, Lecture notes, 21 (2003), p. 2003

    work page 2003

  11. [11]

    Carson, X

    E. Carson, X. Chen, and X. Liu , Mixed precision HODLR matrices, SIAM Journal on Scientific Computing, 47 (2025), pp. A1408–A1435

    work page 2025

  12. [12]

    Chandrasekaran, P

    S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals , A fast solver for HSS representations via sparse matrices, SIAM Journal on Matrix Analysis and Applications, 29 (2007), pp. 67–81

    work page 2007

  13. [13]

    Gillman, P

    A. Gillman, P. M. Young, and P.-G. Martinsson , A direct solver withO(N ) complexity for integral equations on one-dimensional domains, Frontiers of Mathematics in China, 7 (2012), pp. 217–247

    work page 2012

  14. [14]

    Grasedyck and W

    L. Grasedyck and W. Hackbusch , Construction and arithmetics ofH-matrices, Comput- ing, 70 (2003), pp. 295–334

    work page 2003

  15. [15]

    Grasedyck, R

    L. Grasedyck, R. Kriemann, and S. Le Borne , Domain decomposition based-lu precondi- tioning, Numerische Mathematik, 112 (2009), pp. 565–600

    work page 2009

  16. [16]

    Gray and A

    A. Gray and A. Moore , N-body’problems in statistical learning, Advances in neural infor- mation processing systems, 13 (2000)

    work page 2000

  17. [17]

    Greengard and V

    L. Greengard and V. Rokhlin , A fast algorithm for particle simulations, Journal of com- putational physics, 73 (1987), pp. 325–348

    work page 1987

  18. [18]

    Hackbusch , A sparse matrix arithmetic based on H-matrices

    W. Hackbusch , A sparse matrix arithmetic based on H-matrices. part i: Introduction to H-matrices, Computing, 62 (1999), pp. 89–108

    work page 1999

  19. [19]

    49, Springer, 12 2015

    , Hierarchical Matrices: Algorithms and Analysis, vol. 49, Springer, 12 2015

    work page 2015

  20. [20]

    Hackbusch and B

    W. Hackbusch and B. N. Khoromskij , A sparse H-matrix arithmetic. part ii: Application to multi-dimensional problems, Computing, 64 (2000), pp. 21–47

    work page 2000

  21. [21]

    Hackbusch, B

    W. Hackbusch, B. N. Khoromskij, and R. Kriemann , Hierarchical matrices based on a weak admissibility criterion, Computing, 73 (2004), pp. 207–243

    work page 2004

  22. [22]

    N. J. Higham , Accuracy and stability of numerical algorithms, SIAM, 2002

    work page 2002

  23. [23]

    N. J. Higham and T. Mary , Mixed precision algorithms in numerical linear algebra, Acta Numerica, 31 (2022), pp. 347–414

    work page 2022

  24. [24]

    N. J. Higham and S. Pranesh , Simulating low precision floating-point arithmetic, SIAM Journal on Scientific Computing, 41 (2019), pp. C585–C602

    work page 2019

  25. [25]

    K. L. Ho and L. Ying , Hierarchical interpolative factorization for elliptic operators: integral equations, arXiv preprint arXiv:1307.2666, (2013)

    work page Pith review arXiv 2013

  26. [26]

    Huang, Q.-Y

    G.-B. Huang, Q.-Y. Zhu, and C.-K. Siew , Extreme learning machine: theory and applica- tions, Neurocomputing, 70 (2006), pp. 489–501

    work page 2006

  27. [27]

    R. Khan, V. A. Kandappan, and S. Ambikasaran , HODLRdD: A new black-box fast algorithm forN-body problems in d-dimensions with guaranteed error bounds: Applications to integral equations and support vector machines, Journal of Computational Physics, 501 (2024), p. 112786

    work page 2024

  28. [28]

    N. M. Kriege, F. D. Johansson, and C. Morris , A survey on graph kernels, Applied Network Science, 5 (2020), pp. 1–42

    work page 2020

  29. [29]

    Kriemann, Performance ofH-matrix-vector multiplication with floating point compression, arXiv preprint arXiv:2405.03456, (2024)

    R. Kriemann, Performance ofH-matrix-vector multiplication with floating point compression, arXiv preprint arXiv:2405.03456, (2024)

    work page arXiv 2024

  30. [30]

    B763–B784

    , Hierarchical low-rank arithmetic with floating point compression, SIAM Journal on Scientific Computing, 47 (2025), pp. B763–B784

    work page 2025

  31. [31]

    Mary, Approximate computing in numerical linear algebra: algorithms, analysis, and ap- plications, PhD thesis, Sorbonne Université, 2025

    T. Mary, Approximate computing in numerical linear algebra: algorithms, analysis, and ap- plications, PhD thesis, Sorbonne Université, 2025

    work page 2025

  32. [32]

    Massei, L

    S. Massei, L. Robol, and D. Kressner , hm-toolbox: Matlab software for HODLR and HSS matrices, SIAM Journal on Scientific Computing, 42 (2020), pp. C43–C68

    work page 2020

  33. [33]

    ,Hierarchical adaptive low-rank format with applications to discretized partial differential equations, Numerical Linear Algebra with Applications, 29 (2022), p. e2448

    work page 2022

  34. [34]

    R. Ooi, T. Iw ashita, T. Fukaya, A. Ida, and R. Yokota ,Effect of mixed precision comput- ing on H-matrix vector multiplication in bem analysis, in Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region, 2020, pp. 92–101

    work page 2020

  35. [35]

    J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li , Fast algorithms for hierarchically semiseparable matrices, Numerical Linear Algebra with Applications, 17 (2010), pp. 953– 976. HYBRID HIERARCHICAL MATRICES WITH ADAPTIVE PRECISION STORAGE 27 Appendix A. Proof of Lemma 4.2. In this section, we prove Lemma 4.2, which gives a bound on the approximation error ...

    work page 2010