Improvements of convex-dense factorization of bivariate polynomials

2025/01/10 by Martin Weimann, Weimann, Martin
Computer Science · Engineering · #13P05 #68W30 #Commutative Algebra (math.AC) #FOS: Mathematics #Matrix Theory and Algorithms #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2501.06028

openalex publication_date 2025/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a new algorithm for factoring a bivariate polynomial F∈ \mathbbK[x,y] which takes fully advantage of the geometry of the Newton polygon of F. Under a non degeneracy hypothesis, the complexity is O(Vr₀^ω-1 ) where V is the volume of the polygon and r₀ is its minimal lower lattice length. This improves the complexity O(d^ω+1) of the classical algorithms which consider the total degree d of F as the main complexity indicator. The integer r₀≤ d reflects some combinatorial constraints imposed by the Newton polygon, giving a reasonable and easy-to-compute upper bound for the number of its indecomposable Minkovski summands of positive volume. The proof is based on a new fast factorization algorithm in \mathbbK[[x]][y] with respect to a slope valuation, a result which has its own interest.

Related

• A lifting and recombination algorithm for rational factorization of sparse polynomials
• Decomposition of polytopes and polynomials
• A tau-conjecture for Newton polygons
• Factoring bivariate sparse (lacunary) polynomials
• Bivariate factorization using a critical fiber