4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – J. M.'s ennui♦ Jul 2 '16 at 10:48
  • $\begingroup$ 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. $\endgroup$ – Oliver Miller Jul 2 '16 at 11:01
  • $\begingroup$ Are you doing this conversion after multiplying all those products, or during the multiplication? $\endgroup$ – J. M.'s ennui♦ Jul 2 '16 at 11:07
  • $\begingroup$ During the multiplication. Every product I make is a product of sparse matrices. $\endgroup$ – Oliver Miller Jul 2 '16 at 11:13
  • 1
    $\begingroup$ 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. $\endgroup$ – mikado Jul 2 '16 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.