Sharper Bounds on the Required Fixed-Point Precision for Emulating Floating-Point Matrix Multiplication

Abstract

Precision emulation algorithms, such as the Ozaki schemes, can leverage low-precision matrix multiply–accumulate to approximate the product \(AB\) , where \(A\) and \(B\) are high-precision floating-point matrices, via fixed-point arithmetic. A key difficulty of these approaches is that achieving a target floating-point precision \(p\) requires a fixed-point bit width \(w=p+\star\) , where the required number of extra bits \(\star\) depends strongly on the matrix coefficients. The exponent span capacity (ESC), recently introduced in the literature, is an upper bound \(\overline{e}\geq\star\) . For square matrices of order \(n\) , the ESC can be estimated with \(O(n^{2}k)\) operations, where the parameter \(k\) can be increased to improve the sharpness of \(\overline{e}\) . We show that this bound can be very pessimistic, and that for the estimator to be useful, \(k\) must scale with \(n\) , effectively incurring an \(O(n^{3})\) overhead. Building on a rigorous error analysis, we then derive a new formula for \(\star\) , which corroborates the previously proposed formula up to a few bits. We propose an alternative, sharper bound, which can be computed with \(O(n^{2}k)\) operations, where \(k\) becomes independent of \(n\) . Our numerical experiments demonstrate that the current approach can substantially overestimate \(\star\) in many cases, whilst our new approach is almost perfectly sharp even for moderate values of \(k\) . We present strategies for handling matrices with zero coefficients and give a refined formulation for \(\star\) , in which different fixed-point bit widths are used for \(A\) and \(B\) . Overall, this work provides rigorous theoretical accuracy guarantees for fixed-point emulation and a practical algorithm to inexpensively yet sharply determine the required fixed-point bit width.