# Sparse matrix multiplication mod p

Let A and B be sparse matrices with integer coefficients between 0 and p-1, with p prime. Which is the fastest way to compute their product mod p and obtain another sparse matrix? I'm mainly interested in p = 2.

The code Mod[A.B, p] returns a sparse matrix, but it may not be "optimal" in the sense that elements that are non-zero in A.B but zero in Mod[A.B, p] are stored. The code SparseArray[Mod[A.B, p]] yields the correct result, but there should be a much faster way.

• Unfortunately Inner[] does not give SparseArray[] results, so that alternative's out. Are your actual matrices large enough that SparseArray[Mod[A.B, p]] is unfeasible? – J. M. will be back soon Jul 2 '16 at 10:48
• My matrices are small (not bigger than 12 x 12), but I need to compute millions of products. I tried using SparseArray[Mod[A.B, p]] and it's taking too long. – Oliver Miller Jul 2 '16 at 11:01
• Are you doing this conversion after multiplying all those products, or during the multiplication? – J. M. will be back soon Jul 2 '16 at 11:07
• During the multiplication. Every product I make is a product of sparse matrices. – Oliver Miller Jul 2 '16 at 11:13
• In my timing experiments, full 12x12 matrix multiplication was faster than sparse 12x12 matrix multiplication. (I tested with the identify matrix). There may be no benefit in looking for a sparse solution. – mikado Jul 2 '16 at 14:22