Groebner - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Groebner

  

MultiplicationMatrix

  

compute multiplication matrices

  

NormalSet

  

compute monomial bases

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

NormalSet(J, tord)

MultiplicationMatrix(f, ns, rv, G, tord, characteristic=p)

Parameters

J

-

Groebner basis with respect to tord or a PolynomialIdeal (zero-dimensional)

tord

-

ShortMonomialOrder

f

-

a polynomial

ns, rv

-

normal set (the sequence returned by NormalSet)

p

-

(optional) characteristic

Description

• 

The NormalSet command computes a monomial basis for the quotient K[x1,...,xn]/J when J is a zero-dimensional ideal. The input can be either a Groebner basis with respect to tord or a PolynomialIdeal, in which case a Groebner basis with respect to tord is computed. The output is a sequence of two elements, ns and rv.  ns is sorted list of monomials comprising a basis for the quotient as a vector space, while rv is a table which reverses ns, i.e.: rv[ns[i]] = i for i=1..nops(ns).  The purpose of rv is to allow one to assign the coefficients of a polynomial to a vector with respect to ns in linear time.

• 

The number of elements in a normal set ns is equal to the number of solutions of the system over the algebraic closure of the coefficient field.

• 

The MultiplicationMatrix command constructs the multiplication matrix for a polynomial f with respect to J and tord. The rows of this matrix are the normal forms of ns[i]*f written as a vector with respect to ns, and its eigenvalues include the values of the polynomial f on the variety V(J). In particular, if f = x is a variable one obtains the x-coordinates of the solution of J among the eigenvalues of the multiplication matrix. This can be used to solve a zero-dimensional polynomial system.

Examples

Example 1: A Lagrange multiplier problem

withGroebner:

fx3+2xyzz2:

gx2+y2+z21:

Ff+λg:

JconvertVectorCalculusGradientF,λ,x,y,z,set

J2λy+2xz,2λz+2xy2z,2λx+3x2+2yz,x2+y2+z21

(1)

tordtdegλ,x,y,z

tordtdegλ,x,y,z

(2)

GBasisJ,tord:

ns,rvNormalSetG,tord

ns,rv1,z,y,x,λ,z2,yz,xz,λz,y2,λ2,z3,tableyz=7,1=1,λ2=11,xz=8,λ=5,y=3,x=4,z2=6,y2=10,z=2,z3=12,λz=9

(3)

MxMultiplicationMatrixx,ns,rv,G,tord

(4)

MyMultiplicationMatrixy,ns,rv,G,tord

(5)

MzMultiplicationMatrixz,ns,rv,G,tord

(6)

MlambdaMultiplicationMatrixλ,ns,rv,G,tord

(7)

Verify that the matrices commute

LinearAlgebraNorm`.`Mx,My`.`My,Mx,∞

0

(8)

Example 2: A geometric intersection problem

f_13x_12x_2+9x_12+2x_1x_2+5x_1+x_23:

f_22x_13x_2+6x_132x_12x_1x_23x_1x_2+3:

f_3x_13x_2+3x_13+x_12x_2+2x_12:

GBasisf_1,f_2,f_3,tdegx_1,x_2

G2x_228x_15x_23,x_1x_2+x_1x_2+3,2x_123x_1+2x_26

(9)

ns,rvNormalSetG,tdegx_1,x_2

ns,rv1,x_2,x_1,table1=1,x_1=3,x_2=2

(10)

M1MultiplicationMatrixx_1,ns,rv,G,tdegx_1,x_2

M1001−31−13−132

(11)

M2MultiplicationMatrixx_2,ns,rv,G,tdegx_1,x_2

M201032524−31−1

(12)

`.`M1,M2`.`M1,M2

000000000

(13)

Read the roots of the system from the eigenvalues of the multiplication matrices M1, M2

LinearAlgebraEigenvectorsM1

054+65454654,13154+6541546541254+3654514+6542543654514654011

(14)

LinearAlgebraEigenvectorsM2

334+65434654,1314252+65234+6541425265234654114252+65214252652011

(15)

Example 3: A celestial mechanics problem. System S4 (Newtonian planar 4-body problem with equal masses)

e12p3+2p3φ34φ3sp2+5φ3s3pφ3s5:

e22sp32φ3s2+φ3s43φ3s2p+2φ3p:

e32s2+s44s2p+φ2+1+4p:

GBasise1,e2,e3,tdegs,p,φ:

ns,rvNormalSetG,tdegp,s,φ:

MphiMultiplicationMatrixφ,ns,rv,G,tdegp,s,φ

(16)

P37sortfactorLinearAlgebraCharacteristicPolynomialMphi,φ

P37φ23φ3761φ34+336φ33240φ32+2052φ3112120φ30+8400φ2930456φ28+175113φ2788548φ26+241040φ251364385φ24+338994φ231081984φ22+6241506φ21+642162φ20+2319507φ1915790278φ1812287376φ17+1386909φ16+11212992φ15+55894536φ1419889496φ13+53738964φ12128353329φ11+44215308φ10172452240φ9+160917273φ842764598φ7+217615248φ6115440795φ5+17124210φ4139060395φ3+39858075φ2+39858075φ2+16φ48

(17)

The minimal polynomial of Mphi is part of the plex Groebner basis of [e1,e2,e3] and P37 is a multiple of it.

LGroebnerBasise1,e2,e3,plexp,s,φ:

normalP37L1

φ41φ2+13

(18)

References

  

Corless, Robert M. "Groebner Bases and Matrix Eigenproblems." SIGSAM Bulletin (Communications in Computer Algebra), Vol. 30, No. 4, Issue 118, (December 1996): 26-32.

  

Cox, D.; Little, J.; and O'Shea, D. Using Algebraic Geometry. Springer-Verlag, 1998

See Also

Basis

NormalForm

UnivariatePolynomial