The RegularChains:-ChainTools subpackage is a collection of commands for manipulating regular chains. Some commands create regular chains from polynomials and possibly other regular chains. Other commands are used to study the properties of regular chains.

The commands Empty, ListConstruct, Construct, and Chain create regular chains from a list of polynomials representing a regular chain. The commands ListConstruct and Construct try to simplify this regular chain, which may result in splitting it into several ones. On the contrary, Chain returns only one regular chain.

The commands Cut, Polynomial, Under, and Upper, allow the user to extract part of the polynomials defining a regular chain.

The commands IsEmptyChain, IsZeroDimensional, IsAlgebraic, IsStronglyNormalized, Dimension, NumberOfSolutions, and IsPrimitive allow the user to inspect properties of a regular chain. This is often necessary since certain commands apply only to regular chains satisfying a particular property. For instance, the command NormalForm applies only to strongly normalized regular chains whereas SparsePseudoRemainder can be used with any regular chain. See the mathematical definitions below, for a description of some of those properties.

Like the commands RegularGcd and ExtendedRegularGcd, the command ExtendedNormalizedGcd computes a regular GCD of two input polynomials modulo the saturated ideal of a regular chain; in addition, ExtendedNormalizedGcd ensures that the output GCDs and regular chains are normalized.

The command IteratedResultant computes the iterated resultant of a polynomial w.r.t. a regular chain. This type of calculation is motivated by the following fundamental result: a polynomial p is regular w.r.t. the saturated ideal of a regular chain rc if and only if the iterated resultant of p w.r.t. rc is not zero.

The command Regularize provides a regularity test for a polynomial modulo the saturated ideal. In fact, it decomposes the input regular chain such that the input polynomial is either zero or regular modulo the saturated ideal of each output regular chains.

The command NormalizeRegularChain computes a triangular decomposition of a regular chain into other regular chains such that the intersection of the saturated ideals of the output regular chains has the same radical as the saturated ideal of input regular chain. Moreover, each output regular chain is normalized, and optionally, strongly normalized.

The command Squarefree computes a triangular decomposition of a regular chain into other regular chains such that the intersection of the saturated ideals of the output regular chains has the same radical as the saturated ideal of input regular chain. Moreover, each output regular chain is square free.

The command SquareFreeFactorization computes square-free decompositions of polynomials modulo the saturated ideal of a regular chain.

The command Extend computes a triangular decomposition into regular chains of the quasi-component of a triangular set.

The commands ChangeOfOrder, ChangeOfCoordinates, DahanSchostTransform, and Lift perform transformations on a regular chain. Refer to the help pages of those commands for more details.

The commands EquiprojectableDecomposition, SeparateSolutions, and RemoveRedundantComponents perform transformation on a list of regular chains. The first one takes as input a zero-dimensional variety V given as a list of strongly normalized regular chains; it then returns the equiprojectable decomposition of V in the form of another list of regular chains. The second one takes as input two zero-dimensional varieties V1 and V2 given by lists of regular chains; it then returns a list of regular chains pairwise disjoint and encoding the reunion of V1 and V2. RemoveRedundantComponents takes as input a list lrc1 of regular chains and returns another list lrc2 of regular chains such that they both form a triangular decomposition of the same variety (in the sense of Lazard) and the quasi-components of the regular chains in lrc2 are pairwise noninclusive.

The commands IsInSaturate and IsInRadical compare one polynomial p and one regular chain T. The first one decides whether p belongs to the saturated ideal I of T. This is done without computing a system of generators of I but just by pseudo-division. In fact, the RegularChains package never computes explicitly a system of generators for a saturated ideal. The second command decides whether p belongs to the radical of I; this is achieved simply by GCD computations.

The commands EqualSaturatedIdeals and IsIncluded compare two regular chains T1 and T2. More precisely, the first one decides whether the saturated ideals of T1 and T2 are equal or not. If the second one returns true, then the saturated ideal of T1 is contained in that of T2. However, if it returns false, nothing can be said.

The command SubresultantChain returns a data structure which encodes the subresultant chain of two univariate polynomials.  The commands LastSubresultant and SubresultantOfIndex inspect such a data structure.

A polynomial p is said to be normalized with respect to a regular chain T if p is constant or if the main variable of p is not algebraic with respect to T and the initial of p is normalized with respect to T. The regular chain T is said to be normalized if every polynomial p of T is normalized with respect to the polynomials of T with main variable less than v, where v is the main variable of p.

A regular chain T is said to be strongly normalized if for every polynomial p in T, each variable of in the initial of p is free (that is, not algebraic) with respect to T. Strongly normalized regular chains have the following fundamental property: Let U and X be the set of the free variables and algebraic variables of T. Let K be the field of rational functions with variables in U. and let T be a strongly normalized regular chain. Then T is a lexicographical Groebner basis of the ideal it generates in K[X].

The following is a list of available commands.

Aubry, P.; Lazard, D. and Moreno Maza, M. "On the theories of triangular sets" J. Symb. Comp., Vol. 28 (1999): 105-124.

Boulier, F. and Lemaire, F. "Computing canonical representatives of regular differential ideals" In Proc. ISSAC 2000, St Andrews, Scotland, 2000.

Chen, C.; Lemaire, F.; Moreno Maza, M.; Pan, W. and Xie, Y. "Efficient Computations of Irredundant Triangular Decompositions with the RegularChains Library" Proceedings of CASA 2007, Lecture Notes in Computer Science, Vol. 4488, Springer, 2007.

Dahan, X. and Schost, E. "Sharp Estimates for Triangular Sets" In Proc. ISSAC 2004, Santander, Spain, ACM Press, 2004.

Dahan, X.; Moreno Maza, M.; Schost, E.; Wu, W. and Xie, Y. "Lifting techniques for triangular decompositions" In Proc. ISSAC 2005, Beijing, China, ACM Press, 2005.

Dahan, X.; Jin, X.; Moreno Maza, M.; and Schost, E. "Change of ordering for regular chains in positive dimension" J. of Theoretical Computer Science, Vol. 392 (2008): 3765.

Della Dora, J.; Discrescenzo, C.; and Duval, D. "About a new method for computing in algebraic number fields" In Proc. EUROCAL 85 Vol. 2, 1985.

Kalkbrener, M. "Three contributions to elimination theory" PhD Thesis, University of Linz, Austria, 1991.

Kalkbrener, M. "A generalized Euclidean algorithm for computing triangular representations of algebraic varieties" J. Symb. Comp., Vol. 15 (1993): 143-167.

Lazard, D. "Solving zero-dimensional algebraic systems" J. Symb. Comp., Vol. 13 (1992) : 117-133.

Lemaire, F.; Moreno Maza, M.; Pan, W.; and Xie, Y. "When does T equal Sat(T)?" In Proc. ISSAC 2008, Linz, Austria, ACM Press, 2008.

Li, X.; Moreno Maza, M.; and Pan, W. "Computations modulo regular chains." In Proc. ISSAC 2009, Linz, Austria, ACM Press, 2009.

Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties" MEGA-2000 conference Bath, UK, England.

Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions" In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948, Springer, 1995.

Schost, E. "Complexity results for triangular sets" J. Symb. Comp., Vol. 36 No. 3-4 (2003): 555-594.

Wang, D. M. "Decomposing Polynomial Systems into Simple Systems" J. Symb. Comp., Vol. 25 No. 3 (1998): 295-314.