SMS scnews item created by Bill Unger at Thu 27 Feb 2020 1024
Type: Seminar
Modified: Thu 27 Feb 2020 1026
Distribution: World
Expiry: 27 Mar 2020
Calendar1: 26 Mar 2020 1505-1600
CalLoc1: Carslaw 535A
CalTitle1: Computational Algebra Seminar: Monagan - Factoring multivariate polynomials
Auth: billu@laplace.maths.usyd.edu.au

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.