Clever Geek Handbook

Complexity of large matrix multiplication

What is the time complexity of the fastest algorithm known today for large matrix multiplication?

How about the theoretical optimal time complexity that can be achieved?

+3


source to share


1 answer


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!

+5


source






More articles:


All Articles