Groebner - Maple Programming Help

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

Groebner

 NormalForm
 normal form of a polynomial modulo an ideal
 Reduce
 full reduction of a polynomial

 Calling Sequence NormalForm(f, G, T, Q, characteristic=p) Reduce(f, G, T, s, Q, characteristic=p)

Parameters

 f - a polynomial or a list or set of polynomials G - a list of polynomials or a PolynomialIdeal T - a MonomialOrder or ShortMonomialOrder Q - (optional) name - assigned quotients p - (optional) characteristic s - (optional) name - assigned denominator

Description

 • The NormalForm command computes the remainder of a multivariate polynomial f divided by a list of multivariate polynomials G.  The division takes place with respect to a monomial order T.  If G is a Groebner basis with respect to T then the result is a canonical representative for the equivalence class of f modulo G. A list of quotients can be assigned to an optional fourth argument Q.
 • The Reduce command is similar to NormalForm, except that denominators are cleared and content is removed. The result is a scaled remainder r, denominator s, and quotients Q such that $\frac{r}{s}=f-{\sum }_{i=1}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{Q}_{i}{G}_{i}$ where r/s is the normal form. Note that NormalForm and Reduce return the same quotients Q (they are not scaled by s).
 • If the first argument is a list or set then a sparse algorithm based on linear algebra is used to divide all the polynomials simultaneously.  This is more efficient than mapping NormalForm or Reduce over the list or set.  It is also more efficient when a lot of reduction steps are expected (the polynomials involved have high degree or many terms).  The sparse algorithm does not compute quotients. Setting infolevel[F4] to either 4 or 5 will output information about the size of the linear system being solved.
 • If T is a ShortMonomialOrder then the elements of f and G must be polynomials in the ring implied by T.  If T is a MonomialOrder created with the Groebner[MonomialOrder] command, then the elements of f and G must be members of the algebra used to define T.  If G is a PolynomialIdeal, a Groebner basis with respect to T is computed automatically and used for the division.
 • The optional argument characteristic=p can be used to specify the ring characteristic when G is a list of polynomials and T is a ShortMonomialOrder.  The default value is zero.
 • Note that the normalf and reduce commands have been superseded by NormalForm and Reduce. They are now deprecated, and may not be supported in a future Maple release.

Examples

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $F≔\left[{x}^{2}-2xz+5,x{y}^{2}+y{z}^{3},3{y}^{2}-8{z}^{3}\right]$
 ${F}{≔}\left[{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}{,}{y}{}{{z}}^{{3}}{+}{x}{}{{y}}^{{2}}{,}{-}{8}{}{{z}}^{{3}}{+}{3}{}{{y}}^{{2}}\right]$ (1)
 > $G≔\mathrm{Basis}\left(F,\mathrm{tdeg}\left(x,y,z\right)\right)$
 ${G}{≔}\left[{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}{,}{8}{}{{z}}^{{3}}{-}{3}{}{{y}}^{{2}}{,}{8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}{,}{9}{}{{y}}^{{4}}{+}{48}{}{{y}}^{{3}}{}{z}{+}{320}{}{{y}}^{{2}}\right]$ (2)
 > $p≔320x{y}^{2}+9x{y}^{4}-96{z}^{2}{y}^{4}x+1600{y}^{3}-18{y}^{5}xz-592xz{y}^{3}+45{y}^{5}+240z{y}^{4}$
 ${p}{≔}{-}{18}{}{x}{}{{y}}^{{5}}{}{z}{-}{96}{}{x}{}{{y}}^{{4}}{}{{z}}^{{2}}{+}{9}{}{x}{}{{y}}^{{4}}{-}{592}{}{x}{}{{y}}^{{3}}{}{z}{+}{45}{}{{y}}^{{5}}{+}{240}{}{{y}}^{{4}}{}{z}{+}{320}{}{x}{}{{y}}^{{2}}{+}{1600}{}{{y}}^{{3}}$ (3)
 > $\mathrm{NormalForm}\left(p,G,\mathrm{tdeg}\left(x,y,z\right),'Q'\right)$
 ${0}$ (4)
 > $Q$
 $\left[{0}{,}{0}{,}{-}\frac{{9}}{{4}}{}{{y}}^{{3}}{}{z}{-}{12}{}{{z}}^{{2}}{}{{y}}^{{2}}{+}\frac{{9}}{{8}}{}{{y}}^{{2}}{-}{74}{}{z}{}{y}{+}{40}{,}\frac{{3}}{{4}}{}{z}{}{{y}}^{{2}}{+}\frac{{37}}{{8}}{}{y}\right]$ (5)
 > $r≔p-\mathrm{add}\left({Q}_{i}{G}_{i},i=1..\mathrm{nops}\left(G\right)\right)$
 ${r}{≔}{-}{18}{}{{y}}^{{5}}{}{x}{}{z}{-}{96}{}{{z}}^{{2}}{}{{y}}^{{4}}{}{x}{+}{9}{}{x}{}{{y}}^{{4}}{-}{592}{}{x}{}{z}{}{{y}}^{{3}}{+}{45}{}{{y}}^{{5}}{+}{240}{}{z}{}{{y}}^{{4}}{+}{320}{}{x}{}{{y}}^{{2}}{+}{1600}{}{{y}}^{{3}}{-}\left({-}\frac{{9}}{{4}}{}{{y}}^{{3}}{}{z}{-}{12}{}{{z}}^{{2}}{}{{y}}^{{2}}{+}\frac{{9}}{{8}}{}{{y}}^{{2}}{-}{74}{}{z}{}{y}{+}{40}\right){}\left({8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}\right){-}\left(\frac{{3}}{{4}}{}{z}{}{{y}}^{{2}}{+}\frac{{37}}{{8}}{}{y}\right){}\left({9}{}{{y}}^{{4}}{+}{48}{}{{y}}^{{3}}{}{z}{+}{320}{}{{y}}^{{2}}\right)$ (6)
 > $\mathrm{expand}\left(r\right)$
 ${0}$ (7)
 > $q≔3{x}^{3}y{z}^{2}-x{z}^{2}+{y}^{3}+yz$
 ${q}{≔}{3}{}{{x}}^{{3}}{}{y}{}{{z}}^{{2}}{-}{x}{}{{z}}^{{2}}{+}{{y}}^{{3}}{+}{y}{}{z}$ (8)
 > $\mathrm{NormalForm}\left(q,G,\mathrm{tdeg}\left(x,y,z\right)\right)$
 ${9}{}{{y}}^{{3}}{}{{z}}^{{2}}{-}{15}{}{y}{}{{z}}^{{2}}{}{x}{-}{x}{}{{z}}^{{2}}{-}\frac{{41}}{{4}}{}{{y}}^{{3}}{+}{60}{}{z}{}{{y}}^{{2}}{+}{z}{}{y}$ (9)
 > $\mathrm{Reduce}\left(q,G,\mathrm{tdeg}\left(x,y,z\right),'s'\right)$
 ${36}{}{{y}}^{{3}}{}{{z}}^{{2}}{-}{60}{}{x}{}{y}{}{{z}}^{{2}}{-}{4}{}{x}{}{{z}}^{{2}}{-}{41}{}{{y}}^{{3}}{+}{240}{}{{y}}^{{2}}{}{z}{+}{4}{}{y}{}{z}$ (10)
 > $s$
 ${4}$ (11)
 > ${\mathrm{infolevel}}_{\mathrm{F4}}≔5:$
 > $\mathrm{NormalForm}\left(\left[p,q\right],G,\mathrm{tdeg}\left(x,y,z\right)\right)$
 19 x 19 with 2 rhs  symbolic preproc       0.000 sec  linear solve           0.000 sec  build result           0.000 sec
 $\left[{0}{,}{9}{}{{y}}^{{3}}{}{{z}}^{{2}}{-}{15}{}{y}{}{{z}}^{{2}}{}{x}{-}{x}{}{{z}}^{{2}}{-}\frac{{41}}{{4}}{}{{y}}^{{3}}{+}{60}{}{z}{}{{y}}^{{2}}{+}{z}{}{y}\right]$ (12)

The next example is a non-commutative (Weyl) algebra where Dn*n = n*Dn + 1

 > $\mathrm{with}\left(\mathrm{Ore_algebra}\right):$
 > $A≔\mathrm{diff_algebra}\left(\left[\mathrm{Dn},n\right]\right)$
 ${A}{≔}{\mathrm{Ore_algebra}}$ (13)
 > $T≔\mathrm{MonomialOrder}\left(A,\mathrm{tdeg}\left(\mathrm{Dn}\right)\right)$
 ${T}{≔}{\mathrm{monomial_order}}$ (14)
 > $\mathrm{w1}≔7n\mathrm{Dn}+1$
 ${\mathrm{w1}}{≔}{7}{}{\mathrm{Dn}}{}{n}{+}{1}$ (15)
 > $\mathrm{w2}≔5\mathrm{Dn}-2$
 ${\mathrm{w2}}{≔}{5}{}{\mathrm{Dn}}{-}{2}$ (16)
 > $\mathrm{Reduce}\left(\mathrm{skew_product}\left({n}^{5}{\mathrm{Dn}}^{4}-1,\mathrm{w1},A\right),\left[\mathrm{w1}\right],T\right)$
 ${0}$ (17)
 > $w≔\mathrm{skew_product}\left(\mathrm{skew_product}\left(n\mathrm{Dn}+5,\mathrm{w1},A\right),\mathrm{skew_product}\left({n}^{3}{\mathrm{Dn}}^{2},\mathrm{w2},A\right),A\right)+{\mathrm{Dn}}^{5}-1$
 ${w}{≔}{35}{}{{n}}^{{5}}{}{{\mathrm{Dn}}}^{{5}}{+}\left({-}{14}{}{{n}}^{{5}}{+}{425}{}{{n}}^{{4}}\right){}{{\mathrm{Dn}}}^{{4}}{+}\left({-}{170}{}{{n}}^{{4}}{+}{880}{}{{n}}^{{3}}\right){}{{\mathrm{Dn}}}^{{3}}{-}{352}{}{{n}}^{{3}}{}{{\mathrm{Dn}}}^{{2}}{+}{{\mathrm{Dn}}}^{{5}}{-}{1}$ (18)
 > $\mathrm{Reduce}\left(w,\left[\mathrm{w1},\mathrm{w2}\right],T,'s'\right)$
 ${-}{1}$ (19)
 > $s$
 $\frac{{16807}{}{{n}}^{{5}}}{{225008}{}{{n}}^{{6}}{+}{16807}{}{{n}}^{{5}}{+}{76560}}$ (20)
 > $r≔\mathrm{NormalForm}\left(w,\left[\mathrm{w1},\mathrm{w2}\right],T,'Q'\right)$
 ${r}{≔}\frac{{1}}{{16807}}{}\frac{{-}{225008}{}{{n}}^{{6}}{-}{16807}{}{{n}}^{{5}}{-}{76560}}{{{n}}^{{5}}}$ (21)
 > $Q$
 $\left[{5}{}{{\mathrm{Dn}}}^{{4}}{}{{n}}^{{4}}{-}{2}{}{{\mathrm{Dn}}}^{{3}}{}{{n}}^{{4}}{+}{40}{}{{n}}^{{3}}{}{{\mathrm{Dn}}}^{{3}}{-}{18}{}{{n}}^{{3}}{}{{\mathrm{Dn}}}^{{2}}{+}\frac{{1}}{{7}}{}\frac{{{\mathrm{Dn}}}^{{4}}}{{n}}{-}\frac{{82}}{{7}}{}{{n}}^{{2}}{}{\mathrm{Dn}}{-}\frac{{29}}{{49}}{}\frac{{{\mathrm{Dn}}}^{{3}}}{{{n}}^{{2}}}{+}\frac{{656}}{{49}}{}{n}{+}\frac{{638}}{{343}}{}\frac{{{\mathrm{Dn}}}^{{2}}}{{{n}}^{{3}}}{-}\frac{{9570}}{{2401}}{}\frac{{\mathrm{Dn}}}{{{n}}^{{4}}}{+}\frac{{76560}}{{16807}{}{{n}}^{{5}}}{,}{0}\right]$ (22)
 > $\mathrm{normal}\left(w-\left(\mathrm{skew_product}\left({Q}_{1},\mathrm{w1},A\right)+\mathrm{skew_product}\left({Q}_{2},\mathrm{w2},A\right)\right),\mathrm{expanded}\right)$
 $\frac{{1}}{{16807}}{}\frac{{-}{225008}{}{{n}}^{{6}}{-}{16807}{}{{n}}^{{5}}{-}{76560}}{{{n}}^{{5}}}$ (23)

References

 Cox, D.; Little, J.; and O'Shea, D. Ideals, Varieties, and Algorithms. 2nd ed. Springer-Verlag, 1997.
 Pearce, R., and Monagan, M. "A Sparse Algorithm for Polynomial Division with Application to F4." In preparation, 2006.