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

Priority:  major  Milestone:  sage8.4 
Component:  combinatorics  Keywords:  sagedays@icerm 
Cc:  Travis Scrimshaw, Frédéric 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
Authors:  → Jori Mäntysalo 

Cc:  Travis Scrimshaw Frédéric Chapoton added 
Component:  PLEASE CHANGE → combinatorics 
Description:  modified (diff) 
Status:  new → needs_review 
Type:  PLEASE CHANGE → enhancement 
comment:2 Changed 4 years ago by
Branch:  → u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases 

comment:3 Changed 4 years ago by
Commit:  → 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 better to have at least one usecase in the same ticket.
comment:5 Changed 4 years ago by
Commit:  4b1799d1d4103c45e4b78103a4f5f16502d6fb31 → 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:  3b3b08c871c60fa26bdc884ea912320b91138f03 → 16b2719be5edf9aa357bda3bbcfaeb7295abe63f 

Branch pushed to git repo; I updated commit sha1. New commits:
16b2719  Add example use case.

comment:7 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:  → Travis Scrimshaw 
Status:  needs_review → 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 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:  u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases → 16b2719be5edf9aa357bda3bbcfaeb7295abe63f 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
Add function for trivial congruence.