Commutative matrix multiplication algorithm by 
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21A "commutative matrix multiplication algorithm" is a matrix multiplication algorithm that requires the ring to be commutative. Such algorithms are inferior because you cannot use them to create more efficient algorithms for general matrix matrix multiplication by decomposing the bigger matrix into smaller ones.
For example, the Strassen algorithm is based on reduction to non-commutative 2x2 matrix multiplication optimized to be done in 7 multiplications rather than 8 as in the native algorithm.
For 3x3 matrix multiplication, the best algorithms as of 2025 are:and beating the Strassen algorithm using 3x3 matrices would require a non-commutative algorithm with 21 multiplications.
- commutative: 21 multiplications
- non-commutative: 23 multiplications
Blog post: deepmind.google/discover/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/
Whitepaper: storage.googleapis.com/deepmind-media/DeepMind.com/Blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/AlphaEvolve.pdf
Basically they require users to hand-code a metric and provide a program skeleton with some parts of the code marked to be replaced, and then the system focuses on modifying the code regions in question to optimize the metric.
All the novel results they announced were in constraint satisfaction problems or optimization problem. Their results are still awesome, but it's not very different from AlphaGo style things.
Multiplication of matrices of specific size by Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21DeepMind likes coming up with new improved algorithms for these more specific cases, e.g. it was announced in 2025 that AlphaEvolve found a novel 4x4 complex valued algorithm that uses 48 multiplications.
Bibliography:
- fmm.univ-lille.fr/ attempts to keep an up-to-date list for various sizes
Steve Jobs' Apple-1 sells for $945k
. Source. Semiconductor device fabrication bibliography by Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Saint Eligius by Petrus Christus
. Source. Eligius pool is named after Saint Eligius, patron of goldsmiths and miners[ref]
Magic: The Gathering is Turing complete by Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21Related: Antihydra in Magic: The Gathering.
Updates Translation of Xi Jinping saying those against raise their hands by Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21 Updates Understanding the state of 3x3 matrix multiplication by Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21
Ciro Santilli 37 Updated 2025-05-26 +Created 2025-05-21After yet another awesome announcement by DeepMind that it had improved theoretical 4x4 matrix multiplication reducing the number of scalar multiplications with its AlphaEvolve system, I decided to have a look at the smallest open size 3x3 to understand what was going on in there.
Unlisted articles are being shown, click here to show only listed articles.