For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n^2.376) steps. Last year, though, buried deep in his PhD thesis, Andy Stothers discussed an improvement to O(n^2.374) steps. And today, Virginia Vassilevska Williams of Berkeley and Stanford, released a breakthrough paper [pdf] that improves the matrix-multiplication time to a lightning-fast O(n^2.373) steps. [via][more inside]
posted by albrecht
on Nov 29, 2011 -
If you could use a great big free handbook of discrete math and algorithms, Jörg Arndt's fxtbook wants to be your friend. Plain text table of contents to whet your appetite.
posted by Wolfdog
on Mar 5, 2008 -