A new iterative algorithm for comprehensive Gröbner systems

Let us start with a simple example to introduce the central object of this paper. Consider ${\cal C}_{1}$, a circle with center $(0,0)$ and radius $1$, and ${\cal C}_{2}$, a circle with center $(c,0)$ and radius $\sqrt{r}$. What is their intersection as $c$ and $r$ vary in $\mathbb{C}$? We can see that there are three cases: if $c=0,\,r=1$ the two circles coincide, if $c=0,\,r\neq 1$ the two circles do not intersect, if $c\neq 0$ the two circles intersect in two points in $\mathbb{C}^{2}$ (may be one double point).

Algebraically speaking, the ideal $I=\langle x^{2}{+}y^{2}{-}1,\;(x{-}c)^{2}{+}y^{2}{-}r\rangle$, defined by the equations of $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, has a collection of different Gröbner bases depending on the values of the parameters. This is described by a Comprehensive Gröbner system, which is a set of pairs $\{(\mathcal{A}_{1},G_{1}),\dots,(\mathcal{A}_{l},G_{l})\}$, the Gröbner bases $G_{i}$ under the conditions $\mathcal{A}_{i}$. For example, one such pair is $\mathcal{A}_{1}=\{(r,c)\in\mathbb{C}^{2}\mid c\neq 0\}$ and its corresponding ${\rm lex}$-Gröbner basis (${\rm lex}$ with $x>y>c>r$)
. $\{\;x^{2}+y^{2}-1,\;\;cx-\frac{1}{2}c^{2}+\frac{1}{2}r-\frac{1}{2},\;\;{c^{2}}{y^{2}}+\frac{1}{4}c^{4}-\frac{1}{2}rc^{2}+\frac{1}{4}r^{2}-\frac{1}{2}c^{2}-\frac{1}{2}r+\frac{1}{4}\;\}$

Comprehensive Gröbner systems for parametric ideals were introduced, constructed, and studied in 1992 by Weispfenning, see [12]. After Weispfenning’s work, Kapur in [4] introduced an algorithm for parametric Gröbner bases. However, there was no big development on comprehensive Gröbner systems for around ten years. On the other hand, around 2003, big developments were made by Kapur-Sun-Wang [5], Montes [7], Nabeshima [8], Sato and Suzuki [10, 11], and Weispfenning [13].

Some of algorithms for computing comprehensive Gröbner systems are based on stability of Gröbner bases of ideals under specializations. Each algorithm has a different “stability condition” for monomial bases.

In this paper, taking inspiration from [9], we create a new iterative algorithm to compute comprehensive Gröbner systems.

In Section 2, we recall the definition of a comprehensive Gröbner system and we fix the notation and basic definitions needed for the rest of the paper. In Section 3, we describe the stability conditions used in previous papers to construct comprehensive Gröbner systems involving only computations in $K[A,X]$ instead of doing Gröbner basis computations in $K(A)[X]$. In Section 4, we describe our new iterative approach to compute comprehensive Gröbner system and we prove its correctness. In Section 5, we illustrate timings and statistics of our algorithm on known examples. In Section 6, we provide some ideas for further investigations and possible improvements.

Let $K$ be a field, $\bar{K}$ its algebraic closure, $X$ a set of $N_{X}$ indeterminates, and $A$ a set of $N_{A}$ parameters. We work in the polynomial ring $K[A,X]=K[a_{1},\dots,a_{N\!_{A}},\;x_{1},\dots,x_{N\!_{X}}]$.

We want to study what happens when we specialize the parameters $A$.

For example, given the point $P=(1,3)\in\mathbb{Q}^{2}$ and $f=3axy^{2}-bxy^{2}+ax^{2}+b$ in $\mathbb{Q}[a,b,\;x,y]$, we have $\mathrm{eval}_{P}(f)=x^{2}+3\in\mathbb{Q}[X]$.

Fixed a term-ordering $\tau$ on the power-products of $K[A,X]$, for a polynomial $f\in K[A,X]$ we denote by $\operatorname{LPP}(f)\in K[A,X]$ the $\tau$-greatest power-product in the support of $f$, by $\operatorname{LC}(f)\in K$ its coefficient, and by $\operatorname{LM}(f)=\operatorname{LC}(f)\cdot\operatorname{LPP}(f)$.

Throughout this paper we will only consider elimination orderings for $X$, i.e. such that any power-product only in $A$ is smaller than all power-products containing some $x_{i}\in X$. Such orderings reflect the interpretation of $K[A,X]$ as $K[A][X]$, with the polynomials in $A$ seen as “parametric coefficients”:

Throughout this paper, we indicate with gothic letters $\mathfrak{a}$, $\mathfrak{b}$, $\mathfrak{g}$ ideals in $K[A]$ (and their embedding in $K[A,X]$), and with $I$, $J$ ideals in $K[A,X]$.

Now we can formally define a Comprehensive Gröbner system.

In this section we recall how recent algorithms use stability conditions to construct comprehensive Gröbner systems involving only computations in $K[A,X]$ instead of having to track the arithmetic inside a Gröbner basis computation in $K(A)[X]$.

Suzuki-Sato in [11] observed that the stability theorem proved by Kalkbrener (for any ring homomorphism $\phi:K[A]\longrightarrow\bar{K}$), re-read in terms of $\mathrm{eval}_{P}$, provided this new approach for computing comprehensive Gröbner systems.

We briefly illustrate with a small example how they applied this theorem for constructing a comprehensive Gröbner system.

There is a delicate balance to keep in mind: reducing the number of cases to be considered, while controlling the cost for detecting them.

In this direction, further advance was achieved by proving that just a subset of the Gröbner basis in $K[A,X]$ needs to be considered. In [5] Kapur-Sun-Wang discovered a new stability condition, and in [9], Nabeshima improved it, further reducing redundant computation branches.

They are both centered on the following definition.

In general, it is always worth investigating whether a recursion could be translated into an iteration. Thinking this way may produce new insights and more efficient code. Instead of recursively passing the objects to be dealt with, we can collect them into one set (we call it VanishingToDo), and one by one we pick and process them.

This approach offers two general optimizations. One is that we can choose how to keep this set “minimal” (where the meaning of “minimal” may vary), and the other is that we can choose which “object” to pick first.

Inspired by Nabeshima’s [9] recursive algorithm, we designed this iterative algorithm. We keep VanishingToDo “minimal” in the sense of ideal inclusion (see Theorem 4.3).

Although not optimal, we can prove that many redundant branches of computations are avoided by checking ideal membership. In fact, throughout the computation, the set of ideals VanishingToDo is naturally inclusion-minimalized and new additions to it are “inclusion-increasing”. More precisely,

In this table we compare our iterative algorithm, “iter”, with our best implementations of Nabeshima’s algorithm, “N” and “N^∗”, in CoCoA-5.4.1v, running on a MacBookPro (i7, 2.3GHz).

In “N^∗” we disabled Nabeshima’s “RoughCheck”, because this operation is costly and may be intended as a post-processing applicable at the end of any algorithm for removing those segments whose support set is empty. Thus “N^∗” takes less time and returns a higher number of segments.

We used the examples listed in the papers [9], [5] and [6], and we encountered some discrepancies, so we indicate both names. Moreover, for some examples, the time of the very first GB in CoCoA is higher than the time obtained by the other authors for the whole computation, thus we are not quite sure we are using the same conditions/definitions. In particular, CoCoA could not compute the GBasis of Nabeshima’s example S2 with $a>b>c>d$, so we changed the example into $b>c>d>a$.

At the following link

http://www.dima.unige.it/b̃igatti/data/ComprehensiveGroebnerSystems/

the interested reader will find our CoCoA-5 package, CGS.cpkg5 (which is part of the forthcoming release CoCoA-5.4.2), together with the file containing all examples (which we used to generate the table of timings).

To investigate the different routes followed by the two algorithms, we tracked the number of calls and the time spent for some crucial operations:

GB in $K[A,X]$

the Gröbner basis computations of $I+\mathfrak{a}\in K[A,X]$ with an elimination ordering for $X$. This may be quite time consuming, especially for the very first computation: the Gröbner basis of the input ideal $I$.

GB in $K[A]$

the Gröbner basis computations of $\mathfrak{a}\in K[A]$: this is information is extracted from its actual application within “check $\mathfrak{a}\subseteq\mathfrak{b}$” and “check $\mathbb{V}(\mathfrak{a})\backslash\mathbb{V}(\mathfrak{b}){=}\emptyset$”.

check $\mathfrak{a}\subseteq\mathfrak{b}$

only in our iterative algorithm: ideal membership $f\in\mathfrak{b}$, using the Gröbner basis of $\mathfrak{b}$

check $\mathbb{V}(\mathfrak{a})\backslash\mathbb{V}(\mathfrak{b}){=}\emptyset$

(“Checking consistency” in [9] radical membership $f\in\sqrt{\mathfrak{b}}$, checking first if $f\in\mathfrak{b}$ (using “GB in $K[A]$”), and then using the Gröbner basis of $\mathfrak{b}+\langle 1-t{\cdot}f\rangle$.

product

only in Nabeshima’s algorithm: the product of the ideals, $N$, passed recursively as second argument

MB

the computations of the minimal basis of the monomial ideal $\langle\operatorname{LPP}_{X}(f)\mid f\in GB\rangle\;\subset K[X]$ (Definition 3.4)

sqfr

the computations for making square-free the generators of the ideals in $K[A]$ (Steps 2.5.2 and 2.6.5, and Remark 4.5) without computing the actual radical of the ideal.

last column

final number of segments in the resulting CGS, and the total time for its computation.

In this table we observe that most of the time is spent in computing the GB in $K[A,X]$ and the operations involved in removing redundant computational branches (GB in $K[A]$, product of ideals, the checks themselves). The complete algorithm “N” also performs “RoughCheck” which removes some useless segment from the final output.

We believe that tackling the problem with an iterative approach allows to have a better perspective on the computation: having the cases yet to be considered altogether in a single list makes it possible to compare them with the looser but faster ideal membership, instead of keeping track of them through the recursion with product of ideals and the costlier radical membership. Moreover, we expect that further new strategies may be developed for optimizing the computations.

In particular, we think that there are two main areas that can be studied further:

• •

  Strategies for picking the next ideal $\mathfrak{a}\subseteq K[A]$ to be considered (Step 2.1, function ChooseVanishing).

  Currently we randomly pick one out of those with maximum dimension.

• •

  Study possible criteria to minimize VanishingToDo, in order to reduce even further the cases that we analyze.

  Currently we keep in the list the minimal ones (Steps 2.5.2 and 2.6.6), so that we have “more zeroes”, and we make their generators square-free. But ideally with should keep the radicals of these ideals, or just keep the larger when two ideals sharing the same radical. Thus, finding a cheap check to detect “more zeroes or closer to the radical” should be a further improvement.

Acknowledgements The authors would like to thank Katsusuke Nabeshima, Yosuke Sato and Miwa Taniwaki.

This research was partly supported by the “National Group for Algebraic and Geometric Structures, and their Applications” (GNSAGA-INdAM).