Type: Seminar

Modified: Thu 27 Feb 2020 1026

Distribution: World

Expiry: 27 Mar 2020

CalTitle1: Computational Algebra Seminar: Monagan - Factoring multivariate polynomials

Auth: billu@laplace.maths.usyd.edu.au

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.

Calendar (ICS file) download, for import into your favourite calendar application

UNCLUTTER for printing

AUTHENTICATE to mark the scnews item as read