Andy Novocin
|
MATHEMATICS COLLOQUIUM
Speaker: Andy Novocin Abstract. In this talk we present several algorithms for finding the factorization of a polynomial with integer coefficients. Over the last 25 years there has been an unpleasant dichotomy in such algorithms. Certain algorithms are considered fast in practice and are used in popular Computer Algebra Systems such as MAPLE, MAGMA, SAGE, etc. While a completely different set of algorithms have nice proved bounds on the number of CPU operations needed for termination. Such bounds are needed by theoretical computer scientists for analysis of their own algorithms. The goal of the talk is to arrive at a new algorithm by myself and Mark van Hoeij which resolves this dichotomy. This algorithm has the best proved bounds in the theoretical sense and, as a recent implementation shows, it can be made very practical. |