Skip to Main content Skip to Navigation
Journal articles

A lifting and recombination algorithm for rational factorization of sparse polynomials

Abstract : We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton poly-tope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with now a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterions in toric varieties.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02137320
Contributor : Martin Weimann <>
Submitted on : Wednesday, May 22, 2019 - 9:52:12 PM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM

File

Revised_Version_Weimann.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Martin Weimann. A lifting and recombination algorithm for rational factorization of sparse polynomials. Journal of Complexity, Elsevier, 2010, 26 (6), pp.608-628. ⟨10.1016/j.jco.2010.06.005⟩. ⟨hal-02137320⟩

Share

Metrics

Record views

40

Files downloads

96