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

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

and thus

$\displaystyle 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

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

Combining the relations

$\displaystyle \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

$\displaystyle 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

$\displaystyle \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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $A=(a_{ij...
... := $c_{i,j} - m$\ \\
\> {\bf return}($(c_{ij})$)
\end{tabbing}\end{minipage}}

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

Marc Moreno Maza
2008-01-07