# Is there a fast way to compute matrix multiplication mod 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.)

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$.)

-
It seems to me that by doing the obvious thing -- i.e., reducing modulo $n$ after doing every addition and multiplication -- will already make matrix multiplication mod $\mathbb{Z}/n\mathbb{Z}$ (whether $n$ is prime or not...) much faster than multiplication of matrices with entries in $\mathbb{Z}$. Maybe you could say more about exactly how fast you are looking for? – Pete L. Clark Apr 23 '11 at 6:21
I mean, for matrix over the reals, while usual matrix multiplication is O(n^3), people can find trick to push it below O(n^2.4). I want to know if it is possible to make it easier in the special case of mod p. e.g. I think even if a polynomial is known to be factorizable over Z, it is easier to factor a polynomial mod p (sometimes one can even do it by hand), for an algorithm see en.wikipedia.org/wiki/Berlekamp%27s_algorithm. – 36min Apr 23 '11 at 6:50
@#6min: estimates like $O(n^3)$ on matrix multiplication treat basic operations like addition and multiplication as having constant time. But this is not realistic: if you have a matrix with integer entries, then the size of the entries is obviously going to factor into the time it takes to do the matrix multiplication. This is the sort of thing you will (obviously) save on by going mod $n$. Conversely, if you ignore this issue it's hard for me to believe that you're going to save any time by working over a finite ring. – Pete L. Clark Apr 23 '11 at 7:53
To amplify on my previous comment: if we fix the size $t$ of the matrices and also bound the size of the integer entries by $M$, say, then clearly for all $n$ sufficiently large compared to $M$ and $t$, doing the matrix multiplication mod $n$ is equivalent to doing it over $\mathbb{Z}$. Since there can't be a time savings for all values of the parameters, it would be helpful if you could indicate more specifically what you are interested in. For instance, are you regarding $p$ as fixed? – Pete L. Clark Apr 23 '11 at 8:09

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.)

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.

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$).

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.

-

The improvement of matrix multiplication from $O(n^3)$ to $O(n^{2.4})$ is based on the Strassen equations for matrix multiplication. Strassen Algorithm 7 multiplications 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?

-

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.

It is called M4RI ; on this website in particular under further reading one can find various text related to this.

In particular, a paper by developpers of the library:

Martin Albrecht, Gregory Bard, William Hart. Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2). ACM Transactions on Mathematical Software 2010.

Preprint at http://arxiv.org/abs/0811.1714.

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.

Let me also say some things in part already in the comments:

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 $O(n^{\log_2 7})$ is mentioned and one also has this for integers.

Yet, for certain computations related to integer matrices, it is 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.

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
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 unique integer satisfying both the congruence conditions and the size condition (implied by the bound).

Things like this are for example discussed in H. Cohen, A course in computational Algebraic Number Theory, Springer GTM 138.

-