convert Groebner bases from one ordering to another - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/FGLM

Groebner[FGLM] - convert Groebner bases from one ordering to another

Calling Sequence

FGLM(G, T1, T2, opts)

Parameters

G

-

Groebner basis with respect to starting order T1 or a PolynomialIdeal

T1,T2

-

monomial orders (of type ShortMonomialOrder)

opts

-

optional arguments of the form keyword=value

Description

• 

The FGLM algorithm converts a Groebner basis of commutative polynomials from one monomial order to another. This algorithm is frequently applied when a Groebner basis is too difficult to compute directly.

• 

The FGLM command takes as input a Groebner basis G with respect to a monomial order T1, and outputs the reduced Groebner basis for G with respect to T2.  If the first argument G is a PolynomialIdeal then a Groebner basis for G with respect to T1 is computed if one is not already known.  

• 

The ideal defined by G must have a finite number of complex solutions (see IsZeroDimensional), otherwise the algorithm would not terminate.  This condition is not checked if one of the optional arguments stoppingcondition or truncationorder is specified (see below).  The check may also fail incorrectly if G is not a Groebner basis.

• 

The orders T1 and T2 must be proper monomial orders on the polynomial ring, so 'min' orders such as 'plex_min' and 'tdeg_min' are not supported. FGLM does not check that G is a Groebner basis with respect to T1. Also, due to a limitation, T2 cannot be a matrix order that eliminates variables, i.e.: the first row of any matrix order must be strictly positive.

• 

The optional argument characteristic=p specifies the characteristic of the coefficient field. The default is zero.  This option is ignored if G is a PolynomialIdeal. For problems with extreme coefficient blowup, it may be useful to run FGLM modulo a large prime p. Heuristically, this constructs the image modulo p of the desired Groebner basis, which may be sufficient for some applications.  Another option is to compute a RationalUnivariateRepresentation.

• 

The optional argument truncationorder=n, for a non-negative integer n specifies that monomials of degree greater than n not be considered.  This crudely bounds the algorithm and ensures termination even for non zero-dimensional ideals, however the output may not be a Groebner basis with respect to T2.

• 

The optional argument stoppingcondition=f, for a boolean-valued procedure f with one argument m, terminates the algorithm prematurely if the current monomial m satisfies the condition f(m)=true. Its primary use is the elimination of variables (illustrated below), but there are also more inventive uses.  For example, one could terminate the algorithm after some amount of time and still obtain a partial result.

• 

The optional argument output=basislm returns the basis in an extended format containing leading monomials and coefficients.  Each element is a list of the form [leading coefficient, leading monomial, polynomial].

• 

Setting infolevel[FGLM] to a positive integer value directs FGLM to output increasingly detailed information about its performance and progress.

• 

The MultivariateCyclicVector command is a generalization of FGLM to modules and non-commutative skew algebras.

Examples

withGroebner:

F:=x3+xyy2+1,y3xy+x

F:=x3+xyy2+1,y3xy+x

(1)

G:=BasisF,tdegx,y

G:=y3xy+x,x3+xyy2+1

(2)

FGLMG,tdegx,y,plexx,y

y9+y63y5+4y42y32y2+3y1,y8+y7+y6+2y5y4+3y3+x2y+1

(3)

BasisG,plexx,y

y9+y63y5+4y42y32y2+3y1,y8+y7+y6+2y5y4+3y3+x2y+1

(4)

Here we use the stoppingcondition option to compute only the univariate polynomial in x.

FGLMG,tdegx,y,plexy,x,stoppingcondition=m→hasm,y

x92x7+2x62x55x4+3x33x22x+1

(5)

See Also

Basis, IsZeroDimensional, MultivariateCyclicVector, RationalUnivariateRepresentation, Walk

References

  

Faugere, J.; Gianni, P.; Lazard, P.; and Mora, T. "Efficient computation of zero-dimensional Grobner bases by change of ordering." J. Symbolic Comput., Vol. 16, (1993): 329-344.


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam