News for hackers. Stuff that matters.

A comment on Limits on Matrix Multiplication. Parent comment

Re:Limits on Matrix Multiplication by wbhart on Saturday September 01, 2018 @09:28AM (#17891735)
Is it yet known what the optimal sequence is for 3x3 matrix multiplication (for noncommuting entries, of course)?
[ Parent | on HN ]
Re:Limits on Matrix Multiplication by wLMeOv2qjsFOjZG on Saturday September 01, 2018 @11:34AM (#17892285)
No!
[ Parent | on HN ]
Re:Limits on Matrix Multiplication by stochastic_monk on Saturday September 01, 2018 @01:44PM (#17893003)
Wouldn’t this be easy to explore exhaustively? 27! is ~1e26, but most of these orderings are obviously terrible ideas.
[ Parent | on HN ]
Re:Limits on Matrix Multiplication by wLMeOv2qjsFOjZG on Sunday September 02, 2018 @06:07AM (#17896416)
For 2x2 matrix multiplication, it is known that Strassen's algorithm is optimal in the sense that there exists no algebraic circuit that uses only 6 "scalar" multiplications. I took your question to ask whether for 3x3 matrix multiplication, the minimum number of scalar multiplications required was similarly known. It is not, and there are more options to take into account than just orderings.
[ Parent | on HN ]