HEXAGONbeta

Improved basis-change transformations for 2×22 \times 2 matrix multiplication

Primarily human-written textHuman understanding: all partscs.DS — Data Structures and Algorithms

Contributed by Hugo Nielsen ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

To the best of our knowledge, we present a state-of-the-art change-of-basis algorithm for 2×22 \times 2 matrix multiplication under the Karstadt--Schwartz-style basis change regime [1]. We do this by introducing basis-change matrices BUB_U, BVB_V, and BWB_W that each require only a single addition and hence give rise to a matrix-multiplication algorithm performing 5nlog⁡27−4n2+34n2log⁡2n,5n^{\log_2{7}} - 4n^2 + \frac{3}{4}n^2 \log_2{n}, arithmetic operations when multiplying two n×nn \times n matrices, with nn a power of 22. This improves on the previous best bound, which had last term 32n2log⁡2n\frac{3}{2}n^2\log_2{n}.

Provenance statement

GPT-6-Astra was used to conduct the computational search that identified the main result. The mathematical verification and exposition were carried out and written by the author.

Tools used

OpenAI
ChatGPTVersion GPT-6 Astra

References

  1. barticle Schwartz , O. , Vaknin , N. : Pebbling game and alternative basis for high performance matrix multiplication . SIAM Journal on Scientific Computing 45 ( 6 ), C277--C303 ( 2023 ) url 10.1137/22M1502719 barticleDOI
  2. barticle Karstadt , E. , Schwartz , O. : Matrix multiplication, a little faster . Journal of the ACM 67 ( 1 ), 1 -- 31 ( 2020 ) url 10.1145/3364504 barticleDOI
  3. bchapter Karstadt , E. , Schwartz , O. : Matrix multiplication, a little faster . In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures . SPAA '17 , pp. 101 -- 110 . Association for Computing Machinery , New York, NY, USA ( 2017 ). url 10.1145/3087556.3087579 . https://doi.org/10.1145/3087556.3087579 bchapterDOI
  4. botherref Nielsen , H. : A 52-Addition, Rank-23 Scheme for Exact 3×33 \times 3 Matrix Multiplication (2026). url 10.48550/arXiv.2609.06588 . https://arxiv.org/abs/2609.06588 botherrefDOI
  5. botherref Van Zee , F.G. , Smith , T.M. : Inducing complex matrix multiplication via the 3m and 4m methods. FLAME Working Note 81, The University of Texas at Austin, Austin, TX, USA (October 2016). https://www.cs.utexas.edu/%7Eflame/pubs/flawn81.pdf botherreflink
  6. barticle Bl ä ser , M. : Fast matrix multiplication . Theory of Computing Library, Graduate Surveys 5 , 1 -- 60 ( 2013 ) url 10.4086/toc.gs.2013.005 barticleDOI

Version history

  1. v1Submitted by Hugo NielsenInitial depositCurrentOct 30, 2026