Is there a fast way to compute matrix multiplication mod p? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T03:00:02Z http://mathoverflow.net/feeds/question/62695 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62695/is-there-a-fast-way-to-compute-matrix-multiplication-mod-p Is there a fast way to compute matrix multiplication mod p? 36min 2011-04-23T02:44:33Z 2011-04-23T16:49:17Z <p>I think people have some general strategy to do matrix multiplication fast. But what about for the finite field of $p$ elements? (e.g. when $p=2$, one should have some faster way.)</p> <p>So my question is, given two integer entry matrix, $A$ and $B$. Is there a fast way to compute $AB \mod p$?. And is there a fast way of computing $A^n \mod p$ for $n$ not too big. (Note that for $n=|GL_t(Z/p)|$, we have $A^n=I \mod p$, where $t$ is the size of $A$.)</p> http://mathoverflow.net/questions/62695/is-there-a-fast-way-to-compute-matrix-multiplication-mod-p/62748#62748 Answer by quid for Is there a fast way to compute matrix multiplication mod p? quid 2011-04-23T15:20:49Z 2011-04-23T15:20:49Z <p>For $\mathbb{Z}/2 \mathbb{Z}$ (and other finite fields of characteristic $2$) there is a specialized library for compting with matrices over that structure.</p> <p>It is called <a href="http://m4ri.sagemath.org/" rel="nofollow">M4RI</a> ; on this website in particular under further reading one can find various text related to this.</p> <p>In particular, a paper by developpers of the library:</p> <p>Martin Albrecht, Gregory Bard, William Hart. Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2). ACM Transactions on Mathematical Software 2010. </p> <p>Preprint at <a href="http://arxiv.org/abs/0811.1714" rel="nofollow">http://arxiv.org/abs/0811.1714</a>.</p> <p>Yet, the main point there, as far as my understanding goes, is that modolu $2$ arithmetic can be done very efficiently on a computer and the point is to really optimize the methods to exploit this.</p> <p>Let me also say some things in part already in the comments:</p> <p>I (also) believe for multiplication if one counts say just number of multiplications over the base-structure and takes this as a measure of 'goodness' it does not matter whether one is over $\mathbb{Z}$ or modulo $n$. This also seems to be in line with the fact that in M4RI <code>$O(n^{\log_2 7})$</code> is mentioned and one also has this for integers.</p> <p>Yet, for certain computations related to integer matrices, it <em>is</em> useful to pass to modular arithmetic and then go back, yet (only) due to the fact that the arithemtic over the base structure (mod $n$ vs. integers) can be much faster; in particular, if the integers involved are large or (perhaps more importantly) can grow large in the process.</p> <p>For example, to compute determinants of integers matrices a strategy can be to on the one hand compute a bound on the determinant (e.g., using Hadamard's bound) and<br> on the other hand to compute the determinant modulo many primes. As then combinining the modulo $p$ pieces of information on the determinant, one knows the determinant modulo such a large modulus that actually there remains only a <em>unique</em> integer satisfying both the congruence conditions and the size condition (implied by the bound). </p> <p>Things like this are for example discussed in H. Cohen, A course in computational Algebraic Number Theory, Springer GTM 138.</p> http://mathoverflow.net/questions/62695/is-there-a-fast-way-to-compute-matrix-multiplication-mod-p/62753#62753 Answer by aginensky for Is there a fast way to compute matrix multiplication mod p? aginensky 2011-04-23T15:43:27Z 2011-04-23T15:43:27Z <p>The improvement of matrix multiplication from $O(n^3)$ to $O(n^{2.4})$ is based on the Strassen equations for matrix multiplication. <a href="http://mathoverflow.net/questions/57725/strassen-algorithm-7-multiplications" rel="nofollow">http://mathoverflow.net/questions/57725/strassen-algorithm-7-multiplications</a> talks about this and gives further references. If your question is rephrased as "are there special equations for matrix multiplication in characteristic $p$ ?", then I think the answer, if known, will be in one of those references. If I were a betting man, I'd bet no. As a person not adverse to speculation, I am highly skeptical. Matrix multiplication feels to me to be characteristic independent and of the flavor if it was true in all large (positive) characteristics, then it would be true in characteristic zero. Also, almost all results about equations of determinantal varieties, secant varieties etc don't seem to be different in any characteristic. Of course, this is not true on the nose as higher syzygies can be different,and in my very feeble understanding of such matters, more complicated. Anyone in a position to terminate or validate my musings?</p> http://mathoverflow.net/questions/62695/is-there-a-fast-way-to-compute-matrix-multiplication-mod-p/62759#62759 Answer by Henry Cohn for Is there a fast way to compute matrix multiplication mod p? Henry Cohn 2011-04-23T16:49:17Z 2011-04-23T16:49:17Z <p>For any field, we can define the exponent of matrix multiplication over that field to be the smallest number $\omega$ such that $n \times n$ matrix multiplication can be done in $n^{\omega + o(1)}$ field operations as $n \to \infty$. Schönhage proved that it is invariant under taking field extensions, so it depends only on the characteristic of the field. Probably it equals $2$ in every characteristic, but that isn't known. (Certainly $\omega \ge 2$, since it takes at least one operation to get each entry.)</p> <p>Let $\omega_p$ be the exponent in characteristic $p$. Then one can show that $\limsup_{p \to \infty} \omega_p \le \omega_0$, basically because every low-rank tensor decomposition in characteristic $0$ will work for all but finitely many primes. Over the rationals, you just need to avoid primes that occur in denominators.</p> <p>However, for small primes the exponent could (as far as we know) be better or worse than in characteristic $0$, and it's even possible that it could be substantially better for all primes, although in that case you can show that as $p \to \infty$ the asymptotics would have to take longer and longer to kick in (i.e., the size of the matrices needed to see the improvement would grow as a function of $p$).</p> <p>Strassen's exponent $2.8$ algorithm works in every characteristic, and it's the only practical method that achieves exponent less than $3$. However, if you want to do this in practice, it's important to think about issues like cache and memory access. (These issues are often more important than counting arithmetic operations.) Unless you really know what you are doing, it's not worth trying to write your own code, except as a learning exercise. For example, in characteristic $2$ the M4RI code mentioned by unknown (google) seems like it could be a good bet.</p>