
D.2.4 grobcov_lib
 Library:
 grobcov.lib
 Purpose:
 Oktober 2016 Groebner Cover for parametric ideals.
Groebner Cover for parametric ideals.
Comprehensive Groebner Systems, Groebner Cover, Canonical Forms, Parametric Polynomial Systems,
Dynamic Geometry, Loci, Envelop, Constructible sets. See:
A. Montes A, M. Wibmer,
"Groebner Bases for Polynomial Systems with parameters",
Journal of Symbolic Computation 45 (2010) 13911425.
(https://www.mat.upc.edu//en/people/antonio.montes/).
 Important:
 The book, not yet published:
A. Montes. "Discussing Parametric Polynomial Systems: The Groebner Cover"
can be used as a user manual of all the routines included in this library.
It defines and proves all the theoretic results used here, and shows examples of all the routines.
It will be published soon.
 Authors:
 Antonio Montes (Universitat Politecnica de Catalunya),
Hans Schoenemann (Techische Universitaet Kaiserslautern).
 Overview:
 In 2010, the library was designed to contain MontesWibmer's algorithms for computing the
Canonical Groebner Cover of a parametric ideal.
The central routine is grobcov. Given a parametric ideal, grobcov outputs its Canonical
Groebner Cover, consisting of a set of pairs of (basis, segment). The basis (after normalization)
is the reduced Groebner basis for each point of the segment. The segments are disjoint, locally closed
and correspond to constant lpp (leading power product) of the basis, and are represented in canonical
representation. The segments are disjoint and cover the whole parameter space. The output is
canonical, it only depends on the given parametric ideal and the monomial order.
This is much more than a simple Comprehensive Groebner System. The algorithm grobcov allows
options to solve partially the problem when the whole automatic algorithm does not finish
in reasonable time.
grobcov uses a first algorithm cgsdr that outputs a disjoint reduced Comprehensive Groebner System
with constant lpp. For this purpose, in this library, the implemented algorithm is
KapurSunWang algorithm, because it is actually the most efficient algorithm known for this purpose.
D. Kapur, Y. Sun, and D.K. Wang "A New Algorithm for Computing Comprehensive Groebner Systems".
Proceedings of ISSAC'2010, ACM Press, (2010), 2936.
The library has evolved to include new applications of the Groebner Cover, and new theoretical
developments have been done.
The actual version also includes a routine (ConsLevels) for computing the canonical form of a
constructible set, given as a union of locally closed sets. It is used in the new version for the
computation of loci and envelops. It determines the canonical locally closed level sets of a
constructible set. It is described in:
J.M. Brunat, A. Montes, "Computing the canonical representation of constructible sets".
Math. Comput. Sci. (2016) 19: 165178.
A new set of routines (locus, locusdg, locusto) has been included to compute loci of points.
The routines are used in the Dynamic Geometry software Geogebra. They are described in:
M.A. Abanades, F. Botana, A. Montes, T. Recio:
"An Algebraic Taxonomy for Locus Computation in Dynamic Geometry".
ComputerAided Design 56 (2014) 2233.
Recently also routines for computing the generalized envelop of a family of hypersurfaces (envelop),
to be used in Dynamic Geometry, has been included and is described in the book (not yet published)
A. Montes. "Discussing Parametric Polynomial Systems: The Groebner Cover"
This version was finished on 31/10/2016
 Notations:
 All given and determined polynomials and ideals are in the
basering Q[a][x]; (a=parameters, x=variables)
After defining the ring, the main routines
grobcov, cgsdr,
generate the global rings
@R (Q[a][x]),
@P (Q[a]),
@RP (Q[x,a])
that are used inside and killed before the output.
Procedures:
D.2.4.1 setglobalrings   Generates the global rings @R, @P and @RP that are respectively the rings Q[a][x], Q[a], Q[x,a]. It is called inside each of the fundamental routines of the library: grobcov, cgsdr, locus, locusdg and killed before the output. In the actual version, after the call of setglobalrings on Q[a][x], the public names of the defined ideals generated by setglobalrings are Grobcov::@R, Grobcov::@P, Grobcov::@RP. 
D.2.4.2 grobcov   Is the basic routine giving the canonical Groebner Cover of the parametric ideal F. This routine accepts many options, that allow to obtain results even when the canonical computation does not finish in reasonable time. 
D.2.4.3 cgsdr   Is the procedure for obtaining a first disjoint, reduced Comprehensive Groebner System that is used in grobcov, but can also be used independently if only a CGS is required. It is a more efficient routine than buildtree (the own routine of 2010 that is no more used). Now, KapurSunWang (KSW) algorithm is used. 
D.2.4.4 pdivi   Performs a pseudodivision of a parametric polynomial by a parametric ideal. 
D.2.4.5 pnormalf   Reduces a parametric polynomial f over V(E)  V(N) (E is the null ideal and N the nonnull ideal ) over the parameters. 
D.2.4.6 Crep   Computes the canonical Crepresentation of V(N)  V(M). It can be called in Q[a] or in Q[a][x], but the ideals N,M can only contain parameters of Q[a]. 
D.2.4.7 Prep   Computes the canonical Prepresentation of V(N)  V(M). It can be called in Q[a] or in Q[a][x], but the ideals N,M can only contain parameters of Q[a]. 
D.2.4.8 PtoCrep   Starting from the canonical Prep of a locally closed set computes its Crep. 
D.2.4.9 extendpoly   Given the generic representation f of an Iregular function F defined by poly f on V(p)  V(q) it returns its full representation. 
D.2.4.10 extendGC   When the grobcov of an ideal has been computed with the default option ("ext",0) and the explicit option ("rep",2) (which is not the default), then one can call extendGC(GC) (and options) to obtain the full representation of the bases. With the default option ("ext",0) only the generic representation of the bases is computed, and one can obtain the full representation using extendGC. 
D.2.4.11 ConsLevels   Given a list L of locally closed sets, it returns the closures of the canonical levels of the constructible set and its complements of the union of them. It is described in J.M. Brunat, A. Montes, "Computing the canonical representation of constructible sets". Math. Comput. Sci. (2016) 19: 165178. 
D.2.4.12 ConsLevelsToLevels   Transforms the output of ConsLevels into the proper Levels of the constructible set. 
D.2.4.13 locus   Special routine for determining the geometrical locus of points verifying given conditions. Given a parametric ideal J with parameters (x,y) and variables (x_1,..,xn), representing the system determining the locus of points (x,y) who verify certain properties, one can apply locus to the output of grobcov(J). locus determines the different classes of locus components, following the taxonomy described in M. Abanades, F. Botana, A. Montes, T. Recio, "An Algebraic Taxonomy for Locus Computation in Dynamic Geometry", ComputerAided Design 56 (2014) 2233. The components can be "Normal", "Special", "Accumulation", "Degenerate". The output are the components given in Pcanonical form. It also detects automatically a possible point that is to be avoided by the mover, whose coordinates must be the last coordinates in the definition of the ring. If such a point is detected, then it eliminates the segments of the grobcov depending on the point that is to be avoided. 
D.2.4.14 locusdg   Is a special routine that determines the "Relevant" components of the locus in dynamic geometry. It is to be called to the output of locus and selects from it the useful components. 
D.2.4.15 envelop   Special routine for determining the envelop of a family of hypersurfaces F in Q[x1,..,xn][t1,..,tm] depending on a ideal of constraints C in Q[t1,..,tm]. It detemines the different components as well as its type: "Normal", "Special", "Accumulation", "Degenerate". And it also classifies the "Special" components, determining the zero dimensional antiimage of the component and verifying if the component is a special hypersurface of the family or not. It calls internally first grobcov and then locus with special options to obtain the complete result. The taxonomy that it provides, as well as the algorithms involved are described in the book: (not yet published) A. Montes. "Discussing Parametric Polynomial Systems: The Groebner Cover" 
D.2.4.16 locusto   Transforms the output of locus, locusdg, envelop into a string that can be reed from different computational systems. 
D.2.4.17 AssocTanToEnv   Having computed an envelop component E of a family of hypersurfaces F, with constraints C, it returns the parameter values of the associated tangent hypersurface of the family passing at one point of the envelop component E. 
D.2.4.18 FamElemsAtEnvCompPoints   Having computed an envelop component E of a family of hypersurfaces F, with constraints C, it returns the parameter values of all the hypersurfaes of the family passing at one point of the envelop component E. 
D.2.4.19 discrim   Determines the factorized discriminant of a degree 2 polynomial in the variable x. The polynomial can be defined on any ring where x is a variable. The polynomial f can depend on parameters and variables. 
D.2.4.20 WLemma   Given an ideal F in K[a][x] and an ideal A in K[a], it returns the list (lpp,B,S) were B is the reduced Groebner basis of the specialized F over the segment computed in Prepresentation (or optionally in Crepresentation). The basis is given by Iregular functions. 
See also:
compregb_lib.
