Arnold Sch\"onhage, Institut f\"ur Informatik~II der Universit\"at Bonn

Algorithms with exact divisions made faster

Algorithms like Bareiss' method for the exact evaluation of determinants with integral entries, and similarly Collins' subresultant algorithm, spend a substantial amount of their running time in performing {\it exact divisions}, integer by an integer, or polynomial by a polynomial, with the remainder known to be zero. The main topics of this talk are: \begin{itemize} \item[--] faster algorithms for exact division; \item[--] in determinant evaluation and subresultant algorithms, the number of divisions and the other operation costs can considerably be reduced; \item[--] asymptotically, fast computations modulo numbers of the form $2^N + 1$ can be used. \end{itemize}