Source-linked AI summary
The 2M Multiplication Algorithm for Complex Matrices
Peter Caday
TL;DR
Complex matrix multiplication traditionally requires four real GEMMs, while 3M reduces this to three but remains above the scalar multiplication lower bound. This paper introduces 2M for integer-valued complex matrices, extends it through Ozaki-II to floating-point GEMMs, and reports practical speedups approaching the predicted two-GEMM cost.
Problem
Complex matrix multiplication uses four real GEMMs, and although 3M reduces this to three, scalar complex products show that three real multiplications is minimal only in the scalar setting.
Method
2M uses a suitable odd modulus with a square root of −1 modulo that modulus to reduce complex GEMMs to two real GEMMs, and substitutes this multiplication into Ozaki-II for floating-point inputs.
Results
2M reduces complex GEMMs to two real GEMMs of the same size and achieves practical speedups close to theoretical predictions; with N=16, it is up to 8× faster than reference 4M fp64 ZGEMM and averages 1.84× the effective TF/s of Ozaki-II DGEMM at equal accuracy.
Takeaways & Limitations
The approach provides practical complex GEMM and rank-k update algorithms using fewer real matrix multiplications, with floating-point performance close to twice the cost of a real GEMM.
Takeaways & Limitations
The available 2M moduli can be exhausted when additional precision is required, such as for inputs with a large exponent span; hybrid 2M/3M moduli may then be needed.
Abstract
from arXiv · showhide
Complex matrix multiplication is typically computed using 4 real matrix multiplications (GEMMs) of the same size. The well-known 3M multiplication algorithm reduces this cost to 3 real GEMMs, together with quadratic time pre- and post-processing steps. In this paper, we reduce 3M to 2M for matrices with integer real and imaginary parts, performing complex GEMM with only 2 real GEMMs of the same size, along with quadratic time pre- and post-processing. For floating-point matrices, 2M multiplication combines naturally with the Ozaki-II scheme, yielding a practical, high-performance algorithm for computing a complex floating-point GEMM in roughly twice the time of a real GEMM of the same size. As corollaries, we derive new algorithms for symmetric rank-$k$ updates (SYRK/HERK) that internally use full rectangular GEMMs.
1 Introduction
Complex matrix multiplication conventionally uses four real matrix multiplications, while 3M reduces this to three but may reduce numerical stability in floating-point arithmetic. The paper motivates improving on this matrix-level limit despite three multiplications being minimal for scalar complex products.
- The classical 4M algorithm expands complex matrix multiplication into four real matrix multiplications.
- 3M reduces the cost to three real matrix multiplications by first forming A_r + A_i and B_r + B_i.
- Floating-point additions in 3M can reduce numerical stability, so numerical libraries typically expose 3M as an opt-in feature.
- Three real multiplications are minimal for scalar complex products, but the paper investigates whether matrix products can do better.
2 2M Complex Multiplication
2M computes integer-part complex matrix products modulo a specially chosen odd modulus whose square root of −1 provides a real surrogate for i. Preprocessing, two real matrix multiplications, and modular reconstruction recover the complex result with quadratic additional work.
- 2M applies to matrices with integer real and imaginary parts by choosing an odd modulus m large enough to recover the product from its residue.
- A 2M modulus is an odd product of primes congruent to 1 modulo 4 that admits an integer s satisfying s^2 = −1 mod m.
- The preprocessing forms A_± = A_r ± sA_i and B_± = B_r ± sB_i modulo m before the two real multiplications.
- Equations (2a–2c) complete the algorithm by combining the two modular products and recovering the complex result.
- The algorithm adds Θ(mn + mk + nk) scalar operations beyond the matrix multiplications.
- Algebraically, the method uses quotient-ring isomorphisms and the Chinese remainder theorem to represent complex residues as real modular computations.
3 2M Multiplication In Floating Point
The paper combines 2M multiplication with Ozaki-II by quantizing complex floating-point inputs to integers, reducing products modulo suitable moduli, and reconstructing results with CRT. This yields a complex floating-point GEMM method that can use 2M after modular reduction, with hybrid 2M/3M variants when needed.
- The Ozaki-II Scheme: Ozaki-II quantizes floating-point inputs to integers, computes modular matrix products, and reconstructs the result with the Chinese remainder theorem.Accuracy depends primarily on the product M of the chosen coprime moduli, with relative elementwise error roughly O(M^-1/2).
- Complex Ozaki-II With 2M: 2M Ozaki-II interprets the computation over Gaussian integers with conjugate pairs of complex integer moduli, while hardware-supported narrow-precision products provide the speed advantage.The chosen moduli are constrained by the input range of the available matrix multiplication units.
- Complex Ozaki-II With 2M: Complex Ozaki-II separately quantizes the real and imaginary parts, performs modular products, and reconstructs both parts using CRT.Scaling factors can be selected using extensions of existing real-valued algorithms.
- Complex Ozaki-II With 2M: Substituting 2M for 3M after modular reduction produces a 2M Ozaki-II algorithm for complex floating-point GEMMs.The substitution is valid because 3M is an algebraic identity that remains valid modulo each modulus.
- Complex Ozaki-II With 2M: Hybrid Ozaki-II uses 2M for odd moduli with a square root of −1 and 3M for the remaining moduli.This approach can reach higher precision when too few valid 2M moduli are available.
- Other 2M Ozaki-II Variants: The method extends to other imaginary quadratic number rings, changing the set of valid 2M moduli and potentially affecting practical performance.Asymptotically, half of all primes are valid 2M moduli for any fixed imaginary quadratic number ring, while hardware bounds matter in practice.
4 ZGEMM with 8-bit Integer GEMMs
The section applies 2M multiplication to integer-emulated complex GEMMs and derives symmetric-update algorithms using full GEMMs while preserving expected speedups.
- ZGEMM with 8-bit Integer GEMMs: 16 moduli with product M≈2^117 often achieve accuracy comparable to standard double-precision ZGEMM.The 2M modulus set is sparser than the real Ozaki-II set, which needs 15 moduli for the same M≈2^117.
- ZGEMM with 8-bit Integer GEMMs: Restricted 2M moduli can exhaust available precision for large exponent spans, motivating a hybrid 2M/3M extension.The complete 2M set has product M≈2^152, below real Ozaki-II’s M≈2^342.
- Symmetric rank-k updates: The method supports efficient SYRK, HERK, SYR2K, and HER2K implementations through complex reformulations and residue-domain additions.Real SYRK converts to an HERK problem with half the k dimension, and SYR2K similarly converts to HER2K.
- Symmetric rank-k updates: 2M exploits Hermitian symmetry to compute symmetric products with full, unmasked GEMMs while maintaining the expected 2x speedup.The induced symmetry among real integer products permits computing only half as many integer GEMMs.
6 Computational Results
Experiments on an NVIDIA B200 GPU show that 2M ZGEMM reaches Ozaki-II accuracy trends and substantially improves performance over 4M, 3M, and real Ozaki-II baselines.
- Accuracy: 2M ZGEMM’s accuracy converges similarly to real Ozaki-II DGEMM as the modulus count increases.For the tested integer arithmetic, the choice among 2M, 3M, and 4M does not affect accuracy.
- Experimental setup: Performance is evaluated across square problem sizes using effective teraflops per second based on the baseline ZGEMM operation count.The experiments use N=16 moduli for the size sweep.
- Performance: At N=16, 2M ZGEMM is up to 8× faster than reference 4M fp64 ZGEMM and 1.4–1.5× faster than GEMMul8’s 3M ZGEMM.It also averages a 1.84× effective-TF/s speedup over Ozaki-II DGEMM at the same accuracy, costing approximately 2.16 DGEMMs in absolute time.
- Performance: At N=8 and m=n=k=16384, 2M reaches up to 570 TF/s, or 15× the reference ZGEMM performance.Across modulus counts, it shows similar speedups over GEMMul8’s 3M ZGEMM and Ozaki-II DGEMM.
7 Conclusion
The paper combines integer quantization with algebraic structure to reduce complex GEMMs to two real GEMMs and extends the approach to rank-k updates.
- Conclusion: Integer quantization and narrow-precision integer GEMMs provide the computational basis for accelerating floating-point GEMMs.The Ozaki-II scheme exploits hardware trends in which narrow-precision GEMM throughput outpaces traditional single- and double-precision arithmetic.
- Conclusion: 2M multiplication reduces a complex GEMM to two same-size real GEMMs instead of the three or four required by previous algorithms.The method adds quadratic-time pre- and post-processing and achieves practical speedups close to theoretical predictions.