We conclude this chapter with another modular algorithm.
We assume that we have a highly efficient matrix multiplication
over
, for any machine-word size prime number
,
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
and
of order
with coefficients in
.
Let
and
be the maximum absolute value
of a coefficient in
and
, respectively.
Let
be the matrix product
and let
be any odd integer (prime or not).
For all
, we have
|
(137) |
and thus
|
(138) |
Now, let
and
be the images of
and
modulo
. (Hence the coefficient
of
is the remainder of
modulo
.)
Let
be the matrix product
computed in
.
Hence, we have
|
(139) |
Combining the relations
|
(140) |
with Equations (138) and (139)
we obtain
|
(141) |
In particular, if we use a symmetric representation
for representing the elements of
and if we have
, then Equation (141)
simply becomes
.
Observe that for all
, we have
|
(142) |
Hence we define
.
We are ready to state a modular algorithm.
Algorithm 6
Note that the first for loop computes the matrcies
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
and the second one in
.
This is a better estimate than the one which can be given
for the naive (non-modular approach):
.
Marc Moreno Maza
2008-01-07