🔢 mathematics

Error Analysis of Matrix Multiplication Emulation Using Ozaki-II Scheme

This paper presents a rigorous deterministic error analysis of the Ozaki-II scheme for high-precision matrix multiplication, clarifying its accuracy limitations under wide exponent distributions and providing a method to estimate the necessary number of low-precision operations to achieve a desired precision level.

Original authors: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuki Uchino, Katsuhisa Ozaki, Toshiyuki Imamura

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Building a Giant Wall with Tiny Bricks

Imagine you are an architect trying to build a massive, incredibly precise wall (a high-precision calculation) using only tiny, rough bricks (low-precision computer chips).

Modern computers, especially those designed for Artificial Intelligence, are incredibly fast at handling these "tiny, rough bricks" (specifically, 8-bit integers). However, they are slow or less efficient at handling "giant, smooth bricks" (standard high-precision numbers like 32-bit or 64-bit floats).

The Ozaki-II scheme is a clever construction method that lets you build a perfect high-precision wall using only those fast, tiny bricks. The authors of this paper have created a blueprint (error analysis) to prove exactly how strong and accurate this wall will be, and how many tiny bricks you need to use to get the job done right.

The Problem: The "Wide Range" Issue

In previous tests, this method worked great, but there was a catch. If the numbers you were multiplying had a "wide range" (some were huge, some were tiny), the wall sometimes developed cracks. To fix this, you had to use so many tiny bricks that the process became slow again.

The authors wanted to know: Exactly how many bricks do we need to guarantee a perfect wall, no matter how wide the range of numbers is?

The Solution: The "Chinese Remainder Theorem" Magic Trick

To solve this, the Ozaki-II scheme uses a mathematical magic trick called the Chinese Remainder Theorem (CRT).

The Analogy: The Secret Code Lockers
Imagine you want to know the exact weight of a giant elephant, but your scale can only weigh small items (up to 100 lbs).

You put the elephant in a locker that only shows the weight mod 7 (the remainder when divided by 7).
You put it in another locker that shows the weight mod 11.
You put it in a third that shows mod 13.

Even though each locker only gives you a tiny, confusing remainder, if you know the remainders for several different "moduli" (7, 11, 13, etc.), you can mathematically reconstruct the exact total weight of the elephant.

The Ozaki-II scheme does this with matrices (grids of numbers):

Slicing: It breaks the big numbers down into smaller pieces that fit into the tiny 8-bit bricks.
Modulo Math: It calculates the result using these small pieces in many different "locks" (using different prime numbers).
Reassembly: It uses the CRT to stitch all those small results back together into one giant, precise answer.

What This Paper Actually Does: The "Safety Inspector"

While we knew this method could work, we didn't have a rigorous rulebook for how well it would work in every situation. This paper acts as the Safety Inspector.

The authors performed a deterministic error analysis. This means they didn't just guess or run random tests; they used strict math to write down a formula that predicts the maximum possible "crack" (error) in the final wall.

Key Findings from the Inspection:

The Formula: They derived a specific equation that tells you exactly how accurate the result will be based on two things:
1. The "width" of the numbers you are multiplying (the exponent distribution).
2. The number of "locks" (moduli) you used.
The Trade-off: The paper proves that if the numbers are very "wide" (some huge, some tiny), you simply need to increase the number of locks (moduli) to keep the error small.
Validation: They tested this formula on a powerful NVIDIA GPU (an RTX 4090). The actual errors they saw in the computer were always smaller than the "worst-case" numbers predicted by their formula. This proves their safety blueprint is accurate and reliable.

Why This Matters (According to the Paper)

The paper claims this analysis is a foundation for automatic tuning.

Think of it like a self-driving construction crew. Before, a human had to guess how many bricks to use. Now, with this formula, the computer can look at the numbers it's about to multiply, calculate the "width" of the data, and automatically decide: "Okay, for this specific job, I need 15 locks to be safe. For that other job, I only need 5."

This allows the computer to get the highest possible speed without sacrificing accuracy, ensuring that the "tiny brick" method is both fast and trustworthy for scientific computing.

Summary

The Goal: Use fast, low-precision computer chips to do slow, high-precision math.
The Method: Use a mathematical trick (CRT) to combine many small, simple calculations into one big, precise one.
The Paper's Contribution: It provides a strict mathematical guarantee (an error bound) that tells us exactly how accurate the result will be and how many small calculations are needed to achieve a desired level of precision.
The Result: The method is proven to be reliable, and the new formula allows computers to automatically adjust their settings to get the best balance of speed and accuracy.

Technical Summary: Error Analysis of Matrix Multiplication Emulation Using Ozaki-II Scheme

Problem Statement
Modern AI hardware, particularly GPUs equipped with INT8 matrix engines, offers exceptional throughput for low-precision arithmetic, significantly outperforming native single- (FP32) and double-precision (FP64) floating-point operations. However, classical high-performance computing (HPC) and many machine learning workloads require the numerical reliability of higher precision. While emulation methods exist to reconstruct high-precision results using sequences of low-precision operations, the accuracy of these methods is not guaranteed across all input distributions. Specifically, the Ozaki-II scheme, which leverages the Chinese Remainder Theorem (CRT) to emulate matrix multiplication, has demonstrated high performance but lacks a rigorous deterministic error analysis. Previous studies noted that the scheme's accuracy degrades when input matrices possess a wide exponent distribution, necessitating a large number of low-precision multiplications to maintain precision. Without a theoretical bound, it is difficult to determine the number of moduli required to achieve a specific accuracy target.

Methodology
The paper presents a rigorous deterministic error analysis for the Ozaki-II scheme applied to General Matrix-Matrix Multiplication (GEMM) in both single (SGEMM) and double (DGEMM) precision. The methodology involves:

Formalizing the Ozaki-II Scheme: The authors detail the emulation process, which converts floating-point matrices $A$ and $B$ into integer matrices $A'$ and $B'$ via diagonal scaling and truncation. These integers are then decomposed modulo pairwise coprime integers $p_\ell$ . The products are computed using INT8 matrix engines, and the results are reconstructed using the CRT to form an integer approximation of the product, which is finally rescaled to floating-point format.
Deriving Error Bounds: The authors decompose the total error into three primary components:
- Truncation Error: Arising from the conversion of floating-point inputs to scaled integers.
- Accumulation Error: Resulting from the summation of modular products in high-precision floating-point arithmetic.
- Final Reduction Error: Occurring during the CRT reconstruction and rescaling steps.
Theoretical Proofs: The paper provides formal proofs for a series of lemmas establishing the uniqueness of the candidate solution, bounds on truncation and accumulation errors, and the validity of the rounding operations used in the reconstruction. These lemmas culminate in Theorem 2, which provides a deterministic upper bound for the error $|AB - C_b|$ , where $C_b$ is the computed result.
Experimental Validation: Numerical experiments were conducted on an NVIDIA GeForce RTX 4090 GPU. Theoretical error bounds derived from the analysis were compared against observed numerical errors for matrices with varying dynamic ranges (controlled by a parameter $\phi$ ).

Key Contributions

Rigorous Deterministic Error Analysis: The primary contribution is the derivation of a deterministic error bound (Theorem 2) for the Ozaki-II scheme. This bound explicitly relates the numerical error to the exponent distribution of the input matrices and the number of moduli ( $N$ ) used in the CRT.
Refined Bounds: The paper offers two forms of error estimation: a tighter bound (Eq. 16) that depends on the magnitude of the intermediate integer product $|A'B'|$ , and a more conservative but computationally cheaper bound (Eq. 20) that replaces this term with a constant upper bound.
Validation of Accuracy Behavior: The analysis theoretically explains why the scheme's accuracy depends on the input exponent distribution and confirms that increasing the number of moduli reduces truncation error, thereby improving accuracy.
Proof of Correctness for Implementation Details: The authors prove that specific implementation choices, such as the use of double-double arithmetic for constants and the specific handling of INT8 wrapping, do not introduce unbounded errors that would compromise the final result.

Results

Theoretical vs. Observed Error: Numerical experiments on the RTX 4090 demonstrated that the observed emulation errors for both SGEMM and DGEMM are consistently bounded by the theoretical estimates derived in Theorem 2.
Bound Tightness: The tighter bound (Eq. 16) was found to more accurately capture the range of observed errors compared to the conservative bound (Eq. 20). However, the conservative bound was shown to be practical for robust error estimation as it relies only on matrix-vector products rather than computing the potentially expensive $|A'B'|$ .
Comparison with Native Precision: The results illustrated the relative accuracy of the emulation compared to native FP32 and FP64 routines, confirming that the Ozaki-II scheme can achieve high precision when configured with an appropriate number of moduli.

Significance
The paper claims that this error analysis provides a critical foundation for the future development of the Ozaki-II scheme. Specifically, it enables the automatic tuning of accuracy-related parameters, such as the number of moduli, based on the exponent distribution of input matrices to achieve a desired level of numerical accuracy. By clarifying the relationship between input characteristics and numerical reliability, the analysis addresses the gap between the scheme's high performance and its variable accuracy, making it more viable for general-purpose high-precision computing on modern AI hardware. The authors note that this analytical framework could also be extended to complex-valued matrix multiplication emulation in future work.