"Fossies" - the Fresh Open Source Software Archive

Member "doc/jython/basic_sigbased_gb-pysrc.html" (21 Apr 2019, 170551 Bytes) of package /linux/privat/jas-2.6.5988-doc.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) HTML source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 <?xml version="1.0" encoding="ascii"?>
    2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    3           "DTD/xhtml1-transitional.dtd">
    4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    5 <head>
    6   <title>basic_sigbased_gb</title>
    7   <link rel="stylesheet" href="epydoc.css" type="text/css" />
    8   <script type="text/javascript" src="epydoc.js"></script>
    9 </head>
   10 
   11 <body bgcolor="white" text="black" link="blue" vlink="#204080"
   12       alink="#204080">
   13 <!-- ==================== NAVIGATION BAR ==================== -->
   14 <table class="navbar" border="0" width="100%" cellpadding="0"
   15        bgcolor="#a0c0ff" cellspacing="0">
   16   <tr valign="middle">
   17 
   18   <!-- Tree link -->
   19       <th>&nbsp;&nbsp;&nbsp;<a
   20         href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>
   21 
   22   <!-- Index link -->
   23       <th>&nbsp;&nbsp;&nbsp;<a
   24         href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>
   25 
   26   <!-- Help link -->
   27       <th>&nbsp;&nbsp;&nbsp;<a
   28         href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>
   29 
   30   <!-- Project homepage -->
   31       <th class="navbar" align="right" width="100%">
   32         <table border="0" cellpadding="0" cellspacing="0">
   33           <tr><th class="navbar" align="center"
   34             ><a class="navbar" target="_top" href="../../index.html">Python to JAS</a></th>
   35           </tr></table></th>
   36   </tr>
   37 </table>
   38 <table width="100%" cellpadding="0" cellspacing="0">
   39   <tr valign="top">
   40     <td width="100%">
   41       <span class="breadcrumbs">
   42         Module&nbsp;basic_sigbased_gb
   43       </span>
   44     </td>
   45     <td>
   46       <table cellpadding="0" cellspacing="0">
   47         <!-- hide/show private -->
   48         <tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
   49     onclick="toggle_private();">hide&nbsp;private</a>]</span></td></tr>
   50         <tr><td align="right"><span class="options"
   51             >[<a href="frames.html" target="_top">frames</a
   52             >]&nbsp;|&nbsp;<a href="basic_sigbased_gb-pysrc.html"
   53             target="_top">no&nbsp;frames</a>]</span></td></tr>
   54       </table>
   55     </td>
   56   </tr>
   57 </table>
   58 <h1 class="epydoc">Source Code for <a href="basic_sigbased_gb-module.html">Module basic_sigbased_gb</a></h1>
   59 <pre class="py-src">
   60 <a name="L1"></a><tt class="py-lineno">  1</tt>  <tt class="py-line"><tt class="py-comment"># Implementations of algorithms found in joint paper by Eder and Perry</tt> </tt>
   61 <a name="L2"></a><tt class="py-lineno">  2</tt>  <tt class="py-line"><tt class="py-comment"># Copyright (C) 2010-2011, the University of Southern Mississippi</tt> </tt>
   62 <a name="L3"></a><tt class="py-lineno">  3</tt>  <tt class="py-line"><tt class="py-comment"># released into the public domain</tt> </tt>
   63 <a name="L4"></a><tt class="py-lineno">  4</tt>  <tt class="py-line"><tt class="py-comment">#</tt> </tt>
   64 <a name="L5"></a><tt class="py-lineno">  5</tt>  <tt class="py-line"><tt class="py-comment"># Originally from http://www.math.usm.edu/perry/Research/basic_sigbased_gb.py</tt> </tt>
   65 <a name="L6"></a><tt class="py-lineno">  6</tt>  <tt class="py-line"><tt class="py-comment"># slightly changed for JAS compatibility, changes are labled with JAS</tt> </tt>
   66 <a name="L7"></a><tt class="py-lineno">  7</tt>  <tt class="py-line"><tt class="py-comment"># $Id: basic_sigbased_gb.py 5474 2016-03-25 16:39:42Z kredel $</tt> </tt>
   67 <a name="L8"></a><tt class="py-lineno">  8</tt>  <tt class="py-line"> </tt>
   68 <a name="L9"></a><tt class="py-lineno">  9</tt>  <tt class="py-line"><tt class="py-comment"># this implementation has one significant difference from the paper:</tt> </tt>
   69 <a name="L10"></a><tt class="py-lineno"> 10</tt>  <tt class="py-line"><tt class="py-comment"># the paper maintains monic signatures, but</tt> </tt>
   70 <a name="L11"></a><tt class="py-lineno"> 11</tt>  <tt class="py-line"><tt class="py-comment"># this implementation maintains monic polynomials</tt> </tt>
   71 <a name="L12"></a><tt class="py-lineno"> 12</tt>  <tt class="py-line"> </tt>
   72 <a name="sigbased_gb"></a><div id="sigbased_gb-def"><a name="L13"></a><tt class="py-lineno"> 13</tt> <a class="py-toggle" href="#" id="sigbased_gb-toggle" onclick="return toggle('sigbased_gb');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html">sigbased_gb</a><tt class="py-op">:</tt> </tt>
   73 </div><div id="sigbased_gb-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="sigbased_gb-expanded"><a name="L14"></a><tt class="py-lineno"> 14</tt>  <tt class="py-line">  <tt class="py-comment"># the base class from which all other classes are derived</tt> </tt>
   74 <a name="L15"></a><tt class="py-lineno"> 15</tt>  <tt class="py-line">   </tt>
   75 <a name="sigbased_gb.basis_sig"></a><div id="sigbased_gb.basis_sig-def"><a name="L16"></a><tt class="py-lineno"> 16</tt> <a class="py-toggle" href="#" id="sigbased_gb.basis_sig-toggle" onclick="return toggle('sigbased_gb.basis_sig');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#basis_sig">basis_sig</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
   76 </div><div id="sigbased_gb.basis_sig-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.basis_sig-expanded"><a name="L17"></a><tt class="py-lineno"> 17</tt>  <tt class="py-line">    <tt class="py-comment"># incremental basis computation</tt> </tt>
   77 <a name="L18"></a><tt class="py-lineno"> 18</tt>  <tt class="py-line">    <tt class="py-comment"># F is a container of generators of an ideal</tt> </tt>
   78 <a name="L19"></a><tt class="py-lineno"> 19</tt>  <tt class="py-line">    <tt class="py-name">F</tt><tt class="py-op">.</tt><tt class="py-name">sort</tt><tt class="py-op">(</tt><tt class="py-name">key</tt><tt class="py-op">=</tt><tt class="py-keyword">lambda</tt> <tt class="py-name">x</tt><tt class="py-op">:</tt> <tt class="py-op">-</tt><tt class="py-name">x</tt><tt class="py-op">.</tt><tt id="link-0" class="py-name" targets="Method jas.RingElem.lm()=jas.RingElem-class.html#lm"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-0', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-1" class="py-name" targets="Method jas.RingElem.degree()=jas.RingElem-class.html#degree"><a title="jas.RingElem.degree" class="py-name" href="#" onclick="return doclink('link-1', 'degree', 'link-1');">degree</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-comment"># JAS</tt> </tt>
   79 <a name="L20"></a><tt class="py-lineno"> 20</tt>  <tt class="py-line">    <tt class="py-comment">#F.sort(key=lambda x: -x.lm().totalDeg()) # JAS</tt> </tt>
   80 <a name="L21"></a><tt class="py-lineno"> 21</tt>  <tt class="py-line">    <tt class="py-comment">#print "JAS F = " + str([ str(g) for g in F]); </tt> </tt>
   81 <a name="L22"></a><tt class="py-lineno"> 22</tt>  <tt class="py-line">    <tt class="py-name">G</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
   82 <a name="L23"></a><tt class="py-lineno"> 23</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">f</tt> <tt class="py-keyword">in</tt> <tt class="py-name">F</tt><tt class="py-op">:</tt> </tt>
   83 <a name="L24"></a><tt class="py-lineno"> 24</tt>  <tt class="py-line">      <tt class="py-name">ff</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-2" class="py-name" targets="Method jas.RingElem.reduce()=jas.RingElem-class.html#reduce"><a title="jas.RingElem.reduce" class="py-name" href="#" onclick="return doclink('link-2', 'reduce', 'link-2');">reduce</a></tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> </tt>
   84 <a name="L25"></a><tt class="py-lineno"> 25</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">ff</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
   85 <a name="L26"></a><tt class="py-lineno"> 26</tt>  <tt class="py-line">          <tt class="py-keyword">continue</tt><tt class="py-op">;</tt> </tt>
   86 <a name="L27"></a><tt class="py-lineno"> 27</tt>  <tt class="py-line">      <tt class="py-name">G</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-3" class="py-name" targets="Method basic_sigbased_gb.sigbased_gb.incremental_basis()=basic_sigbased_gb.sigbased_gb-class.html#incremental_basis"><a title="basic_sigbased_gb.sigbased_gb.incremental_basis" class="py-name" href="#" onclick="return doclink('link-3', 'incremental_basis', 'link-3');">incremental_basis</a></tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">,</tt><tt class="py-name">f</tt><tt class="py-op">)</tt> </tt>
   87 <a name="L28"></a><tt class="py-lineno"> 28</tt>  <tt class="py-line">      <tt class="py-name">Gnew</tt> <tt class="py-op">=</tt> <tt class="py-op">[</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">]</tt> </tt>
   88 <a name="L29"></a><tt class="py-lineno"> 29</tt>  <tt class="py-line">      <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-4" class="py-name" targets="Method jas.RingElem.parent()=jas.RingElem-class.html#parent"><a title="jas.RingElem.parent" class="py-name" href="#" onclick="return doclink('link-4', 'parent', 'link-4');">parent</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
   89 <a name="L30"></a><tt class="py-lineno"> 30</tt>  <tt class="py-line">      <tt class="py-keyword">print</tt> <tt class="py-string">"size before reduction"</tt><tt class="py-op">,</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
   90 <a name="L31"></a><tt class="py-lineno"> 31</tt>  <tt class="py-line">      <tt class="py-name">G</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-5" class="py-name" targets="Method jas.Ring.ideal()=jas.Ring-class.html#ideal,Method jas.RingElem.ideal()=jas.RingElem-class.html#ideal,Method jas.SolvableRing.ideal()=jas.SolvableRing-class.html#ideal,Method jas.WordRing.ideal()=jas.WordRing-class.html#ideal"><a title="jas.Ring.ideal
   91 jas.RingElem.ideal
   92 jas.SolvableRing.ideal
   93 jas.WordRing.ideal" class="py-name" href="#" onclick="return doclink('link-5', 'ideal', 'link-5');">ideal</a></tt><tt class="py-op">(</tt><tt class="py-name">Gnew</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt id="link-6" class="py-name" targets="Method jas.Ideal.interreduced_basis()=jas.Ideal-class.html#interreduced_basis"><a title="jas.Ideal.interreduced_basis" class="py-name" href="#" onclick="return doclink('link-6', 'interreduced_basis', 'link-6');">interreduced_basis</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
   94 <a name="L32"></a><tt class="py-lineno"> 32</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">G</tt> </tt>
   95 </div><a name="L33"></a><tt class="py-lineno"> 33</tt>  <tt class="py-line">   </tt>
   96 <a name="sigbased_gb.spoly_multipliers"></a><div id="sigbased_gb.spoly_multipliers-def"><a name="L34"></a><tt class="py-lineno"> 34</tt> <a class="py-toggle" href="#" id="sigbased_gb.spoly_multipliers-toggle" onclick="return toggle('sigbased_gb.spoly_multipliers');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#spoly_multipliers">spoly_multipliers</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">f</tt><tt class="py-op">,</tt><tt class="py-param">g</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
   97 </div><div id="sigbased_gb.spoly_multipliers-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.spoly_multipliers-expanded"><a name="L35"></a><tt class="py-lineno"> 35</tt>  <tt class="py-line">    <tt class="py-comment"># multipliers for the s-polynomial of f and g</tt> </tt>
   98 <a name="L36"></a><tt class="py-lineno"> 36</tt>  <tt class="py-line">    <tt class="py-comment"># returns uf,ug such that</tt> </tt>
   99 <a name="L37"></a><tt class="py-lineno"> 37</tt>  <tt class="py-line">    <tt class="py-comment"># that is, spoly(f,g) = uf.f - ug.g</tt> </tt>
  100 <a name="L38"></a><tt class="py-lineno"> 38</tt>  <tt class="py-line">    <tt class="py-name">tf</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-7" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-7', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">tg</tt> <tt class="py-op">=</tt> <tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-8" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-8', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  101 <a name="L39"></a><tt class="py-lineno"> 39</tt>  <tt class="py-line">    <tt class="py-name">tfg</tt> <tt class="py-op">=</tt> <tt class="py-name">tf</tt><tt class="py-op">.</tt><tt class="py-name">lcm</tt><tt class="py-op">(</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt> </tt>
  102 <a name="L40"></a><tt class="py-lineno"> 40</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  103 <a name="L41"></a><tt class="py-lineno"> 41</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-9" class="py-name" targets="Method jas.RingElem.monomial_quotient()=jas.RingElem-class.html#monomial_quotient"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-9', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tf</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-10" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-10', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  104 </div><a name="L42"></a><tt class="py-lineno"> 42</tt>  <tt class="py-line">   </tt>
  105 <a name="sigbased_gb.subset"></a><div id="sigbased_gb.subset-def"><a name="L43"></a><tt class="py-lineno"> 43</tt> <a class="py-toggle" href="#" id="sigbased_gb.subset-toggle" onclick="return toggle('sigbased_gb.subset');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#subset">subset</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">criterion</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  106 </div><div id="sigbased_gb.subset-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.subset-expanded"><a name="L44"></a><tt class="py-lineno"> 44</tt>  <tt class="py-line">    <tt class="py-comment"># this should be changed to use Python's filter() command</tt> </tt>
  107 <a name="L45"></a><tt class="py-lineno"> 45</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  108 <a name="L46"></a><tt class="py-lineno"> 46</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">s</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  109 <a name="L47"></a><tt class="py-lineno"> 47</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">criterion</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  110 <a name="L48"></a><tt class="py-lineno"> 48</tt>  <tt class="py-line">        <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">)</tt> </tt>
  111 <a name="L49"></a><tt class="py-lineno"> 49</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  112 </div><a name="L50"></a><tt class="py-lineno"> 50</tt>  <tt class="py-line">   </tt>
  113 <a name="sigbased_gb.min_sig_degree"></a><div id="sigbased_gb.min_sig_degree-def"><a name="L51"></a><tt class="py-lineno"> 51</tt> <a class="py-toggle" href="#" id="sigbased_gb.min_sig_degree-toggle" onclick="return toggle('sigbased_gb.min_sig_degree');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#min_sig_degree">min_sig_degree</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">P</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  114 </div><div id="sigbased_gb.min_sig_degree-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.min_sig_degree-expanded"><a name="L52"></a><tt class="py-lineno"> 52</tt>  <tt class="py-line">    <tt class="py-comment"># determines the minimal degree of a signature in P</tt> </tt>
  115 <a name="L53"></a><tt class="py-lineno"> 53</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">min</tt><tt class="py-op">(</tt><tt class="py-op">[</tt><tt class="py-name">p</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-11" class="py-name"><a title="jas.RingElem.degree" class="py-name" href="#" onclick="return doclink('link-11', 'degree', 'link-1');">degree</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">p</tt> <tt class="py-keyword">in</tt> <tt class="py-name">P</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
  116 </div><a name="L54"></a><tt class="py-lineno"> 54</tt>  <tt class="py-line">   </tt>
  117 <a name="sigbased_gb.new_pair"></a><div id="sigbased_gb.new_pair-def"><a name="L55"></a><tt class="py-lineno"> 55</tt> <a class="py-toggle" href="#" id="sigbased_gb.new_pair-toggle" onclick="return toggle('sigbased_gb.new_pair');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#new_pair">new_pair</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sig</tt><tt class="py-op">,</tt><tt class="py-param">p</tt><tt class="py-op">,</tt><tt class="py-param">q</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  118 </div><div id="sigbased_gb.new_pair-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.new_pair-expanded"><a name="L56"></a><tt class="py-lineno"> 56</tt>  <tt class="py-line">    <tt class="py-comment"># creates a new critical pair from p and q, with signature sig</tt> </tt>
  119 <a name="L57"></a><tt class="py-lineno"> 57</tt>  <tt class="py-line">    <tt class="py-comment"># it needs G for the sake of F5; see derived class below</tt> </tt>
  120 <a name="L58"></a><tt class="py-lineno"> 58</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">p</tt><tt class="py-op">,</tt><tt class="py-name">q</tt><tt class="py-op">)</tt> </tt>
  121 </div><a name="L59"></a><tt class="py-lineno"> 59</tt>  <tt class="py-line">   </tt>
  122 <a name="sigbased_gb.spoly"></a><div id="sigbased_gb.spoly-def"><a name="L60"></a><tt class="py-lineno"> 60</tt> <a class="py-toggle" href="#" id="sigbased_gb.spoly-toggle" onclick="return toggle('sigbased_gb.spoly');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#spoly">spoly</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  123 </div><div id="sigbased_gb.spoly-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.spoly-expanded"><a name="L61"></a><tt class="py-lineno"> 61</tt>  <tt class="py-line">    <tt class="py-comment"># computes the spolynomial</tt> </tt>
  124 <a name="L62"></a><tt class="py-lineno"> 62</tt>  <tt class="py-line">    <tt class="py-comment"># assumes that s has the form (signature, poly, poly)</tt> </tt>
  125 <a name="L63"></a><tt class="py-lineno"> 63</tt>  <tt class="py-line">    <tt class="py-name">f</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">;</tt> <tt class="py-name">g</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">2</tt><tt class="py-op">]</tt> </tt>
  126 <a name="L64"></a><tt class="py-lineno"> 64</tt>  <tt class="py-line">    <tt class="py-name">tf</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-12" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-12', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">tg</tt> <tt class="py-op">=</tt> <tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-13" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-13', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  127 <a name="L65"></a><tt class="py-lineno"> 65</tt>  <tt class="py-line">    <tt class="py-name">tfg</tt> <tt class="py-op">=</tt> <tt class="py-name">tf</tt><tt class="py-op">.</tt><tt class="py-name">lcm</tt><tt class="py-op">(</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt> </tt>
  128 <a name="L66"></a><tt class="py-lineno"> 66</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-14" class="py-name"><a title="jas.RingElem.parent" class="py-name" href="#" onclick="return doclink('link-14', 'parent', 'link-4');">parent</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  129 <a name="L67"></a><tt class="py-lineno"> 67</tt>  <tt class="py-line">    <tt class="py-name">uf</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-15" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-15', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tf</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">ug</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-16" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-16', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt> </tt>
  130 <a name="L68"></a><tt class="py-lineno"> 68</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">uf</tt><tt class="py-op">*</tt><tt class="py-name">f</tt> <tt class="py-op">-</tt> <tt class="py-name">ug</tt><tt class="py-op">*</tt><tt class="py-name">g</tt> </tt>
  131 </div><a name="L69"></a><tt class="py-lineno"> 69</tt>  <tt class="py-line">   </tt>
  132 <a name="sigbased_gb.initialize_Syz"></a><div id="sigbased_gb.initialize_Syz-def"><a name="L70"></a><tt class="py-lineno"> 70</tt> <a class="py-toggle" href="#" id="sigbased_gb.initialize_Syz-toggle" onclick="return toggle('sigbased_gb.initialize_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#initialize_Syz">initialize_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  133 </div><div id="sigbased_gb.initialize_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.initialize_Syz-expanded"><a name="L71"></a><tt class="py-lineno"> 71</tt>  <tt class="py-line">    <tt class="py-comment"># initializes Syz; initially, this does nothing</tt> </tt>
  134 <a name="L72"></a><tt class="py-lineno"> 72</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  135 </div><a name="L73"></a><tt class="py-lineno"> 73</tt>  <tt class="py-line">   </tt>
  136 <a name="sigbased_gb.prune_P"></a><div id="sigbased_gb.prune_P-def"><a name="L74"></a><tt class="py-lineno"> 74</tt> <a class="py-toggle" href="#" id="sigbased_gb.prune_P-toggle" onclick="return toggle('sigbased_gb.prune_P');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#prune_P">prune_P</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">P</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  137 </div><div id="sigbased_gb.prune_P-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.prune_P-expanded"><a name="L75"></a><tt class="py-lineno"> 75</tt>  <tt class="py-line">    <tt class="py-comment"># prunes P using Syz; initially, this does nothing</tt> </tt>
  138 <a name="L76"></a><tt class="py-lineno"> 76</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">P</tt> </tt>
  139 </div><a name="L77"></a><tt class="py-lineno"> 77</tt>  <tt class="py-line">     </tt>
  140 <a name="sigbased_gb.prune_S"></a><div id="sigbased_gb.prune_S-def"><a name="L78"></a><tt class="py-lineno"> 78</tt> <a class="py-toggle" href="#" id="sigbased_gb.prune_S-toggle" onclick="return toggle('sigbased_gb.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  141 </div><div id="sigbased_gb.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.prune_S-expanded"><a name="L79"></a><tt class="py-lineno"> 79</tt>  <tt class="py-line">    <tt class="py-comment"># prunes S using Syz, Done, and G; initially, this does nothing</tt> </tt>
  142 <a name="L80"></a><tt class="py-lineno"> 80</tt>  <tt class="py-line">    <tt class="py-comment"># (Done is used as a shortcut)</tt> </tt>
  143 <a name="L81"></a><tt class="py-lineno"> 81</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">S</tt> </tt>
  144 </div><a name="L82"></a><tt class="py-lineno"> 82</tt>  <tt class="py-line">   </tt>
  145 <a name="sigbased_gb.update_Syz"></a><div id="sigbased_gb.update_Syz-def"><a name="L83"></a><tt class="py-lineno"> 83</tt> <a class="py-toggle" href="#" id="sigbased_gb.update_Syz-toggle" onclick="return toggle('sigbased_gb.update_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#update_Syz">update_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  146 </div><div id="sigbased_gb.update_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.update_Syz-expanded"><a name="L84"></a><tt class="py-lineno"> 84</tt>  <tt class="py-line">    <tt class="py-comment"># updates Syz using sigma and r</tt> </tt>
  147 <a name="L85"></a><tt class="py-lineno"> 85</tt>  <tt class="py-line">    <tt class="py-comment"># some algorithms use this; some don't</tt> </tt>
  148 <a name="L86"></a><tt class="py-lineno"> 86</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">Syz</tt> </tt>
  149 </div><a name="L87"></a><tt class="py-lineno"> 87</tt>  <tt class="py-line">   </tt>
  150 <a name="sigbased_gb.sigsafe_reduction"></a><div id="sigbased_gb.sigsafe_reduction-def"><a name="L88"></a><tt class="py-lineno"> 88</tt> <a class="py-toggle" href="#" id="sigbased_gb.sigsafe_reduction-toggle" onclick="return toggle('sigbased_gb.sigsafe_reduction');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#sigsafe_reduction">sigsafe_reduction</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  151 </div><div id="sigbased_gb.sigsafe_reduction-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.sigsafe_reduction-expanded"><a name="L89"></a><tt class="py-lineno"> 89</tt>  <tt class="py-line">    <tt class="py-comment"># computes a complete sigma-reduction of s modulo G</tt> </tt>
  152 <a name="L90"></a><tt class="py-lineno"> 90</tt>  <tt class="py-line">    <tt class="py-comment"># F is assumed to be a subset of G that represents the previous GB incrementally</tt> </tt>
  153 <a name="L91"></a><tt class="py-lineno"> 91</tt>  <tt class="py-line">    <tt class="py-comment"># Syz is sent but not used (I should probably remove this)</tt> </tt>
  154 <a name="L92"></a><tt class="py-lineno"> 92</tt>  <tt class="py-line">    <tt class="py-name">r</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt> </tt>
  155 <a name="L93"></a><tt class="py-lineno"> 93</tt>  <tt class="py-line">    <tt class="py-name">r_sigma</tt> <tt class="py-op">=</tt> <tt class="py-name">sigma</tt> </tt>
  156 <a name="L94"></a><tt class="py-lineno"> 94</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  157 <a name="L95"></a><tt class="py-lineno"> 95</tt>  <tt class="py-line">    <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">True</tt> </tt>
  158 <a name="L96"></a><tt class="py-lineno"> 96</tt>  <tt class="py-line">    <tt class="py-keyword">while</tt> <tt class="py-op">(</tt><tt class="py-name">r</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">reduced</tt><tt class="py-op">:</tt> </tt>
  159 <a name="L97"></a><tt class="py-lineno"> 97</tt>  <tt class="py-line">      <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">False</tt> </tt>
  160 <a name="L98"></a><tt class="py-lineno"> 98</tt>  <tt class="py-line">      <tt class="py-name">r</tt> <tt class="py-op">=</tt> <tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-17" class="py-name"><a title="jas.RingElem.reduce" class="py-name" href="#" onclick="return doclink('link-17', 'reduce', 'link-2');">reduce</a></tt><tt class="py-op">(</tt><tt class="py-name">F</tt><tt class="py-op">)</tt> </tt>
  161 <a name="L99"></a><tt class="py-lineno"> 99</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-18" class="py-name" targets="Method jas.RingElem.monomial_divides()=jas.RingElem-class.html#monomial_divides"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-18', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-19" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-19', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-20" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-20', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  162 <a name="L100"></a><tt class="py-lineno">100</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">:</tt> </tt>
  163 <a name="L101"></a><tt class="py-lineno">101</tt>  <tt class="py-line">          <tt class="py-keyword">if</tt> <tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-21" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-21', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-22" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-22', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-23" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-23', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  164 <a name="L102"></a><tt class="py-lineno">102</tt>  <tt class="py-line">            <tt class="py-name">u</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-24" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-24', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-25" class="py-name" targets="Method jas.RingElem.lt()=jas.RingElem-class.html#lt"><a title="jas.RingElem.lt" class="py-name" href="#" onclick="return doclink('link-25', 'lt', 'link-25');">lt</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-26" class="py-name"><a title="jas.RingElem.lt" class="py-name" href="#" onclick="return doclink('link-26', 'lt', 'link-25');">lt</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">coeff</tt><tt class="py-op">=</tt><tt class="py-name">True</tt><tt class="py-op">)</tt> </tt>
  165 <a name="L103"></a><tt class="py-lineno">103</tt>  <tt class="py-line">            <tt class="py-name">sig_ug</tt> <tt class="py-op">=</tt> <tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> </tt>
  166 <a name="L104"></a><tt class="py-lineno">104</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">sig_ug</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">)</tt> <tt class="py-keyword">or</tt> <tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sig_ug</tt><tt class="py-op">.</tt><tt id="link-27" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-27', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">==</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">.</tt><tt id="link-28" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-28', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-op">(</tt><tt class="py-name">sig_ug</tt><tt class="py-op">.</tt><tt id="link-29" class="py-name" targets="Method jas.RingElem.lc()=jas.RingElem-class.html#lc"><a title="jas.RingElem.lc" class="py-name" href="#" onclick="return doclink('link-29', 'lc', 'link-29');">lc</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">.</tt><tt id="link-30" class="py-name"><a title="jas.RingElem.lc" class="py-name" href="#" onclick="return doclink('link-30', 'lc', 'link-29');">lc</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  167 <a name="L105"></a><tt class="py-lineno">105</tt>  <tt class="py-line">              <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">True</tt> </tt>
  168 <a name="L106"></a><tt class="py-lineno">106</tt>  <tt class="py-line">              <tt class="py-name">r</tt> <tt class="py-op">-=</tt> <tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> </tt>
  169 <a name="L107"></a><tt class="py-lineno">107</tt>  <tt class="py-line">              <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">sig_ug</tt><tt class="py-op">.</tt><tt id="link-31" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-31', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">==</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">.</tt><tt id="link-32" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-32', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  170 <a name="L108"></a><tt class="py-lineno">108</tt>  <tt class="py-line">                <tt class="py-name">r_sigma</tt> <tt class="py-op">-=</tt> <tt class="py-name">sig_ug</tt> </tt>
  171 <a name="L109"></a><tt class="py-lineno">109</tt>  <tt class="py-line">    <tt class="py-comment"># ensure that r is monic</tt> </tt>
  172 <a name="L110"></a><tt class="py-lineno">110</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  173 <a name="L111"></a><tt class="py-lineno">111</tt>  <tt class="py-line">      <tt class="py-name">c</tt> <tt class="py-op">=</tt> <tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-33" class="py-name"><a title="jas.RingElem.lc" class="py-name" href="#" onclick="return doclink('link-33', 'lc', 'link-29');">lc</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  174 <a name="L112"></a><tt class="py-lineno">112</tt>  <tt class="py-line">      <tt class="py-name">r</tt> <tt class="py-op">*=</tt> <tt class="py-name">c</tt><tt class="py-op">**</tt><tt class="py-op">(</tt><tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt> </tt>
  175 <a name="L113"></a><tt class="py-lineno">113</tt>  <tt class="py-line">      <tt class="py-name">r_sigma</tt> <tt class="py-op">*=</tt> <tt class="py-name">c</tt><tt class="py-op">**</tt><tt class="py-op">(</tt><tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt> </tt>
  176 <a name="L114"></a><tt class="py-lineno">114</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">,</tt> <tt class="py-name">r</tt> </tt>
  177 </div><a name="L115"></a><tt class="py-lineno">115</tt>  <tt class="py-line">     </tt>
  178 <a name="sigbased_gb.sig_redundant"></a><div id="sigbased_gb.sig_redundant-def"><a name="L116"></a><tt class="py-lineno">116</tt> <a class="py-toggle" href="#" id="sigbased_gb.sig_redundant-toggle" onclick="return toggle('sigbased_gb.sig_redundant');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#sig_redundant">sig_redundant</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  179 </div><div id="sigbased_gb.sig_redundant-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.sig_redundant-expanded"><a name="L117"></a><tt class="py-lineno">117</tt>  <tt class="py-line">    <tt class="py-comment"># test whether (sigma,r) is signature-redundant wrt G</tt> </tt>
  180 <a name="L118"></a><tt class="py-lineno">118</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  181 <a name="L119"></a><tt class="py-lineno">119</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-34" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-34', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-35" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-35', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-36" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-36', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-37" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-37', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-38" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-38', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-39" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-39', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-40" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-40', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">==</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-41" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-41', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  182 <a name="L120"></a><tt class="py-lineno">120</tt>  <tt class="py-line">    <tt class="py-comment">#if any ((g[0] != 0 and R.monomial_divides(g[0].lm(),sigma.lm())) and (g[1] != 0 and R.monomial_divides(g[1].lm(),r.lm())) and not R.monomial_quotient(sigma.lm(),g[0].lm())*g[1].lm()==r.lm() for g in G):</tt> </tt>
  183 <a name="L121"></a><tt class="py-lineno">121</tt>  <tt class="py-line">    <tt class="py-comment">#  print "counterexample at", (sigma, r.lm())</tt> </tt>
  184 <a name="L122"></a><tt class="py-lineno">122</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">any</tt> <tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-42" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-42', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-43" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-43', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-44" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-44', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-45" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-45', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-46" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-46', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-47" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-47', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  185 </div><a name="L123"></a><tt class="py-lineno">123</tt>  <tt class="py-line">   </tt>
  186 <a name="sigbased_gb.incremental_basis"></a><div id="sigbased_gb.incremental_basis-def"><a name="L124"></a><tt class="py-lineno">124</tt> <a class="py-toggle" href="#" id="sigbased_gb.incremental_basis-toggle" onclick="return toggle('sigbased_gb.incremental_basis');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.sigbased_gb-class.html#incremental_basis">incremental_basis</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">g</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  187 </div><div id="sigbased_gb.incremental_basis-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="sigbased_gb.incremental_basis-expanded"><a name="L125"></a><tt class="py-lineno">125</tt>  <tt class="py-line">    <tt class="py-comment"># assuming that F is a Groebner basis of the ideal generated by F,</tt> </tt>
  188 <a name="L126"></a><tt class="py-lineno">126</tt>  <tt class="py-line">    <tt class="py-comment"># compute a Groebner basis of F+[g]</tt> </tt>
  189 <a name="L127"></a><tt class="py-lineno">127</tt>  <tt class="py-line">    <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-48" class="py-name"><a title="jas.RingElem.parent" class="py-name" href="#" onclick="return doclink('link-48', 'parent', 'link-4');">parent</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  190 <a name="L128"></a><tt class="py-lineno">128</tt>  <tt class="py-line">    <tt class="py-comment"># to record a signature, we use only the leading monomial of a minimal representation</tt> </tt>
  191 <a name="L129"></a><tt class="py-lineno">129</tt>  <tt class="py-line">    <tt class="py-comment"># so that elements of F have "signature" 0 and g has "signature" 1</tt> </tt>
  192 <a name="L130"></a><tt class="py-lineno">130</tt>  <tt class="py-line">    <tt class="py-name">G</tt> <tt class="py-op">=</tt> <tt class="py-op">[</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">(</tt><tt class="py-number">0</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">F</tt><tt class="py-op">[</tt><tt class="py-name">i</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">i</tt> <tt class="py-keyword">in</tt> <tt class="py-name">xrange</tt><tt class="py-op">(</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">F</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">]</tt> <tt class="py-op">+</tt> <tt class="py-op">[</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">(</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">)</tt><tt class="py-op">]</tt> </tt>
  193 <a name="L131"></a><tt class="py-lineno">131</tt>  <tt class="py-line">    <tt class="py-comment">#print "JAS G = " + str([ str(gg[0])+","+str(gg[1]) for gg in G]); </tt> </tt>
  194 <a name="L132"></a><tt class="py-lineno">132</tt>  <tt class="py-line">    <tt class="py-comment"># the structure of a pair can vary, except for its first entry,</tt> </tt>
  195 <a name="L133"></a><tt class="py-lineno">133</tt>  <tt class="py-line">    <tt class="py-comment"># which should be the signature</tt> </tt>
  196 <a name="L134"></a><tt class="py-lineno">134</tt>  <tt class="py-line">    <tt class="py-name">P</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">[</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-49" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.new_pair()=basic_sigbased_gb.arris_algorithm-class.html#new_pair,Method basic_sigbased_gb.f5.new_pair()=basic_sigbased_gb.f5-class.html#new_pair,Method basic_sigbased_gb.ggv.new_pair()=basic_sigbased_gb.ggv-class.html#new_pair,Method basic_sigbased_gb.ggv_first_implementation.new_pair()=basic_sigbased_gb.ggv_first_implementation-class.html#new_pair,Method basic_sigbased_gb.sigbased_gb.new_pair()=basic_sigbased_gb.sigbased_gb-class.html#new_pair"><a title="basic_sigbased_gb.arris_algorithm.new_pair
  197 basic_sigbased_gb.f5.new_pair
  198 basic_sigbased_gb.ggv.new_pair
  199 basic_sigbased_gb.ggv_first_implementation.new_pair
  200 basic_sigbased_gb.sigbased_gb.new_pair" class="py-name" href="#" onclick="return doclink('link-49', 'new_pair', 'link-49');">new_pair</a></tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-50" class="py-name" targets="Method basic_sigbased_gb.sigbased_gb.spoly_multipliers()=basic_sigbased_gb.sigbased_gb-class.html#spoly_multipliers"><a title="basic_sigbased_gb.sigbased_gb.spoly_multipliers" class="py-name" href="#" onclick="return doclink('link-50', 'spoly_multipliers', 'link-50');">spoly_multipliers</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">,</tt><tt class="py-name">f</tt><tt class="py-op">)</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">,</tt><tt class="py-name">f</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">f</tt> <tt class="py-keyword">in</tt> <tt class="py-name">F</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
  201 <a name="L135"></a><tt class="py-lineno">135</tt>  <tt class="py-line">    <tt class="py-name">Syz</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-51" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.initialize_Syz()=basic_sigbased_gb.arris_algorithm-class.html#initialize_Syz,Method basic_sigbased_gb.f5.initialize_Syz()=basic_sigbased_gb.f5-class.html#initialize_Syz,Method basic_sigbased_gb.ggv.initialize_Syz()=basic_sigbased_gb.ggv-class.html#initialize_Syz,Method basic_sigbased_gb.sigbased_gb.initialize_Syz()=basic_sigbased_gb.sigbased_gb-class.html#initialize_Syz"><a title="basic_sigbased_gb.arris_algorithm.initialize_Syz
  202 basic_sigbased_gb.f5.initialize_Syz
  203 basic_sigbased_gb.ggv.initialize_Syz
  204 basic_sigbased_gb.sigbased_gb.initialize_Syz" class="py-name" href="#" onclick="return doclink('link-51', 'initialize_Syz', 'link-51');">initialize_Syz</a></tt><tt class="py-op">(</tt><tt class="py-name">F</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  205 <a name="L136"></a><tt class="py-lineno">136</tt>  <tt class="py-line">    <tt class="py-comment"># Done will track new polynomials computed by the algorithm</tt> </tt>
  206 <a name="L137"></a><tt class="py-lineno">137</tt>  <tt class="py-line">    <tt class="py-name">Done</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  207 <a name="L138"></a><tt class="py-lineno">138</tt>  <tt class="py-line">    <tt class="py-keyword">while</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  208 <a name="L139"></a><tt class="py-lineno">139</tt>  <tt class="py-line">      <tt class="py-name">P</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-52" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.prune_P()=basic_sigbased_gb.arris_algorithm-class.html#prune_P,Method basic_sigbased_gb.f5.prune_P()=basic_sigbased_gb.f5-class.html#prune_P,Method basic_sigbased_gb.ggv.prune_P()=basic_sigbased_gb.ggv-class.html#prune_P,Method basic_sigbased_gb.sigbased_gb.prune_P()=basic_sigbased_gb.sigbased_gb-class.html#prune_P"><a title="basic_sigbased_gb.arris_algorithm.prune_P
  209 basic_sigbased_gb.f5.prune_P
  210 basic_sigbased_gb.ggv.prune_P
  211 basic_sigbased_gb.sigbased_gb.prune_P" class="py-name" href="#" onclick="return doclink('link-52', 'prune_P', 'link-52');">prune_P</a></tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">,</tt><tt class="py-name">Syz</tt><tt class="py-op">)</tt> </tt>
  212 <a name="L140"></a><tt class="py-lineno">140</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  213 <a name="L141"></a><tt class="py-lineno">141</tt>  <tt class="py-line">        <tt class="py-name">S</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-53" class="py-name" targets="Method basic_sigbased_gb.sigbased_gb.subset()=basic_sigbased_gb.sigbased_gb-class.html#subset"><a title="basic_sigbased_gb.sigbased_gb.subset" class="py-name" href="#" onclick="return doclink('link-53', 'subset', 'link-53');">subset</a></tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">,</tt><tt class="py-keyword">lambda</tt> <tt class="py-name">x</tt><tt class="py-op">:</tt> <tt class="py-name">x</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-54" class="py-name"><a title="jas.RingElem.degree" class="py-name" href="#" onclick="return doclink('link-54', 'degree', 'link-1');">degree</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">==</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-55" class="py-name" targets="Method basic_sigbased_gb.sigbased_gb.min_sig_degree()=basic_sigbased_gb.sigbased_gb-class.html#min_sig_degree"><a title="basic_sigbased_gb.sigbased_gb.min_sig_degree" class="py-name" href="#" onclick="return doclink('link-55', 'min_sig_degree', 'link-55');">min_sig_degree</a></tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  214 <a name="L142"></a><tt class="py-lineno">142</tt>  <tt class="py-line">        <tt class="py-keyword">print</tt> <tt class="py-string">"treating"</tt><tt class="py-op">,</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">S</tt><tt class="py-op">)</tt><tt class="py-op">,</tt> <tt class="py-string">"signatures of degree"</tt><tt class="py-op">,</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-56" class="py-name"><a title="basic_sigbased_gb.sigbased_gb.min_sig_degree" class="py-name" href="#" onclick="return doclink('link-56', 'min_sig_degree', 'link-55');">min_sig_degree</a></tt><tt class="py-op">(</tt><tt class="py-name">P</tt><tt class="py-op">)</tt> </tt>
  215 <a name="L143"></a><tt class="py-lineno">143</tt>  <tt class="py-line">        <tt class="py-name">P</tt><tt class="py-op">.</tt><tt class="py-name">difference_update</tt><tt class="py-op">(</tt><tt class="py-name">S</tt><tt class="py-op">)</tt> </tt>
  216 <a name="L144"></a><tt class="py-lineno">144</tt>  <tt class="py-line">        <tt class="py-keyword">while</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">S</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  217 <a name="L145"></a><tt class="py-lineno">145</tt>  <tt class="py-line">          <tt class="py-name">S</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-57" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.prune_S()=basic_sigbased_gb.arris_algorithm-class.html#prune_S,Method basic_sigbased_gb.f5.prune_S()=basic_sigbased_gb.f5-class.html#prune_S,Method basic_sigbased_gb.ggv.prune_S()=basic_sigbased_gb.ggv-class.html#prune_S,Method basic_sigbased_gb.ggv_first_implementation.prune_S()=basic_sigbased_gb.ggv_first_implementation-class.html#prune_S,Method basic_sigbased_gb.min_size_mons.prune_S()=basic_sigbased_gb.min_size_mons-class.html#prune_S,Method basic_sigbased_gb.sigbased_gb.prune_S()=basic_sigbased_gb.sigbased_gb-class.html#prune_S"><a title="basic_sigbased_gb.arris_algorithm.prune_S
  218 basic_sigbased_gb.f5.prune_S
  219 basic_sigbased_gb.ggv.prune_S
  220 basic_sigbased_gb.ggv_first_implementation.prune_S
  221 basic_sigbased_gb.min_size_mons.prune_S
  222 basic_sigbased_gb.sigbased_gb.prune_S" class="py-name" href="#" onclick="return doclink('link-57', 'prune_S', 'link-57');">prune_S</a></tt><tt class="py-op">(</tt><tt class="py-name">S</tt><tt class="py-op">,</tt><tt class="py-name">Syz</tt><tt class="py-op">,</tt><tt class="py-name">Done</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  223 <a name="L146"></a><tt class="py-lineno">146</tt>  <tt class="py-line">          <tt class="py-keyword">if</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">S</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  224 <a name="L147"></a><tt class="py-lineno">147</tt>  <tt class="py-line">            <tt class="py-comment"># sort by signature</tt> </tt>
  225 <a name="L148"></a><tt class="py-lineno">148</tt>  <tt class="py-line">            <tt class="py-name">S</tt><tt class="py-op">.</tt><tt class="py-name">sort</tt><tt class="py-op">(</tt><tt class="py-name">key</tt><tt class="py-op">=</tt><tt class="py-keyword">lambda</tt> <tt class="py-name">x</tt><tt class="py-op">:</tt><tt class="py-name">x</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">s</tt> <tt class="py-op">=</tt> <tt class="py-name">S</tt><tt class="py-op">.</tt><tt class="py-name">pop</tt><tt class="py-op">(</tt><tt class="py-number">0</tt><tt class="py-op">)</tt> </tt>
  226 <a name="L149"></a><tt class="py-lineno">149</tt>  <tt class="py-line">            <tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-58" class="py-name" targets="Method basic_sigbased_gb.coeff_free_sigbased_gb.sigsafe_reduction()=basic_sigbased_gb.coeff_free_sigbased_gb-class.html#sigsafe_reduction,Method basic_sigbased_gb.sigbased_gb.sigsafe_reduction()=basic_sigbased_gb.sigbased_gb-class.html#sigsafe_reduction"><a title="basic_sigbased_gb.coeff_free_sigbased_gb.sigsafe_reduction
  227 basic_sigbased_gb.sigbased_gb.sigsafe_reduction" class="py-name" href="#" onclick="return doclink('link-58', 'sigsafe_reduction', 'link-58');">sigsafe_reduction</a></tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-59" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.spoly()=basic_sigbased_gb.arris_algorithm-class.html#spoly,Method basic_sigbased_gb.f5.spoly()=basic_sigbased_gb.f5-class.html#spoly,Method basic_sigbased_gb.ggv.spoly()=basic_sigbased_gb.ggv-class.html#spoly,Method basic_sigbased_gb.ggv_first_implementation.spoly()=basic_sigbased_gb.ggv_first_implementation-class.html#spoly,Method basic_sigbased_gb.sigbased_gb.spoly()=basic_sigbased_gb.sigbased_gb-class.html#spoly"><a title="basic_sigbased_gb.arris_algorithm.spoly
  228 basic_sigbased_gb.f5.spoly
  229 basic_sigbased_gb.ggv.spoly
  230 basic_sigbased_gb.ggv_first_implementation.spoly
  231 basic_sigbased_gb.sigbased_gb.spoly" class="py-name" href="#" onclick="return doclink('link-59', 'spoly', 'link-59');">spoly</a></tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">,</tt><tt class="py-name">F</tt><tt class="py-op">,</tt><tt class="py-name">Syz</tt><tt class="py-op">)</tt> </tt>
  232 <a name="L150"></a><tt class="py-lineno">150</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">r</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-op">(</tt><tt class="py-keyword">not</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-60" class="py-name" targets="Method basic_sigbased_gb.sigbased_gb.sig_redundant()=basic_sigbased_gb.sigbased_gb-class.html#sig_redundant"><a title="basic_sigbased_gb.sigbased_gb.sig_redundant" class="py-name" href="#" onclick="return doclink('link-60', 'sig_redundant', 'link-60');">sig_redundant</a></tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt>  </tt>
  233 <a name="L151"></a><tt class="py-lineno">151</tt>  <tt class="py-line">              <tt class="py-comment">#print "new polynomial", str(sigma), ", ", str(r)</tt> </tt>
  234 <a name="L152"></a><tt class="py-lineno">152</tt>  <tt class="py-line">              <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">:</tt> </tt>
  235 <a name="L153"></a><tt class="py-lineno">153</tt>  <tt class="py-line">                <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">g</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  236 <a name="L154"></a><tt class="py-lineno">154</tt>  <tt class="py-line">                  <tt class="py-name">rmul</tt><tt class="py-op">,</tt><tt class="py-name">gmul</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-61" class="py-name"><a title="basic_sigbased_gb.sigbased_gb.spoly_multipliers" class="py-name" href="#" onclick="return doclink('link-61', 'spoly_multipliers', 'link-50');">spoly_multipliers</a></tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">)</tt> </tt>
  237 <a name="L155"></a><tt class="py-lineno">155</tt>  <tt class="py-line">                  <tt class="py-keyword">if</tt> <tt class="py-name">rmul</tt><tt class="py-op">*</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-62" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-62', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">!=</tt> <tt class="py-name">gmul</tt><tt class="py-op">*</tt><tt class="py-name">tau</tt><tt class="py-op">.</tt><tt id="link-63" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-63', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  238 <a name="L156"></a><tt class="py-lineno">156</tt>  <tt class="py-line">                    <tt class="py-keyword">if</tt> <tt class="py-name">rmul</tt><tt class="py-op">*</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-64" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-64', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">&gt;</tt> <tt class="py-name">gmul</tt><tt class="py-op">*</tt><tt class="py-name">tau</tt><tt class="py-op">.</tt><tt id="link-65" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-65', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  239 <a name="L157"></a><tt class="py-lineno">157</tt>  <tt class="py-line">                      <tt class="py-name">p</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-66" class="py-name"><a title="basic_sigbased_gb.arris_algorithm.new_pair
  240 basic_sigbased_gb.f5.new_pair
  241 basic_sigbased_gb.ggv.new_pair
  242 basic_sigbased_gb.ggv_first_implementation.new_pair
  243 basic_sigbased_gb.sigbased_gb.new_pair" class="py-name" href="#" onclick="return doclink('link-66', 'new_pair', 'link-49');">new_pair</a></tt><tt class="py-op">(</tt><tt class="py-name">rmul</tt><tt class="py-op">*</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  244 <a name="L158"></a><tt class="py-lineno">158</tt>  <tt class="py-line">                    <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
  245 <a name="L159"></a><tt class="py-lineno">159</tt>  <tt class="py-line">                      <tt class="py-name">p</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-67" class="py-name"><a title="basic_sigbased_gb.arris_algorithm.new_pair
  246 basic_sigbased_gb.f5.new_pair
  247 basic_sigbased_gb.ggv.new_pair
  248 basic_sigbased_gb.ggv_first_implementation.new_pair
  249 basic_sigbased_gb.sigbased_gb.new_pair" class="py-name" href="#" onclick="return doclink('link-67', 'new_pair', 'link-49');">new_pair</a></tt><tt class="py-op">(</tt><tt class="py-name">gmul</tt><tt class="py-op">*</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  250 <a name="L160"></a><tt class="py-lineno">160</tt>  <tt class="py-line">                    <tt class="py-keyword">if</tt> <tt class="py-name">p</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-68" class="py-name"><a title="jas.RingElem.degree" class="py-name" href="#" onclick="return doclink('link-68', 'degree', 'link-1');">degree</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">==</tt> <tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-69" class="py-name"><a title="jas.RingElem.degree" class="py-name" href="#" onclick="return doclink('link-69', 'degree', 'link-1');">degree</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  251 <a name="L161"></a><tt class="py-lineno">161</tt>  <tt class="py-line">                      <tt class="py-name">S</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">)</tt> </tt>
  252 <a name="L162"></a><tt class="py-lineno">162</tt>  <tt class="py-line">                    <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
  253 <a name="L163"></a><tt class="py-lineno">163</tt>  <tt class="py-line">                      <tt class="py-name">P</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">)</tt> </tt>
  254 <a name="L164"></a><tt class="py-lineno">164</tt>  <tt class="py-line">              <tt class="py-name">G</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  255 <a name="L165"></a><tt class="py-lineno">165</tt>  <tt class="py-line">              <tt class="py-name">Done</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  256 <a name="L166"></a><tt class="py-lineno">166</tt>  <tt class="py-line">            <tt class="py-keyword">elif</tt> <tt class="py-name">r</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  257 <a name="L167"></a><tt class="py-lineno">167</tt>  <tt class="py-line">              <tt class="py-comment">#print "zero reduction at", (sigma,r.lm()) </tt> </tt>
  258 <a name="L168"></a><tt class="py-lineno">168</tt>  <tt class="py-line">              <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-70" class="py-name" targets="Method basic_sigbased_gb.arris_algorithm.update_Syz()=basic_sigbased_gb.arris_algorithm-class.html#update_Syz,Method basic_sigbased_gb.f5.update_Syz()=basic_sigbased_gb.f5-class.html#update_Syz,Method basic_sigbased_gb.f5z.update_Syz()=basic_sigbased_gb.f5z-class.html#update_Syz,Method basic_sigbased_gb.ggv.update_Syz()=basic_sigbased_gb.ggv-class.html#update_Syz,Method basic_sigbased_gb.sigbased_gb.update_Syz()=basic_sigbased_gb.sigbased_gb-class.html#update_Syz"><a title="basic_sigbased_gb.arris_algorithm.update_Syz
  259 basic_sigbased_gb.f5.update_Syz
  260 basic_sigbased_gb.f5z.update_Syz
  261 basic_sigbased_gb.ggv.update_Syz
  262 basic_sigbased_gb.sigbased_gb.update_Syz" class="py-name" href="#" onclick="return doclink('link-70', 'update_Syz', 'link-70');">update_Syz</a></tt><tt class="py-op">(</tt><tt class="py-name">Syz</tt><tt class="py-op">,</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">)</tt> </tt>
  263 <a name="L169"></a><tt class="py-lineno">169</tt>  <tt class="py-line">              <tt class="py-name">Done</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  264 <a name="L170"></a><tt class="py-lineno">170</tt>  <tt class="py-line">            <tt class="py-comment">#else:</tt> </tt>
  265 <a name="L171"></a><tt class="py-lineno">171</tt>  <tt class="py-line">              <tt class="py-comment">#print "sig-redundant at", sigma</tt> </tt>
  266 <a name="L172"></a><tt class="py-lineno">172</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-71" class="py-name"><a title="basic_sigbased_gb.sigbased_gb.subset" class="py-name" href="#" onclick="return doclink('link-71', 'subset', 'link-53');">subset</a></tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">,</tt><tt class="py-keyword">lambda</tt> <tt class="py-name">x</tt><tt class="py-op">:</tt> <tt class="py-name">x</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  267 </div></div><a name="L173"></a><tt class="py-lineno">173</tt>  <tt class="py-line"> </tt>
  268 <a name="ggv"></a><div id="ggv-def"><a name="L174"></a><tt class="py-lineno">174</tt> <a class="py-toggle" href="#" id="ggv-toggle" onclick="return toggle('ggv');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html">ggv</a><tt class="py-op">(</tt><tt class="py-base-class">sigbased_gb</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  269 </div><div id="ggv-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="ggv-expanded"><a name="L175"></a><tt class="py-lineno">175</tt>  <tt class="py-line">  <tt class="py-comment"># the plugin implementation of ggv</tt> </tt>
  270 <a name="L176"></a><tt class="py-lineno">176</tt>  <tt class="py-line">   </tt>
  271 <a name="ggv.new_pair"></a><div id="ggv.new_pair-def"><a name="L177"></a><tt class="py-lineno">177</tt> <a class="py-toggle" href="#" id="ggv.new_pair-toggle" onclick="return toggle('ggv.new_pair');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#new_pair">new_pair</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sig</tt><tt class="py-op">,</tt><tt class="py-param">p</tt><tt class="py-op">,</tt><tt class="py-param">q</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  272 </div><div id="ggv.new_pair-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.new_pair-expanded"><a name="L178"></a><tt class="py-lineno">178</tt>  <tt class="py-line">    <tt class="py-comment"># creates a new critical pair from p and q, with signature sig</tt> </tt>
  273 <a name="L179"></a><tt class="py-lineno">179</tt>  <tt class="py-line">    <tt class="py-comment"># it needs G for the sake of F5; see derived class below</tt> </tt>
  274 <a name="L180"></a><tt class="py-lineno">180</tt>  <tt class="py-line">    <tt class="py-name">i</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">k</tt> <tt class="py-op">=</tt> <tt class="py-number">0</tt> </tt>
  275 <a name="L181"></a><tt class="py-lineno">181</tt>  <tt class="py-line">    <tt class="py-name">up</tt><tt class="py-op">,</tt><tt class="py-name">uq</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-72" class="py-name"><a title="basic_sigbased_gb.sigbased_gb.spoly_multipliers" class="py-name" href="#" onclick="return doclink('link-72', 'spoly_multipliers', 'link-50');">spoly_multipliers</a></tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">,</tt><tt class="py-name">q</tt><tt class="py-op">)</tt> </tt>
  276 <a name="L182"></a><tt class="py-lineno">182</tt>  <tt class="py-line">    <tt class="py-keyword">while</tt> <tt class="py-op">(</tt><tt class="py-name">i</tt><tt class="py-op">&lt;</tt><tt class="py-number">0</tt> <tt class="py-keyword">or</tt> <tt class="py-name">j</tt><tt class="py-op">&lt;</tt><tt class="py-number">0</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">k</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  277 <a name="L183"></a><tt class="py-lineno">183</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">p</tt> <tt class="py-op">==</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">k</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">:</tt> </tt>
  278 <a name="L184"></a><tt class="py-lineno">184</tt>  <tt class="py-line">        <tt class="py-name">i</tt> <tt class="py-op">=</tt> <tt class="py-name">k</tt> </tt>
  279 <a name="L185"></a><tt class="py-lineno">185</tt>  <tt class="py-line">      <tt class="py-keyword">elif</tt> <tt class="py-name">q</tt> <tt class="py-op">==</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">k</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">:</tt> </tt>
  280 <a name="L186"></a><tt class="py-lineno">186</tt>  <tt class="py-line">        <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-name">k</tt> </tt>
  281 <a name="L187"></a><tt class="py-lineno">187</tt>  <tt class="py-line">      <tt class="py-name">k</tt> <tt class="py-op">+=</tt> <tt class="py-number">1</tt><tt class="py-op">;</tt> </tt>
  282 <a name="L188"></a><tt class="py-lineno">188</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">i</tt> <tt class="py-op">==</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  283 <a name="L189"></a><tt class="py-lineno">189</tt>  <tt class="py-line">      <tt class="py-name">i</tt><tt class="py-op">=</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  284 <a name="L190"></a><tt class="py-lineno">190</tt>  <tt class="py-line">    <tt class="py-keyword">elif</tt> <tt class="py-op">(</tt><tt class="py-name">j</tt> <tt class="py-op">==</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  285 <a name="L191"></a><tt class="py-lineno">191</tt>  <tt class="py-line">      <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  286 <a name="L192"></a><tt class="py-lineno">192</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">i</tt><tt class="py-op">,</tt><tt class="py-name">j</tt><tt class="py-op">)</tt> </tt>
  287 </div><a name="L193"></a><tt class="py-lineno">193</tt>  <tt class="py-line">   </tt>
  288 <a name="ggv.initialize_Syz"></a><div id="ggv.initialize_Syz-def"><a name="L194"></a><tt class="py-lineno">194</tt> <a class="py-toggle" href="#" id="ggv.initialize_Syz-toggle" onclick="return toggle('ggv.initialize_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#initialize_Syz">initialize_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  289 </div><div id="ggv.initialize_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.initialize_Syz-expanded"><a name="L195"></a><tt class="py-lineno">195</tt>  <tt class="py-line">    <tt class="py-comment"># recognize trivial syzygies</tt> </tt>
  290 <a name="L196"></a><tt class="py-lineno">196</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">[</tt><tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-73" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-73', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">f</tt> <tt class="py-keyword">in</tt> <tt class="py-name">F</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
  291 </div><a name="L197"></a><tt class="py-lineno">197</tt>  <tt class="py-line">     </tt>
  292 <a name="ggv.spoly"></a><div id="ggv.spoly-def"><a name="L198"></a><tt class="py-lineno">198</tt> <a class="py-toggle" href="#" id="ggv.spoly-toggle" onclick="return toggle('ggv.spoly');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#spoly">spoly</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  293 </div><div id="ggv.spoly-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.spoly-expanded"><a name="L199"></a><tt class="py-lineno">199</tt>  <tt class="py-line">    <tt class="py-comment"># ggv only computes part of an S-polynomial</tt> </tt>
  294 <a name="L200"></a><tt class="py-lineno">200</tt>  <tt class="py-line">    <tt class="py-comment"># (as if it were computing a row of the Macaulay matrix</tt> </tt>
  295 <a name="L201"></a><tt class="py-lineno">201</tt>  <tt class="py-line">    <tt class="py-comment"># and not subsequently triangularizing)</tt> </tt>
  296 <a name="L202"></a><tt class="py-lineno">202</tt>  <tt class="py-line">    <tt class="py-name">f</tt> <tt class="py-op">=</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">;</tt> <tt class="py-name">g</tt> <tt class="py-op">=</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">2</tt><tt class="py-op">]</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> </tt>
  297 <a name="L203"></a><tt class="py-lineno">203</tt>  <tt class="py-line">    <tt class="py-name">tf</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-74" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-74', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">tg</tt> <tt class="py-op">=</tt> <tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-75" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-75', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  298 <a name="L204"></a><tt class="py-lineno">204</tt>  <tt class="py-line">    <tt class="py-name">tfg</tt> <tt class="py-op">=</tt> <tt class="py-name">tf</tt><tt class="py-op">.</tt><tt class="py-name">lcm</tt><tt class="py-op">(</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt> </tt>
  299 <a name="L205"></a><tt class="py-lineno">205</tt>  <tt class="py-line">    <tt class="py-name">uf</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-76" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-76', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tf</tt><tt class="py-op">)</tt> </tt>
  300 <a name="L206"></a><tt class="py-lineno">206</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">uf</tt><tt class="py-op">*</tt><tt class="py-name">f</tt> </tt>
  301 </div><a name="L207"></a><tt class="py-lineno">207</tt>  <tt class="py-line">   </tt>
  302 <a name="ggv.prune_P"></a><div id="ggv.prune_P-def"><a name="L208"></a><tt class="py-lineno">208</tt> <a class="py-toggle" href="#" id="ggv.prune_P-toggle" onclick="return toggle('ggv.prune_P');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#prune_P">prune_P</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">P</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  303 </div><div id="ggv.prune_P-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.prune_P-expanded"><a name="L209"></a><tt class="py-lineno">209</tt>  <tt class="py-line">    <tt class="py-comment"># remove any pair whose signature is divisible by an element of Syz</tt> </tt>
  304 <a name="L210"></a><tt class="py-lineno">210</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  305 <a name="L211"></a><tt class="py-lineno">211</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  306 <a name="L212"></a><tt class="py-lineno">212</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">p</tt> <tt class="py-keyword">in</tt> <tt class="py-name">P</tt><tt class="py-op">:</tt> </tt>
  307 <a name="L213"></a><tt class="py-lineno">213</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-77" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-77', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">p</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  308 <a name="L214"></a><tt class="py-lineno">214</tt>  <tt class="py-line">        <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">)</tt> </tt>
  309 <a name="L215"></a><tt class="py-lineno">215</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  310 </div><a name="L216"></a><tt class="py-lineno">216</tt>  <tt class="py-line">   </tt>
  311 <a name="ggv.prune_S"></a><div id="ggv.prune_S-def"><a name="L217"></a><tt class="py-lineno">217</tt> <a class="py-toggle" href="#" id="ggv.prune_S-toggle" onclick="return toggle('ggv.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  312 </div><div id="ggv.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.prune_S-expanded"><a name="L218"></a><tt class="py-lineno">218</tt>  <tt class="py-line">    <tt class="py-comment"># watch out for new syzygies discovered, and allow only one polynomial</tt> </tt>
  313 <a name="L219"></a><tt class="py-lineno">219</tt>  <tt class="py-line">    <tt class="py-comment"># per signature</tt> </tt>
  314 <a name="L220"></a><tt class="py-lineno">220</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  315 <a name="L221"></a><tt class="py-lineno">221</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  316 <a name="L222"></a><tt class="py-lineno">222</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">s</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  317 <a name="L223"></a><tt class="py-lineno">223</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-78" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-78', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  318 <a name="L224"></a><tt class="py-lineno">224</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-79" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-79', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">==</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-80" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-80', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">&lt;</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-keyword">for</tt> <tt class="py-name">sig</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  319 <a name="L225"></a><tt class="py-lineno">225</tt>  <tt class="py-line">          <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-81" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-81', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">==</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-82" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-82', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">sig</tt> <tt class="py-keyword">in</tt> <tt class="py-name">result</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  320 <a name="L226"></a><tt class="py-lineno">226</tt>  <tt class="py-line">            <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">)</tt> </tt>
  321 <a name="L227"></a><tt class="py-lineno">227</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  322 </div><a name="L228"></a><tt class="py-lineno">228</tt>  <tt class="py-line">   </tt>
  323 <a name="ggv.update_Syz"></a><div id="ggv.update_Syz-def"><a name="L229"></a><tt class="py-lineno">229</tt> <a class="py-toggle" href="#" id="ggv.update_Syz-toggle" onclick="return toggle('ggv.update_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv-class.html#update_Syz">update_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  324 </div><div id="ggv.update_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv.update_Syz-expanded"><a name="L230"></a><tt class="py-lineno">230</tt>  <tt class="py-line">    <tt class="py-comment"># add non-trivial syzygies to the basis</tt> </tt>
  325 <a name="L231"></a><tt class="py-lineno">231</tt>  <tt class="py-line">    <tt class="py-comment"># polynomials that reduce to zero indicate non-trivial syzygies</tt> </tt>
  326 <a name="L232"></a><tt class="py-lineno">232</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  327 <a name="L233"></a><tt class="py-lineno">233</tt>  <tt class="py-line">      <tt class="py-name">Syz</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-83" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-83', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  328 <a name="L234"></a><tt class="py-lineno">234</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">Syz</tt> </tt>
  329 </div></div><a name="L235"></a><tt class="py-lineno">235</tt>  <tt class="py-line"> </tt>
  330 <a name="ggv_first_implementation"></a><div id="ggv_first_implementation-def"><a name="L236"></a><tt class="py-lineno">236</tt> <a class="py-toggle" href="#" id="ggv_first_implementation-toggle" onclick="return toggle('ggv_first_implementation');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv_first_implementation-class.html">ggv_first_implementation</a><tt class="py-op">(</tt><tt class="py-base-class">ggv</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  331 </div><div id="ggv_first_implementation-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="ggv_first_implementation-expanded"><a name="L237"></a><tt class="py-lineno">237</tt>  <tt class="py-line">   </tt>
  332 <a name="ggv_first_implementation.new_pair"></a><div id="ggv_first_implementation.new_pair-def"><a name="L238"></a><tt class="py-lineno">238</tt> <a class="py-toggle" href="#" id="ggv_first_implementation.new_pair-toggle" onclick="return toggle('ggv_first_implementation.new_pair');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv_first_implementation-class.html#new_pair">new_pair</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sig</tt><tt class="py-op">,</tt><tt class="py-param">p</tt><tt class="py-op">,</tt><tt class="py-param">q</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  333 </div><div id="ggv_first_implementation.new_pair-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv_first_implementation.new_pair-expanded"><a name="L239"></a><tt class="py-lineno">239</tt>  <tt class="py-line">    <tt class="py-comment"># creates a new critical pair from p and q, with signature sig</tt> </tt>
  334 <a name="L240"></a><tt class="py-lineno">240</tt>  <tt class="py-line">    <tt class="py-comment"># it needs G for the sake of F5; see derived class below</tt> </tt>
  335 <a name="L241"></a><tt class="py-lineno">241</tt>  <tt class="py-line">    <tt class="py-name">i</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">k</tt> <tt class="py-op">=</tt> <tt class="py-number">0</tt> </tt>
  336 <a name="L242"></a><tt class="py-lineno">242</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">p</tt><tt class="py-op">,</tt><tt class="py-name">q</tt><tt class="py-op">)</tt> </tt>
  337 </div><a name="L243"></a><tt class="py-lineno">243</tt>  <tt class="py-line">   </tt>
  338 <a name="ggv_first_implementation.spoly"></a><div id="ggv_first_implementation.spoly-def"><a name="L244"></a><tt class="py-lineno">244</tt> <a class="py-toggle" href="#" id="ggv_first_implementation.spoly-toggle" onclick="return toggle('ggv_first_implementation.spoly');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv_first_implementation-class.html#spoly">spoly</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  339 </div><div id="ggv_first_implementation.spoly-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv_first_implementation.spoly-expanded"><a name="L245"></a><tt class="py-lineno">245</tt>  <tt class="py-line">    <tt class="py-comment"># ggv only computes part of an S-polynomial</tt> </tt>
  340 <a name="L246"></a><tt class="py-lineno">246</tt>  <tt class="py-line">    <tt class="py-comment"># (as if it were computing a row of the Macaulay matrix</tt> </tt>
  341 <a name="L247"></a><tt class="py-lineno">247</tt>  <tt class="py-line">    <tt class="py-comment"># and not subsequently triangularizing)</tt> </tt>
  342 <a name="L248"></a><tt class="py-lineno">248</tt>  <tt class="py-line">    <tt class="py-comment"># -- at least, that's how I read "(t_i,m+1)" on p. 6 of that paper</tt> </tt>
  343 <a name="L249"></a><tt class="py-lineno">249</tt>  <tt class="py-line">    <tt class="py-name">f</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">;</tt> <tt class="py-name">g</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">2</tt><tt class="py-op">]</tt> </tt>
  344 <a name="L250"></a><tt class="py-lineno">250</tt>  <tt class="py-line">    <tt class="py-name">tf</tt> <tt class="py-op">=</tt> <tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-84" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-84', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">tg</tt> <tt class="py-op">=</tt> <tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-85" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-85', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  345 <a name="L251"></a><tt class="py-lineno">251</tt>  <tt class="py-line">    <tt class="py-name">tfg</tt> <tt class="py-op">=</tt> <tt class="py-name">tf</tt><tt class="py-op">.</tt><tt class="py-name">lcm</tt><tt class="py-op">(</tt><tt class="py-name">tg</tt><tt class="py-op">)</tt> </tt>
  346 <a name="L252"></a><tt class="py-lineno">252</tt>  <tt class="py-line">    <tt class="py-name">uf</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-86" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-86', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tfg</tt><tt class="py-op">,</tt><tt class="py-name">tf</tt><tt class="py-op">)</tt> </tt>
  347 <a name="L253"></a><tt class="py-lineno">253</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">uf</tt><tt class="py-op">*</tt><tt class="py-name">f</tt> </tt>
  348 </div><a name="L254"></a><tt class="py-lineno">254</tt>  <tt class="py-line"> </tt>
  349 <a name="ggv_first_implementation.prune_S"></a><div id="ggv_first_implementation.prune_S-def"><a name="L255"></a><tt class="py-lineno">255</tt> <a class="py-toggle" href="#" id="ggv_first_implementation.prune_S-toggle" onclick="return toggle('ggv_first_implementation.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.ggv_first_implementation-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  350 </div><div id="ggv_first_implementation.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="ggv_first_implementation.prune_S-expanded"><a name="L256"></a><tt class="py-lineno">256</tt>  <tt class="py-line">    <tt class="py-comment"># watch out for new syzygies discovered, and allow only one polynomial</tt> </tt>
  351 <a name="L257"></a><tt class="py-lineno">257</tt>  <tt class="py-line">    <tt class="py-comment"># per signature</tt> </tt>
  352 <a name="L258"></a><tt class="py-lineno">258</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  353 <a name="L259"></a><tt class="py-lineno">259</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  354 <a name="L260"></a><tt class="py-lineno">260</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">s</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  355 <a name="L261"></a><tt class="py-lineno">261</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-87" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-87', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  356 <a name="L262"></a><tt class="py-lineno">262</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-88" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-88', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">==</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-89" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-89', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">sig</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Done</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  357 <a name="L263"></a><tt class="py-lineno">263</tt>  <tt class="py-line">          <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">)</tt> </tt>
  358 <a name="L264"></a><tt class="py-lineno">264</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  359 </div></div><a name="L265"></a><tt class="py-lineno">265</tt>  <tt class="py-line">   </tt>
  360 <a name="coeff_free_sigbased_gb"></a><div id="coeff_free_sigbased_gb-def"><a name="L266"></a><tt class="py-lineno">266</tt> <a class="py-toggle" href="#" id="coeff_free_sigbased_gb-toggle" onclick="return toggle('coeff_free_sigbased_gb');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.coeff_free_sigbased_gb-class.html">coeff_free_sigbased_gb</a><tt class="py-op">(</tt><tt class="py-base-class">sigbased_gb</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  361 </div><div id="coeff_free_sigbased_gb-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="coeff_free_sigbased_gb-expanded"><a name="L267"></a><tt class="py-lineno">267</tt>  <tt class="py-line">  <tt class="py-comment"># child class of sigbased_gb that implements semi-complete reduction</tt> </tt>
  362 <a name="L268"></a><tt class="py-lineno">268</tt>  <tt class="py-line">   </tt>
  363 <a name="coeff_free_sigbased_gb.sigsafe_reduction"></a><div id="coeff_free_sigbased_gb.sigsafe_reduction-def"><a name="L269"></a><tt class="py-lineno">269</tt> <a class="py-toggle" href="#" id="coeff_free_sigbased_gb.sigsafe_reduction-toggle" onclick="return toggle('coeff_free_sigbased_gb.sigsafe_reduction');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.coeff_free_sigbased_gb-class.html#sigsafe_reduction">sigsafe_reduction</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  364 </div><div id="coeff_free_sigbased_gb.sigsafe_reduction-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="coeff_free_sigbased_gb.sigsafe_reduction-expanded"><a name="L270"></a><tt class="py-lineno">270</tt>  <tt class="py-line">    <tt class="py-comment"># see sigbased_gb.sigsafe_reduction</tt> </tt>
  365 <a name="L271"></a><tt class="py-lineno">271</tt>  <tt class="py-line">    <tt class="py-name">r</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt> </tt>
  366 <a name="L272"></a><tt class="py-lineno">272</tt>  <tt class="py-line">    <tt class="py-name">r_sigma</tt> <tt class="py-op">=</tt> <tt class="py-name">sigma</tt> </tt>
  367 <a name="L273"></a><tt class="py-lineno">273</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt> </tt>
  368 <a name="L274"></a><tt class="py-lineno">274</tt>  <tt class="py-line">    <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">True</tt> </tt>
  369 <a name="L275"></a><tt class="py-lineno">275</tt>  <tt class="py-line">    <tt class="py-keyword">while</tt> <tt class="py-op">(</tt><tt class="py-name">r</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">reduced</tt><tt class="py-op">:</tt> </tt>
  370 <a name="L276"></a><tt class="py-lineno">276</tt>  <tt class="py-line">      <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">False</tt> </tt>
  371 <a name="L277"></a><tt class="py-lineno">277</tt>  <tt class="py-line">      <tt class="py-name">r</tt> <tt class="py-op">=</tt> <tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-90" class="py-name"><a title="jas.RingElem.reduce" class="py-name" href="#" onclick="return doclink('link-90', 'reduce', 'link-2');">reduce</a></tt><tt class="py-op">(</tt><tt class="py-name">F</tt><tt class="py-op">)</tt> </tt>
  372 <a name="L278"></a><tt class="py-lineno">278</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt> <tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-91" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-91', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-92" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-92', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-93" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-93', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt> <tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  373 <a name="L279"></a><tt class="py-lineno">279</tt>  <tt class="py-line">        <tt class="py-keyword">for</tt> <tt class="py-name">g</tt> <tt class="py-keyword">in</tt> <tt class="py-name">G</tt><tt class="py-op">:</tt> </tt>
  374 <a name="L280"></a><tt class="py-lineno">280</tt>  <tt class="py-line">          <tt class="py-keyword">if</tt> <tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt> <tt class="py-keyword">and</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-94" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-94', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-95" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-95', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-96" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-96', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  375 <a name="L281"></a><tt class="py-lineno">281</tt>  <tt class="py-line">            <tt class="py-name">u</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-97" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-97', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-98" class="py-name"><a title="jas.RingElem.lt" class="py-name" href="#" onclick="return doclink('link-98', 'lt', 'link-25');">lt</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-99" class="py-name"><a title="jas.RingElem.lt" class="py-name" href="#" onclick="return doclink('link-99', 'lt', 'link-25');">lt</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">,</tt><tt class="py-name">coeff</tt><tt class="py-op">=</tt><tt class="py-name">True</tt><tt class="py-op">)</tt> </tt>
  376 <a name="L282"></a><tt class="py-lineno">282</tt>  <tt class="py-line">            <tt class="py-name">sig_ug</tt> <tt class="py-op">=</tt> <tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> </tt>
  377 <a name="L283"></a><tt class="py-lineno">283</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">sig_ug</tt><tt class="py-op">.</tt><tt id="link-100" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-100', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">.</tt><tt id="link-101" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-101', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> <tt class="py-comment"># type error: sig_ug.lm() &lt; r_sigma </tt> </tt>
  378 <a name="L284"></a><tt class="py-lineno">284</tt>  <tt class="py-line">              <tt class="py-name">reduced</tt> <tt class="py-op">=</tt> <tt class="py-name">True</tt> </tt>
  379 <a name="L285"></a><tt class="py-lineno">285</tt>  <tt class="py-line">              <tt class="py-name">r</tt> <tt class="py-op">-=</tt> <tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> </tt>
  380 <a name="L286"></a><tt class="py-lineno">286</tt>  <tt class="py-line">    <tt class="py-comment"># ensure that r is monic</tt> </tt>
  381 <a name="L287"></a><tt class="py-lineno">287</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-op">!=</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  382 <a name="L288"></a><tt class="py-lineno">288</tt>  <tt class="py-line">      <tt class="py-name">c</tt> <tt class="py-op">=</tt> <tt class="py-name">r</tt><tt class="py-op">.</tt><tt id="link-102" class="py-name"><a title="jas.RingElem.lc" class="py-name" href="#" onclick="return doclink('link-102', 'lc', 'link-29');">lc</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  383 <a name="L289"></a><tt class="py-lineno">289</tt>  <tt class="py-line">      <tt class="py-name">r</tt> <tt class="py-op">*=</tt> <tt class="py-name">c</tt><tt class="py-op">**</tt><tt class="py-op">(</tt><tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt> </tt>
  384 <a name="L290"></a><tt class="py-lineno">290</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">r_sigma</tt><tt class="py-op">,</tt> <tt class="py-name">r</tt> </tt>
  385 </div></div><a name="L291"></a><tt class="py-lineno">291</tt>  <tt class="py-line">     </tt>
  386 <a name="arris_algorithm"></a><div id="arris_algorithm-def"><a name="L292"></a><tt class="py-lineno">292</tt> <a class="py-toggle" href="#" id="arris_algorithm-toggle" onclick="return toggle('arris_algorithm');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html">arris_algorithm</a><tt class="py-op">(</tt><tt class="py-base-class">coeff_free_sigbased_gb</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  387 </div><div id="arris_algorithm-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="arris_algorithm-expanded"><a name="L293"></a><tt class="py-lineno">293</tt>  <tt class="py-line">  <tt class="py-comment"># the plugin implementation of arri's algorithm</tt> </tt>
  388 <a name="L294"></a><tt class="py-lineno">294</tt>  <tt class="py-line">   </tt>
  389 <a name="arris_algorithm.initialize_Syz"></a><div id="arris_algorithm.initialize_Syz-def"><a name="L295"></a><tt class="py-lineno">295</tt> <a class="py-toggle" href="#" id="arris_algorithm.initialize_Syz-toggle" onclick="return toggle('arris_algorithm.initialize_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#initialize_Syz">initialize_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  390 </div><div id="arris_algorithm.initialize_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.initialize_Syz-expanded"><a name="L296"></a><tt class="py-lineno">296</tt>  <tt class="py-line">    <tt class="py-comment"># recognize trivial syzygies</tt> </tt>
  391 <a name="L297"></a><tt class="py-lineno">297</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">[</tt><tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-103" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-103', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">f</tt> <tt class="py-keyword">in</tt> <tt class="py-name">F</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
  392 </div><a name="L298"></a><tt class="py-lineno">298</tt>  <tt class="py-line">     </tt>
  393 <a name="arris_algorithm.update_Syz"></a><div id="arris_algorithm.update_Syz-def"><a name="L299"></a><tt class="py-lineno">299</tt> <a class="py-toggle" href="#" id="arris_algorithm.update_Syz-toggle" onclick="return toggle('arris_algorithm.update_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#update_Syz">update_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  394 </div><div id="arris_algorithm.update_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.update_Syz-expanded"><a name="L300"></a><tt class="py-lineno">300</tt>  <tt class="py-line">    <tt class="py-comment"># add non-trivial syzygies to the basis</tt> </tt>
  395 <a name="L301"></a><tt class="py-lineno">301</tt>  <tt class="py-line">    <tt class="py-comment"># polynomials that reduce to zero indicate non-trivial syzygies</tt> </tt>
  396 <a name="L302"></a><tt class="py-lineno">302</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  397 <a name="L303"></a><tt class="py-lineno">303</tt>  <tt class="py-line">      <tt class="py-name">Syz</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-104" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-104', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  398 <a name="L304"></a><tt class="py-lineno">304</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">Syz</tt> </tt>
  399 </div><a name="L305"></a><tt class="py-lineno">305</tt>  <tt class="py-line">   </tt>
  400 <a name="arris_algorithm.prune_P"></a><div id="arris_algorithm.prune_P-def"><a name="L306"></a><tt class="py-lineno">306</tt> <a class="py-toggle" href="#" id="arris_algorithm.prune_P-toggle" onclick="return toggle('arris_algorithm.prune_P');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#prune_P">prune_P</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">P</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  401 </div><div id="arris_algorithm.prune_P-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.prune_P-expanded"><a name="L307"></a><tt class="py-lineno">307</tt>  <tt class="py-line">    <tt class="py-comment"># remove any pair whose signature is divisible by an element of Syz</tt> </tt>
  402 <a name="L308"></a><tt class="py-lineno">308</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  403 <a name="L309"></a><tt class="py-lineno">309</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">p</tt> <tt class="py-keyword">in</tt> <tt class="py-name">P</tt><tt class="py-op">:</tt> </tt>
  404 <a name="L310"></a><tt class="py-lineno">310</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-105" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-105', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">p</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  405 <a name="L311"></a><tt class="py-lineno">311</tt>  <tt class="py-line">        <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">)</tt> </tt>
  406 <a name="L312"></a><tt class="py-lineno">312</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  407 </div><a name="L313"></a><tt class="py-lineno">313</tt>  <tt class="py-line">   </tt>
  408 <a name="arris_algorithm.prune_S"></a><div id="arris_algorithm.prune_S-def"><a name="L314"></a><tt class="py-lineno">314</tt> <a class="py-toggle" href="#" id="arris_algorithm.prune_S-toggle" onclick="return toggle('arris_algorithm.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  409 </div><div id="arris_algorithm.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.prune_S-expanded"><a name="L315"></a><tt class="py-lineno">315</tt>  <tt class="py-line">    <tt class="py-comment"># watch out for new syzygies discovered, and apply arri's rewritable criterion:</tt> </tt>
  410 <a name="L316"></a><tt class="py-lineno">316</tt>  <tt class="py-line">    <tt class="py-comment"># for any s-polynomial of a given signature, if there exists another (s-)polynomial</tt> </tt>
  411 <a name="L317"></a><tt class="py-lineno">317</tt>  <tt class="py-line">    <tt class="py-comment"># in S or Done of identical signature but lower lm, discard the first</tt> </tt>
  412 <a name="L318"></a><tt class="py-lineno">318</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  413 <a name="L319"></a><tt class="py-lineno">319</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">s</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  414 <a name="L320"></a><tt class="py-lineno">320</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-106" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-106', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  415 <a name="L321"></a><tt class="py-lineno">321</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">==</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-keyword">and</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-107" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-107', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">&gt;</tt><tt class="py-name">sig</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-108" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-108', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">sig</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  416 <a name="L322"></a><tt class="py-lineno">322</tt>  <tt class="py-line">          <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">f</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Done</tt><tt class="py-op">:</tt> </tt>
  417 <a name="L323"></a><tt class="py-lineno">323</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-109" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-109', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  418 <a name="L324"></a><tt class="py-lineno">324</tt>  <tt class="py-line">              <tt class="py-name">u</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-110" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-110', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">,</tt><tt class="py-name">sig</tt><tt class="py-op">)</tt> </tt>
  419 <a name="L325"></a><tt class="py-lineno">325</tt>  <tt class="py-line">              <tt class="py-keyword">if</tt> <tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-111" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-111', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-112" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-112', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  420 <a name="L326"></a><tt class="py-lineno">326</tt>  <tt class="py-line">                <tt class="py-keyword">break</tt> </tt>
  421 <a name="L327"></a><tt class="py-lineno">327</tt>  <tt class="py-line">          <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
  422 <a name="L328"></a><tt class="py-lineno">328</tt>  <tt class="py-line">            <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">)</tt> </tt>
  423 <a name="L329"></a><tt class="py-lineno">329</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  424 </div><a name="L330"></a><tt class="py-lineno">330</tt>  <tt class="py-line">   </tt>
  425 <a name="arris_algorithm.new_pair"></a><div id="arris_algorithm.new_pair-def"><a name="L331"></a><tt class="py-lineno">331</tt> <a class="py-toggle" href="#" id="arris_algorithm.new_pair-toggle" onclick="return toggle('arris_algorithm.new_pair');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#new_pair">new_pair</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sig</tt><tt class="py-op">,</tt><tt class="py-param">p</tt><tt class="py-op">,</tt><tt class="py-param">q</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  426 </div><div id="arris_algorithm.new_pair-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.new_pair-expanded"><a name="L332"></a><tt class="py-lineno">332</tt>  <tt class="py-line">    <tt class="py-comment"># in arri's algorithm, each pair is (sigma,s) where s is the s-polynomial</tt> </tt>
  427 <a name="L333"></a><tt class="py-lineno">333</tt>  <tt class="py-line">    <tt class="py-comment"># and sigma is its natural signature</tt> </tt>
  428 <a name="L334"></a><tt class="py-lineno">334</tt>  <tt class="py-line">    <tt class="py-name">tp</tt> <tt class="py-op">=</tt> <tt class="py-name">p</tt><tt class="py-op">.</tt><tt id="link-113" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-113', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">tq</tt> <tt class="py-op">=</tt> <tt class="py-name">q</tt><tt class="py-op">.</tt><tt id="link-114" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-114', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  429 <a name="L335"></a><tt class="py-lineno">335</tt>  <tt class="py-line">    <tt class="py-name">tpq</tt> <tt class="py-op">=</tt> <tt class="py-name">tp</tt><tt class="py-op">.</tt><tt class="py-name">lcm</tt><tt class="py-op">(</tt><tt class="py-name">tq</tt><tt class="py-op">)</tt> </tt>
  430 <a name="L336"></a><tt class="py-lineno">336</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">p</tt><tt class="py-op">.</tt><tt id="link-115" class="py-name"><a title="jas.RingElem.parent" class="py-name" href="#" onclick="return doclink('link-115', 'parent', 'link-4');">parent</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-comment">#JAS tpq.parent()</tt> </tt>
  431 <a name="L337"></a><tt class="py-lineno">337</tt>  <tt class="py-line">    <tt class="py-name">up</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-116" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-116', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tpq</tt><tt class="py-op">,</tt><tt class="py-name">tp</tt><tt class="py-op">)</tt><tt class="py-op">;</tt> <tt class="py-name">uq</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-117" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-117', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">tpq</tt><tt class="py-op">,</tt><tt class="py-name">tq</tt><tt class="py-op">)</tt> </tt>
  432 <a name="L338"></a><tt class="py-lineno">338</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">up</tt><tt class="py-op">*</tt><tt class="py-name">p</tt><tt class="py-op">-</tt><tt class="py-name">uq</tt><tt class="py-op">*</tt><tt class="py-name">q</tt><tt class="py-op">)</tt> </tt>
  433 </div><a name="L339"></a><tt class="py-lineno">339</tt>  <tt class="py-line">   </tt>
  434 <a name="arris_algorithm.spoly"></a><div id="arris_algorithm.spoly-def"><a name="L340"></a><tt class="py-lineno">340</tt> <a class="py-toggle" href="#" id="arris_algorithm.spoly-toggle" onclick="return toggle('arris_algorithm.spoly');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.arris_algorithm-class.html#spoly">spoly</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  435 </div><div id="arris_algorithm.spoly-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="arris_algorithm.spoly-expanded"><a name="L341"></a><tt class="py-lineno">341</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> </tt>
  436 </div></div><a name="L342"></a><tt class="py-lineno">342</tt>  <tt class="py-line"> </tt>
  437 <a name="f5"></a><div id="f5-def"><a name="L343"></a><tt class="py-lineno">343</tt> <a class="py-toggle" href="#" id="f5-toggle" onclick="return toggle('f5');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html">f5</a><tt class="py-op">(</tt><tt class="py-base-class">coeff_free_sigbased_gb</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  438 </div><div id="f5-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="f5-expanded"><a name="L344"></a><tt class="py-lineno">344</tt>  <tt class="py-line">  <tt class="py-comment"># the plugin implementation of arri's algorithm</tt> </tt>
  439 <a name="L345"></a><tt class="py-lineno">345</tt>  <tt class="py-line">   </tt>
  440 <a name="f5.initialize_Syz"></a><div id="f5.initialize_Syz-def"><a name="L346"></a><tt class="py-lineno">346</tt> <a class="py-toggle" href="#" id="f5.initialize_Syz-toggle" onclick="return toggle('f5.initialize_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#initialize_Syz">initialize_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">F</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  441 </div><div id="f5.initialize_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.initialize_Syz-expanded"><a name="L347"></a><tt class="py-lineno">347</tt>  <tt class="py-line">    <tt class="py-comment"># recognize trivial syzygies</tt> </tt>
  442 <a name="L348"></a><tt class="py-lineno">348</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">[</tt><tt class="py-name">f</tt><tt class="py-op">.</tt><tt id="link-118" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-118', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">f</tt> <tt class="py-keyword">in</tt> <tt class="py-name">F</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt>
  443 </div><a name="L349"></a><tt class="py-lineno">349</tt>  <tt class="py-line">     </tt>
  444 <a name="f5.update_Syz"></a><div id="f5.update_Syz-def"><a name="L350"></a><tt class="py-lineno">350</tt> <a class="py-toggle" href="#" id="f5.update_Syz-toggle" onclick="return toggle('f5.update_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#update_Syz">update_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  445 </div><div id="f5.update_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.update_Syz-expanded"><a name="L351"></a><tt class="py-lineno">351</tt>  <tt class="py-line">    <tt class="py-comment"># recognize trivial syzygies</tt> </tt>
  446 <a name="L352"></a><tt class="py-lineno">352</tt>  <tt class="py-line">    <tt class="py-comment"># see class f5z for a more thorough update_Syz in line w/arri and ggv</tt> </tt>
  447 <a name="L353"></a><tt class="py-lineno">353</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">Syz</tt> </tt>
  448 </div><a name="L354"></a><tt class="py-lineno">354</tt>  <tt class="py-line">   </tt>
  449 <a name="f5.prune_P"></a><div id="f5.prune_P-def"><a name="L355"></a><tt class="py-lineno">355</tt> <a class="py-toggle" href="#" id="f5.prune_P-toggle" onclick="return toggle('f5.prune_P');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#prune_P">prune_P</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">P</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  450 </div><div id="f5.prune_P-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.prune_P-expanded"><a name="L356"></a><tt class="py-lineno">356</tt>  <tt class="py-line">    <tt class="py-comment"># remove any pair whose signature is divisible by an element of Syz</tt> </tt>
  451 <a name="L357"></a><tt class="py-lineno">357</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">set</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  452 <a name="L358"></a><tt class="py-lineno">358</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-name">p</tt> <tt class="py-keyword">in</tt> <tt class="py-name">P</tt><tt class="py-op">:</tt> </tt>
  453 <a name="L359"></a><tt class="py-lineno">359</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-119" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-119', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">p</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  454 <a name="L360"></a><tt class="py-lineno">360</tt>  <tt class="py-line">        <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">)</tt> </tt>
  455 <a name="L361"></a><tt class="py-lineno">361</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  456 </div><a name="L362"></a><tt class="py-lineno">362</tt>  <tt class="py-line">   </tt>
  457 <a name="f5.prune_S"></a><div id="f5.prune_S-def"><a name="L363"></a><tt class="py-lineno">363</tt> <a class="py-toggle" href="#" id="f5.prune_S-toggle" onclick="return toggle('f5.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  458 </div><div id="f5.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.prune_S-expanded"><a name="L364"></a><tt class="py-lineno">364</tt>  <tt class="py-line">    <tt class="py-comment"># watch out for new syzygies discovered, and apply faugere's rewritable criterion:</tt> </tt>
  459 <a name="L365"></a><tt class="py-lineno">365</tt>  <tt class="py-line">    <tt class="py-comment"># for any (sigma,p,q) in S, if there exists (tau,g) such that tau divides sigma</tt> </tt>
  460 <a name="L366"></a><tt class="py-lineno">366</tt>  <tt class="py-line">    <tt class="py-comment"># but g was generated after p, discard (sigma,p,q)</tt> </tt>
  461 <a name="L367"></a><tt class="py-lineno">367</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  462 <a name="L368"></a><tt class="py-lineno">368</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">u</tt><tt class="py-op">,</tt><tt class="py-name">j</tt><tt class="py-op">,</tt><tt class="py-name">v</tt><tt class="py-op">,</tt><tt class="py-name">k</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  463 <a name="L369"></a><tt class="py-lineno">369</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-120" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-120', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">t</tt><tt class="py-op">,</tt><tt class="py-name">sig</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">t</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  464 <a name="L370"></a><tt class="py-lineno">370</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">j</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt> <tt class="py-keyword">or</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-121" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-121', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">Done</tt><tt class="py-op">[</tt><tt class="py-name">i</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">,</tt><tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">j</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">*</tt><tt class="py-name">u</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">Done</tt><tt class="py-op">[</tt><tt class="py-name">i</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-op">&gt;</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">j</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> <tt class="py-keyword">for</tt> <tt class="py-name">i</tt> <tt class="py-keyword">in</tt> <tt class="py-name">xrange</tt><tt class="py-op">(</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">Done</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  465 <a name="L371"></a><tt class="py-lineno">371</tt>  <tt class="py-line">          <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">u</tt><tt class="py-op">,</tt><tt class="py-name">j</tt><tt class="py-op">,</tt><tt class="py-name">v</tt><tt class="py-op">,</tt><tt class="py-name">k</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  466 <a name="L372"></a><tt class="py-lineno">372</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  467 </div><a name="L373"></a><tt class="py-lineno">373</tt>  <tt class="py-line">   </tt>
  468 <a name="f5.new_pair"></a><div id="f5.new_pair-def"><a name="L374"></a><tt class="py-lineno">374</tt> <a class="py-toggle" href="#" id="f5.new_pair-toggle" onclick="return toggle('f5.new_pair');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#new_pair">new_pair</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">sig</tt><tt class="py-op">,</tt><tt class="py-param">p</tt><tt class="py-op">,</tt><tt class="py-param">q</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  469 </div><div id="f5.new_pair-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.new_pair-expanded"><a name="L375"></a><tt class="py-lineno">375</tt>  <tt class="py-line">    <tt class="py-comment"># it's easier to deal with faugere's criterion if one creates pairs</tt> </tt>
  470 <a name="L376"></a><tt class="py-lineno">376</tt>  <tt class="py-line">    <tt class="py-comment"># using indices rather than polynomials</tt> </tt>
  471 <a name="L377"></a><tt class="py-lineno">377</tt>  <tt class="py-line">    <tt class="py-comment"># note that this while look gives f5 a disadvantage</tt> </tt>
  472 <a name="L378"></a><tt class="py-lineno">378</tt>  <tt class="py-line">    <tt class="py-name">i</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">;</tt> <tt class="py-name">k</tt> <tt class="py-op">=</tt> <tt class="py-number">0</tt> </tt>
  473 <a name="L379"></a><tt class="py-lineno">379</tt>  <tt class="py-line">    <tt class="py-name">up</tt><tt class="py-op">,</tt><tt class="py-name">uq</tt> <tt class="py-op">=</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt id="link-122" class="py-name"><a title="basic_sigbased_gb.sigbased_gb.spoly_multipliers" class="py-name" href="#" onclick="return doclink('link-122', 'spoly_multipliers', 'link-50');">spoly_multipliers</a></tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">,</tt><tt class="py-name">q</tt><tt class="py-op">)</tt> </tt>
  474 <a name="L380"></a><tt class="py-lineno">380</tt>  <tt class="py-line">    <tt class="py-keyword">while</tt> <tt class="py-op">(</tt><tt class="py-name">i</tt><tt class="py-op">&lt;</tt><tt class="py-number">0</tt> <tt class="py-keyword">or</tt> <tt class="py-name">j</tt><tt class="py-op">&lt;</tt><tt class="py-number">0</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">k</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  475 <a name="L381"></a><tt class="py-lineno">381</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-name">p</tt> <tt class="py-op">==</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">k</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">:</tt> </tt>
  476 <a name="L382"></a><tt class="py-lineno">382</tt>  <tt class="py-line">        <tt class="py-name">i</tt> <tt class="py-op">=</tt> <tt class="py-name">k</tt> </tt>
  477 <a name="L383"></a><tt class="py-lineno">383</tt>  <tt class="py-line">      <tt class="py-keyword">elif</tt> <tt class="py-name">q</tt> <tt class="py-op">==</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">k</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">:</tt> </tt>
  478 <a name="L384"></a><tt class="py-lineno">384</tt>  <tt class="py-line">        <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-name">k</tt> </tt>
  479 <a name="L385"></a><tt class="py-lineno">385</tt>  <tt class="py-line">      <tt class="py-name">k</tt> <tt class="py-op">+=</tt> <tt class="py-number">1</tt><tt class="py-op">;</tt> </tt>
  480 <a name="L386"></a><tt class="py-lineno">386</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-op">(</tt><tt class="py-name">i</tt> <tt class="py-op">==</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  481 <a name="L387"></a><tt class="py-lineno">387</tt>  <tt class="py-line">      <tt class="py-name">i</tt><tt class="py-op">=</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  482 <a name="L388"></a><tt class="py-lineno">388</tt>  <tt class="py-line">    <tt class="py-keyword">elif</tt> <tt class="py-op">(</tt><tt class="py-name">j</tt> <tt class="py-op">==</tt> <tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  483 <a name="L389"></a><tt class="py-lineno">389</tt>  <tt class="py-line">      <tt class="py-name">j</tt> <tt class="py-op">=</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">G</tt><tt class="py-op">)</tt> </tt>
  484 <a name="L390"></a><tt class="py-lineno">390</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-op">(</tt><tt class="py-name">sig</tt><tt class="py-op">,</tt><tt class="py-name">up</tt><tt class="py-op">,</tt><tt class="py-name">i</tt><tt class="py-op">,</tt><tt class="py-name">uq</tt><tt class="py-op">,</tt><tt class="py-name">j</tt><tt class="py-op">)</tt> </tt>
  485 </div><a name="L391"></a><tt class="py-lineno">391</tt>  <tt class="py-line">     </tt>
  486 <a name="f5.spoly"></a><div id="f5.spoly-def"><a name="L392"></a><tt class="py-lineno">392</tt> <a class="py-toggle" href="#" id="f5.spoly-toggle" onclick="return toggle('f5.spoly');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5-class.html#spoly">spoly</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">s</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  487 </div><div id="f5.spoly-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5.spoly-expanded"><a name="L393"></a><tt class="py-lineno">393</tt>  <tt class="py-line">    <tt class="py-comment"># since s has the structure (sigma,up,i,uq,j)</tt> </tt>
  488 <a name="L394"></a><tt class="py-lineno">394</tt>  <tt class="py-line">    <tt class="py-comment"># we have to compute the s-polynomial by looking up f and g</tt> </tt>
  489 <a name="L395"></a><tt class="py-lineno">395</tt>  <tt class="py-line">    <tt class="py-name">f</tt> <tt class="py-op">=</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">2</tt><tt class="py-op">]</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">;</tt> <tt class="py-name">g</tt> <tt class="py-op">=</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">4</tt><tt class="py-op">]</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt> </tt>
  490 <a name="L396"></a><tt class="py-lineno">396</tt>  <tt class="py-line">    <tt class="py-name">uf</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">;</tt> <tt class="py-name">ug</tt> <tt class="py-op">=</tt> <tt class="py-name">s</tt><tt class="py-op">[</tt><tt class="py-number">3</tt><tt class="py-op">]</tt> </tt>
  491 <a name="L397"></a><tt class="py-lineno">397</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">uf</tt><tt class="py-op">*</tt><tt class="py-name">f</tt> <tt class="py-op">-</tt> <tt class="py-name">ug</tt><tt class="py-op">*</tt><tt class="py-name">g</tt> </tt>
  492 </div></div><a name="L398"></a><tt class="py-lineno">398</tt>  <tt class="py-line">     </tt>
  493 <a name="f5z"></a><div id="f5z-def"><a name="L399"></a><tt class="py-lineno">399</tt> <a class="py-toggle" href="#" id="f5z-toggle" onclick="return toggle('f5z');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.f5z-class.html">f5z</a><tt class="py-op">(</tt><tt class="py-base-class">f5</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  494 </div><div id="f5z-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="f5z-expanded"><a name="L400"></a><tt class="py-lineno">400</tt>  <tt class="py-line">   </tt>
  495 <a name="f5z.update_Syz"></a><div id="f5z.update_Syz-def"><a name="L401"></a><tt class="py-lineno">401</tt> <a class="py-toggle" href="#" id="f5z.update_Syz-toggle" onclick="return toggle('f5z.update_Syz');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.f5z-class.html#update_Syz">update_Syz</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">sigma</tt><tt class="py-op">,</tt><tt class="py-param">r</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  496 </div><div id="f5z.update_Syz-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="f5z.update_Syz-expanded"><a name="L402"></a><tt class="py-lineno">402</tt>  <tt class="py-line">    <tt class="py-comment"># recognize trivial syzygies</tt> </tt>
  497 <a name="L403"></a><tt class="py-lineno">403</tt>  <tt class="py-line">    <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-op">==</tt> <tt class="py-number">0</tt><tt class="py-op">:</tt> </tt>
  498 <a name="L404"></a><tt class="py-lineno">404</tt>  <tt class="py-line">      <tt class="py-name">Syz</tt><tt class="py-op">.</tt><tt class="py-name">add</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">.</tt><tt id="link-123" class="py-name"><a title="jas.RingElem.lm" class="py-name" href="#" onclick="return doclink('link-123', 'lm', 'link-0');">lm</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  499 <a name="L405"></a><tt class="py-lineno">405</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">Syz</tt> </tt>
  500 </div></div><a name="L406"></a><tt class="py-lineno">406</tt>  <tt class="py-line">     </tt>
  501 <a name="min_size_mons"></a><div id="min_size_mons-def"><a name="L407"></a><tt class="py-lineno">407</tt> <a class="py-toggle" href="#" id="min_size_mons-toggle" onclick="return toggle('min_size_mons');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="basic_sigbased_gb.min_size_mons-class.html">min_size_mons</a><tt class="py-op">(</tt><tt class="py-base-class">arris_algorithm</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  502 </div><div id="min_size_mons-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="min_size_mons-expanded"><a name="L408"></a><tt class="py-lineno">408</tt>  <tt class="py-line">  <tt class="py-comment"># the plugin implementation of arri's algorithm</tt> </tt>
  503 <a name="L409"></a><tt class="py-lineno">409</tt>  <tt class="py-line">   </tt>
  504 <a name="min_size_mons.prune_S"></a><div id="min_size_mons.prune_S-def"><a name="L410"></a><tt class="py-lineno">410</tt> <a class="py-toggle" href="#" id="min_size_mons.prune_S-toggle" onclick="return toggle('min_size_mons.prune_S');">-</a><tt class="py-line">  <tt class="py-keyword">def</tt> <a class="py-def-name" href="basic_sigbased_gb.min_size_mons-class.html#prune_S">prune_S</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt><tt class="py-param">S</tt><tt class="py-op">,</tt><tt class="py-param">Syz</tt><tt class="py-op">,</tt><tt class="py-param">Done</tt><tt class="py-op">,</tt><tt class="py-param">G</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  505 </div><div id="min_size_mons.prune_S-collapsed" style="display:none;" pad="+++" indent="++++++"></div><div id="min_size_mons.prune_S-expanded"><a name="L411"></a><tt class="py-lineno">411</tt>  <tt class="py-line">    <tt class="py-comment"># watch out for new syzygies discovered, and apply the minimal "number of monomials" criterion:</tt> </tt>
  506 <a name="L412"></a><tt class="py-lineno">412</tt>  <tt class="py-line">    <tt class="py-comment"># for any s-polynomial of a given signature, if there exists another polynomial</tt> </tt>
  507 <a name="L413"></a><tt class="py-lineno">413</tt>  <tt class="py-line">    <tt class="py-comment"># in Done of identical signature but fewer monomials, replace this s-polynomial</tt> </tt>
  508 <a name="L414"></a><tt class="py-lineno">414</tt>  <tt class="py-line">    <tt class="py-comment"># by the multiple of the polynomial with fewer monomials</tt> </tt>
  509 <a name="L415"></a><tt class="py-lineno">415</tt>  <tt class="py-line">    <tt class="py-name">result</tt> <tt class="py-op">=</tt> <tt class="py-name">list</tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  510 <a name="L416"></a><tt class="py-lineno">416</tt>  <tt class="py-line">    <tt class="py-name">R</tt> <tt class="py-op">=</tt> <tt class="py-name">G</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">.</tt><tt id="link-124" class="py-name"><a title="jas.RingElem.parent" class="py-name" href="#" onclick="return doclink('link-124', 'parent', 'link-4');">parent</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt>
  511 <a name="L417"></a><tt class="py-lineno">417</tt>  <tt class="py-line">    <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">S</tt><tt class="py-op">:</tt> </tt>
  512 <a name="L418"></a><tt class="py-lineno">418</tt>  <tt class="py-line">      <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-125" class="py-name"><a title="jas.RingElem.monomial_divides" class="py-name" href="#" onclick="return doclink('link-125', 'monomial_divides', 'link-18');">monomial_divides</a></tt><tt class="py-op">(</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">sigma</tt><tt class="py-op">)</tt> <tt class="py-keyword">for</tt> <tt class="py-name">tau</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Syz</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  513 <a name="L419"></a><tt class="py-lineno">419</tt>  <tt class="py-line">        <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">any</tt><tt class="py-op">(</tt><tt class="py-name">tau</tt> <tt class="py-op">==</tt> <tt class="py-name">sigma</tt> <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">result</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  514 <a name="L420"></a><tt class="py-lineno">420</tt>  <tt class="py-line">          <tt class="py-keyword">for</tt> <tt class="py-op">(</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">g</tt><tt class="py-op">)</tt> <tt class="py-keyword">in</tt> <tt class="py-name">Done</tt><tt class="py-op">:</tt> </tt>
  515 <a name="L421"></a><tt class="py-lineno">421</tt>  <tt class="py-line">            <tt class="py-keyword">if</tt> <tt class="py-name">tau</tt><tt class="py-op">.</tt><tt id="link-126" class="py-name" targets="Method jas.RingElem.divides()=jas.RingElem-class.html#divides"><a title="jas.RingElem.divides" class="py-name" href="#" onclick="return doclink('link-126', 'divides', 'link-126');">divides</a></tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">)</tt> <tt class="py-keyword">and</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">g</tt><tt class="py-op">.</tt><tt id="link-127" class="py-name" targets="Method jas.RingElem.monomials()=jas.RingElem-class.html#monomials"><a title="jas.RingElem.monomials" class="py-name" href="#" onclick="return doclink('link-127', 'monomials', 'link-127');">monomials</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> <tt class="py-op">&lt;</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">s</tt><tt class="py-op">.</tt><tt id="link-128" class="py-name"><a title="jas.RingElem.monomials" class="py-name" href="#" onclick="return doclink('link-128', 'monomials', 'link-127');">monomials</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt>
  516 <a name="L422"></a><tt class="py-lineno">422</tt>  <tt class="py-line">              <tt class="py-name">u</tt> <tt class="py-op">=</tt> <tt class="py-name">R</tt><tt class="py-op">.</tt><tt id="link-129" class="py-name"><a title="jas.RingElem.monomial_quotient" class="py-name" href="#" onclick="return doclink('link-129', 'monomial_quotient', 'link-9');">monomial_quotient</a></tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">tau</tt><tt class="py-op">)</tt> </tt>
  517 <a name="L423"></a><tt class="py-lineno">423</tt>  <tt class="py-line">              <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">tau</tt><tt class="py-op">,</tt><tt class="py-name">u</tt><tt class="py-op">*</tt><tt class="py-name">g</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  518 <a name="L424"></a><tt class="py-lineno">424</tt>  <tt class="py-line">              <tt class="py-keyword">break</tt> </tt>
  519 <a name="L425"></a><tt class="py-lineno">425</tt>  <tt class="py-line">          <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt>
  520 <a name="L426"></a><tt class="py-lineno">426</tt>  <tt class="py-line">            <tt class="py-name">result</tt><tt class="py-op">.</tt><tt class="py-name">append</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">sigma</tt><tt class="py-op">,</tt><tt class="py-name">s</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt>
  521 <a name="L427"></a><tt class="py-lineno">427</tt>  <tt class="py-line">    <tt class="py-keyword">return</tt> <tt class="py-name">result</tt> </tt>
  522 </div></div><a name="L428"></a><tt class="py-lineno">428</tt>  <tt class="py-line"> </tt><script type="text/javascript">
  523 <!--
  524 expandto(location.href);
  525 // -->
  526 </script>
  527 </pre>
  528 <br />
  529 <!-- ==================== NAVIGATION BAR ==================== -->
  530 <table class="navbar" border="0" width="100%" cellpadding="0"
  531        bgcolor="#a0c0ff" cellspacing="0">
  532   <tr valign="middle">
  533 
  534   <!-- Tree link -->
  535       <th>&nbsp;&nbsp;&nbsp;<a
  536         href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>
  537 
  538   <!-- Index link -->
  539       <th>&nbsp;&nbsp;&nbsp;<a
  540         href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>
  541 
  542   <!-- Help link -->
  543       <th>&nbsp;&nbsp;&nbsp;<a
  544         href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>
  545 
  546   <!-- Project homepage -->
  547       <th class="navbar" align="right" width="100%">
  548         <table border="0" cellpadding="0" cellspacing="0">
  549           <tr><th class="navbar" align="center"
  550             ><a class="navbar" target="_top" href="../../index.html">Python to JAS</a></th>
  551           </tr></table></th>
  552   </tr>
  553 </table>
  554 <table border="0" cellpadding="0" cellspacing="0" width="100%%">
  555   <tr>
  556     <td align="left" class="footer">
  557     Generated by Epydoc 3.0.1 on Sun Apr 21 14:11:38 2019
  558     </td>
  559     <td align="right" class="footer">
  560       <a target="mainFrame" href="http://epydoc.sourceforge.net"
  561         >http://epydoc.sourceforge.net</a>
  562     </td>
  563   </tr>
  564 </table>
  565 
  566 <script type="text/javascript">
  567   <!--
  568   // Private objects are initially displayed (because if
  569   // javascript is turned off then we want them to be
  570   // visible); but by default, we want to hide them.  So hide
  571   // them unless we have a cookie that says to show them.
  572   checkCookie();
  573   // -->
  574 </script>
  575 </body>
  576 </html>