On the complexity of computing Gröbner bases for weighted homogeneous systems

DOI10.1016/J.JSC.2015.12.001zbMATH Open1430.13044arXiv1412.7547OpenAlexW2188410026MaRDI QIDQ5963397FDOQ5963397

Mohab Safey El Din, Jean-Charles Faugère, Thibaut Verron

Publication date: 19 February 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a structure: given a system of weights $W=(w_1,dots,w_n)$, $W$-homogeneous polynomials are polynomials which are homogeneous w.r.t the weighted degree $de{g}_W(X_1^{alph{a}_1},dots,X_n^{alph{a}_n})=sum{w}_{i}alph{a}_i$. Gr"obner bases for weighted homogeneous systems can be computed by adapting existing algorithms for homogeneous systems to the weighted homogeneous case. We show that in this case, the complexity estimate for Algorithm~F5 $$ can be divided by a factor $left(prod{w}_{i}ight{)}^{omega}$. For zero-dimensional systems, the complexity of Algorithm~FGLM $n{D}^{omega}$ (where $D$ is the number of solutions of the system) can be divided by the same factor $left(prod{w}_{i}ight{)}^{omega}$. Under genericity assumptions, for zero-dimensional weighted homogeneous systems of $W$-degree $(d_1,dots,d_n)$, these complexity estimates are polynomial in the weighted B'ezout bound $pro{d}_{i=1}^n{d}_i/pro{d}_{i=1}^n{w}_i$. Furthermore, the maximum degree reached in a run of Algorithm F5 is bounded by the weighted Macaulay bound $sum(d_i-w_i)+w_n$, and this bound is sharp if we can order the weights so that $w_n=1$. For overdetermined semi-regular systems, estimates from the homogeneous case can be adapted to the weighted case. We provide some experimental results based on systems arising from a cryptography problem and from polynomial inversion problems. They show that taking advantage of the weighted homogeneous structure yields substantial speed-ups, and allows us to solve systems which were otherwise out of reach.

Full work available at URL: https://arxiv.org/abs/1412.7547

Recommendations

• On the complexity of computing Gröbner bases for quasi-homogeneous systems
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Sparse Gröbner bases: the unmixed case
• Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity

zbMATH Keywords

polynomial system solvingquasi-homogeneous systemsGröbner basesweighted homogeneous systems

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• The Magma algebra system. I: The user language
• FGb: A Library for Computing Gröbner Bases
• Title not available (Why is that?)
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• On Complete Intersections and Their Hilbert Functions
• Title not available (Why is that?)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms in invariant theory
• Title not available (Why is that?)
• Degrevlex Gröbner bases of generic complete intersections.
• Converting bases with the Gröbner walk
• An inequality for Hilbert series of graded algebras.
• Hilbert functions and the Buchberger algorithm
• FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Generic sequences of polynomials
• On the complexity of computing gröbner bases for quasi-homogeneous systems
• Using symmetries in the index calculus for elliptic curves discrete logarithm
• Title not available (Why is that?)
• On variations of the subset sum problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A weighted module view of integral closures of affine domains of type I

Cited In (5)

• Toric eigenvalue methods for solving sparse polynomial systems
• Dimension results for extremal-generic polynomial systems over complete toric varieties
• On the robust hardness of Gröbner basis computation
• On the computation of Gröbner bases for matrix-weighted homogeneous systems
• Short proofs of ideal membership

Uses Software

• FGb
• Macaulay2
• Magma
• SINGULAR

This page was built for publication: On the complexity of computing Gröbner bases for weighted homogeneous systems

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