Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations


Authors: Jérémy Berthomieu and Grégoire Lecerf
Journal: Math. Comp. 81 (2012), 1799-1821
MSC (2010): Primary 12Y05; Secondary 68W30, 11Y16, 12D05, 13P05
Published electronically: November 10, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we present a new algorithm for reducing the usual sparse bivariate factorization problems to the dense case. This reduction simply consists of computing an invertible monomial transformation that produces a polynomial with a dense size of the same order of magnitude as the size of the integral convex hull of the support of the input polynomial. This approach turns out to be very efficient in practice, as demonstrated with our implementation.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 68W30, 11Y16, 12D05, 13P05

Retrieve articles in all journals with MSC (2010): 12Y05, 68W30, 11Y16, 12D05, 13P05


Additional Information

Jérémy Berthomieu
Affiliation: Laboratoire d’Informatique UMR 7161 CNRS, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France
Address at time of publication: Laboratoire de Mathématiques UMR8100 CNRS, Université de Versailles-Sr-Quentin-en-Yvelynes, 45 avenue des États-Unis, 78035 Versailles Cedex, France
Email: berthomieu@lix.polytechnique.fr

Grégoire Lecerf
Affiliation: Laboratoire d’Informatique UMR 7161 CNRS, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France
Email: gregoire.lecerf@math.cnrs.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-2011-02562-7
PII: S 0025-5718(2011)02562-7
Keywords: Polynomial factorization
Received by editor(s): October 15, 2010
Received by editor(s) in revised form: March 28, 2011, and April 11, 2011
Published electronically: November 10, 2011
Additional Notes: This work was partly supported by the French ANR-09-JCJC-0098-01 MaGiX project, and by the Digiteo 2009-36HD grant of the Région Île-de-France.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.