Matrix multiplication algorithm over F_2 in just O(n^2.81/(log n)^0.4). Create algorithm. But how?

Question

We have a matrix with elements in the field of integers modulo 2 (F_2). We are looking for algorithm that multiply n x n matrix over F_2 in just O(n^2.81/(log n)^0.4)

How it is possible?

I know, that Strassen's algorithm gives O(n^2.81), but how can we get this factor of (log n)^0.4?

Answer 1

You can do following:

Take each possible matrix with dimensions . There are such matrices ().

Precompute multiplication result for these matrices. This gives you table with dimensions . Then in recursion phase of Strassen algorithm, if required matrices for multiplication are small enough you can use precomputed values in this table (if smaller than you could fill appropriate rows and cols with zeros). Let . So you've got following recursion:

Notice, that the recurrence depth is , so you've got:

Using geometric series formula: