Computational Algebra Seminar: Monagan -- A new random polynomial time algorithm for factoring multivariate polynomials

Speaker : Michael Monagan, Department of Mathematics, Simon Fraser University.
Title : A new random polynomial time algorithm for factoring multivariate polynomials
Time & Place: Thursday 26 March, 3.05-4pm, Carslaw 535

To factor a multivariate polynomial in n variables, all of our
Computer Algebra Systems use Paul Wang’s organization of Hensel lifting.
This method recovers the variables in the factors one at a time.
It is exponential in the number of variables in the worst case.
We present a new algorithm which is random polynomial time.
The new algorithm is based on an observation about the terms that
appear in a Taylor polynomial when expanded about a random point.
We call this observation the Strong Sparse Hensel Assumption.
This leads to an approach for factoring polynomials that is
fast in practice for both sparse and dense polynomials.
Our new algorithm is now the default algorithm in Maple 2019.

In the talk I will explain how Paul Wang’s Hensel lifting works.
I will then present the Strong Sparse Hensel Assumption,
the new algorithm, and discuss it’s failure probability.
I will also present some timings in Maple 2019 showing the
improvement obtained by the new algorithm.  The main tool we use to
analyse the failure probability is the Schwartz-Zippel Lemma.

This is joint worth with Baris Tuncer.