Gcd of multivariate polynomials via Newton polytopes

DOI10.1016/J.AMC.2011.03.035MaRDI QIDQ545987zbMATH OpenOpenAlexFDO

Authors Luiz Emilio Allem, Vilmar Trevisan

Publication date 24 June 2011

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2011.03.035

zbMATH Keywords

greatest common divisormultivariate polynomialNewton polytope

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Polynomials, factorization in commutative rings (13P05)

Review text

In this paper the authors used some geometric properties of Newton polytopes to obtain a criterion establishing that two multivariate polynomials are relatively prime. More precisely, they studied the coprimality between multivariate polynomials verifying whether their associated Newton polytopes have no common factors by showing that they have no common parallel edges. In the latest section a detailed example and a polynomial-time algorithm to compute the gcd between two bivariate polynomials using Newton polygons are presented. One of the first results connecting geometric and algebraic properties of polynomials was done by Ostrowski (1921); and recently, \textit{S. Gao} [J. Algebra 237, 501--520 (2001; Zbl 0997.12001)] used the geometric properties of polytopes to construct families of absolutely irreducible polynomials. Some geometric properties of polytopes are also used to study the indecomposable polynomials (for example, \textit{G. Chéze} and \textit{S. Najib} [J. Algebra 324, No. 1, 1--11 (2010; Zbl 1202.13014)]) and the problem of irreducibility of polynomials after deformation (for example, \textit{A. Bodin, P. Dèbes} and \textit{S. Najib} [Acta Arith. 139, No. 1, 79--100 (2009; Zbl 1228.12002)]).

Recommendations

• Resultants and coprimeness of polynomials
• Three new algorithms for multivariate polynomial GCD
• Factoring polynomials via polytopes
• GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation
• Greatest common divisors of polynomials given by straight-line programs

Cites work

• Absolute irreducibility of polynomials via Newton polytopes
• Decomposition of polytopes and polynomials
• Factoring polynomials via polytopes
• Flexible object hierarchies in polymake. (Extended abstract)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• scientific article; zbMATH DE number 960150 (Why is no real title available?)
• Modern computer algebra

Cited in

(3)

• Approximate GCD of multivariate polynomials
• Resultants and coprimeness of polynomials
• Decomposition of polytopes and polynomials

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Gcd of multivariate polynomials via Newton polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q545987)