- is not singular,
- no row or column permutations are necessary,

(110) |

- Let be an upper bound for the absolute value of the numerators and the denominators of all .
- In particular for we have .

(112) |

**In what follows, we present an approach whose goal is to control
the growth of the intermediate computations when calculating the determinant of
.
Let
be this determinant.
Let us choose a prime number
such that
**

(113) |

(114) |

(115) |

(117) |

(118) |

(119) |

(120) |

(121) |

(122) |

(123) |

- How to choose ?
- What do we win?

(124) |

(125) |

(126) |

(127) |

(128) |

- The word length of
is in the order of magnitude of
(129)

- Prime numbers are frequent enough to find one with a word length in the same order of magnitude as .
- So each element of can be coded by an array with at most words.
- Hence, each operation (like addition, multiplication, inverse computation) in costs at most word operations.
- Gaussian elimination will require operations in .

**This is not in fact a big progress w.r.t. Gaussian elimination over
.
But this can be improved using a small primes modular computation
as follows.
**

(130) |

Using the ring isomorphism of Corollary 2

(131) |

we deduce

(132) |

where is the product of the moduli . Now observe that

(133) |

Hence actually we have .

(134) |

(135) |

(136) |

- All intermediate computations can be made modulo small prime numbers. In practice these small primes are machine integers allowing fast computations.
- The only possible large value is the determinant itself.
- The space and the time required for the whole computation can be estimated in advance.

*
*

2008-01-07