Opened 4 years ago
Closed 4 years ago
#25895 closed enhancement (fixed)
LatticePoset, optimize congruencerelated functions for trivial cases
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  combinatorics  Keywords:  sagedays@icerm 
Cc:  tscrim, chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  16b2719 (Commits, GitHub, GitLab)  Commit:  16b2719be5edf9aa357bda3bbcfaeb7295abe63f 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch adds an internal function to find "doubledouble irreducible". To be used for counting out trivial cases for is_isoform
etc.
Change History (12)
comment:1 Changed 4 years ago by
 Cc tscrim chapoton added
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 4 years ago by
 Branch set to u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases
comment:3 Changed 4 years ago by
 Commit set to 4b1799d1d4103c45e4b78103a4f5f16502d6fb31
comment:4 followup: ↓ 7 Changed 4 years ago by
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 usecase in the same ticket.
comment:5 Changed 4 years ago by
 Commit changed from 4b1799d1d4103c45e4b78103a4f5f16502d6fb31 to 3b3b08c871c60fa26bdc884ea912320b91138f03
Branch pushed to git repo; I updated commit sha1. New commits:
3b3b08c  Merge branch 'develop' into t/25895/latticeposet__optimize_congruence_related_functions_for_trivial_cases

comment:6 Changed 4 years ago by
 Commit changed from 3b3b08c871c60fa26bdc884ea912320b91138f03 to 16b2719be5edf9aa357bda3bbcfaeb7295abe63f
Branch pushed to git repo; I updated commit sha1. New commits:
16b2719  Add example use case.

comment:7 in reply to: ↑ 4 Changed 4 years ago by
Replying to tscrim:
I think it is generally better to have at least one usecase in the same ticket.
Done this. If Lats
is a list of all 10element lattices, then the time for
sum(1 for L in Lats if L.is_uniform())
drops from 26 seconds to 9 seconds with this patch.
comment:8 Changed 4 years ago by
 Keywords sagedays@icerm added
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM. Thanks. Nice speedup too.
comment:9 Changed 4 years ago by
Thanks.
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?
At the other extreme we have for example is_orthocomplemented
, where we start by checking that the number of elements is even; here the quick test is extremely cheap.
comment:10 followup: ↓ 11 Changed 4 years ago by
Because the test for distributive is relatively expensive (and a stronger property?), I would not do it. One possibility is putting a .. NOTE::
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?)
comment:11 in reply to: ↑ 10 Changed 4 years ago by
Replying to tscrim:
Because the test for distributive is relatively expensive (and a stronger property?), I would not do it. One possibility is putting a
.. NOTE::
in the doc saying something like in your comment: that the distributive test is faster but more likely to fail.
Maybe... But that might depend on use case.
(Although perhaps stronger properties are easier to test for in general?)
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.
comment:12 Changed 4 years ago by
 Branch changed from u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases to 16b2719be5edf9aa357bda3bbcfaeb7295abe63f
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Add function for trivial congruence.