General  Information
Home
Important Dates
Conference Poster
Organizing Committee
Sponsors
 Program
Program and Schedule
Invited Talks
Contributed Talks
Tutorials
Posters
Software Exhibitions
 Registration
Information
Registered Participants
 Call  For
Research Papers
Posters
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Lodging
Traveling
Gastronomic Guide
Additional Information
 Miscellaneous
Social Events
Previous ISSACs
Other Events

 

 

Complexity Issues in Bivariate Polynomial Factorization

A. Bostan, G. Lecerf, B. Salvy, E. Schost, B. Wiebelt

 

Many polynomial factorization algorithms are based on the Hensel lifting and factor recombination scheme. In the case of bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, for the so-called trace recombination approach. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting often appears to be the practical bottleneck of this method: we propose a new algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

  issac2004 @ risc.uni-linz.ac.at