How fast can matrix multiplication with/on integers be performed? I would like to know how fast a matrix of integers can be multiplied by another matrix of integers.  My motivation is because I've got a few ideas that seem to make the multiplication possible in around $O(n^2)$, but maybe this has already been accomplished somewhere else.  Most likely I've made a zillion errors or this has been done already...  I guess I'd like to know the best methods available, such as Strassen's algorithm.
 A: The best known algorithm is Coppersmith-Winograd, which runs in time $O(n^{2.376})$. It is believed, however, that for every $\epsilon > 0$ there is an algorithm that runs in time $O(n^{2+\epsilon})$. There is an $\Omega(n^2\log n)$ lower bound by Ran Raz for (arithmetic) circuit complexity with some restrictions on the circuit.
It will be very surprising if there were an $O(n^2)$ algorithm. Today's asymptotically efficient algorithms are not only complicated, but also impractical. Even Strassen's is only marginally practical. It will thus be even more surprising if there is a simple, practical $O(n^2)$ algorithm.
Finally, I don't believe that the restriction to integers makes the problem fundamentally easier.
A: There is a newer O(n^2.373) algorithm, see Virginia Vassilevska Williams, "Breaking the Coppersmith-Winograd barrier": http://theory.stanford.edu/~virgi/matrixmult-f.pdf (published in 2014).
A: I think the best known Is Coppersmith-Winograd ($O(n^{2.376})$). I think there is a very good presentation on lots of the material, too.
You should probably look over your algorithm a lot - I would be stunned if you had such an algorithm. What's the basic idea?
