Adaptive bit allocation cuts storage for hierarchical matrix compression
Integer-Quantized Hierarchical Matrices with Adaptive Bit Allocation
Mathematical SoftwarePerformance
Summary
Storing large matrices, which are big grids of numbers, usually needs a lot of space. The paper introduces a method that gives more storage bits to important parts of the matrix and fewer bits where less detail is needed. This helps keep the matrix accurate while using less memory overall. The authors tested this with real-world kinds of matrices and showed it saves a lot of storage compared to regular methods.
What this means in practice
- •For computational scientists: Reduce memory usage when simulating physical systems modeled by large boundary element method matrices without losing accuracy.
- •For machine learning engineers: Compress kernel matrices in kernel-based learning algorithms to enable faster training and inference with limited resources.
Authors
Erin Carson, Xinye Chen, Ritesh Khan
Abstract
We present an adaptive bitwidth allocation method for quantizing low-rank factors in hierarchical matrices in order to decrease storage while meeting a given constraint on their reconstruction error. For the bitwidth allocation we formulate a discrete storage minimization problem and show that an optimal assignment can give larger singular values at least as many bits as smaller ones. We further develop a greedy algorithm that meets the specified max-norm quantization error budget. We investigate a hierarchical block partition in which all of the non-diagonal blocks are represented by quantized low-rank factors and only dense blocks remain dense; in this way a global reconstruction bound related to $η_k$ and $R_k$ is obtained, with the former and latter being bounds on the truncation and reconstruction arithmetic errors, respectively. Extensive simulations, carried out with kernel and BEM matrices under block-relative budgets, indicate that the proposed method achieves a reduction in storage of up to $44.3\times$ when compared to storing the complete matrix densely in FP64, and a reduction of up to $5.70\times$ when compared to the FP64 low-rank factors within the same partition, together with measured reconstruction errors that remained below the maximum norm bounds in all the hierarchical tests.