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.
How fast can matrix multiplication with/on integers be performed?
3 Answers
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.
-
0"Even Strassen's is only marginally practical." - Emphasis on "marginally"... I don't think I've ever seen anything where using Strassen's made for better results... – 2011-08-11
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).
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?
-
0@Qiaochu: Sorry, I didn't get technical enough. I meant that the product is returned by using multiplication. It's a faulty algorithm - I forgot to look at enough coefficients. – 2011-08-27