general-purpose and parametrizable iteration algorithm - Maple Help

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

Groebner[MultivariateCyclicVector] - general-purpose and parametrizable iteration algorithm

 Calling Sequence MultivariateCyclicVector(NFproc, FDproc, TMproc, M)

Parameters

 NFproc - function to compute normal forms FDproc - function to find dependencies TMproc - function to decide when to terminate M - monomial order on an Ore algebra

Description

 • The MultivariateCyclicVector command performs an iteration algorithm (similar to FGLM) to compute a Groebner basis with respect to M of (skew) polynomials whose normal forms under NFproc are zero.
 • Common uses of the MultivariateCyclicVector command are the following.
 (i) - To compute Groebner bases by change of ordering (a first Groebner basis is known for a monomial order, a second one is computed for another order).
 (ii) - To find equations defining a function. See the Examples section.
 • More specifically, NFproc takes three arguments.

 m a monomial in the algebra ${M}_{\mathrm{algebra}}$; NF a table with monomials already dealt with as indices and normal forms already computed as corresponding entries; M a monomial order (actually, the table M of the call to MultivariateCyclicVector).

 It returns a normal form for the monomial m and stores it as ${\mathrm{NF}}_{m}$ into NF.
 • FDproc takes two arguments:

 mi a list of monomials that generate a monoideal (that is, a set of monomials that is stable under product); NF is a table of the same type as above.

 It returns either a nontrivial linear combination of the indices of NF that evaluates to 0 under NFproc, or FAIL when no such dependency exists.  This function must not use entries in NF corresponding to indices that are elements of the monoideal generated by mi.
 • The procedure TMproc is used to decide when to stop the algorithm.  It takes three arguments.

 border a list of monomials still to be dealt with by the algorithm; monoideal a list of monomials that generate a monoideal (that is, a set of monomials that is stable under product); TOrd the monomial order with respect to which they are enumerated.

 • The MultivariateCyclicVector command returns an expseq NF, EQ, where NF is the table of all normal forms computed during the calculations and EQ is a table of all linear dependencies found.
 Note: The algorithm cannot detect non-zero-dimensional cases; it may loop forever when called on such cases.
 • For the purpose of computing changes of orderings in the commutative case, the alternative command FGLM is more efficient.

Examples

Change of orderings

The FGLM algorithm was originally introduced to compute Groebner bases by a change of monomial orderings.

 > $\mathrm{with}\left(\mathrm{Ore_algebra}\right):$
 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $A:=\mathrm{poly_algebra}\left(x,y,z,t\right):$
 > $G:=\left[{x}^{31}-{x}^{6}-x-y,{x}^{8}-z,{x}^{10}-t,{x}^{2}+{y}^{2}+{z}^{2}-{t}^{2}\right]:$
 > ${M}_{\mathrm{org}}:=\mathrm{MonomialOrder}\left(A,\mathrm{wdeg}\left(\left[1,31,8,10\right],\left[x,y,z,t\right]\right)\right):$

Here is the initial Groebner basis.

 > ${\mathrm{GB}}_{\mathrm{org}}:=\mathrm{Basis}\left(G,{M}_{\mathrm{org}}\right)$
 ${{\mathrm{GB}}}_{{\mathrm{org}}}{:=}\left[{{x}}^{{8}}{-}{z}{,}{{x}}^{{2}}{}{z}{-}{t}{,}{-}{t}{}{{x}}^{{6}}{+}{{z}}^{{2}}{,}{{x}}^{{6}}{-}{{t}}^{{3}}{}{x}{+}{x}{+}{y}{,}{-}{2}{}{{t}}^{{3}}{}{{x}}^{{7}}{+}{{t}}^{{6}}{}{{x}}^{{2}}{+}{t}{}{{x}}^{{6}}{+}{2}{}{{x}}^{{7}}{-}{2}{}{{t}}^{{3}}{}{{x}}^{{2}}{+}{t}{}{{x}}^{{2}}{-}{{t}}^{{2}}{+}{2}{}{{x}}^{{2}}{,}{-}{{t}}^{{2}}{}{{x}}^{{6}}{+}{{t}}^{{6}}{}{z}{-}{2}{}{{t}}^{{4}}{}{{x}}^{{3}}{-}{2}{}{{t}}^{{3}}{}{z}{+}{{t}}^{{2}}{}{{x}}^{{2}}{+}{2}{}{t}{}{{x}}^{{3}}{+}{t}{}{z}{+}{2}{}{z}{,}{-}{2}{}{{t}}^{{4}}{}{{x}}^{{5}}{+}{{t}}^{{7}}{+}{{t}}^{{2}}{}{{x}}^{{4}}{+}{2}{}{t}{}{{x}}^{{5}}{-}{2}{}{{t}}^{{4}}{-}{{t}}^{{2}}{}{z}{+}{{t}}^{{2}}{+}{2}{}{t}\right]$ (1)

Check that you are in the zero-dimensional case.

 > $\mathrm{HilbertDimension}\left(,{M}_{\mathrm{org}}\right)$
 ${0}$ (2)

Define NFproc and FDproc in view of a call to MultivariateCyclicVector.

 > NFproc:=proc(m,NF,MOrd)     NF[m]:=NormalForm(m,GB[org],M[org]) end proc:
 > FDproc:=proc(M,NF)     local ind_lst,term,eta,sol;     ind_lst:=map(op,[indices(NF)]);     for term in M do         ind_lst:=remove(divide,ind_lst,term)     end do;     expand(numer(normal(add(eta[term]*NF[term],term=ind_lst))));     sol:=[solve({coeffs(%,{x,y,z,t})},{seq(eta[term],term=ind_lst)})];     subs(op(1,sol),add(eta[term]*term,term=ind_lst));     if(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,         map2(op,1,select(evalb,sol[1]))),%)),[x,y,z,t]),         [x,y,z,t],distributed,factor)) end proc:
 > TMproc:=proc(border,monoideal,MOrd)     border<>[] end proc:
 > ${M}_{\mathrm{new}}:=\mathrm{MonomialOrder}\left(A,\mathrm{tdeg}\left(x,y,z,t\right)\right):$
 > $\mathrm{fglm}:=\left[\mathrm{MultivariateCyclicVector}\left(\mathrm{NFproc},\mathrm{FDproc},\mathrm{TMproc},{M}_{\mathrm{new}}\right)\right]:$

Up to reordering, here is the final Groebner basis.

 > $\mathrm{map}\left(\mathrm{op},\left[\mathrm{entries}\left({\mathrm{fglm}}_{2}\right)\right]\right)$
 $\left[{-}{{t}}^{{2}}{+}{{x}}^{{2}}{+}{{y}}^{{2}}{+}{{z}}^{{2}}{,}{{t}}^{{4}}{}{y}{-}{{t}}^{{3}}{}{{z}}^{{2}}{-}{{t}}^{{2}}{}{x}{}{z}{+}{x}{}{{z}}^{{3}}{+}{{t}}^{{2}}{}{x}{+}{t}{}{x}{-}{t}{}{y}{+}{{z}}^{{2}}{,}{-}{{t}}^{{3}}{}{x}{}{y}{+}{{t}}^{{2}}{}{x}{}{{z}}^{{2}}{-}{{z}}^{{4}}{-}{{t}}^{{3}}{+}{t}{}{{y}}^{{2}}{+}{t}{}{{z}}^{{2}}{+}{{t}}^{{2}}{+}{2}{}{x}{}{y}{-}{{z}}^{{2}}{,}{{t}}^{{4}}{}{z}{+}{{t}}^{{3}}{}{x}{}{y}{+}{{t}}^{{2}}{}{x}{}{{y}}^{{2}}{-}{x}{}{y}{}{{z}}^{{2}}{+}{{z}}^{{4}}{+}{{t}}^{{3}}{-}{t}{}{{y}}^{{2}}{-}{t}{}{{z}}^{{2}}{-}{{t}}^{{2}}{-}{t}{}{x}{-}{t}{}{y}{-}{t}{}{z}{-}{2}{}{x}{}{y}{,}{-}{{t}}^{{5}}{+}{t}{}{x}{}{y}{}{z}{+}{x}{}{{z}}^{{3}}{+}{{t}}^{{2}}{,}{-}{{t}}^{{4}}{}{x}{+}{t}{}{x}{+}{t}{}{y}{+}{{z}}^{{2}}{,}{t}{}{x}{}{y}{}{{z}}^{{3}}{+}{2}{}{{t}}^{{3}}{}{x}{-}{{t}}^{{2}}{}{{z}}^{{2}}{-}{{z}}^{{3}}{+}{{t}}^{{2}}{+}{t}{}{x}{-}{t}{}{y}{-}{2}{}{x}{-}{2}{}{y}{,}{t}{}{{z}}^{{4}}{-}{{t}}^{{3}}{-}{t}{}{x}{}{y}{+}{t}{}{{y}}^{{2}}{+}{t}{}{{z}}^{{2}}{-}{x}{}{{z}}^{{2}}{,}{-}{{t}}^{{4}}{-}{{t}}^{{2}}{}{x}{}{y}{+}{2}{}{{t}}^{{2}}{}{{y}}^{{2}}{+}{t}{}{{z}}^{{3}}{+}{x}{}{{y}}^{{3}}{+}{x}{}{y}{}{{z}}^{{2}}{-}{{y}}^{{4}}{+}{{z}}^{{4}}{+}{2}{}{t}{}{z}{-}{x}{}{z}{,}{{t}}^{{3}}{}{x}{}{y}{-}{{t}}^{{2}}{}{y}{}{{z}}^{{2}}{+}{x}{}{{z}}^{{3}}{-}{{z}}^{{4}}{-}{{t}}^{{2}}{}{x}{+}{t}{}{x}{}{y}{+}{{t}}^{{2}}{-}{2}{}{{y}}^{{2}}{-}{{z}}^{{2}}{,}{2}{}{{t}}^{{4}}{}{y}{-}{{t}}^{{3}}{}{x}{}{z}{+}{t}{}{{y}}^{{4}}{-}{2}{}{{t}}^{{2}}{}{x}{}{z}{-}{t}{}{x}{}{y}{}{z}{+}{x}{}{{z}}^{{3}}{+}{2}{}{{z}}^{{4}}{-}{{t}}^{{3}}{+}{2}{}{{t}}^{{2}}{}{x}{-}{2}{}{{t}}^{{2}}{}{z}{-}{t}{}{x}{}{y}{+}{t}{}{{y}}^{{2}}{+}{t}{}{{z}}^{{2}}{-}{x}{}{{z}}^{{2}}{-}{{t}}^{{2}}{+}{2}{}{t}{}{x}{-}{2}{}{t}{}{y}{+}{x}{}{z}{+}{y}{}{z}{+}{2}{}{{z}}^{{2}}{,}{x}{}{{z}}^{{4}}{-}{{t}}^{{2}}{}{x}{-}{{t}}^{{2}}{}{y}{+}{x}{}{{y}}^{{2}}{+}{x}{}{{z}}^{{2}}{+}{{y}}^{{3}}{+}{y}{}{{z}}^{{2}}{-}{z}{,}{2}{}{{t}}^{{4}}{}{y}{+}{{t}}^{{4}}{}{z}{-}{4}{}{{t}}^{{2}}{}{{y}}^{{3}}{-}{t}{}{x}{}{{z}}^{{3}}{-}{t}{}{y}{}{{z}}^{{3}}{+}{2}{}{{y}}^{{5}}{+}{2}{}{{t}}^{{3}}{}{x}{-}{2}{}{{t}}^{{3}}{}{z}{-}{2}{}{t}{}{x}{}{{y}}^{{2}}{-}{2}{}{t}{}{x}{}{{z}}^{{2}}{-}{x}{}{y}{}{{z}}^{{2}}{-}{2}{}{{t}}^{{2}}{}{y}{-}{t}{}{x}{}{z}{-}{4}{}{t}{}{y}{}{z}{-}{2}{}{x}{}{{y}}^{{2}}{+}{x}{}{y}{}{z}{+}{2}{}{{y}}^{{3}}{+}{2}{}{y}{}{{z}}^{{2}}{-}{t}{}{z}{+}{t}{+}{2}{}{z}{,}{y}{}{{z}}^{{4}}{+}{{t}}^{{3}}{}{x}{-}{{t}}^{{3}}{}{z}{-}{t}{}{x}{}{{y}}^{{2}}{-}{t}{}{x}{}{{z}}^{{2}}{-}{{t}}^{{2}}{}{y}{-}{x}{}{{y}}^{{2}}{+}{{y}}^{{3}}{+}{y}{}{{z}}^{{2}}{+}{z}{,}{{z}}^{{5}}{-}{{t}}^{{4}}{,}{{t}}^{{4}}{}{z}{+}{{t}}^{{3}}{}{x}{}{z}{+}{{t}}^{{3}}{}{y}{}{z}{-}{{t}}^{{2}}{}{{z}}^{{3}}{-}{t}{}{x}{}{{z}}^{{2}}{-}{x}{}{y}{}{{z}}^{{2}}{+}{t}{}{x}{}{z}{-}{t}{}{z}{-}{2}{}{y}{}{z}{,}{{t}}^{{4}}{}{y}{+}{{t}}^{{3}}{}{{y}}^{{2}}{-}{{t}}^{{2}}{}{x}{}{z}{-}{t}{}{x}{}{y}{}{z}{+}{{z}}^{{4}}{+}{{t}}^{{2}}{}{x}{-}{{t}}^{{2}}{+}{t}{}{x}{-}{t}{}{y}{+}{{z}}^{{2}}{,}{-}{{t}}^{{2}}{}{z}{+}{{y}}^{{2}}{}{z}{+}{{z}}^{{3}}{+}{t}\right]$ (3)

Computation of dependencies

Find equations that define the product $\mathrm{\phi }\left(x,y\right){P}_{n}\left(x\right)$, where ${P}_{n}\left(x\right)$ is the n-th Legendre polynomial and $\mathrm{\phi }\left(x,y\right)$ is the generating function of the Legendre polynomials.

 > $\mathrm{φ}:=\frac{1}{\sqrt{1-2xy+{y}^{2}}}$
 ${\mathrm{φ}}{:=}\frac{{1}}{\sqrt{{-}{2}{}{x}{}{y}{+}{{y}}^{{2}}{+}{1}}}$ (4)

Compute the derivative ${Q}_{n}\left(x\right)$ of ${P}_{n}\left(x\right)$.

 > diff/P:=proc(x,v) Q[op(1,procname)](x)*diff(args) end proc:

Compute the derivative of ${Q}_{n}\left(x\right)$.

 > diff/Q:=proc(x,v)     local n;     n:=op(1,procname);     (2*x*Q[n](x)-n*(n+1)*P[n](x))*diff(args)/(1-x^2) end proc:

Shift ${P}_{n}\left(x\right)$ and ${Q}_{n}\left(x\right)$.

 > ${P}_{n+2}\left(x\right):=\frac{\left(2n+3\right)x{P}_{n+1}\left(x\right)-\left(n+1\right){P}_{n}\left(x\right)}{n+2}$
 ${{P}}_{{n}{+}{2}}{}\left({x}\right){:=}\frac{\left({2}{}{n}{+}{3}\right){}{x}{}{{P}}_{{n}{+}{1}}{}\left({x}\right){-}\left({n}{+}{1}\right){}{{P}}_{{n}}{}\left({x}\right)}{{n}{+}{2}}$ (5)
 > ${Q}_{n+1}\left(x\right):=\frac{\left(n+1\right)\left({P}_{n}\left(x\right)-x{Q}_{n}\left(x\right)\right)}{1-{x}^{2}}$
 ${{Q}}_{{n}{+}{1}}{}\left({x}\right){:=}\frac{\left({n}{+}{1}\right){}\left({{P}}_{{n}}{}\left({x}\right){-}{x}{}{{Q}}_{{n}}{}\left({x}\right)\right)}{{-}{{x}}^{{2}}{+}{1}}$ (6)

Declare an Ore algebra and a monomial order to define phi, P and Q.

 > $A:=\mathrm{skew_algebra}\left(\mathrm{shift}=\left[\mathrm{Sn},n\right],\mathrm{diff}=\left[\mathrm{Dx},x\right],\mathrm{diff}=\left[\mathrm{Dy},y\right]\right):$
 > $M:=\mathrm{MonomialOrder}\left(A,\mathrm{tdeg}\left(\mathrm{Sn},\mathrm{Dx},\mathrm{Dy}\right)\right):$

Define NFproc and FDproc in view of a call to MultivariateCyclicVector.

 > NFproc:=proc(t,NF,MOrd)     NF[t]:=normal(eval(subs(n=n+degree(t,Sn),         diff(P[n](x)*phi,[x$degree(t,Dx),y$degree(t,Dy)])))) end proc:
 > FDproc:=proc(M,NF)     local ind_lst,t,eta,sol;     ind_lst:=map(op,[indices(NF)]);     for t in M do         ind_lst:=remove(divide,ind_lst,t)     end do;     expand(numer(normal(add(eta[t]*NF[t],t=ind_lst))));     coeffs(%,[P[n](x),P[n+1](x),Q[n](x)]);     sol:=[solve({%},{seq(eta[t],t=ind_lst)})];     subs(op(1,sol),add(eta[t]*t,t=ind_lst));     if(%=0,FAIL,collect(primpart(numer(subs(map(n->n=1,         map2(op,1,select(evalb,sol[1]))),%)),[Dx,Dy,Sn]),         [Dx,Dy,Sn],distributed,factor)) end proc:
 > TMproc:=proc(border,monoideal,MOrd)     border<>[] end proc:

Compute equations satisfied by $\mathrm{\phi }\left(x,y\right){P}_{n}\left(x\right)$.

 > $\mathrm{fglm}:=\left[\mathrm{MultivariateCyclicVector}\left(\mathrm{NFproc},\mathrm{FDproc},\mathrm{TMproc},M\right)\right]:$
 > $\mathrm{map}\left(\mathrm{op},\left[\mathrm{entries}\left({\mathrm{fglm}}_{2}\right)\right]\right)$
 $\left[\left({x}{-}{1}\right){}\left({x}{+}{1}\right){}\left({2}{}{x}{}{y}{-}{{y}}^{{2}}{-}{1}\right){}{\mathrm{Sn}}{}{\mathrm{Dx}}{-}{x}{}\left({n}{+}{1}\right){}\left({2}{}{x}{}{y}{-}{{y}}^{{2}}{-}{1}\right){}{\mathrm{Dx}}{+}{y}{}\left({x}{-}{1}\right){}\left({x}{+}{1}\right){}{\mathrm{Sn}}{+}\left({x}{}{y}{-}{{y}}^{{2}}{-}{1}\right){}\left({n}{+}{1}\right){,}\left({x}{-}{1}\right){}\left({x}{+}{1}\right){}{\left({2}{}{x}{}{y}{-}{{y}}^{{2}}{-}{1}\right)}^{{2}}{}{{\mathrm{Dx}}}^{{2}}{+}{2}{}\left({2}{}{x}{}{y}{-}{{y}}^{{2}}{-}{1}\right){}\left({3}{}{{x}}^{{2}}{}{y}{-}{x}{}{{y}}^{{2}}{-}{x}{-}{y}\right){}{\mathrm{Dx}}{-}{4}{}{{n}}^{{2}}{}{{x}}^{{2}}{}{{y}}^{{2}}{+}{4}{}{{n}}^{{2}}{}{x}{}{{y}}^{{3}}{-}{{n}}^{{2}}{}{{y}}^{{4}}{-}{4}{}{n}{}{{x}}^{{2}}{}{{y}}^{{2}}{+}{4}{}{n}{}{x}{}{{y}}^{{3}}{-}{n}{}{{y}}^{{4}}{+}{4}{}{{n}}^{{2}}{}{x}{}{y}{-}{2}{}{{n}}^{{2}}{}{{y}}^{{2}}{+}{3}{}{{x}}^{{2}}{}{{y}}^{{2}}{-}{2}{}{x}{}{{y}}^{{3}}{+}{4}{}{n}{}{x}{}{y}{-}{2}{}{n}{}{{y}}^{{2}}{-}{{n}}^{{2}}{-}{2}{}{x}{}{y}{+}{{y}}^{{2}}{-}{n}{,}\left({2}{}{x}{}{y}{-}{{y}}^{{2}}{-}{1}\right){}{\mathrm{Dy}}{+}{x}{-}{y}{,}{{\mathrm{Sn}}}^{{2}}{}\left({n}{+}{2}\right){-}{x}{}\left({2}{}{n}{+}{3}\right){}{\mathrm{Sn}}{+}{n}{+}{1}\right]$ (7)
 > $\mathrm{normal}\left(\mathrm{eval}\left(\mathrm{map}\left(\mathrm{applyopr},,\mathrm{φ}{P}_{n}\left(x\right),A\right)\right)\right)$
 $\left[{0}{,}{0}{,}{0}{,}{0}\right]$ (8)