#25895 closed enhancement (fixed)

LatticePoset, optimize congruence-related functions for trivial cases

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-8.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) Commit: 16b2719be5edf9aa357bda3bbcfaeb7295abe63f
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

This patch adds an internal function to find "double-double -irreducible". To be used for counting out trivial cases for is_isoform etc.

Change History (12)

comment:1 Changed 17 months ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • 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 17 months ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet__optimize_congruence_related_functions_for_trivial_cases

comment:3 Changed 17 months ago by git

  • Commit set to 4b1799d1d4103c45e4b78103a4f5f16502d6fb31

Branch pushed to git repo; I updated commit sha1. New commits:

4b1799dAdd function for trivial congruence.

comment:4 follow-up: Changed 17 months ago by tscrim

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.

Last edited 17 months ago by tscrim (previous) (diff)

comment:5 Changed 17 months ago by git

  • Commit changed from 4b1799d1d4103c45e4b78103a4f5f16502d6fb31 to 3b3b08c871c60fa26bdc884ea912320b91138f03

Branch pushed to git repo; I updated commit sha1. New commits:

3b3b08cMerge branch 'develop' into t/25895/latticeposet__optimize_congruence_related_functions_for_trivial_cases

comment:6 Changed 17 months ago by git

  • Commit changed from 3b3b08c871c60fa26bdc884ea912320b91138f03 to 16b2719be5edf9aa357bda3bbcfaeb7295abe63f

Branch pushed to git repo; I updated commit sha1. New commits:

16b2719Add example use case.

comment:7 in reply to: ↑ 4 Changed 17 months ago by jmantysalo

Replying to tscrim:

I think it is generally better to have at least one use-case in the same ticket.

Done this. If Lats is a list of all 10-element 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 17 months ago by tscrim

  • 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 17 months ago by jmantysalo

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 follow-up: Changed 17 months ago by 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. (Although perhaps stronger properties are easier to test for in general?)

comment:11 in reply to: ↑ 10 Changed 17 months ago by jmantysalo

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 16 months ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.