Ideal-specific elimination orders form a star-shaped region

Abstract: This paper shows that Gr"obner walks aiming for the elimination of variables from a polynomial ideal can be terminated much earlier than previously known. To this end we provide an improved stopping criterion for a known Gr"obner walk algorithm for the elemination of variables. This results from two new geometric insights on Gr"obner fans: We show that for any given ideal I subset K[x_1, ..., x_n] the collection of Gr"obner cones corresponding to I-specific elimination orders may contain Gr"obner cones in the relative interior of the positive orthant. Moreover we prove that the corresponding Gr"obner cones form a star-shaped region (the center being the set of all universal elimination vectors) which contrary to first intuition in general is not convex.

Review text

This paper shows that for any given polynomial ideal \(I \subset K[x_1,\ldots,x_n]\) the collection of Gröbner cones corresponding to \(I\)-specific elimination orders forms a star-shaped region contrary to first intuition in general is not convex. The authors show that for any given ideal \(I \subseteq K[x_1, \ldots, x_n, u_1, \ldots, u_m]\), the union of all Gröbner cones belonging to \(I\)-specific orders for the elimination of \(u_1,\ldots ,u_m\) from \(I\) forms a star-shaped region with center \(\Omega_u:=\{\omega\in {\mathbb R}_{\geq 0}^{n+m}:\;\omega_1=0,\ldots,\omega_n=0\}\). This means that if one wants to calculate some Gröbner basis for \(I \cap K[X]\), the orders \(\prec\) that do yield such a Gröbner basis have Gröbner cones, whose union is a star-shaped region with center \(\Omega_u\) (Theorem 1). Moreover, it is shown that (for some ideals \(I\)) some of the Gröbner cones which belong to \(I\)-specific elimination orders intersect the boundary of the Gröbner fan in the point zero only, meaning that for such cones all points but the vertex lie in the relative interior of the Gröbner fan (Lemma 4.1). These results slightly improved the Algorithm of Tran (Algorithm 1 in [\textit{Q.-N. Tran}, J. Symb. Comput. 42, No. 5, 533--548 (2007; Zbl 1127.13025)]) which calculates a Gröbner basis for the elimination ideal by means of a Gröbner walk, this is done by changing the termination criterion (Algorithm 1).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Ideal-specific elimination orders form a star-shaped region

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