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

Quelle  chap3_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/difsets/doc/chap3_mj.html


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

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

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (DifSets) - Chapter 3: Results</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap2_mj.html">[Previous Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X7A92ECF9816C7E28" name="X7A92ECF9816C7E28"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X7A92ECF9816C7E28">3 <span class="Heading">Results</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X85CC7A44864637B3">3.1 <span class="Heading">Order 16 and 36</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7806C267831D6985">3.2 <span class="Heading">Order 64 and 96</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X780C79EB85C32138">3.3 <span class="Heading">Comments</span></a>
</span>
</div>
</div>

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

<p>The <strong class="pkg">DifSets</strong> Package was designed with the goal of finding all difference sets up to equivalence in groups of order 64 and 96, a goal which was accomplished. Overall, the algorithm has successfully computed results for 1006 of the 1032 groups of order less than 100. Full results, which include timings, number of sets, and the sets themselves can be found in the <code class="code">data</code> subdirectory of the package, which is organized by group order and contains a single <code class="code">.txt</code> file for each computed group. A list of all timings can also be found in the file <code class="code">groups.csv</code> in the <code class="code">data</code> directory, and the difference sets themselves can be loaded using the function <code class="func">LoadDifferenceSets</code> (<a href="chap2_mj.html#X848925877C3C891F"><span class="RefLink">2.6-2</span></a>). All computations were performed using <strong class="pkg">GAP</strong> 4.9.1 on a 4.00GHz i7-6700K using 8GB of RAM. Here we give a basic overview of results and comments on timings. Throughout this chapter we will refer to the group returned by the <strong class="pkg">GAP</strong> function <code class="code">SmallGroup(v, n)</code> as <code class="code">[v, n]</code>.</p>

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

<h4>3.1 <span class="Heading">Order 16 and 36</span></h4>

<p>Difference sets in groups of order 16 and 36 form the first nontrivial examples of the Hadamard parameters, and exhaustive enumerations are already well known. Still, computation of these sets gives a useful benchmark and check of accuracy.</p>

<p>Almost all groups in these orders take less than a second. The group <code class="code">[36, 9]</code>, however, takes several orders of magnitude longer than other groups of order 36. This is because <code class="code">[36, 9]</code> does not have small normal subgroups (in particular, its smallest nontrivial normal subgroup has order 9), and refining across a large gap in sizes, expecially near the end of the algorithm, requires checking significantly more preimages.</p>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Group</td>
<td class="tdcenter">Difference Sets</td>
<td class="tdcenter">Time (seconds)</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 1]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.030</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 2]</code></td>
<td class="tdcenter">3</td>
<td class="tdcenter">0.103</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 3]</code></td>
<td class="tdcenter">4</td>
<td class="tdcenter">0.100</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 4]</code></td>
<td class="tdcenter">3</td>
<td class="tdcenter">0.100</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 5]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.061</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 6]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.071</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 7]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.072</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 8]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.070</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 9]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.082</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 10]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.187</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 11]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.121</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 12]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.195</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 13]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">0.117</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[16, 14]</code></td>
<td class="tdcenter">1</td>
<td class="tdcenter">0.059</td>
</tr>
</table><br /><p> </p><br />
</div>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Group</td>
<td class="tdcenter">Difference Sets</td>
<td class="tdcenter">Time (seconds)</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 1]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.335</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 2]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.201</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 3]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.407</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 4]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.322</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 5]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">0.218</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 6]</code></td>
<td class="tdcenter">6</td>
<td class="tdcenter">0.412</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 7]</code></td>
<td class="tdcenter">1</td>
<td class="tdcenter">0.795</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 8]</code></td>
<td class="tdcenter">4</td>
<td class="tdcenter">0.340</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 9]</code></td>
<td class="tdcenter">5</td>
<td class="tdcenter">340.989</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 10]</code></td>
<td class="tdcenter">6</td>
<td class="tdcenter">1.137</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 11]</code></td>
<td class="tdcenter">3</td>
<td class="tdcenter">0.699</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 12]</code></td>
<td class="tdcenter">6</td>
<td class="tdcenter">0.417</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 13]</code></td>
<td class="tdcenter">1</td>
<td class="tdcenter">0.801</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[36, 14]</code></td>
<td class="tdcenter">3</td>
<td class="tdcenter">0.434</td>
</tr>
</table><br /><p> </p><br />
</div>

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

<h4>3.2 <span class="Heading">Order 64 and 96</span></h4>

<p>Difference sets in groups of order 64 also satisfy the Hadamard parameters, while difference sets in groups of order 96 satisfy the McFarland parameters. Since there are many groups of both orders, here we just give some examples and summaries. In particular, the tables below list the fastest, slowest, and median five groups of each order, sorted by time.</p>

<p>Groups of order 64 are <span class="SimpleMath">\(p\)</span>-groups, and thus always have enough normal subgroups to form long refining series. This means the refining steps are relatively efficient for all groups in this order. The main difference between groups is the size of the automorphism group, and, in particular, four of the five groups taking the largest amount of time are four of the five groups with the largest automorphism groups in this order. The additional group in the top five, <code class="code">[64, 235]</code>, has a relatively large number of difference sets, but is otherwise unremarkable. In general, smaller numbers of difference sets correspond to faster times, and in fact the eight groups with no difference sets were computed the fastest, beating the next fastest groups by an order of magnitude. Overall, the mean computation time for a group of order 64 was 3988.476 seconds, with a median time of 1493.175 seconds. This means that the total computer time to compute all difference sets in groups of order 64 was roughly 12 days.</p>

<p>In groups of order 96 we do not always have large numbers of normal subgroups, and, as with <code class="code">[36, 9]</code>, this can substantially slow down computation. In fact, the five groups taking the longest computation time are five of the six groups with fewest normal subgroups in this order. We are helped, however, by the fact that the only valid choice of <span class="SimpleMath">\(k\)</span> is 20, which is relatively small and thus does not lead to large numbers of preimages even across large gaps in the refining series. Many groups in this order have no difference sets, but even for these groups computation can be slow. While the fastest groups contain no difference sets, many groups with no difference sets actually take much longer than other groups that do contain difference sets. Overall, the mean computation time for a group of order 96 was 24447.991 seconds, with a median time of 11278.765 seconds. This means that the total computer time to compute all difference sets in groups of order 96 was roughly 65 days.</p>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Group</td>
<td class="tdcenter">Difference Sets</td>
<td class="tdcenter">Time (seconds)</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 52]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">3.451</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 54]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">3.463</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 47]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">3.594</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 186]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">3.940</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 1]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">3.950</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 166]</code></td>
<td class="tdcenter">2312</td>
<td class="tdcenter">1424.692</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 134]</code></td>
<td class="tdcenter">342</td>
<td class="tdcenter">1439.484</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 135]</code></td>
<td class="tdcenter">540</td>
<td class="tdcenter">1493.175</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 7]</code></td>
<td class="tdcenter">1320</td>
<td class="tdcenter">1515.710</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 160]</code></td>
<td class="tdcenter">3192</td>
<td class="tdcenter">1518.693</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 192]</code></td>
<td class="tdcenter">222</td>
<td class="tdcenter">21131.394</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 267]</code></td>
<td class="tdcenter">4</td>
<td class="tdcenter">23662.500</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 235]</code></td>
<td class="tdcenter">4317</td>
<td class="tdcenter">24566.186</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 260]</code></td>
<td class="tdcenter">30</td>
<td class="tdcenter">144338.020</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[64, 262]</code></td>
<td class="tdcenter">148</td>
<td class="tdcenter">229488.988</td>
</tr>
</table><br /><p> </p><br />
</div>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Group</td>
<td class="tdcenter">Difference Sets</td>
<td class="tdcenter">Time (seconds)</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 2]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">8.731</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 59]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">8.791</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 189]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">29.378</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 66]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">29.777</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 46]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">44.478</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 209]</code></td>
<td class="tdcenter">4</td>
<td class="tdcenter">10809.673</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 133]</code></td>
<td class="tdcenter">16</td>
<td class="tdcenter">11198.052</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 224]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">11278.765</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 89]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">11349.466</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 102]</code></td>
<td class="tdcenter">0</td>
<td class="tdcenter">11415.688</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 227]</code></td>
<td class="tdcenter">42</td>
<td class="tdcenter">308246.830</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 64]</code></td>
<td class="tdcenter">14</td>
<td class="tdcenter">310447.407</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 70]</code></td>
<td class="tdcenter">28</td>
<td class="tdcenter">514559.313</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 72]</code></td>
<td class="tdcenter">2</td>
<td class="tdcenter">515196.547</td>
</tr>
<tr>
<td class="tdcenter"><code class="code">[96, 71]</code></td>
<td class="tdcenter">8</td>
<td class="tdcenter">871439.024</td>
</tr>
</table><br /><p> </p><br />
</div>

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

<h4>3.3 <span class="Heading">Comments</span></h4>

<p>Overall, the algorithm spends almost all of its time performing four operations: refining sums to sums in several stages using <code class="func">SomeRefinedDifferenceSums</code> (<a href="chap2_mj.html#X866272667D6032BA"><span class="RefLink">2.3-8</span></a>), refining sums to sets in the final stage using <code class="func">SomeRefinedDifferenceSets</code> (<a href="chap2_mj.html#X7E1012C07FB328B4"><span class="RefLink">2.3-4</span></a>), removing equivalent difference sums in several stages using <code class="func">EquivalentFreeListOfDifferenceSums</code> (<a href="chap2_mj.html#X8639AB227B0CF9F3"><span class="RefLink">2.4-3</span></a>), and removing equivalent difference sets in the final stage using <code class="func">SmallestEquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X8741BBF4811F942A"><span class="RefLink">2.4-6</span></a>). On typical groups of order 16 and order 36 (i.e., not <code class="code">[36, 9]</code>), each of these four operations takes roughly the same time. On groups of order 64, some testing indicates that one or two orders of magnitude more time are spent in the final stage, when the algorithm uses <code class="func">SomeRefinedDifferenceSets</code> (<a href="chap2_mj.html#X7E1012C07FB328B4"><span class="RefLink">2.3-4</span></a>) and <code class="func">SmallestEquivalentFreeListOfDifferenceSets</code> (<a href="chap2_mj.html#X8741BBF4811F942A"><span class="RefLink">2.4-6</span></a>). This discrepency is likely to remain or increase for larger order groups, as the number of preimages to check increases exponentially with the number of cosets. For the tested groups of order 64, roughly 60% of the time in the final stage was spent refining, with the remaining 40% spent removing equivalent sets.</p>

<p>Large automorphism groups make removing equivalents time-consuming and large jumps in the size of the normal subgroups used, especially near the end of the algorithm, make refining difficult. So, in general, the algorithm seems to work well when the group has a small automorphism group and many (small) normal subgroups. In addition, the algorithm does better when the values of <span class="SimpleMath">\(k\)</span> that need to be checked are small, as this limits both the number of preimages to check as well as the amount of time required for checking sets and equivalences. It is also generally faster when the final result is a smaller number of difference sets.</p>

<p>There are twenty-six groups of order less than 100 in which the algorithm was not able to complete a search. Fourteen of these groups are prime order cyclic. As simple groups, these groups have no normal subgroups and thus no possibility for refining, which means the algorithm must search every possible subset of size <span class="SimpleMath">\(k\)</span> to find all difference sets of size <span class="SimpleMath">\(k\)</span>. Even for groups of relatively small order, such as order 31, this is infeasible, and with current implementation will overflow memory before even starting the search (one of these groups, <code class="code">[37, 1]</code> is actually feasible to search without this implementation issue, but the others have too many sets to check). The remaining groups have either too few normal subgroups, large jumps in the refining series, large possible values of <span class="SimpleMath">\(k\)</span>, or a combination of these problems.</p>

<p>The next natural cases for exhaustive search are groups of order 100 and order 144, which give the next Hadamard parameters. Unfortunately, preliminary testing indicates that this algorithm is not likely to be able to compute all difference sets for these groups. For example, a typical difference sum in <code class="code">[100, 9]</code> is <code class="code">[5, 4, 3, 3, 0, 3, 2, 3, 2, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 3]</code>, which has roughly <span class="SimpleMath">\(6 \times 10^{16}\)</span> preimage sets to check. In the search for difference sets in <code class="code">[36, 9]</code> the single difference sum <code class="code">[6, 3, 3, 3]</code>, with around <span class="SimpleMath">\(3 \times 10^7\)</span> preimages, takes around 300 seconds to search. Thus even if we could check sets in <code class="code">[100, 9]</code> as fast as in <code class="code">[36, 9]</code>, the search would take roughly 20000 years. Some testing suggests that coding pieces of the algorithm in C could give one or two orders of magnitude of speedup, but even further speedup is required to make the search feasible, so some other improvements, either in theory or implementation, are needed as well.</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap2_mj.html">[Previous Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  </div>

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

98%


¤ Dauer der Verarbeitung: 0.12 Sekunden  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.