D.2.9 redcgs_lib

Library:

redcgs.lib

Purpose:

Reduced Comprehensive Groebner Systems.

Overview:

Comprehensive Groebner Systems. Canonical Forms.
The library contains Monte's algorithms to compute disjoint, reduced Comprehensive Groebner Systems (CGS). A CGS is a set of pairs of (segment,basis). The segments S_i are subsets of the parameter space, and the bases B_i are sets of polynomials specializing to Groebner bases of the specialized ideal for every point in S_i.

The purpose of the routines in this library is to obtain CGS with better properties, namely disjoint segments forming a partition of the parameter space and reduced bases. Reduced bases are sets of polynomials that specialize to the reduced Groebner basis of the specialized ideal preserving the leading power products (lpp). The lpp characterize the type of solution in each segment.

A further objective is to summarize as much as possible the segments with the same lpp into a single segment, and if possible to obtain a final result that is canonical, i.e. independent of the algorithm and only attached to the given ideal.

There are three fundamental routines in the library: mrcgs, rcgs and crcgs. mrcgs (Minimal Reduced CGS) is an algorithm that packs so much as it is able to do (using algorithms adhoc) the segments with the same lpp, obtaining the minimal number of segments. The hypothesis is that the result is also canonical, but for the moment there is no proof of the uniqueness of this minimal packing. Moreover, the segments that are obtained are not locally closed, i.e. there are not difference of two varieties.

On the other side, Michael Wibmer has proved that for homogeneous ideals, all the segments with reduced bases having the same lpp admit a unique basis specializing well. For this purpose it is necessary to extend the description of the elements of the bases to functions, forming sheaves of polynomials instead of simple polynomials, so that the polynomials in a sheaf either preserve the lpp of the corresponding polynomial of the specialized Groebner basis (and then it specializes well) or it specializes to 0. Moreover, in a sheaf, for every point in the corresponding segment, at least one of the polynomials specializes well. specializes well. And moreover Wibmer's Theorem ensures that the packed segments are locally closed, that is can be described as the difference of two varieties.

Using Wibmer's Theorem we proved that an affine ideal can be homogenized, than discussed by mrcgs and finally de-homogenized. The bases so obtained can be reduced and specialize well in the segment. If the theoretic objective is reached, and all the segments of the homogenized ideal have been packed, locally closed segments will be obtained.

If we only homogenize the given basis of the ideal, then we cannot ensure the canonicity of the partition obtained, because there are many different bases of the given ideal that can be homogenized, and the homogenized ideals are not identical. This corresponds to the algorithm rcgs and is recommended as the most practical routine. It provides locally closed segments and is usually faster than mrcgs and crcgs. But the given partition is not always canonical.

Finally it is possible to homogenize the whole affine ideal, and then the packing algorithm will provide canonical segments by dehomogenizing. This corresponds to crcgs routine. It provides the best description of the segments and bases. In contrast crcgs algorithm is usually much more time consuming and it will not always finish in a reasonable time. Moreover it will contain more segments than mrcgs and possibly also more than rcgs.

But the actual algorithms in the library to pack segments have some lacks. They are not theoretically always able to pack the segments that we know that can be packed. Nevertheless, thanks to Wibmer's Theorem, the algorithms rcgs and crcgs are able to detect if the objective has not been reached, and if so, to give a Warning. The warning does not invalidate the output, but it only recognizes that the theoretical objective is not completely reached by the actual computing methods and that some segments that can be packed have not been packed with a single basis.

The routine buildtree is the first algorithm used in all the previous methods providing a first disjoint CGS, and can be used if none of the three fundamental algorithms of the library finishes in a reasonable time.

There are also routines to visualize better the output of the previous algorithms:
finalcases can be applied to the list provided by buildtree to obtain the CGS. The list provided by buildtree contains the whole discussion, and finalcases extracts the CGS.
The output of buildtree can also be transformed into a file using buildtreetoMaple routine that can be read in Maple. Using Monte's dpgb library in Maple the output can be plotted (with the routine tplot). To plot the output of mrcgs, rcgs or crcgs in Maple, the library also provides the routine cantreetoMaple. The file written using it and read in Maple can then be plotted with the command plotcantree and printed with printcantree from the Monte's dpgb library in Maple. The output of mrcgs, rcgs and crcgs is given in form of tree using prime ideals in a canonical form that is described in the papers. Nevertheless this canonical form is somewhat uncomfortable to be interpreted. When the segments are all locally closed (and this is always the case for rcgs and crcgs) the routine cantodiffcgs transforms the output into a simpler form having only one list element for each segment and providing the two varieties whose difference represent the segment also in a canonical form.

Authors:

Antonio Montes , Hans Schoenemann.

Overview:

see "Minimal Reduced Comprehensive Groebner Systems" by Antonio Montes. (http://www-ma2.upc.edu/~montes/).

Notations:

All given and determined polynomials and ideals are in the
basering K[a][x]; (a=parameters, x=variables)
After defining the ring and calling setglobalrings(); the rings
@R (K[a][x]),
@P (K[a]),
@RP (K[x,a]) are defined globally
They are used internally and can also be used by the user.
The fundamental routines are: buildtree, mrcgs, rcgs and crcgs

Procedures:

D.2.9.1 setglobalrings		It is called by the fundamental routines of the library: (buildtree, mrcgs, rcgs, crcgs). After calling it, the rings @R, @P and @RP are defined globally.
D.2.9.2 memberpos		Returns the list of two integers: the value 0 or 1 depending on if f belongs to J or not, and the position in J (0 if it does not belong).
D.2.9.3 subset		If all elements of F belong to the ideal G it returns 1, and 0 otherwise.
D.2.9.4 pdivi2		Pseudodivision of a polynomial f by an ideal F in @R. Returns a list (r,q,m) such that m*f=r+sum(q.G).
D.2.9.5 facvar		Returns all the free-square factors of the elements of ideal J (non repeated). Integer factors are ignored, even 0 is ignored. It can be called from ideal @R, but the given ideal J must only contain polynomials in the parameters.
D.2.9.6 redspec		Given null and non-null conditions depending only on the parameters it returns a red-specification.
D.2.9.7 pnormalform		Reduces the polynomial f w.r.t. to the null condition ideal N and the non-null condition ideal W (both depending on the parameters).
D.2.9.8 buildtree		Returns a list T describing a first reduced CGS of the ideal F in K[a][x].
D.2.9.9 buildtreetoMaple		Writes into a file the output of buildtree in Maple readable form.
D.2.9.10 finalcases		From the output of buildtree it provides the list of its terminal vertices. That list represents the dichotomic, reduced CGS obtained by buildtree.
D.2.9.11 mrcgs		Returns a list T describing the Minimal Reduced CGS of the ideal F of K[a][x]
D.2.9.12 rcgs		Returns a list T describing the Reduced CGS of the ideal F of K[a][x] obtained by direct homogenizing and de-homogenizing the basis of the given ideal.
D.2.9.13 crcgs		Returns a list T describing the Canonical Reduced CGS of the ideal F of K[a][x] obtained by homogenizing and de-homogenizing the initial ideal. cantreetoMaple)(M); Writes into a file the output of mrcgs, rcgs or crcgs in Maple readable form.
D.2.9.14 cantodiffcgs		From the output of rcgs or crcgs (or even of mrcgs when it is possible) it returns a simpler list where the segments are given as difference of varieties.