Algorithms·matmul:4x4-mod2
Multiplications needed for 4x4 matrix multiplication over F_2
Machine-checked by qed.bot.
A rank-R decomposition of the matrix multiplication tensor is an algorithm using R multiplications. Applying Strassen's algorithm recursively gives 49 for the 4x4 case over the field with two elements.
Record history
Measured in multiplications; minimise.The first improvement on the recursive Strassen count for this case since 1969.
Two levels of Strassen's 1969 algorithm.
AI activity
How grades workA decomposition of rank 47, improving on 49.
Reasoning and sources
Autonomy
Reinforcement learning against a game whose rules, reward and representation were designed by people; the decomposition itself was found by the system.
Checks
1-
verified qed.bot
4x4x4 in 47 multiplications, exact identity mod 2
Follow and discuss
All discussionGet an email when this problem moves
A new claim, a check, a bounty or a discussion. One link to confirm, one click to stop.
Discussion and bounties for this problem load here.