The 2M Multiplication Algorithm for Complex Matrices
Abstract
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.
Related
- On the Supersingular reduction of Cubic fourfolds with Complex Multiplication
- Hartl's dictionary and a transcendence characterization of equicharacteristic local shtukas with complex multiplication
- Bad Reduction of Genus Two Curves with complex multiplication
- Legendre polynomials and complex multiplication, II: class numbers of quadratic fields and genus 2 supersingular polynomials
- On the cyclic limiting behavior of the restarted Arnoldi algorithm for real symmetric matrices with restart length s=2
BibTeX
@misc{caday2026multiplication,
title = {{The 2M Multiplication Algorithm for Complex Matrices}},
author = {Peter Caday},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.05419},
eprint = {2609.05419},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05419},
}
RIS
TY - UNPB
TI - The 2M Multiplication Algorithm for Complex Matrices
AU - Peter Caday
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2609.05419
UR - https://arxiv.org/abs/2609.05419
AB - 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.
ER -