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

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

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (lpres) - Chapter 6: On a parallel nilpotent quotient algorithm</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap6"  onload="jscontent()">


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

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

<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X7BC16B0082A2B827" name="X7BC16B0082A2B827"></a></p>
<div class="ChapSects"><a href="chap6.html#X7BC16B0082A2B827">6 <span class="Heading">On a parallel nilpotent quotient algorithm</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X86A9B6F87E619FFF">6.1 <span class="Heading">Usage</span></a>
</span>
</div>
</div>

<h3>6 <span class="Heading">On a parallel nilpotent quotient algorithm</span></h3>

<p>We included a parallel version of <strong class="pkg">lpres</strong>'s nilpotent quotient algorithm using the <strong class="pkg">ParGAP</strong>-package of <strong class="pkg">GAP</strong>; see <a href="chapBib.html#biBParGap">[Coo04]</a>. In this chapter, we outline the basic usage of this parallel part of the <strong class="pkg">lpres</strong>-package. For further details on the parallel <strong class="pkg">GAP</strong>-sessions we refer to the <strong class="pkg">ParGAP</strong>-manual <a href="chapBib.html#biBParGap">[Coo04]</a>. We note that the <strong class="pkg">ParGAP</strong>-package has some bottlenecks in practice. Nevertheless the significant speed-up of our computations on a multiple-core system shows that this is a reasonable extension of the <strong class="pkg">lpres</strong>-package.</p>

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

<h4>6.1 <span class="Heading">Usage</span></h4>

<p>For using the parallel version of the nilpotent quotient algorithm, you will need to install the <strong class="pkg">ParGAP</strong>-package as described in its manual <a href="chapBib.html#biBParGap">[Coo04]</a>. When using Version 1.1.2 of the <strong class="pkg">ParGAP</strong>-package, you will need to apply the following patch to `pargap/lib/masslave.g' as otherwise the <strong class="pkg">ParGAP</strong>-session may crash. On a linux machine you can simply use `patch < ../../nql/gap/pargap/patch' from within the directory `pargap/lib/'.</p>


<pre class="normal">

--- masslave.g 2001-11-16 13:17:04.000000000 +0100
+++ masslave.g 2009-05-06 12:20:19.000000000 +0200
@@ -467,8 +467,9 @@
   if Length(deltas)>1 then max2 := Maximum(max2, deltas[Length(deltas)-1]); fi;
   max1 := deltas[Length(deltas)];
   pos1 := Position( List(slaveArray, x->realtime-x.time), max1 );
-  if max1 > slaveTaskTimeFactor and max1 > 30
-     and slaveTaskTime[pos2].total > 60 then
+  if max1 > slaveTaskTimeFactor and
+     max1 > 30 and pos2 <> fail and 
+     slaveTaskTime[pos2].total > 60 then
     Print("SLAVE ",pos1," SEEMS DEAD!!\n");
   fi;
 end);

</pre>

<p>Now, you are ready for creating a <strong class="pkg">ParGAP</strong>-session and you can load the <strong class="pkg">lpres</strong>-package from within <strong class="pkg">ParGAP</strong> using `LoadPackage' as usual. The same methods as described previously are available. The following example shows the application of the `NilpotentQuotient'-method to the Grigorchuk group on a quad-core machine. Note that the significant speed-up of the nilpotent quotient algorithm is especially noticeable for large nilpotent quotients. This parallel version of <strong class="pkg">lpres</strong> successfully computes some nilpotent quotients which normally took more than a month to complete.</p>


<div class="example"><pre>
GAP4, Version: 4.4.12 of 17-Dec-2008, i686-pc-linux-gnu-gcc
GAP4, Version: 4.4.12 of 17-Dec-2008, i686-pc-linux-gnu-gcc
GAP4, Version: 4.4.12 of 17-Dec-2008, i686-pc-linux-gnu-gcc
GAP4, Version: 4.4.12 of 17-Dec-2008, i686-pc-linux-gnu-gcc
GAP4, Version: 4.4.12 of 17-Dec-2008, i686-pc-linux-gnu-gcc
<span class="GAPprompt">gap></span> <span class="GAPinput">TOPCnumSlaves;</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">LoadPackage("LPRES");</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">G:=ExamplesOfLPresentations(1);</span>
<L-presented group on the generators [ a, b, c, d ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetInfoLevel(InfoLPRES,1);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NilpotentQuotient(G,2);</span>
#I  Class 1: 3 generators with relative orders: [ 2, 2, 2 ]
#I  Computing a polycyclic presentation for the covering group...
#I  Checking the consistency relations...
master -> 1: (AGGLOM_TASK): [ [ -3, 1 ], [ -3, 2 ], [ -2, 1 ], [ 2, -1 ],
  [ 3, -1 ] ]
master -> 2: (AGGLOM_TASK): [ [ 3, -2 ], [ 1 ], [ 2 ], [ 3 ] ]
1 -> master: [ [ 0, 0, 0, 0, 0, -2, 0 ], [ 0, 0, 0, 0, 0, 0, -2 ],
  [ 0, 0, 0, 0, -2, 0, 0 ], [ 0, 0, 0, 0, -2, 0, 0 ],
  [ 0, 0, 0, 0, 0, -2, 0 ] ]
2 -> master: [ [ 0, 0, 0, 0, 0, 0, -2 ], [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0 ] ]
#I  Broadcasting the slaves...
#I  Inducing the endomorphisms...
master -> 1:  1
master -> 2:  2
master -> 3:  3
master -> 4:  4
3 -> master: [ 2, 1 ]
UPDATE: [ 3, [ 2, 1 ] ]
1 -> master: [ 2, 1, 8, 1 ]
UPDATE: [ 1, [ 2, 1, 8, 1 ] ]
2 -> master: [ 2, 1, 3, 1, 4, 1 ]
UPDATE: [ 2, [ 2, 1, 3, 1, 4, 1 ] ]
master -> 1:  5
master -> 2:  6
master -> 3:  7
4 -> master: [ 4, -1, 6, -1, 10, -1 ]
UPDATE: [ 4, [ 4, -1, 6, -1, 10, -1 ] ]
1 -> master: [ 6, 1, 8, 2 ]
UPDATE: [ 5, [ 6, 1, 8, 2 ] ]
2 -> master: [ 4, 2, 6, 1, 7, 1, 10, 1 ]
UPDATE: [ 6, [ 4, 2, 6, 1, 7, 1, 10, 1 ] ]
3 -> master: [ 6, 1 ]
UPDATE: [ 7, [ 6, 1 ] ]
master -> 1:  8
master -> 2:  9
master -> 3:  10
1 -> master: [ 10, 1 ]
UPDATE: [ 8, [ 10, 1 ] ]
2 -> master: [  ]
UPDATE: [ 9, [  ] ]
3 -> master: [ 10, -1 ]
UPDATE: [ 10, [ 10, -1 ] ]
#I  Broadcasting the slaves...
#I  Mapping the relations...
master -> 1:  1
master -> 2:  2
master -> 3:  3
master -> 4:  4
1 -> master: [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ]
2 -> master: [ 0, 0, 0, 2, 0, 1, 1, 0, 0, 1 ]
3 -> master: [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ]
4 -> master: [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ]
master -> 1:  5
master -> 2:  6
master -> 3:  7
1 -> master: [ 0, 0, 0, 1, 0, 1, 1, 0, 0, 1 ]
2 -> master: [ 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 ]
3 -> master: [ 0, 0, 0, 0, 0, 0, 0, 4, 6, 4 ]
#I  Start spinning...
#I  Extend the quotient system...
#I  Class 2: 2 generators with relative orders: [ 2, 2 ]
Pcp-group with orders [ 2, 2, 2, 2, 2 ]
</pre></div>

<p>Note that the only difference in the parallel version of the <strong class="pkg">lpres</strong>-package is a parallel version of the operation `ExtendQuotientSystem'. This latter operation covers the induction step of the nilpotent quotient algorithm.</p>


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


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

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