A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914171636940800 |
|---|---|
| author | Dumas, Jean-Guillaume Pernet, Clément Sedoglavic, Alexandre |
| author_facet | Dumas, Jean-Guillaume Pernet, Clément Sedoglavic, Alexandre |
| contents | The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two $4\times4$ matrices was first reduced in \cite{Fawzi:2022aa} from 49 (two recursion levels of Strassen's algorithm) to 47 but only in characteristic 2 or more recently to 48 in \cite{alphaevolve} but over complex numbers. We propose an algorithm in 48 multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in $7 n^{2+\frac{\log_2 3}{2}} +o\left(n^{2+\frac{log_2 3}{2}}\right)$ operations over any ring containing an inverse of 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13242 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications Dumas, Jean-Guillaume Pernet, Clément Sedoglavic, Alexandre Symbolic Computation The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two $4\times4$ matrices was first reduced in \cite{Fawzi:2022aa} from 49 (two recursion levels of Strassen's algorithm) to 47 but only in characteristic 2 or more recently to 48 in \cite{alphaevolve} but over complex numbers. We propose an algorithm in 48 multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in $7 n^{2+\frac{\log_2 3}{2}} +o\left(n^{2+\frac{log_2 3}{2}}\right)$ operations over any ring containing an inverse of 2. |
| title | A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2506.13242 |