-
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.
|
|
|