Quelle chap3.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/ibnp/doc/chap3.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (IBNP) - Chapter 3: Commutative Involutive Bases</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<a href="chap3_mj.html">[MathJax on]</a>
<a id="X780AAD6F8095AE49" name="X780AAD6F8095AE49"></a>
<div class="ChapSects"><a href="chap3.html#X780AAD6F8095AE49">3 Commutative Involutive Bases</a>
<div class="ContSect"> <a href="chap3.html#X7BBDABD3799443BB">3.1 Reduction Paths</a>

<div class="ContSSBlock">
 <a href="chap3.html#X7B5623E3821CC0D0">3.1-1 An Example</a>

</div></div>
<div class="ContSect"> <a href="chap3.html#X7E43F2087BC8B4F9">3.2 Commutative Involutive Divisions</a>

<div class="ContSSBlock">
 <a href="chap3.html#X85861B017AEEC50B">3.2-1 Example</a>

 <a href="chap3.html#X83A3B3F77C712DA1">3.2-2 Selecting a Division</a>

 <a href="chap3.html#X785D706A86DD7343">3.2-3 Selecting an Ordering</a>

 <a href="chap3.html#X82712BA57EBE9170">3.2-4 PommaretDivision</a>
 <a href="chap3.html#X8756720A86A6B125">3.2-5 ThomasDivision</a>
 <a href="chap3.html#X7E214DDF794BB14D">3.2-6 JanetDivision</a>
 <a href="chap3.html#X8781FDB7865FA48B">3.2-7 DivisionRecord</a>
 <a href="chap3.html#X79F5892C80AE2667">3.2-8 IPolyReduce</a>
 <a href="chap3.html#X7A36AE827C4012FF">3.2-9 LoggedIPolyReduce</a>
 <a href="chap3.html#X7C58A339832877E9">3.2-10 IAutoreduce</a>
</div></div>
<div class="ContSect"> <a href="chap3.html#X864907F987701716">3.3 Computing a Commutative Involutive Basis</a>

<div class="ContSSBlock">
 <a href="chap3.html#X7ACAA0847CC0DBCC">3.3-1 Prolongations and Autoreduction</a>

 <a href="chap3.html#X7B60A306820D4ED2">3.3-2 InvolutiveBasis</a>
 <a href="chap3.html#X831D45437DE37177">3.3-3 A more detailed example</a>

 <a href="chap3.html#X791740DF84B742A2">3.3-4 Using homogeneous polynomials</a>

</div></div>
</div>

<h3>3 Commutative Involutive Bases</h3>

Given a Gröbner Basis G for an ideal J over a polynomial ring R, the remainder of any polynomial p ∈ R with respect to G is unique. Although this remainder is unique, there may be many ways of finding it, as it is possible that several polynomials in G divide p, each giving a reduction path for p.

<a id="X7BBDABD3799443BB" name="X7BBDABD3799443BB"></a>

<h4>3.1 Reduction Paths</h4>

<a id="X7B5623E3821CC0D0" name="X7B5623E3821CC0D0"></a>

<h5>3.1-1 An Example</h5>

Consider the DegLex Gröbner basis G := {g_1, g_2, g_3} = {a^2-2ab+3, : 2ab+b^2+5, : frac54b^3-frac52a+frac374b} over the polynomial ring Q[a,b], and consider the polynomial p := a^2b+b^3+8b. The remainder of p with respect to G is 0 (so that p is a member of the ideal J generated by G), but there are two ways of obtaining this remainder, as shown in the following diagram.



\vcenter{\xymatrix{
& a^2b+b^3+8b \ar[dl]_{g_1} \ar[dr]^{g_2} \\
2ab^2+b^3+5b \ar[d]_{g_2}
&& -\frac{1}{2}ab^2 + b^3 - \frac{5}{2}a+8b \ar[d]^{g_2} \\
0 && \frac{5}{4}b^3-\frac{5}{2}a+\frac{37}{4}b \ar[d]^{g_3} \\
&& 0
}}


An Involutive Basis for J is a Gröbner Basis G such that there is only one possible reduction path for any polynomial p ∈ R. In order to find such a basis, we restrict which reductions or divisions may take place by requiring, for each potential reduction of a polynomial p by a polynomial g_i ∈ G (so that LM(p) = LM(g_i)× u for some monomial u), some extra conditions on the variables in u to be satisfied, namely that all variables in u have to be in a set of multiplicative variables for g_i, a set that is determined by a particular choice of an involutive division.

<a id="X7E43F2087BC8B4F9" name="X7E43F2087BC8B4F9"></a>

<h4>3.2 Commutative Involutive Divisions</h4>

Recall that a commutative monomial u is divisible by another monomial w if there exists a third monomial u' such that u = wu'. We use the notation w ∣ u and refer to w as a conventional divisor of u. An involutive division I partitions the variables in the polynomial ring into sets of multiplicative and nonmultiplicative variables for each polynomial. The set of multiplicative variables for w is denoted by M_I(w). Then w is an involutive divisor of u, written w ∣_I u, if all variables in u' are in M_I(w).

<a id="X85861B017AEEC50B" name="X85861B017AEEC50B"></a>

<h5>3.2-1 Example</h5>

Let u := ab^3c, v := abc^3 and w := bc be three monomials over the polynomial ring R := Q[a,b,c]. Let an involutive division I partition the variables in R into the following two sets of variables for the monomial w: multiplicative = {a,b}; nonmultiplicative = {c}. It is true that w conventionally divides both monomials u and v, but w only involutively divides monomial u as, defining u' := ab^2 and v' := ac^2 (so that u = wu' and v = wv'), we observe that all variables in u' are in M_I(w), but the variables in v' (in particular the variable c) are not all in M_I(w). So w ∣_I u and w ∤_I v.

<a id="X83A3B3F77C712DA1" name="X83A3B3F77C712DA1"></a>

<h5>3.2-2 Selecting a Division</h5>

The global variable <code class="code">CommutativeDivision</code> is a string which can take values "Pommaret", "Thomas" or "Janet". The default is "Pommaret". The example shows how to select the Pommaret division.

<div class="example"><pre>

gap> CommutativeDivision := "Pommaret";
"Pommaret"

</pre></div>

<a id="X785D706A86DD7343" name="X785D706A86DD7343"></a>

<h5>3.2-3 Selecting an Ordering</h5>

These three divisions are defined for a set of monomials, but we shall define a <code class="code">DivisionRecord</code> below for a set of polynomials. The first step is therefore to select the leading monomials from this set, and that will bepend of the ordering chosen. We shall be using the orderings provided by the main GAP library as described in <a href="chap2.html#X7F82A3608248CD31">2.3</a>.

When calling <code class="code">MonomialLexOrdering</code>, <code class="code">MonomialGrlexOrdering</code> etc., it is essential to provide a list of indeterminates, as shown in the example. Otherwise some of the functions in this package will throw an error.

<div class="example"><pre>

gap> R := PolynomialRing( Rationals, [ "x", "y", "z" ] );;
gap> x := R.1;; y := R.2;; z := R.3;;
gap> ord := MonomialLexOrdering( [x,y,z] );;

</pre></div>

<a id="X82712BA57EBE9170" name="X82712BA57EBE9170"></a>

<h5>3.2-4 PommaretDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PommaretDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let w be a polynomial in R with leading monomoial a_1^e_1a_2^e_2 ... a_n^e_n where e_i is the first non-zero exponent. The Pommaret involutive division P sets M_P}(w) = {a_1, a_2, ..., a_i}.

Because M_P}(w) does not depend in any way on the other leading monomials in polys, this is a global division.

In the example the first five monomials u_i in U contain a power of x, so M_P}(u_i) = {x}. Then u_6 involves y and z, so M_P}(u_6) = {x,y}, and similarly M_P}(u_7) = {x,y,z}.

<div class="example"><pre>

gap> U := [ x^5*y^2*z, x^4*y*z^2, x^2*y^2*z, x*y*z^3, x*z^3, y^2*z, z ];
[ x^5*y^2*z, x^4*y*z^2, x^2*y^2*z, x*y*z^3, x*z^3, y^2*z, z ]
gap> PommaretDivision( R, U, ord );
[ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2 ], [ 1 .. 3 ] ]

</pre></div>

<a id="X8756720A86A6B125" name="X8756720A86A6B125"></a>

<h5>3.2-5 ThomasDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ThomasDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let P be a set of polynomials P = {p_1,...,p_m} in R with leading monomials U = {u_1,...,u_m} where u_i = a_1^e^1_ia_2^e^2_i ... a_n^e^n_i. The Thomas involutive division T sets a_i to be multiplicative for p_j and u_j if e^i_j = max_k e^i_k for all 1 leqslant k leqslant m.

In the example, using the same seven monomials, the highest powers of [x,y,z] are [5,2,3] respectively. So x is multiplicative only for u_1, y is multiplicative for {u_1,u_3,u_6}, and z is multiplicative only for u_4 and u_5. Note that two of the monomials have no multiplicative variable.

<div class="example"><pre>

gap> ThomasDivision( R, U, ord );
[ [ 1, 2 ], [ ], [ 2 ], [ 3 ], [ 3 ], [ 2 ], [ ] ]

</pre></div>

<a id="X7E214DDF794BB14D" name="X7E214DDF794BB14D"></a>

<h5>3.2-6 JanetDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ JanetDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Let R = F[a_1,...,a_n] with a_1 > a_2 > ... > a_n, and let P be a set of polynomials P = {p_1,...,p_m} in R with leading monomials U = {u_1,...,u_m} where u_i = a_1^e^1_ia_2^e^2_i ... a_n^e^n_i. The Janet involutive division J sets a_n to be multiplicative for u_j provided e^n_j = max_k e^n_k for all 1 leqslant k leqslant m. To determine whether a_i is multiplicative for u_j, let L = [e^i+1_j,e^i+2_j,...,e^n_j]. Let S be the subset of {1,...,m} containing those k such that [e^i+1_k,e^i+2_k,...,e^n_k] = L. Then a_i is multiplicative for u_j provided e^i_j = max_k ∈ Se^i_k.

In the example, recall that the exponent lists for the seven monomials are


[5,2,1],~~~ [4,1,2],~~~ [2,2,1],~~~ [1,1,3],~~~ [1,0,3],~~~ [0,2,1],~~~ [0,0,1].


As with the Thomas division, max_k e^3_k = 3 and z is multiplicative only for u_4 and u_5.

For y, L = [1] when k ∈ {1,3,6,7} and max_{1,3,6,7} e^2_k = 2, so y is multiplicative for u_1, u_3 and u_6, but not for u_7. L = [2] only for u_2, so y is multiplicative for u_2. L = [3] for u_4 and u_5, and e^2_4 > e^2_5, so y is multiplicative for u_4 but not u_5.

For x, L = [2,1] for k ∈ {1,3,6} and e^1_1 = 5 is greater than e^1_3 and e^1_6, so x is multiplicative for u_1. The other values for L, namely [1,2], [1,3], [0,3] and [0,1], occur just once each, so x is multiplicative for u_2, u_4, u_5 and u_7.

<div class="example"><pre>

gap> JanetDivision( R, U, ord );
[ [ 1, 2 ], [ 1, 2 ], [ 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 1 ] ]

</pre></div>

<a id="X8781FDB7865FA48B" name="X8781FDB7865FA48B"></a>

<h5>3.2-7 DivisionRecord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisionRecord</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisionRecordCP</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
The global function <code class="code">DivisionRecord</code> calls one of the operations <code class="code">DivisionRecordCP</code> and <code class="code">DivisionRecordNP</code>, depending on whether the algebra is commutative or not. In the commutative case, this function finds the sets of multiplicative variables for a set of polynomials using one of the involutive divisions listed above. The record constructed has three fields: the chosen division; a list of lists of positions of the multiplicative variables; and the set of polynomials.

In the following example, polynomials {u = b^3-3a, v=a^3-3b} define an ideal and form a Gröbner basis for that ideal. Using the Pommaret division, M_P}(u) = {a,b} and M_P}(v) = {a}. The variable <code class="code">drec2.mvars</code> in the listing below contains the positions of these variables in the generating set {a,b}.

<div class="example"><pre>

gap> R := PolynomialRing( Rationals, [ "a", "b" ] );;
gap> a := R.1;; b := R.2;;
gap> L2 := [ b^3 - 3*a, a^3 - 3*b ];;
gap> ord := MonomialGrlexOrdering( [a,b] );;
gap> GB2 := ReducedGroebnerBasis( L2, ord );;
gap> GB2 = L2;
true
gap> CommutativeDivision := "Pommaret";;
gap> drec2 := DivisionRecordCP( R, L2, ord );
rec( div := "Pommaret", mvars := [ [ 1, 2 ], [ 1 ] ],
 polys := [ b^3-3*a, a^3-3*b ] )

</pre></div>

In the reduction diagrams below the nodes (j,k) represent the monomials a^jb^k. The lead monomials of u and v are marked by these two names. In the left hand diagram the two shaded areas indicate those monomials which are conventionally reducible by u and by v, so that the doubly shaded area contains those monomials which are conventionally reducible by both. For an involutive division, this must be avoided.

In the right-hand diagram we see that u involutively divides the same set of monomials in the main shaded area. On the other hand v just involutively divides monomials {a^j ∣ j ≥ 3}. So none of the monomials {a^jb, a^jb^2 ∣ j ≥ 3} reduce by v involutively. The operation <code class="code">InvolutiveBasis</code>, to be described below, produces two further polynomials, w = vb = a^3b-3b^2 and vb^2 which reduces by u to x = a^3b^2 - 9a. Both w and x have multiplicative variables {a} and the monomials which they can reduce lie on the two horizantal line segments in the right-hand diagram. In this way, all the conventionally reducible monomials are involutively reducible by just one of {u,v,w,x}.



\vcenter{\xymatrix@=1em{
b & & & \ar@{-}[ddddrrrr] & \ar@{-}[dddrrr]
 & \ar@{-}[ddrr] & \ar@{-}[dr] & & & &
 b & & & & & & & \\
: \ar[u] \ar@{-}[ur] & \cdot & \cdot
 & \cdot \ar@{-}[ddddrrrr] & \cdot & \cdot & \cdot & & & &
 : \ar[u] \ar@{-}[ur] & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\
5 \ar@{-}[u] \ar@{-}[uurr]
 & \cdot & \cdot & \cdot \ar@{-}[ddddrrrr]
 & \cdot & \cdot & \cdot & & & &
 5 \ar@{-}[u] \ar@{-}[uurr]
 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\
4 \ar@{-}[u] \ar@{-}[uuurrr] & \cdot & \cdot
 & \cdot \ar@{-}[ddddrrrr] & \cdot & \cdot & \cdot & & & &
 4 \ar@{-}[u] \ar@{-}[uuurrr]
 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \\
u \ar@{-}[u] \ar@{-}[rrrrrrr] \ar@{-}[uuuurrrr]
 & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr]
 & \cdot \ar@{-}[dddrrr] \ar@{-}[uuuurrrr]
 & \cdot \ar@{-}[uuurrr]
 & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & & &
 u \ar@{-}[u] \ar@{-}[rrrrrrr] \ar@{-}[uuuurrrr]
 & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuuurrrr]
 & \cdot \ar@{-}[uuuurrrr] & \cdot \ar@{-}[uuurrr]
 & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & \\
2 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[ddrr]
 & \cdot & \cdot & \cdot & & & &
 2 \ar@{-}[u] & \cdot & \cdot & x \ar@{-}[rrrr]& \cdot & \cdot & \cdot & \\
1 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[dr]
 & \cdot & \cdot & \cdot & & & &
 1 \ar@{-}[u] & \cdot & \cdot & w \ar@{-}[rrrr] & \cdot & \cdot & \cdot & \\
0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r]
 & v \ar@{-}[r] \ar@{-}[uuuuuuu]
 & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a & & &
 0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r]
 & v \ar@{-}[r]
 & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a
}}


The polynomial p = a^3b^3 + 2a^3b + 3ab^3 reduces involutively as follows.


p \stackrel{u}{\longrightarrow} 3a^4 + 2a^3b + 3ab^3
 \stackrel{v}{\longrightarrow} 2a^3b + 3ab^3 + 9ab
 \stackrel{w}{\longrightarrow} 3ab^3 + 9ab + 6b^2
 \stackrel{u}{\longrightarrow} 9a^2 + 9ab + 6b^2


This reduction is computed in section <a href="chap3.html#X7B60A306820D4ED2">3.3-2</a>.

<a id="X79F5892C80AE2667" name="X79F5892C80AE2667"></a>

<h5>3.2-8 IPolyReduce</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IPolyReduce</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IPolyReduceCP</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
The global function <code class="code">IPolyReduce</code> calls one of the operations <code class="code">IPolyReduceCP</code> and <code class="code">IPolyReduceNP</code> depending on whether the algebra is commutative or not. This function reduces a polynomial p using the current overlap record for a basis, and an ordering.

In the example, using <code class="code">drec2</code>, the polynomial p reduces only to 2a^3b+9a^2+9ab


p \stackrel{u}{\longrightarrow} 3a^4 + 2a^3b + 3ab^3
 \stackrel{v}{\longrightarrow} 2a^3b + 3ab^3 + 9ab
 \stackrel{u}{\longrightarrow} 2a^3b + 9a^2 + 9ab


because the polynomial x is not available to reduce 2a^3b to 6b^2.

<div class="example"><pre>

gap> p := a^3*b^3 + 2*a^3*b + 3*a*b^3;;
gap> q := IPolyReduce( R, p, drec2, ord );
2*a^3*b+9*a^2+9*a*b

</pre></div>

<a id="X7A36AE827C4012FF" name="X7A36AE827C4012FF"></a>

<h5>3.2-9 LoggedIPolyReduce</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LoggedIPolyReduce</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LoggedIPolyReduceCP</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
The global function <code class="code">LoggedIPolyReduce</code> calls one of the operations <code class="code">LoggedIPolyReduceCP</code> and <code class="code">LoggedIPolyReduceNP</code> depending on whether the algebra is commutative or not. This function is similar to <code class="code">IPolyReduce</code>, reducing a polynomial p using the current overlap record for a basis, and an ordering. It's output, however, is a record containing, as well as the reduced polynomial r, logging information which shows how the reduction has been obtained:

p ~=~ r + \sum_i logs[i] * polys[i].


In the example <code class="code">r.result</code> is equal to the previous result q, and the equation above is verified:


a^3b^3 + 2a^3b + 3ab^3 ~=~ (2a^3b+9a^2+9ab) + (a^3+3a)(b^3-3a) + 3a(a^3-3b).


<div class="example"><pre>

gap> r := LoggedIPolyReduceCP( R, p, drec2, ord );
rec( logs := [ a^3+3*a, 3*a ], polys := [ b^3-3*a, a^3-3*b ],
result := 2*a^3*b+9*a^2+9*a*b )
gap> r.result = q;
true
gap> p = r.result + r.logs[1]*r.polys[1] + r.logs[2]*r.polys[2];
true

</pre></div>

<a id="X7C58A339832877E9" name="X7C58A339832877E9"></a>

<h5>3.2-10 IAutoreduce</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IAutoreduce</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IAutoreduceCP</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
The global function <code class="code">IAutoreduce</code> calls one of the operations <code class="code">IAutoreduceCP</code> and <code class="code">IAutoreduceNP</code> depending on whether the algebra is commutative or not. This function applies <code class="code">IPolyReduce</code> to a list of polynomials recursively until no more reductions are possible. More specifically, this function involutively reduces each member of a list of polynomials with respect to all the other members of the list, removing the polynomial from the list if it reduces involutively to 0. This process is iterated until no more reductions are possible.

If no reduction takes place, so that the result is equal to the initial list of polynomials, then <code class="code">true</code> is returned.

In the example we form <code class="code">L3</code> by adding p to <code class="code">L2</code>. On applying <code class="code">IAutoreduceCP</code>, only p reduces, and the concatenation of <code class="code">L2</code> with q is returned. Starting with <code class="code">L4 = [u,v,w,x]</code>, there are no reductions, and <code class="code">true</code> is returned.

<div class="example"><pre>

gap> L3 := Concatenation( L2, [p] );;
gap> IAutoreduceCP( R, L3, ord );
[ b^3-3*a, a^3-3*b, 2*a^3*b+9*a^2+9*a*b ]
gap> L4 := Concatenation( L2, [ a^3*b-3*b^2, a^3*b^2-9*a ] );;
gap> IAutoreduceCP( R, L4, ord );
true

</pre></div>

<a id="X864907F987701716" name="X864907F987701716"></a>

<h4>3.3 Computing a Commutative Involutive Basis</h4>

The involutive algorithm for constructing an involutive basis uses prolongations and autoreduction.

<a id="X7ACAA0847CC0DBCC" name="X7ACAA0847CC0DBCC"></a>

<h5>3.3-1 Prolongations and Autoreduction</h5>

Given a set of polynomials P, a prolongation of p ∈ P is a product pa_i where the generator a_i is not multiplicative with respect to the current involutive division.

A set of polynomials P is said to be autoreduced if no polynomial p ∈ P contains a term which is involutively divisible by some polynomial p' ∈ P ∖ {p}.

We denote by rem_I(p,Q) the involutive remainder of polynomial p with respect to a set of polynomials Q. Here is the Commutative Autoreduction Algorithm:

<div class="example"><pre>
Input: a set of polynomials P = {p_1,p_2,...,p_n} and an involutive division I
 while there exists p_i in P such that rem_I(p_i, P\{p_i}) <> p_i do
 q := Rem_I(p_i, P\{p_i});
 P := P\{p_i};
 if (q<>0) then
 P := P union {q};
 fi;
 od;
 return P;
</pre></div>

It can be shown that if P is a set of polynomials over a polynomial ring R = F[a_1,...,a_n], such that P is autoreduced with respect to an involutive division I, and if p,q are two polynomials in R, then rem_I(p,P) + rem_I(q,P) = rem_I(p+q,P).

Given an involutive division I and an admissible monomial ordering O, an autoreduced set of polynomials P is a locally involutive basis with respect to I and O if any prolongation of any p_i ∈ P involutively reduces to zero using P. Further, P is an involutive basis with respect to I and O if any multiple p_it of any p_i ∈ P by any term t involutively reduces to zero using P.

The Commutative Involutive Basis Algorithm:

<div class="example"><pre>
Input: a basis F = {f_1,f_2,...,f_m} for an ideal J
 over a commutative polynomial ring R[a_1,...,a_n];
 an admissible monomial ordering O;
 a continuous and constructive involutive division I
Output: an involutive basis G = {g_1,g_2,...,g_k} for J (if it terminates)
 G := { };
 F := autoreduction of F with respect to O and I;
 while G = { } do
 P := set of all prolongations f_i*a_j, 1<=i<=m, 1<=j<=n;
 q := 0;
 while (P <> { }) and (q=0) do
 p := a polynomial in P with minimal lead monomial w.r.t. O;
 P := P \ {p};
 q := rem_I(p,F);
 od;
 if (q <> 0) then ## new basis element found
 F := autoreduction of (F union {q})
 else ## all the prolongations have reduced to zero
 G := F;
 fi;
 od;
 return G;
</pre></div>

<a id="X7B60A306820D4ED2" name="X7B60A306820D4ED2"></a>

<h5>3.3-2 InvolutiveBasis</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InvolutiveBasis</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InvolutiveBasisCP</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
The global function <code class="code">InvolutiveBasis</code> calls one of the operations <code class="code">InvolutiveBasisCP</code> and <code class="code">InvolutiveBasisNP</code> depending on whether the algebra is commutative or not. This function finds an involutive basis for the ideal generated by a set of polynomials, using a chosen ordering, and returns a division record.

Any involutive basis returned by this algorithm is a Gröbner basis, and remainders are involutively unique with respect to this basis.

<div class="example"><pre>

gap> ibasP := InvolutiveBasis( R, L2, ord );
rec( div := "Pommaret", mvars := [ [ 1, 2 ], [ 1 ], [ 1 ], [ 1 ] ],
 polys := [ b^3-3*a, a^3-3*b, a^3*b-3*b^2, a^3*b^2-9*a ] )
gap> r := IPolyReduce( R, p, ibasP, ord );
9*a^2+9*a*b+6*b^2

</pre></div>

Here we have returned to the example in section <a href="chap3.html#X8781FDB7865FA48B">3.2-7</a>. Starting with F={u,v}, there is only one prolongation, P={w=vb}, and F becomes {u,v,w}. At the second iteration, P={vb,wb}; vb reduces to zero; wb reduces to x=a^3b^2-9a; and F becomes {u,v,w,x}. At the third iteration P={vb,wb,xb} and all three of these reduce to zero, so G = F is returned.

It is then shown that the multiplicative variables for {u,v,w,x} are {{a,b},{a},{a},{a}}.

Finally, the full reduction r of p is computed.

If, instead of the Pommaret division, we use Janet or Thomas we obtain:

<div class="example"><pre>

gap> CommutativeDivision := "Janet";;
gap> ibasJ := InvolutiveBasis( R, L2, ord );;
gap> ( ibasJ.mvars = ibasP.mvars ) and ( ibasJ.polys = ibasP.polys );
true
gap> CommutativeDivision := "Thomas";;
gap> ibasT := InvolutiveBasis( R, L2, ord );
rec( div := "Thomas",
 mvars := [ [ 2 ], [ 1 ], [ 2 ], [ 1 ], [ 2 ], [ 1 ], [ 1, 2 ] ],
 polys := [ b^3-3*a, a^3-3*b, a*b^3-3*a^2, a^3*b-3*b^2, a^2*b^3-9*b,
 a^3*b^2-9*a, a^3*b^3-9*a*b ] )

</pre></div>

The Janet division gives the same involutive basis as Pommaret, but the Thomas Division produces 7, rather than 4 polynomials:


[u,v,y,w,z,x,t] ~=~
[~ b^3-3a,\ a^3-3b,\ ab^3-3a^2,\ a^3b-3b^2,\
 a^2b^3-9b,\ a^3b^2-9a,\ a^3b^3-9ab ~].


The multiplicative variables for these polynomials are [ {b}, {a}, {b}, {a}, {b}, {a}, {a,b} ], so the reduction diagram for the Thomas basis is:



\vcenter{\xymatrix@=1em{
b & & & & & & & & \\
: \ar[u] & \cdot & \cdot & \cdot \ar@{-}[ur]
 & \cdot & \cdot & \cdot & & \\
5 \ar@{-}[u] & \cdot & \cdot & \cdot \ar@{-}[uurr]
 & \cdot & \cdot & \cdot & & \\
4 \ar@{-}[u] & \cdot & \cdot
 & \cdot \ar@{-}[uuurrr] & \cdot & \cdot & \cdot & & \\
u \ar@{-}[u] & y \ar@{-}[uuuu] & z \ar@{-}[uuuu]
 & t \ar@{-}[uuuurrrr] \ar@{-}[uuuu] \ar@{-}[rrrr]
 & \cdot \ar@{-}[uuurrr]
 & \cdot \ar@{-}[uurr] & \cdot \ar@{-}[ur] & & \\
2 \ar@{-}[u] & \cdot & \cdot & x \ar@{-}[rrrr]
 & \cdot & \cdot & \cdot & & \\
1 \ar@{-}[u] & \cdot & \cdot & w \ar@{-}[rrrr]
 & \cdot & \cdot & \cdot & & \\
0 \ar@{-}[r]\ar@{-}[u] & 1 \ar@{-}[r] & 2 \ar@{-}[r]
 & v \ar@{-}[r]
 & 4 \ar@{-}[r] & 5 \ar@{-}[r] & \cdots \ar[r] & a &
}}


The reduction of p with this basis is:


p = a^3b^3 + 2a^3b + 3ab^3
 \stackrel{t}{\longrightarrow} 2a^3b + 3ab^3 + 9ab
 \stackrel{w}{\longrightarrow} 3ab^3 + 9ab + 6b^2
 \stackrel{y}{\longrightarrow} 9a^2 + 9ab + 6b^2.


<div class="example"><pre>

gap> r := LoggedIPolyReduceCP( R, p, ibasT, ord );
rec( logs := [ 0, 0, 3, 2, 0, 0, 1 ],
 polys := [ b^3-3*a, a^3-3*b, a*b^3-3*a^2, a^3*b-3*b^2, a^2*b^3-9*b,
 a^3*b^2-9*a, a^3*b^3-9*a*b ], result := 9*a^2+9*a*b+6*b^2 )

</pre></div>

<a id="X831D45437DE37177" name="X831D45437DE37177"></a>

<h5>3.3-3 A more detailed example</h5>

Here we consider Example 4.5.2 in the thesis <a href="chapBib.html#biBgareth-thesis">[Eva05]</a>. On setting <code class="code">InfoLevel(InfoIBNP)</code> to <code class="code">1</code> some of the intermediate calculations are displayed. The setting of the problem is a rational polynomial ring in three variables with the lex ordering [x,y,z], using the Janet involutive division.

<ul>
<li>the initial basis contains two polynomials {a=x^2+y^3,~b=x+z^3}

</li>
<li>the reduced Gröbner basis is {c=y^3+z^6,~b=x+z^3}, and the irreducible monomials are {z^k,~yz^k,~y^2z^k~|~ k geqslant 0}

</li>
<li>when starting to calculate an involutive basis, the autoreduction does nothing because x is not multiplicative for b

</li>
<li>the only prolongation is bx = x^2+xz^3 which reduces, on subtracting a+bz^3 and changing the sign, to c=y^3+z^6

</li>
<li>on restarting with basis [c,b,a], autoreduction replaces a with a-c = d = x^2-z^6

</li>
<li>there are then 3 prolongations [by,bx,dy] and bx now reduces to zero

</li>
<li>by = e = xy+yz^3 is then added to the basis: [c,b,e,d]

</li>
<li>dy = x^2y-yz^6 reduces to zero on adding e(-x+z^3)

</li>
<li>on restarting with basis [c,b,e,d] there are 4 prolongations [by,ey,bx,dy] and of these only f = ey = xy^2+y^2z^3 does not reduce to zero

</li>
<li>restarting with basis [c,b,e,f,d], the 5 prolongations [by,ey,fy,bx,dy] all reduce to zero.

</li>
<li>now see what happens when reducing p = x^7+y^7+z^7 using the basis [c,b,e,f,d]

</li>
<li>x^7-dx^5 = x^5z^6 and x^5z^6 - dx^3z^6 = x^3z^12 and x^3z^12-dxz^12 = xz^18 and xz^18-bz^18=-z^21

</li>
<li>y^7 - cy^4 = -y^4z^6 and -y^4z^6 + cyz^6 = yz^12, so p reduces to -z^21 + yz^12 + z^7.

</li>
</ul>

<div class="example"><pre>

gap> SetInfoLevel( InfoIBNP, 1 );; 
gap> CommutativeDivision := "Janet";;
gap> R3 := PolynomialRing( Rationals, [ "x", "y", "z" ] );;
gap> x := R3.1;; y := R3.2;; z := R3.3;; 
gap> ord3 := MonomialLexOrdering( [x,y,z] );;
gap> F := [ y^3 + x^2, z^3 + x ];;
gap> gbas := GrobnerBasis( F, ord3 );
[ y^3+x^2, z^3+x, -z^6-y^3 ]
gap> rgbas := ReducedGrobnerBasis( F, ord3 );
[ z^6+y^3, z^3+x ]
gap> ibasF := InvolutiveBasisCP( R3, F, ord3 );
#I restarting with basis:
[ z^3+x, y^3+x^2 ]
#I division record for basis: rec(
div := "Janet",
mvars := [ [ 2, 3 ], [ 1, 2, 3 ] ],
polys := [ z^3+x, y^3+x^2 ] )
#I prolongations = [ x*z^3+x^2 ]
#I restarting with basis:
[ z^6+y^3, z^3+x, y^3+x^2 ]
#I after autoreduction basis =
[ z^6+y^3, z^3+x, -z^6+x^2 ]
#I division record for basis: rec(
div := "Janet",
mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ] ],
polys := [ z^6+y^3, z^3+x, -z^6+x^2 ] )
#I prolongations = [ y*z^3+x*y, x*z^3+x^2, -y*z^6+x^2*y ]
#I restarting with basis:
[ z^6+y^3, z^3+x, y*z^3+x*y, -z^6+x^2 ]
#I division record for basis: rec(
div := "Janet",
mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ] ],
polys := [ z^6+y^3, z^3+x, y*z^3+x*y, -z^6+x^2 ] )
#I prolongations = [ y*z^3+x*y, y^2*z^3+x*y^2, x*z^3+x^2, -y*z^6+x^2*y ]
#I restarting with basis:
[ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ]
#I division record for basis: rec(
div := "Janet",
mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ], [ 1, 3 ] ],
polys := [ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ] )
#I prolongations = [ y*z^3+x*y, y^2*z^3+x*y^2, y^3*z^3+x*y^3, x*z^3+x^2, -y*z\
^6+x^2*y ]
rec( div := "Janet",
 mvars := [ [ 1, 2, 3 ], [ 3 ], [ 1, 3 ], [ 1, 3 ], [ 1, 3 ] ],
 polys := [ z^6+y^3, z^3+x, y*z^3+x*y, y^2*z^3+x*y^2, -z^6+x^2 ] )
gap> ## now for a reduction - reset the info level:
gap> SetInfoLevel( InfoIBNP, 2 );; 
gap> p := x^7 + y^7 + z^7;;
gap> IPolyReduce( R3, p, ibasF, ord3 );
#I reduced to: x^5*z^6+y^7+z^7
#I reduced to: x^3*z^12+y^7+z^7
#I reduced to: x*z^18+y^7+z^7
#I reduced to: -z^21+y^7+z^7
#I reduced to: -z^21-y^4*z^6+z^7
#I reduced to: -z^21+y*z^12+z^7
-z^21+y*z^12+z^7

</pre></div>

<a id="X791740DF84B742A2" name="X791740DF84B742A2"></a>

<h5>3.3-4 Using homogeneous polynomials</h5>

If the polynomials in an initial basis are not homogeneous then they may be made homogeneous by introducing an additional variable. The resulting involutive basis will contain only homogeneous polynomials. However, if these are de-homogenised by setting the additional variable equal to 1, the resulting basis may not be involutive.

Applying this to the previous example, the resulting basis contains 10 polynomials which include homogenised versions of [c,b,e,f], but not d.

<div class="example"><pre>

gap> SetInfoLevel( InfoIBNP, 0 );
gap> R4 := PolynomialRing( Rationals, [ "x", "y", "z", "t" ] );;
gap> x := R4.1;; y := R4.2;; z := R4.3;; t := R4.4;;
gap> H := [ x^2*t + y^3, x*t^2 + z^3 ];;
gap> ord4 := MonomialLexOrdering( [x,y,z,t] );;
gap> ibasH := InvolutiveBasisCP( R4, H, ord4 );
rec( div := "Janet",
 mvars := [ [ 1, 2, 3, 4 ], [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 2, 3 ],
 [ 1, 2, 3 ], [ 1, 3, 4 ], [ 1, 3, 4 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ] ],
 polys := [ y^3*t^3+z^6, x*t^2+z^3, x*t^3+z^3*t, x*z^3-y^3*t,
 x*z^3*t-y^3*t^2, x*y*t^3+y*z^3*t, x*y^2*t^3+y^2*z^3*t, x^2*t+y^3,
 x^2*z*t+y^3*z, x^2*z^2*t+y^3*z^2 ] )

</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.37 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.