How Can We Speed Up Matrix Multiplication?

摘要: Due to the new algebraic methods of algorithm design, recently it became possible perform multiplication and inversion $N \times N$ matrices using $O(N^{2.496} )$ rather than $O(N^3 arithmetical operations. Consequently, algorithms for several other computational problems linear algebra combinatorics have been accelerated. The major ideas techniques that led progress are surveyed.