The algorithm is described in
https://en.wikipedia.org/wiki/Matrix_mu ... _algorithm. There you can also see a nice graph about how Coppersmith-Winograd came about in the early 80's, and read that the current record holder is a derivative of that algorithm:
The current O(nk) algorithm with the lowest known exponent k is a generalization of the Coppersmith–Winograd algorithm that has an asymptotic complexity of O(n2.3728639), by François Le Gall.
The suggestion that Le Gall spent 40 years toiling on improving C/W is indeed false; Le Gall is approximately (masters in 2003, PhD in 2006) 40 years old and I know for a fact the math curriculum in French grade schools isn't
that good. The increase from 2.3728642 to 2.3728639 actually took him 'only' about 3 years, furthering research by Vassilevska Williams published in 2011.
Maybe the comic depicts his overly entitled mother.
What really puzzles me is the lack of stress on
these algorithms are only worthwhile for matrices that are too large to handle on present-day computers.
or the fact that mathematicians can get upset if a set of n calculations can actually take n calculations.
The algorithm is described in https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm. There you can also see a nice graph about how Coppersmith-Winograd came about in the early 80's, and read that the current record holder is a derivative of that algorithm: [quote]The current O(nk) algorithm with the lowest known exponent k is a generalization of the Coppersmith–Winograd algorithm that has an asymptotic complexity of O(n2.3728639), by François Le Gall.[/quote]The suggestion that Le Gall spent 40 years toiling on improving C/W is indeed false; Le Gall is approximately (masters in 2003, PhD in 2006) 40 years old and I know for a fact the math curriculum in French grade schools isn't [i]that[/i] good. The increase from 2.3728642 to 2.3728639 actually took him 'only' about 3 years, furthering research by Vassilevska Williams published in 2011.
Maybe the comic depicts his overly entitled mother.
What really puzzles me is the lack of stress on
[quote]these algorithms are only worthwhile for matrices that are too large to handle on present-day computers.[/quote]or the fact that mathematicians can get upset if a set of n calculations can actually take n calculations.