I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has evolved in the following way:
- w = 3 if using a brute-force approach,
- w = 2.8074 if using Volker Strassen's algorithm [1969],
- ... (some interesting improvements later :))
- w = 2.3729 if using Virginia Vassilevska-Williams analysis of the Coppersmith–Winograd algorithm [2011]
- w = 2.3728639 if using François Le Gall's adaptation of the Coppersmith–Winograd algorithm [2014]
I often hear that the more recent algorithms presented, while theoretically interesting since w approaches 2, are not practical due to the large constant hidden by Big-O. In other words, that the size of the input matrix would need to be extremely large in order for it to be an improvement over Strassen's algorithm, for example. I would like to put a number to this.
What is the rough value of this hidden constant for any of the more recent fast matrix multiplication algorithms? Or, for roughly what input size n of a matrix would the fast matrix multiplication algorithm use less operations than Strassen's algorithm, or the brute force approach?