Complexity of large matrix multiplication
This is an active area of research, so this answer may be out of date very soon. :-)
As far as I know, the fastest fast matrix multiplication algorithm runs in O (n 2.373 ) time, due to the result of Virginia Williams . The algorithm is actually a large family of algorithms that generate a complex nonlinear system of equations that gives a general timing, and in fact there are people who are doing the work right now trying to figure out how to improve the score by finding better and better solutions to these equations ... I believe this algorithm is of theoretical interest only.
The holy grail of matrix multiplication would be an O (n 2 ) time matrix multiplication algorithm ), and whether such an algorithm exists remains an open problem. This is a theoretical limit, as the o (n 2 ) algorithm couldn't even read all the matrix entries so that they could be multiplied.
Hope this helps!
source to share