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:

JconvertVectorCalculus[Gradient]F,λ,x,y,z,set

J:=2λy+2xz,2λz+2xy2z,2λx+3x2+2yz,x2+y2+z21

(1)

tordtdegλ,x,y,z

tord:=tdegλ,x,y,z

(2)

GBasisJ,tord:

ns,rvNormalSetG,tord

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

(3)

MxMultiplicationMatrixx,ns,rv,G,tord

Mx:= 12 x 12 MatrixData Type: anythingStorage: sparseOrder: Fortran_order

(4)

MyMultiplicationMatrixy,ns,rv,G,tord

My:= 12 x 12 MatrixData Type: anythingStorage: sparseOrder: Fortran_order

(5)

MzMultiplicationMatrixz,ns,rv,G,tord

Mz:= 12 x 12 MatrixData Type: anythingStorage: sparseOrder: Fortran_order

(6)

MlambdaMultiplicationMatrixλ,ns,rv,G,tord

Mlambda:= 12 x 12 MatrixData Type: anythingStorage: sparseOrder: Fortran_order

(7)

Verify that the matrices commute

LinearAlgebra[Norm]Mx.MyMy.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

G:=2x_228x_15x_23,x_1x_2+x_1x_2+3,2x_123x_1+2x_26

(9)

ns,rvNormalSetG,tdegx_1,x_2

ns,rv:=1,x_2,x_1,table1=1,x_2=2,x_1=3

(10)

M1MultiplicationMatrixx_1,ns,rv,G,tdegx_1,x_2

M1:=0013113132

(11)

M2MultiplicationMatrixx_2,ns,rv,G,tdegx_1,x_2

M2:=01032524311

(12)

M1.M2M1.M2

000000000

(13)

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

LinearAlgebra[Eigenvectors]M1

54+14655414650,154+14651541465132554+346514+1465255434651414651110

(14)

LinearAlgebra[Eigenvectors]M2

334+1465341465,1314252+126534+1465142521265341465114252+1265142521265011

(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,φ

Mphi:= 99 x 99 MatrixData Type: anythingStorage: sparseOrder: Fortran_order

(16)

P37sortfactorLinearAlgebra[CharacteristicPolynomial]Mphi,φ

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.

LGroebner[Basis]e1,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

 


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