题目：           A new random polynomial time algorithm for factoring multivariate polynomials

报告人：      Mike Monagan(Department of Mathematics, Simon Fraser University)

时间地点：   2019.07.19  9:30am  N224

摘要：           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.