arXiv preprint ·
Integer-Quantized Hierarchical Matrices with Adaptive Bit Allocation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Numerical Analysis
The Rise of Low Precision Floating Point
Beyond atol and rtol: Sound Test Oracles for Low-Precision GPU Kernels
Extensible Programmatic Specification of Finite Element Methods
diff-soup: GPU-native Differentiable Simulation and Inference for Large-scale Stiff Dynamical Systems
A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs
Get the few papers worth your time in Numerical Analysis every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.