Modular computation of the matrix product

We conclude this chapter with another modular algorithm. We assume that we have a highly efficient matrix multiplication over ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ , for any machine-word size prime number $p$ , and would like to take advantage of it for multipying matrcies with integer coefficients. This can be achieved by means of a modular algorithm, based on the Chinese Remaindering Algorithm.

Consider two square matrices $A = (a_{i,j}, 1 \leq i \leq j \leq n)$ and $B = (b_{i,j}, 1 \leq i \leq j \leq n)$ of order $n$ with coefficients in ${\mathbb{Z}}$ . Let $\vert\vert A\vert\vert _{\infty}$ and $\vert\vert B\vert\vert _{\infty}$ be the maximum absolute value of a coefficient in $A$ and $B$ , respectively. Let $C = (c_{i,j}, 1 \leq i \leq j \leq n)$ be the matrix product $A B$ and let $m > 2$ be any odd integer (prime or not). For all $1 \leq i \leq j \leq n$ , we have

$$c_{i,j} = {\Sigma}_{k=1}^{k=n} \ a_{i,k} b_{k,j},$$ (137)

and thus

$$c_{i,j} \equiv {\Sigma}_{k=1}^{k=n} \ a_{i,k} b_{k,j} \mod{ \ m}.$$ (138)

Now, let $\overline{A}^{m} = (\overline{a}^m_{i,j}, 1 \leq i \leq j \leq n)$ and $\overline{B}^{m} = (\overline{b}^m_{i,j}, 1 \leq i \leq j \leq n)$ be the images of $A$ and $B$ modulo $m$ . (Hence the coefficient $\overline{a}^m_{i,j}$ of $\overline{A}^{m}$ is the remainder of $a_{i,j}$ modulo $m$ .) Let $\overline{C}^{m} = (\overline{c}^m_{i,j}, 1 \leq i \leq j \leq n)$ be the matrix product $\overline{A}^{m} \overline{B}^{m}$ computed in ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}$ . Hence, we have

$$\overline{c}^m_{i,j} = {\Sigma}_{k=1}^{k=n} \overline{a}^m_{i,k} \overline{b}^m_{k,j}$$ (139)

Combining the relations

$$\overline{a}^m_{i,k} \equiv a_{i,k} \mod{ \ m} \ \ {\rm and} \ \ \overline{b}^m_{i,k} \equiv b_{i,k}\mod{ \ m}$$ (140)

with Equations (138) and (139) we obtain

$$c_{i,j} \equiv \overline{c}^m_{i,j} \mod{ \ m}.$$ (141)

In particular, if we use a symmetric representation $-\frac{m-1}{2} \cdots \frac{m-1}{2}$ for representing the elements of ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}$ and if we have $\vert c_{i,j}\vert < \frac{m}{2}$ , then Equation (141) simply becomes $c_{i,j} = \overline{c}^m_{i,j}$ .

Observe that for all $1 \leq i \leq j \leq n$ , we have

$$\mid c_{i,j} \mid \ \leq \ {\Sigma}_{k=1}^{k=n} \ \mid a_{i,k} \m... ...\ \leq \ n {\mid \mid A \mid \mid}_{\infty} \ {\mid \mid B \mid \mid}_{\infty}.$$ (142)

Hence we define $M = n \vert\vert A\vert\vert _{\infty} \vert\vert B\vert\vert _{\infty}$ . We are ready to state a modular algorithm.

Algorithm 6  

Note that the first for loop computes the matrcies $\overline{C}^{m_0}, \ldots, \overline{C}^{m_{r-1}}$ by the classical method. However, one can use instead any other algorithm (like Strassen's) computing these matrices. Let us give an upper bound for the number of machine-word operations required by Algorithm 6. It suffices to estimate each of the two for loops. The first one runs in $O(r n^3)$ and the second one in $O(n^2 r^2)$ . This is a better estimate than the one which can be given for the naive (non-modular approach): $O(n^3 r^2)$ .