Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/gbnp/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 29.7.2024 mit Größe 140 kB image not shown  

Quelle  chap3.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/gbnp/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 (GBNP) - Chapter 3: Functions</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"><span class="chlink1">Goto Chapter: </span><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="chapA.html">A</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>

<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X86FA580F8055B274" name="X86FA580F8055B274"></a></p>
<div class="ChapSects"><a href="chap3.html#X86FA580F8055B274">3 <span class="Heading">Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X81ABB91B79E00229">3.1 <span class="Heading">Converting polynomials
            into different formats</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7B0EBCBC7857F1AE">3.1-1 GP2NP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2 GP2NPList</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X86C3912F781ABEDC">3.1-3 NP2GP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X844A23EA7D97150C">3.1-4 NP2GPList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X78F44B01851B1020">3.2 <span class="Heading">Printing polynomials in NP format</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7B63BEA87A8D6162">3.2-1 PrintNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7F7510A878045D3A">3.2-2 GBNP.ConfigPrint</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X832103DC79A9E9D0">3.2-3 PrintNPList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X83DE3F817EA74727">3.3 <span class="Heading">Calculating with polynomials in NP format</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7DB3792385AAA805">3.3-1 NumAlgGensNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X865548F07C74AB0A">3.3-2 NumAlgGensNPList</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X782647C57D148379">3.3-3 NumModGensNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8119282084CA8076">3.3-4 NumModGensNPList</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X788E1ACA82A833A8">3.3-5 AddNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X84FC611A822D808F">3.3-6 BimulNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X855F3D4C783000E3">3.3-7 CleanNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7D05B60E83FDA567">3.3-8 GtNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8075AE7E7A8088FF">3.3-9 LtNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7A42AE79811CC5D7">3.3-10 LMonNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80CD462F794A8095">3.3-11 LTermNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X878A8C027DA25196">3.3-12 MkMonicNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X818147CD841BD490">3.3-13 FactorOutGcdNP</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7ABA720E87EFF040">3.3-14 MulNP</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X81381B2D83D2B9A9">3.4 <span class="Heading">Gröbner functions, standard variant</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7CD9F9C97B2563E2">3.4-1 Grobner</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7FEDA29E78B0CEED">3.4-2 SGrobner</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80D4D22C7E643C7B">3.4-3 IsGrobnerBasis</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7D17F9027F08CF0B">3.4-4 IsStrongGrobnerBasis</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7E0105ED7FF4210F">3.4-5 IsGrobnerPair</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8752DA1A7CAF77D3">3.4-6 MakeGrobnerPair</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7F387F7780425B9A">3.5 <span class="Heading">Finite-dimensional quotient
        algebras</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7EAA04247B2C6330">3.5-1 BaseQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X81A50EEE7B56C723">3.5-2 DimQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7DFA841A8425DD94">3.5-3 MatrixQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X78E4BF2F7F0D5E74">3.5-4 MatricesQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80C4D0E882B05FDF">3.5-5 MulQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8563683E7FA604F8">3.5-6 StrongNormalFormNP</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X79FE4A3983E2329F">3.6 <span class="Heading">Finiteness and Hilbert series</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X83C57C3A7DCF0471">3.6-1 DetermineGrowthQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X792E39A98717D779">3.6-2 FinCheckQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7CFD47367CF309EB">3.6-3 HilbertSeriesQA</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X863124677B933CEE">3.6-4 PreprocessAnalysisQA</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7BA5CAA07890F7AA">3.7 <span class="Heading">Functions of the
            trace variant</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X813454F6799B1D57">3.7-1 EvalTrace</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X83D1560C7F2A04BA">3.7-2 PrintTraceList</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8039BEE77C070FB1">3.7-3 PrintTracePol</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7DD0B56D7BD6CD98">3.7-4 PrintNPListTrace</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X78AE6EED83B97595">3.7-5 SGrobnerTrace</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8219059A86A54130">3.7-6 StrongNormalFormTraceDiff</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7E4E3AD07B2465F9">3.8 <span class="Heading">Functions of the truncated variant</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7A489A5D79DA9E5C">3.8-1 <span class="Heading">Examples</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7CD043E081BF2302">3.8-2 SGrobnerTrunc</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X83C9E598798D5809">3.8-3 CheckHomogeneousNPs</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7E33C064875D95CA">3.8-4 BaseQATrunc</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7C6882DB837A9F5A">3.8-5 DimsQATrunc</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7FBA7F1D79DA883F">3.8-6 FreqsQATrunc</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X8706DD3287E82019">3.9 <span class="Heading">Functions of the module variant</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X860966487ED88A43">3.9-1 SGrobnerModule</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7E3160E67C504F37">3.9-2 BaseQM</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X813E6A2C8709C9F3">3.9-3 DimQM</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X805FB42A7EEF510F">3.9-4 MulQM</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X87D51A8379C50A80">3.9-5 StrongNormalFormNPM</a></span>
</div></div>
</div>

<h3>3 <span class="Heading">Functions</span></h3>

<p><a id="X81ABB91B79E00229" name="X81ABB91B79E00229"></a></p>

<h4>3.1 <span class="Heading">Converting polynomials
            into different formats</span></h4>

<p><a id="X7B0EBCBC7857F1AE" name="X7B0EBCBC7857F1AE"></a></p>

<h5>3.1-1 GP2NP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GP2NP</code>( <var class="Arg">gp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: If <var class="Arg">gp</var> is an element of a free algebra, then the polynomial in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2"><span class="RefLink">2.1</span></a>) corresponding to <var class="Arg">gp</var>; if <var class="Arg">gp</var> is an element of a free module, then the vector in NPM format (see Section <a href="chap2.html#X7B27E2D1784538DE"><span class="RefLink">2.2</span></a>) corresponding to <var class="Arg">gp</var>.</p>

<p>This function will convert an element of a free algebra to a polynomial in NP format and an element of a free right module to a vector in NPM format.</p>

<p><em>Example:</em> Let <code class="code">A</code> be the free associative algebra with one over the rationals on the generators <code class="code">a</code> and <code class="code">b</code>. Let <code class="code">e</code> be the one of the algebra.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=A.a;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=A.b;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">e:=One(A);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z:=Zero(A);;</span>
</pre></div>

<p>Now let <code class="code">gp</code> be the polynomial <span class="SimpleMath">ba-ab-e</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gp:=b*a-a*b-e;</span>
(-1)*<identity ...>+(-1)*a*b+(1)*b*a
</pre></div>

<p>The polynomial in NP format, corresponding to <code class="code">gp</code> can now be obtained with GP2NP:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GP2NP(gp);</span>
[ [ [ 2, 1 ], [ 1, 2 ], [  ] ], [ 1, -1, -1 ] ]
</pre></div>

<p>Let <code class="code">D</code> be the free associative algebra over <code class="code">A</code> of rank 2.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := A^2;;</span>
</pre></div>

<p>Take the following list <code class="code">R</code> of two elements of <code class="code">D</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := [ [b-e, z], [e+a*(e+a+b), -e-a*(e+a+b)] ];;</span>
</pre></div>

<p>Convert the list <code class="code">R</code> to a list of vectors in NPM format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(R,GP2NP);</span>
[ [ [ [ -1, 2 ], [ -1 ] ], [ 1, -1 ] ],
  [ [ [ -1, 1, 2 ], [ -1, 1, 1 ], [ -2, 1, 2 ], [ -2, 1, 1 ], [ -1, 1 ],
          [ -2, 1 ], [ -1 ], [ -2 ] ], [ 1, 1, -1, -1, 1, -1, 1, -1 ] ] ]
</pre></div>

<p><a id="X7CF0ED937DDA5A7E" name="X7CF0ED937DDA5A7E"></a></p>

<h5>3.1-2 GP2NPList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GP2NPList</code>( <var class="Arg">Lgp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The list of polynomials in NP or NPM format corresponding to elements of a free algebra or module occurring in the list <var class="Arg">Lgp</var>.</p>

<p>This function has the same effect as <code class="code">List(Lgp,GBNP)</code>.</p>

<p><em>Example:</em> Let <code class="code">A</code> be the free associative algebra with one over the rationals on the generators <code class="code">a</code> and <code class="code">b</code>. Let <code class="code">e</code> be the one of the algebra.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=A.a;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=A.b;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">e:=One(A);;</span>
</pre></div>

<p>Let <code class="code">Lgp</code> be the list of polynomials <span class="SimpleMath">[a^2-e,b^2-e,ba-ab-e]</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lgp:=[a^2-e,b^2-e,b*a-a*b-e];</span>
[ (-1)*<identity ...>+(1)*a^2, (-1)*<identity ...>+(1)*b^2,
  (-1)*<identity ...>+(-1)*a*b+(1)*b*a ]
</pre></div>

<p>The polynomial in NP format corresponding to <code class="code">gp</code> can be obtained with GP2NP:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GP2NPList(Lgp);</span>
[ [ [ [ 1, 1 ], [  ] ], [ 1, -1 ] ], [ [ [ 2, 2 ], [  ] ], [ 1, -1 ] ],
  [ [ [ 2, 1 ], [ 1, 2 ], [  ] ], [ 1, -1, -1 ] ] ]
</pre></div>

<p>The same result is obtained by a simple application of the standard List function in GAP:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(Lgp,GP2NP) = GP2NPList(Lgp);</span>
true
</pre></div>

<p><a id="X86C3912F781ABEDC" name="X86C3912F781ABEDC"></a></p>

<h5>3.1-3 NP2GP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NP2GP</code>( <var class="Arg">np</var>, <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The GAP format of the polynomial <var class="Arg">np</var> in NP format.</p>

<p>This function will convert a polynomial in NP format to a GAP polynomial in the free associative algebra <var class="Arg">A</var> and a vector in NPM format to a GAP vector in the free module <var class="Arg">A</var>. In case of the NP format, the number of variables should not exceed the rank of the free algebra <var class="Arg">A</var>. In case of the NPM format, the absolute of the negative numbers should not exceed the rank of the free module <var class="Arg">A</var>.</p>

<p><em>Example:</em> Let <code class="code">A</code> be the free associative algebra with one over the rationals on the generators <code class="code">a</code> and <code class="code">b</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(GF(3),"a","b");;</span>
</pre></div>

<p>Let <code class="code">np</code> be a polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">np:=[ [ [ 2, 1 ], [ 1, 2 ], [  ] ], [ Z(3)^0, Z(3), Z(3) ] ];;</span>
</pre></div>

<p>The polynomial can be converted to the corresponding element of <var class="Arg">A</var> with NP2GP:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NP2GP(np,A);</span>
(Z(3)^0)*b*a+(Z(3))*a*b+(Z(3))*<identity ...>
</pre></div>

<p>Note that some information of the coefficient field of a polynomial <code class="code">np</code> in NP format can be obtained from the second list of <code class="code">np</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">One(np[2][1]);</span>
Z(3)^0
</pre></div>

<p>Now let <code class="code">M</code> be the module <code class="code">A^2</code> and let <code class="code">npm</code> be a polynomial over that module in NPM form.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=A^2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">npm:=[ [ [ -1, 1 ], [ -2, 2 ] ], [ Z(3)^0, Z(3)^0 ] ];;</span>
</pre></div>

<p>The element of <var class="Arg">M</var> corresponding to <code class="code">npm</code> is</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NP2GP(npm,M);</span>
[ (Z(3)^0)*a, (Z(3)^0)*b ]
</pre></div>

<p>If <code class="code">M</code> is a module of dimension 2 over <code class="code">A</code> and <code class="code">Lnp</code> a list of polynomials in NPM format, then the polynomials can be converted to the corresponding polynomials of <code class="code">M</code> as follows:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=A^2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp:=[ [ [ [ -2, 1, 1 ], [ -2, 1 ] ], [ 1, -1 ] ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [ [ [ -1, 2, 2], [-2, 1 ] ], [ 1, -1 ]*Z(3)^0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(Lnp, m -> NP2GP(m,M));</span>
[ [ <zero> of ..., (Z(3))*a+(Z(3)^0)*a^2 ], [ (Z(3)^0)*b^2, (Z(3))*a ] ]
</pre></div>

<p><a id="X844A23EA7D97150C" name="X844A23EA7D97150C"></a></p>

<h5>3.1-4 NP2GPList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NP2GPList</code>( <var class="Arg">Lnp</var>, <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The list of polynomials corresponding to <var class="Arg">Lnp</var> in GAP format.</p>

<p>This function will convert the list <var class="Arg">Lnp</var> of polynomials in NP format to a list of GAP polynomials in the free associative algebra <var class="Arg">A</var>.</p>

<p><em>Example:</em> Let <code class="code">A</code> be the free associative algebra with one over the rationals on the generators <code class="code">a</code> and <code class="code">b</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;</span>
</pre></div>

<p>Let <code class="code">Lnp</code> be a list of polynomials in NP format. Then <code class="code">Lnp</code> can be converted to a list of polynomials of <code class="code">A</code> with NP2GPList:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp:=[ [ [ [ 1, 1, 1 ], [ 1 ] ], [ 1, -1 ] ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [ [ [ 2, 2 ], [ ] ], [ 1, -1 ] ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NP2GPList(Lnp,A);</span>
[ (1)*a^3+(-1)*a, (1)*b^2+(-1)*<identity ...> ]
</pre></div>

<p>It has the same effect as the function <code class="code">List</code> applied as follows.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(Lnp, p -> NP2GP(p,A));</span>
[ (1)*a^3+(-1)*a, (1)*b^2+(-1)*<identity ...> ]
</pre></div>

<p>Now let <code class="code">M</code> be a module of dimension 2 over <code class="code">A</code> and <code class="code">Lnp</code> a list of vectors in NPM format. Then polynomials <code class="code">Lnp</code> can be converted to the corresponding vectors of <code class="code">M</code> with NP2GPList:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=A^2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp:=[ [ [ [ -2, 1, 1 ], [ -2, 1 ] ], [ 1, -1 ] ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [ [ [ -1, 1 ], [ -2 ] ], [ 1, -1 ] ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NP2GPList(Lnp,M);</span>
[ [ <zero> of ..., (-1)*a+(1)*a^2 ], [ (1)*a, (-1)*<identity ...> ] ]
</pre></div>

<p>The same result can be obtained by application of the standard List function:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(Lnp, m -> NP2GP(m,M)) = NP2GPList(Lnp,M) ;</span>
true
</pre></div>

<p><a id="X78F44B01851B1020" name="X78F44B01851B1020"></a></p>

<h4>3.2 <span class="Heading">Printing polynomials in NP format</span></h4>

<p><a id="X7B63BEA87A8D6162" name="X7B63BEA87A8D6162"></a></p>

<h5>3.2-1 PrintNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrintNP</code>( <var class="Arg">np</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function prints a polynomial <var class="Arg">np</var> in NP format, using the letters <code class="code">a</code>, <code class="code">b</code>, <code class="code">c</code>, <span class="SimpleMath">...</span> for <span class="SimpleMath">x_1</span>, <span class="SimpleMath">x_2</span>, <span class="SimpleMath">x_3</span>, <span class="SimpleMath">...</span>, except that everything beyond <span class="SimpleMath">l</span> (the 12-th letter) is printed as <span class="SimpleMath">x</span>.</p>

<p>This function prints a polynomial <var class="Arg">np</var> in NP format as configured by the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A"><span class="RefLink">3.2-2</span></a>).</p>

<p><em>Example:</em> Consider the following polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := [[[1,1,2],[1,2,2],[]],[1,-2,3]];;</span>
</pre></div>

<p>It can be printed in the guise of a polynomial in <code class="code">a</code> and <code class="code">b</code> by the function <code class="code">PrintNP</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p);</span>
 a^2b - 2ab^2 + 3
</pre></div>

<p><a id="X7F7510A878045D3A" name="X7F7510A878045D3A"></a></p>

<h5>3.2-2 GBNP.ConfigPrint</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GBNP.ConfigPrint</code>( <var class="Arg">arg</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>By default the generators of the algebra are printed as <code class="code">a</code>, ..., <code class="code">l</code> and everything after the twelfth generator as <code class="code">x</code>. By calling <code class="code">ConfigPrint</code> it is possible to alter this printing convention. The argument(s) will be an algebra or arguments used for naming algebras in GAP upon creation. More specifically, we have the following choices.</p>


<dl>
<dt><strong class="Mark"><em>no arguments</em></strong></dt>
<dd><p>When the function is invoked without arguments the printing is reset to the default (see above).</p>

</dd>
<dt><strong class="Mark">algebra</strong></dt>
<dd><p>When the function is invoked with an algebra as argument, generators will be printed as they would be in the algebra.</p>

</dd>
<dt><strong class="Mark">algebra,integer</strong></dt>
<dd><p>When the function is invoked with an algebra and an integer <var class="Arg">n</var> as arguments, generators will be printed as they would be in the algebra and separated over the <var class="Arg">n</var> dimensions.</p>

</dd>
<dt><strong class="Mark">leftmodule</strong></dt>
<dd><p>When the function is invoked with an leftmodule <span class="SimpleMath">A^n</span> of an associative algebra as argument, generators will be printed as they would be in the algebra, separated over the <var class="Arg">n</var> dimensions.</p>

</dd>
<dt><strong class="Mark">string</strong></dt>
<dd><p>When the function is invoked with a string as its argument, it is assumed that there is only 1 generator and that this should be named as indicated by the string.</p>

</dd>
<dt><strong class="Mark">integer</strong></dt>
<dd><p>When the function is invoked with an integer as its argument, the <var class="Arg">n</var>-th generator will be printed as <code class="code">x.<n></code>.</p>

</dd>
<dt><strong class="Mark">integer, string</strong></dt>
<dd><p>When the function is invoked with a non-negative integer and a string as its arguments, generators will be printed as <code class="code"><s>.<n></code>, where <code class="code"><s></code> is the string given as argument and <code class="code"><n></code> the number of the generator. There is no checking whether the number given as argument is really the dimension. So it is possible that higher numbers return in the output. This way of input is useful however, because it is a distinction from the one-dimensional case and compatible with the way a free algebra is created.</p>

</dd>
<dt><strong class="Mark">string, string, ..., string</strong></dt>
<dd><p>When the function is invoked with a sequence of strings, then generators will be printed with the corresponding string or <code class="code">x</code> if the sequence is not long enough.</p>

</dd>
</dl>
<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
</pre></div>

<p>They can be printed by the function <code class="code">PrintNP</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p1);</span>
 a^2b - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p2);</span>
 ab^2 - 1
</pre></div>

<p>We can let the variables be printed as <code class="code">x</code> and <code class="code">y</code> instead of <code class="code">a</code> and <code class="code">b</code> by means of <code class="func">GBNP.ConfigPrint</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GBNP.ConfigPrint("x","y");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p1);</span>
 x^2y - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p2);</span>
 xy^2 - 1
</pre></div>

<p>We can also let the variables be printed as <code class="code">x.1</code> and <code class="code">x.2</code> instead of <code class="code">a</code> and <code class="code">b</code> by means of <code class="func">GBNP.ConfigPrint</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GBNP.ConfigPrint(2,"x");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p1);</span>
 x.1^2x.2 - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p2);</span>
 x.1x.2^2 - 1
</pre></div>

<p>We can even assign strings to the variables to be printed like <code class="code">alice</code> and <code class="code">bob</code> instead of <code class="code">a</code> and <code class="code">b</code> by means of <code class="func">GBNP.ConfigPrint</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GBNP.ConfigPrint("alice","bob");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p1);</span>
 alice^2bob - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p2);</span>
 alicebob^2 - 1
</pre></div>

<p>Alternatively, we can introduce the free algebra <var class="Arg">A</var> with two generators, and print the polynomials as members of <var class="Arg">A</var>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GBNP.ConfigPrint(A);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p1);</span>
 a^2b - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p2);</span>
 ab^2 - 1
</pre></div>

<p><a id="X832103DC79A9E9D0" name="X832103DC79A9E9D0"></a></p>

<h5>3.2-3 PrintNPList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrintNPList</code>( <var class="Arg">Lnp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function prints a list <var class="Arg">Lnp</var> of polynomials in NP format, using the function <code class="code">PrintNP</code>.</p>

<p><em>Example:</em> We put two polynomials in NP format into the list <code class="code">Lnp</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp := [p1,p2];;</span>
</pre></div>

<p>We can print the list with <code class="func">PrintNPList</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Lnp);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p>Alternatively, using the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A"><span class="RefLink">3.2-2</span></a>), we can introduce the free algebra <var class="Arg">A</var> with two generators, and print the polynomials of the list as members of <var class="Arg">A</var>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GBNP.ConfigPrint(A);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Lnp);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p><a id="X83DE3F817EA74727" name="X83DE3F817EA74727"></a></p>

<h4>3.3 <span class="Heading">Calculating with polynomials in NP format</span></h4>

<p><a id="X7DB3792385AAA805" name="X7DB3792385AAA805"></a></p>

<h5>3.3-1 NumAlgGensNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumAlgGensNP</code>( <var class="Arg">np</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The minimum number <code class="code">t</code> so that <var class="Arg">np</var> belongs to the free algebra on <code class="code">t</code> generators.</p>

<p>When called with an NP polynomial <var class="Arg">np</var>, this function returns the minimum number of generators needed for the corresponding algebra to contain the <var class="Arg">np</var>. If <var class="Arg">np</var> is a polynomial without generators, that is, equivalent to <span class="SimpleMath">0</span> or <span class="SimpleMath">1</span>, then <code class="code">0</code> is returned.</p>

<p><em>Example:</em> Consider the following polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">np := [[[2,2,2,1,1,1],[4],[3,2,3]],[1,-3,2]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(np);</span>
 b^3a^3 - 3d + 2cbc
<span class="GAPprompt">gap></span> <span class="GAPinput">NumAlgGensNP(np);</span>
4
</pre></div>

<p><a id="X865548F07C74AB0A" name="X865548F07C74AB0A"></a></p>

<h5>3.3-2 NumAlgGensNPList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumAlgGensNPList</code>( <var class="Arg">Lnp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The minimum number <code class="code">t</code> so that each polynomial in <var class="Arg">Lnp</var> belongs to the free algebra on <code class="code">t</code> generators.</p>

<p>When called with a list of NP polynomials <var class="Arg">Lnp</var>, this function returns the minimum number of generators needed for the corresponding algebra to contain the NP polynomials in <var class="Arg">Lnp</var>. If <var class="Arg">Lnp</var> only contains polynomials without generators, that is equivalent to <span class="SimpleMath">0</span> and <span class="SimpleMath">1</span>, then <code class="code">0</code> is returned.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2,3,1],[2],[1]],[1,-2,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[2,2,1,4,3],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList([p1,p2]);</span>
 a^2bca - 2b + a
 b^2adc - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">NumAlgGensNPList([p1,p2]);</span>
4
</pre></div>

<p><a id="X782647C57D148379" name="X782647C57D148379"></a></p>

<h5>3.3-3 NumModGensNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumModGensNP</code>( <var class="Arg">npm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The minimum number <code class="code">mt</code> so that <var class="Arg">npm</var> belongs to the free module on <code class="code">mt</code> generators.</p>

<p>When called with a polynomial <var class="Arg">npm</var> in NPM format, this function returns the minimum number of module generators needed for the corresponding algebra to contain <var class="Arg">npm</var>. If <var class="Arg">npm</var> is an NP polynomial that does not contain module generators, then <code class="code">0</code> is returned.</p>

<p><em>Example:</em> Consider the following polynomial in NPM format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">np := [[[-1,1,2,3,1],[-2],[-1]],[1,-2,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(np);</span>
[ abca + 1 , - 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NumModGensNP(np);</span>
2
</pre></div>

<p><a id="X8119282084CA8076" name="X8119282084CA8076"></a></p>

<h5>3.3-4 NumModGensNPList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumModGensNPList</code>( <var class="Arg">Lnpm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The minimum number <code class="code">mt</code> so that each member of <var class="Arg">npm</var> belongs to the free module on <code class="code">mt</code> generators.</p>

<p>When called with a list of polynomials <var class="Arg">Lnpm</var> in NPM format, this function returns the minimum number of module generators needed to contain the polynomials in <var class="Arg">Lnpm</var>. If there are only polynomials in <var class="Arg">Lnpm</var> in NP format, then <code class="code">0</code> is returned.</p>

<p><em>Example:</em> Consider the following two polynomials in NPM format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v1 := [[[-1,1,2,3,1],[-2],[-1]],[1,-2,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">v2 := [[[-2,2,1,4,3],[-3]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList([v1,v2]);</span>
[ abca + 1 , - 2 ]
[ 0, badc , - 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NumModGensNPList([v1,v2]);</span>
3
</pre></div>

<p><a id="X788E1ACA82A833A8" name="X788E1ACA82A833A8"></a></p>

<h5>3.3-5 AddNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddNP</code>( <var class="Arg">u</var>, <var class="Arg">v</var>, <var class="Arg">c</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <var class="Arg">c</var><span class="SimpleMath">*</span><var class="Arg">u</var><span class="SimpleMath">+</span><var class="Arg">d</var><span class="SimpleMath">*</span><var class="Arg">v</var></p>

<p>Computes <var class="Arg">c</var><span class="SimpleMath">*</span><var class="Arg">u</var><span class="SimpleMath">+</span><var class="Arg">d</var><span class="SimpleMath">*</span><var class="Arg">v</var> where <var class="Arg">u</var> and <var class="Arg">v</var> are polynomials in NP format and <var class="Arg">c</var> and <var class="Arg">d</var> are scalars.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-3]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-4]];;</span>
</pre></div>

<p>The second can be subtracted from the first by the function <code class="code">AddNP</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(AddNP(p1,p2,1,-1));</span>
 - ab^2 + a^2b + 1
</pre></div>

<p><a id="X84FC611A822D808F" name="X84FC611A822D808F"></a></p>

<h5>3.3-6 BimulNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BimulNP</code>( <var class="Arg">ga</var>, <var class="Arg">np</var>, <var class="Arg">dr</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the polynomial <var class="Arg">ga</var><span class="SimpleMath">*</span><var class="Arg">np</var><span class="SimpleMath">*</span><var class="Arg">dr</var> in NP format</p>

<p>When called with a polynomial <var class="Arg">np</var> and two monomials <var class="Arg">ga</var>, <var class="Arg">dr</var>, the function will return <var class="Arg">ga</var><span class="SimpleMath">*</span><var class="Arg">np</var><span class="SimpleMath">*</span><var class="Arg">dr</var>. Recall from Section <a href="chap2.html#X7FDF3E5E7F33D3A2"><span class="RefLink">2.1</span></a> that monomials are represented as lists.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-3]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-4]];;</span>
</pre></div>

<p>Multiplying <code class="code">p1</code> from the right by <code class="code">b</code> and multiplying <code class="code">p2</code> from the left by <code class="code">a</code> is possible with the function <code class="code">BimulNP</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(BimulNP([],p1,[2]));</span>
 a^2b^2 - 3b
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(BimulNP([1],p2,[]));</span>
 a^2b^2 - 4a
</pre></div>

<p><a id="X855F3D4C783000E3" name="X855F3D4C783000E3"></a></p>

<h5>3.3-7 CleanNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CleanNP</code>( <var class="Arg">u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The cleaned up version of <var class="Arg">u</var></p>

<p>Given a polynomial in NP format, this function collects terms with same monomial, removes trivial monomials, and orders the monomials, with biggest one first.</p>

<p><em>Example:</em> Consider the following polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := [[[1,1,2],[],[1,1,2],[]],[1,-3,-2,3]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p);</span>
 a^2b - 3 - 2a^2b + 3
</pre></div>

<p>The monomials <code class="code">[1,1,2]</code> and <code class="code">[]</code> occur twice each. For many functions this representation of a polynomial in NP format is not allowed. It needs to be cleaned, as by <code class="func">CleanNP</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(CleanNP(p));</span>
 - a^2b
</pre></div>

<p>In order to define a polynomial over <span class="SimpleMath">GF(2)</span>, the coefficients need to be defined over this field. Such a list of coefficients can be obtained in GAP from a list of integers by multiplying with the identity element of the field. The resulting polynomial need not be clean, and so should be made clean again with <code class="code">CleanNP</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := [[[1,1,2],[]],One(GF(2))*[1,-2]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CleanNP(p);</span>
[ [ [ 1, 1, 2 ] ], [ Z(2)^0 ] ]
</pre></div>

<p><a id="X7D05B60E83FDA567" name="X7D05B60E83FDA567"></a></p>

<h5>3.3-8 GtNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GtNP</code>( <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <span class="SimpleMath">u > v</span> and <code class="code">false</code> if <span class="SimpleMath">u ≤ v</span></p>

<p>Greater than function for monomials <var class="Arg">u</var> and <var class="Arg">v</var> represented as in Section <a href="chap2.html#X7FDF3E5E7F33D3A2"><span class="RefLink">2.1</span></a>. It tests whether <var class="Arg">u</var><span class="SimpleMath">></span><var class="Arg">v</var>. The ordering is done by degree and then lexicographically.</p>

<p><em>Example:</em> Consider the following two monomials.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">u := [1,1,2];</span>
[ 1, 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">v := [2,2,1];</span>
[ 2, 2, 1 ]
</pre></div>

<p>We test whether <code class="code">u</code> is greater than <code class="code">v</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GtNP(u,v);</span>
false
</pre></div>

<p><a id="X8075AE7E7A8088FF" name="X8075AE7E7A8088FF"></a></p>

<h5>3.3-9 LtNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LtNP</code>( <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <span class="SimpleMath">u < v</span> and <code class="code">false</code> if <span class="SimpleMath">u ≥ v</span></p>

<p>Less than function for NP monomials, tests whether <var class="Arg">u</var><span class="SimpleMath"><</span><var class="Arg">v</var>. The ordering is done by degree and then lexicographically.</p>

<p><em>Example:</em> Consider the following two monomials.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">u := [1,1,2];</span>
[ 1, 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">v := [2,2,1];</span>
[ 2, 2, 1 ]
</pre></div>

<p>We test whether <code class="code">u</code> is less than <code class="code">v</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LtNP(u,v);</span>
true
</pre></div>

<p><a id="X7A42AE79811CC5D7" name="X7A42AE79811CC5D7"></a></p>

<h5>3.3-10 LMonNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LMonNP</code>( <var class="Arg">Lnp</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">‣ LMonsNP</code>( <var class="Arg">Lnp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The leading monomial or a list of leading monomials.</p>

<p>These functions return the leading monomial of a polynomial (resp. the leading monomials of a list of polynomials) in NP format. The polynomials of <var class="Arg">Lnp</var> are required to be clean; see Section <a href="chap3.html#X855F3D4C783000E3"><span class="RefLink">3.3-7</span></a>.</p>

<p><em>Example:</em> We put two polynomials in NP format into the list <code class="code">Lnp</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp := [p1,p2];;</span>
</pre></div>

<p>The list of leading monomials is computed by <code class="code">LMonsNP</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LMonsNP(Lnp);</span>
[ [ 1, 1, 2 ], [ 1, 2, 2 ] ]
</pre></div>

<p>For a nicer printing, the monomials can be converted into polynomials in NP format, and then submitted to PrintNPList:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(List(LMonsNP(Lnp), q -> [[q],[1]]));</span>
 a^2b
 ab^2
</pre></div>

<p><a id="X80CD462F794A8095" name="X80CD462F794A8095"></a></p>

<h5>3.3-11 LTermNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LTermNP</code>( <var class="Arg">Lnp</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">‣ LTermsNP</code>( <var class="Arg">Lnp</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The leading term or a list of leading terms.</p>

<p>These functions return the leading term of a polynomial (resp. the leading terms of a list of polynomials) in NP format. The polynomials of <var class="Arg">Lnp</var> are required to be clean; see Section <a href="chap3.html#X855F3D4C783000E3"><span class="RefLink">3.3-7</span></a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[1]],[6,-7]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[2]],[8,-9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp := [p1,p2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LTermNP( p1 );</span>
[ [ [ 1, 1, 2 ] ], [ 6 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LTnp := LTermsNP( Lnp );</span>
[ [ [ [ 1, 1, 2 ] ], [ 6 ] ], [ [ [ 1, 2, 2 ] ], [ 8 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList( LTnp );</span>
6a^2b
8ab^2
</pre></div>

<p><a id="X878A8C027DA25196" name="X878A8C027DA25196"></a></p>

<h5>3.3-12 MkMonicNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MkMonicNP</code>( <var class="Arg">np</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <var class="Arg">np</var> made monic</p>

<p>This function returns the scalar multiple of a polynomial <var class="Arg">np</var> in NP format that is monic, i.e., has leading coefficient equal to 1.</p>

<p><em>Example:</em> Consider the following polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := [[[1,1,2],[]],[2,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p);</span>
 2a^2b - 1
</pre></div>

<p>The coefficient of the leading term is <span class="SimpleMath">2</span>. The function <code class="code">MkMonicNP</code> finds this coefficient and divides every term by it:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(MkMonicNP(p));</span>
 a^2b - 1/2
</pre></div>

<p><a id="X818147CD841BD490" name="X818147CD841BD490"></a></p>

<h5>3.3-13 FactorOutGcdNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorOutGcdNP</code>( <var class="Arg">np</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <var class="Arg">np</var> with Gcd(coefficients) factored out</p>

<p>This function returns the scalar multiple of a polynomial <var class="Arg">np</var> in NP format with integer coefficients such that its coefficients have Gcd equal to 1. If the coefficients are not all integers then <code class="code">fail</code> is returned.</p>

<p><em>Example:</em> Consider the following polynomial in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := [[[1,1,2],[1,2],[1]],[30,70,105]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(p);</span>
 30a^2b + 70ab + 105a
</pre></div>

<p>The <code class="code">Gcd</code> of the coefficients <span class="SimpleMath">[30,70,105]</span> is <span class="SimpleMath">5</span>. The function <code class="code">FactorOutGcdNP</code> divides the polynomial by <span class="SimpleMath">5</span>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(FactorOutGcdNP(p));</span>
 6a^2b + 14ab + 21a
<span class="GAPprompt">gap></span> <span class="GAPinput">m := MkMonicNP(p);</span>
[ [ [ 1, 1, 2 ], [ 1, 2 ], [ 1 ] ], [ 1, 7/3, 7/2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">fm := FactorOutGcdNP(m);</span>
fail
</pre></div>

<p><a id="X7ABA720E87EFF040" name="X7ABA720E87EFF040"></a></p>

<h5>3.3-14 MulNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MulNP</code>( <var class="Arg">np1</var>, <var class="Arg">np2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <var class="Arg">np1</var><span class="SimpleMath">*</span><var class="Arg">np2</var></p>

<p>When invoked with two polynomials <var class="Arg">np1</var> and <var class="Arg">np2</var> in NP format, this function will return the product <var class="Arg">np1</var><span class="SimpleMath">*</span><var class="Arg">np2</var>.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
</pre></div>

<p>The function <code class="code">MulNP</code> multiplies the two polynomials.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(MulNP(p1,p2));</span>
 a^2bab^2 - ab^2 - a^2b + 1
</pre></div>

<p>The fact that this multiplication is not commutative is illustrated by the following comparison, using <code class="code">MulNP</code> twice and <code class="code">AddNP</code> once.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNP(AddNP(MulNP(p1,p2),MulNP(p2,p1),1,-1));</span>
 - ab^2a^2b + a^2bab^2
</pre></div>

<p><a id="X81381B2D83D2B9A9" name="X81381B2D83D2B9A9"></a></p>

<h4>3.4 <span class="Heading">Gröbner functions, standard variant</span></h4>

<p><a id="X7CD9F9C97B2563E2" name="X7CD9F9C97B2563E2"></a></p>

<h5>3.4-1 Grobner</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Grobner</code>( <var class="Arg">Lnp</var>[, <var class="Arg">D</var>][, <var class="Arg">max</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: If the algorithm terminates, a Gröbner Basis or a record if <var class="Arg">max</var> is specified (see description).</p>

<p>For a list <var class="Arg">Lnp</var> of polynomials in NP format this function will use Buchberger's algorithm with normal form to find a Gröbner Basis (if possible, the general problem is unsolvable).



<p>When called with the optional argument <var class="Arg">max</var>, which should be a positive integer, the calculation will be interrupted if it has not ended after <var class="Arg">max</var> iterations. The return value will be a record containing lists <code class="code">G</code> and <code class="code">todo</code> of polynomials in NP format, a boolean <code class="code">completed</code>, and an integer <code class="code">iterations</code>. Here <code class="code">G</code> and <code class="code">todo</code> form a Gröbner pair (see <a href="chapBib.html#biBCohenGijsbersEtAl2007">[Coh07]</a>). The number of performed iterations will be placed in <code class="code">iterations</code>. If the algorithm has terminated, then <code class="code">todo</code> will be the empty list and <code class="code">completed</code> will be equal to <code class="code">true</code>. If the algorithm has not terminated, then <code class="code">todo</code> will be a non-empty list of polynomials in NP format and <code class="code">completed</code> will be <code class="code">false</code>.</p>

<p>By use of the optional argument <var class="Arg">D</var>, it is possible to resume a previously interrupted calculation.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList([p1,p2]);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p>Their Gröbner basis can be computed by the function <code class="code">Grobner</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Grobner([p1,p2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(G);</span>
 b - a
 a^3 - 1
</pre></div>

<p>One iteration of the Gröbner computations is invoked by use of the parameter <code class="code">max</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := Grobner([p1,p2],1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(R.G);</span>
 b - a
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(R.todo);</span>
 a^3 - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">R.iterations;</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">R.completed;</span>
false
</pre></div>

<p>The above list <code class="code">R.todo</code> can be used to resume the computation of the Gröbner basis computation with the Gröbner pair <code class="code">R.G</code>, <code class="code">R.todo</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Grobner(R.G,R.todo));</span>
 b - a
 a^3 - 1
</pre></div>

<p>In order to perform the Gröbner basis computation with polynomials in a free algebra over the field <span class="SimpleMath">GF(2)</span>, the coefficients of the polynomials need to be defined over that field.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Grobner([[p1[1],One(GF(2))*p1[2]],[p2[1],One(GF(2))*p1[2]]]));</span>
 b + a
 a^3 + Z(2)^0
</pre></div>

<p><a id="X7FEDA29E78B0CEED" name="X7FEDA29E78B0CEED"></a></p>

<h5>3.4-2 SGrobner</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SGrobner</code>( <var class="Arg">Lnp</var>[, <var class="Arg">todo</var>][, <var class="Arg">max</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: If the algorithm terminates, a Gröbner Basis or a record if <var class="Arg">max</var> is specified (see description).</p>

<p>For a list <var class="Arg">Lnp</var> of polynomials in NP format this function will use Buchberger's algorithm with strong normal form (see [Coh07]) to find a Gröbner Basis (if possible, the general problem is unsolvable).



<p>When called with the optional argument <var class="Arg">max</var>, which should be a positive integer, the calculation will be interrupted if it has not ended after <var class="Arg">max</var> iterations. The return value will be a record containing lists <code class="code">G</code> and <code class="code">todo</code> of polynomials in NP format, a boolean <code class="code">completed</code>, and an integer <code class="code">iterations</code>. Here <code class="code">G</code> and <code class="code">todo</code> form a Gröbner pair (see <a href="chapBib.html#biBCohenGijsbersEtAl2007">[Coh07]</a>). The number of performed iterations will be placed in <code class="code">iterations</code>. If the algorithm has terminated, then <code class="code">todo</code> will be the empty list and <code class="code">completed</code> will be equal to <code class="code">true</code>. If the algorithm has not terminated, then <code class="code">todo</code> will be a non-empty list of polynomials in NP format and <code class="code">completed</code> will be <code class="code">false</code>.</p>

<p>By use of the optional argument <var class="Arg">D</var>, it is possible to resume a previously interrupted calculation.</p>

<p><em>Example:</em> Consider the following two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := [[[1,1,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := [[[1,2,2],[]],[1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList([p1,p2]);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p>Their Gröbner basis can be computed by the function <code class="code">Grobner</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := SGrobner([p1,p2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(G);</span>
 b - a
 a^3 - 1
</pre></div>

<p>One iteration of the Gröbner computations is invoked by use of the parameter <code class="code">max</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := SGrobner([p1,p2],1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(R.G);</span>
 b - a
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(R.todo);</span>
 a^3 - 1
<span class="GAPprompt">gap></span> <span class="GAPinput">R.iterations;</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">R.completed;</span>
false
</pre></div>

<p>The above list <code class="code">R.todo</code> can be used to resume the computation of the Gröbner basis computation with the Gröbner pair <code class="code">R.G</code>, <code class="code">R.todo</code>:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(SGrobner(R.G,R.todo));</span>
 b - a
 a^3 - 1
</pre></div>

<p><a id="X80D4D22C7E643C7B" name="X80D4D22C7E643C7B"></a></p>

<h5>3.4-3 IsGrobnerBasis</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGrobnerBasis</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <var class="Arg">G</var> is a Gröbner basis and <code class="code">false</code> otherwise</p>

<p>When invoked with a list <var class="Arg">G</var> of polynomials in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2"><span class="RefLink">2.1</span></a>), this function will check whether the list is a Gröbner basis. The check is based on Theorem 1.4 from <a href="chapBib.html#biBCohenGijsbersEtAl2007">[Coh07]</a>.</p>

<p>Polynomials representing zero are allowed in <var class="Arg">G</var>.</p>

<p><em>Example:</em> Consider the following list of two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp := [[[[1,1,2],[]],[1,-1]], [[[1,2,2],[]],[1,-1]]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Lnp);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p>The function <code class="code">IsGrobner</code> checks whether the list is a Gröbner basis.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGrobnerBasis(Lnp);</span>
false
</pre></div>

<p>So the answer should be <code class="code">true</code> for the result of a Gröbner computation:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGrobnerBasis(Grobner(Lnp));</span>
true
</pre></div>

<p><a id="X7D17F9027F08CF0B" name="X7D17F9027F08CF0B"></a></p>

<h5>3.4-4 IsStrongGrobnerBasis</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsStrongGrobnerBasis</code>( <var class="Arg">G</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <var class="Arg">G</var> is a strong Gröbner basis and <code class="code">false</code> otherwise</p>

<p>When invoked with a list <var class="Arg">G</var> of polynomials in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2"><span class="RefLink">2.1</span></a>), this function will check whether the polynomials in this list form a strong Gröbner basis (see <a href="chapBib.html#biBCohenGijsbersEtAl2007">[Coh07]</a>).</p>

<p>Polynomials representing zero are allowed in <var class="Arg">G</var>.</p>

<p><em>Example:</em> Consider the following list of two polynomials in NP format.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lnp := [[[[1,1,2],[]],[1,-1]], [[[1,2,2],[]],[1,-1]]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintNPList(Lnp);</span>
 a^2b - 1
 ab^2 - 1
</pre></div>

<p>The function <code class="code">IsStrongGrobner</code> checks whether the list is a strong Gröbner basis.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsStrongGrobnerBasis(Lnp);</span>
false
</pre></div>

<p>But the answer should be <code class="code">true</code> for the result of a strong Gröbner computation:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsStrongGrobnerBasis(SGrobner(Lnp));</span>
true
--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.25 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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.