How Can We Speed Up Matrix Multiplication?

Abstract

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