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}$}$ mathend000#, for any machine-word size prime number p mathend000#, 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) mathend000# and B = (b_{i, j}, 1 $\leq$ i $\leq$ j $\leq$ n) mathend000# of order n mathend000# with coefficients in $\mathbb {Z}$ mathend000#. Let || A||_$\infty$ mathend000# and || B||_$\infty$ mathend000# be the maximum absolute value of a coefficient in A mathend000# and B mathend000#, respectively. Let C = (c_{i, j}, 1 $\leq$ i $\leq$ j $\leq$ n) mathend000# be the matrix product AB mathend000# and let m > 2 mathend000# be any odd integer (prime or not). For all 1 $\leq$ i $\leq$ j $\leq$ n mathend000#, we have

$$\Sigma_{{{k=1}}}^{{{k=n}}}$$ (137)

and thus

$$\equiv \Sigma_{{{k=1}}}^{{{k=n}}}$$ (138)

Now, let $\overline{{A}}^{{m}}_{}$ = ($\overline{{a}}^{m}_{{i,j}}$, 1 $\leq$ i $\leq$ j $\leq$ n) mathend000# and $\overline{{B}}^{{m}}_{}$ = ($\overline{{b}}^{m}_{{i,j}}$, 1 $\leq$ i $\leq$ j $\leq$ n) mathend000# be the images of A mathend000# and B mathend000# modulo m mathend000#. (Hence the coefficient $\overline{{a}}^{m}_{{i,j}}$ mathend000# of $\overline{{A}}^{{m}}_{}$ mathend000# is the remainder of a_{i, j} mathend000# modulo m mathend000#.) Let $\overline{{C}}^{{m}}_{}$ = ($\overline{{c}}^{m}_{{i,j}}$, 1 $\leq$ i $\leq$ j $\leq$ n) mathend000# be the matrix product $\overline{{A}}^{{m}}_{}$$\overline{{B}}^{{m}}_{}$ mathend000# computed in $\mbox{${\mathbb Z}$}$/m$\mbox{${\mathbb Z}$}$ mathend000#. 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 \overline{{b}}^{m}_{{i,k}} \equiv$$ (140)

with Equations (138) and (139) we obtain

$$\equiv \overline{{c}}^{m}_{{i,j}}$$ (141)

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

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

$$\leq \Sigma_{{{k=1}}}^{{{k=n}}} \leq \mid_{{{\infty}}}^{{}} \mid_{{{\infty}}}^{{}}$$ (142)

Hence we define M = n|| A||_$\infty$|| B||_$\infty$ mathend000#. We are ready to state a modular algorithm.

Algorithm 6  

mathend000#

Note that the first for loop computes the matrcies $\overline{{C}}^{{m_0}}_{}$,...,$\overline{{C}}^{{m_{r-1}}}_{}$ mathend000# 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(rn³) mathend000# and the second one in O(n²r²) mathend000#. This is a better estimate than the one which can be given for the naive (non-modular approach): O(n³r²) mathend000#.