Sage: Ticket #5931: [with patch, positive review] Greatly speed up sage.combinat.symmetric_group_algebra.e
https://trac.sagemath.org/ticket/5931
<p>
The old code essentially reimplemented the multiplication in the group algebra. The new code accumulates the symmetrizers and antisymmetrizers separately, and then does one multiply at the end. This probably results in the same number of operations, but it avoids creating many intermediate objects, so it is about 10x faster.
</p>
<p>
Also update docs for e and e_hat.
</p>
<p>
Timing on 2.2 GHz Core2Duo running 32-bit Ubuntu 8.04 of
</p>
<p>
from sage.combinat.symmetric_group_algebra import e<br />
</p>
<p>
time dummy=e(<a class="missing wiki">1,2,3,4],[5,6,7?</a>)
</p>
<p>
Before patch:
</p>
<p>
Time: CPU 3.38 s, Wall: 3.73 s
</p>
<p>
After patch:
</p>
<p>
Time: CPU 0.26 s, Wall: 0.40 s
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/5931
Trac 1.1.6jdcWed, 29 Apr 2009 02:02:04 GMTattachment set
https://trac.sagemath.org/ticket/5931
https://trac.sagemath.org/ticket/5931
<ul>
<li><strong>attachment</strong>
set to <em>e.patch</em>
</li>
</ul>
TicketjdcWed, 29 Apr 2009 02:02:13 GMTattachment set
https://trac.sagemath.org/ticket/5931
https://trac.sagemath.org/ticket/5931
<ul>
<li><strong>attachment</strong>
set to <em>doc.patch</em>
</li>
</ul>
TicketjdcWed, 29 Apr 2009 16:08:46 GMT
https://trac.sagemath.org/ticket/5931#comment:1
https://trac.sagemath.org/ticket/5931#comment:1
<p>
I think the main reason the old code was slow was that it multiplied GAP group elements in the inner loop, while the new code in e.patch uses the combinatorial algebra multiplication, which internally multiplies sage Permutations. Another reason the old code was slower is that it looped over the GAP column_stabilizer group multiple times (probably requiring interaction with GAP) and re-computed v.sign() each time. However, I did some tests where I avoid just these problems, and still the new code in e.patch is better, almost certainly because it avoids creating lots of intermediate elements of QSn.
</p>
<p>
We can avoid even more of the intermediate elements of QSn with dict.patch which I will attach below. But it only speeds things up by about 2% in the test I ran, since the runtime is dominated by the antisym*sym multiplication.
</p>
<p>
If we are willing to assume that the entries in the tableau are distinct, I have another method which is 25% faster, but I don't think we want to make that assumption. Just for the record, the point is that if the entries are distinct, then each of the products v*h is distinct, so we can easily construct a dictionary for the final result whose values are plus or minus 1.
</p>
<p>
Summary: I recommend the new dict.patch (which includes the documentation change), but it would also be ok to use e.patch and doc.patch if that method is preferred.
</p>
<p>
PS: Note that these patches seem to reverse the order of multiplication from h*v to v*h. That's because of differing conventions between GAP group elements and permutations.
</p>
<p>
PPS: My latest test case has been e(<a class="missing wiki">1,2,3,4,5],[6,7,8],[9,10],[11?</a>), which takes forever with sage 3.4, but takes 20-30 seconds with the above patches.
</p>
TicketjdcWed, 29 Apr 2009 16:09:48 GMTattachment set
https://trac.sagemath.org/ticket/5931
https://trac.sagemath.org/ticket/5931
<ul>
<li><strong>attachment</strong>
set to <em>dict.patch</em>
</li>
</ul>
<p>
Replaces both e.patch and doc.patch; relative to 3.4
</p>
TicketmabshoffThu, 30 Apr 2009 07:12:06 GMTmilestone set
https://trac.sagemath.org/ticket/5931#comment:2
https://trac.sagemath.org/ticket/5931#comment:2
<ul>
<li><strong>milestone</strong>
set to <em>sage-4.0</em>
</li>
</ul>
TicketmhansenThu, 04 Jun 2009 19:19:14 GMTstatus, summary changed; resolution set
https://trac.sagemath.org/ticket/5931#comment:3
https://trac.sagemath.org/ticket/5931#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Greatly speed up sage.combinat.symmetric_group_algebra.e</em> to <em>[with patch, positive review] Greatly speed up sage.combinat.symmetric_group_algebra.e</em>
</li>
</ul>
<p>
Looks good to me. Thanks for this!
</p>
<p>
Merged in 4.0.1.rc1.
</p>
TicketmhansenSat, 06 Jun 2009 22:37:10 GMTreviewer, merged, author set
https://trac.sagemath.org/ticket/5931#comment:4
https://trac.sagemath.org/ticket/5931#comment:4
<ul>
<li><strong>reviewer</strong>
set to <em>Mike Hansen</em>
</li>
<li><strong>merged</strong>
set to <em>4.0.1.rc1</em>
</li>
<li><strong>author</strong>
set to <em>Dan Christensen</em>
</li>
</ul>
Ticket