Sage: Ticket #25895: LatticePoset, optimize congruence-related functions for trivial cases
https://trac.sagemath.org/ticket/25895
<p>
This patch adds an internal function to find "double-double -irreducible". To be used for counting out trivial cases for <code>is_isoform</code> etc.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/25895
Trac 1.2Jori MäntysaloSun, 22 Jul 2018 07:19:31 GMTstatus, description, component, type changed; author, cc set
https://trac.sagemath.org/ticket/25895#comment:1
https://trac.sagemath.org/ticket/25895#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/25895?action=diff&version=1">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Jori Mäntysalo</em>
</li>
<li><strong>cc</strong>
<em>Travis Scrimshaw</em> <em>Frédéric Chapoton</em> added
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>combinatorics</em>
</li>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>enhancement</em>
</li>
</ul>
TicketJori MäntysaloSun, 22 Jul 2018 07:19:54 GMTbranch set
https://trac.sagemath.org/ticket/25895#comment:2
https://trac.sagemath.org/ticket/25895#comment:2
<ul>
<li><strong>branch</strong>
set to <em>u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases</em>
</li>
</ul>
TicketgitSun, 22 Jul 2018 07:21:30 GMTcommit set
https://trac.sagemath.org/ticket/25895#comment:3
https://trac.sagemath.org/ticket/25895#comment:3
<ul>
<li><strong>commit</strong>
set to <em>4b1799d1d4103c45e4b78103a4f5f16502d6fb31</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=4b1799d1d4103c45e4b78103a4f5f16502d6fb31"><span class="icon"></span>4b1799d</a></td><td><code>Add function for trivial congruence.</code>
</td></tr></table>
TicketTravis ScrimshawSun, 22 Jul 2018 15:59:37 GMT
https://trac.sagemath.org/ticket/25895#comment:4
https://trac.sagemath.org/ticket/25895#comment:4
<p>
How is this method being used? I don't want to add a hidden method that is not used. I think it is generally better to have at least one use-case in the same ticket.
</p>
TicketgitMon, 23 Jul 2018 05:26:29 GMTcommit changed
https://trac.sagemath.org/ticket/25895#comment:5
https://trac.sagemath.org/ticket/25895#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>4b1799d1d4103c45e4b78103a4f5f16502d6fb31</em> to <em>3b3b08c871c60fa26bdc884ea912320b91138f03</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=3b3b08c871c60fa26bdc884ea912320b91138f03"><span class="icon"></span>3b3b08c</a></td><td><code>Merge branch 'develop' into t/25895/latticeposet__optimize_congruence_related_functions_for_trivial_cases</code>
</td></tr></table>
TicketgitMon, 23 Jul 2018 05:53:59 GMTcommit changed
https://trac.sagemath.org/ticket/25895#comment:6
https://trac.sagemath.org/ticket/25895#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>3b3b08c871c60fa26bdc884ea912320b91138f03</em> to <em>16b2719be5edf9aa357bda3bbcfaeb7295abe63f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=16b2719be5edf9aa357bda3bbcfaeb7295abe63f"><span class="icon"></span>16b2719</a></td><td><code>Add example use case.</code>
</td></tr></table>
TicketJori MäntysaloMon, 23 Jul 2018 05:56:56 GMT
https://trac.sagemath.org/ticket/25895#comment:7
https://trac.sagemath.org/ticket/25895#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25895#comment:4" title="Comment 4">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I think it is generally better to have at least one use-case in the same ticket.
</p>
</blockquote>
<p>
Done this. If <code>Lats</code> is a list of all 10-element lattices, then the time for
</p>
<pre class="wiki">sum(1 for L in Lats if L.is_uniform())
</pre><p>
drops from 26 seconds to 9 seconds with this patch.
</p>
TicketTravis ScrimshawMon, 23 Jul 2018 11:34:32 GMTstatus changed; keywords, reviewer set
https://trac.sagemath.org/ticket/25895#comment:8
https://trac.sagemath.org/ticket/25895#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>keywords</strong>
<em>sagedays@icerm</em> added
</li>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
LGTM. Thanks. Nice speedup too.
</p>
TicketJori MäntysaloMon, 23 Jul 2018 11:44:16 GMT
https://trac.sagemath.org/ticket/25895#comment:9
https://trac.sagemath.org/ticket/25895#comment:9
<p>
Thanks.
</p>
<p>
The speedup thing for this kind of functions is hard to decide. It the user asks if a lattice is modular, should we first try to see if it happens to be distributive? If so, it must be also modular and the test was very fast. But then, distributive lattices are "rare". OTOH also lattices with at least one "doubledouble"-irreducible element are "rare", so should we test for those?
</p>
<p>
At the other extreme we have for example <code>is_orthocomplemented</code>, where we start by checking that the number of elements is even; here the quick test is extremely cheap.
</p>
TicketTravis ScrimshawMon, 23 Jul 2018 11:50:13 GMT
https://trac.sagemath.org/ticket/25895#comment:10
https://trac.sagemath.org/ticket/25895#comment:10
<p>
Because the test for distributive is relatively expensive (and a stronger property?), I would not do it. One possibility is putting a <code>.. NOTE::</code> in the doc saying something like in your comment: that the distributive test is faster but more likely to fail. (Although perhaps stronger properties are easier to test for in general?)
</p>
TicketJori MäntysaloMon, 23 Jul 2018 12:23:07 GMT
https://trac.sagemath.org/ticket/25895#comment:11
https://trac.sagemath.org/ticket/25895#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25895#comment:10" title="Comment 10">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Because the test for distributive is relatively expensive (and a stronger property?), I would not do it. One possibility is putting a <code>.. NOTE::</code> in the doc saying something like in your comment: that the distributive test is faster but more likely to fail.
</p>
</blockquote>
<p>
Maybe... But that might depend on use case.
</p>
<blockquote class="citation">
<p>
(Although perhaps stronger properties are easier to test for in general?)
</p>
</blockquote>
<p>
No, for example testing for semimodularity is faster that testing for modularity. But of course one can always test for a stronger property to get sure "yes"-answer, test for a weaker property to get sure "no"-answer, and only when needed to proceed testing the original property.
</p>
TicketVolker BraunSun, 05 Aug 2018 08:15:49 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/25895#comment:12
https://trac.sagemath.org/ticket/25895#comment:12
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases</em> to <em>16b2719be5edf9aa357bda3bbcfaeb7295abe63f</em>
</li>
</ul>
Ticket