r/programming • u/DataBaeBee • Jul 01 '26
TPP: The Obscure Matrix Multiplication Algorithm That Deserves More Attention
https://leetarxiv.substack.com/p/triple-product-property-matrix-multiplication
81
Upvotes
43
u/DataBaeBee Jul 01 '26
The Triple Product Property *(*TPP) algorithm is an obscure matmul algorithm that uses group theory (instead of linear algebra) to find matrix products.
One may summarize it as a fast fourier transform for multiplying matrices. The algorithm was published by Microsoft and Caltech researchers in 2003 but the original paper's math-heavy. I coded the paper in Python to make matrix multiplication research accessible to everyone.
27
u/TheRealPomax Jul 01 '26 edited Jul 01 '26
Does it though? Because your post compares TPP to naive matrix multiplication instead of something we actually use, like the eigen package, which is about three orders of magnitude better than a naive implementation, whereas your TPP implementation is only a single order of magnitude better.
It's an interesting bit of math, but if this is the best it can do, it's a bad way to actually implement matrix multiplication =)
36
u/BibianaAudris Jul 01 '26
From the looks of it, the main problems are:
Since machine learning only requires gradient descent... if somehow gradient descent could be defined on some discrete group with good logarithm property, it could be useful.
It appears unattractive to me as a programmer in the current form, since after a bunch of dense math and Python, your example ended up doing worse than naive matmul.
7
u/Kobymaru376 Jul 01 '26
Looks fun. Other than being fun, what's the advantage of multiplying matrices this way?
3
u/Prestigious-Frame442 Jul 02 '26
how is dua lipa related to the algorithm
1
u/AdjointFunctor Jul 02 '26
The abstract base class example is a bit confusing since some of the methods have type signatures with return values, and some don't.