Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#20669 closed enhancement (fixed)

LatticePoset: add function to get all sublattices

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.3
Component: combinatorics Keywords: lattice poset, days78
Cc: tscrim Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 1bb87bd (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

This patch will add a function that gives all sublattices of a lattice.

Change History (16)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/all_sublattices

comment:2 Changed 5 years ago by jmantysalo

  • Cc tscrim added
  • Commit set to 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488
  • Status changed from new to needs_review

Travis selected as a random victim for review.


New commits:

1bb87bdAdd sublattices().

comment:3 follow-up: Changed 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to needs_work

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

comment:4 in reply to: ↑ 3 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

For example after B4 = Posets.BooleanLattice(4) it takes 0,02 seconds to count 732 sublattices with len(list(B4._hasse_diagram.sublattices_iterator(set(), 0))), whereas it took 1,13 seconds with len(B4.sublattices()). So if one wants to optimize lattices, then bottleneck is usually not in hasse_diagram.py but in lattices.py.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

comment:5 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).

For example after B4 = Posets.BooleanLattice(4) it takes 0,02 seconds to count 732 sublattices with len(list(B4._hasse_diagram.sublattices_iterator(set(), 0))), whereas it took 1,13 seconds with len(B4.sublattices()). So if one wants to optimize lattices, then bottleneck is usually not in hasse_diagram.py but in lattices.py.

I don't disagree with this, but you should not be creating the lattice by using the LatticePoset but directly creating the necessary data and passing it to FiniteLatticePoset. This avoids the extra overhead and checks that is in the Poset code.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

comment:6 in reply to: ↑ 5 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

Replying to jmantysalo:

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).

Well, now it took only 20 seconds to make ChainPoset(1000). So yes, it is theoretically possible to run this kind of computations. But then, recursion limit can be changed.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.

---

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

comment:7 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

Replying to jmantysalo:

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added.

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)

I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."

comment:9 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.

I don't see anything that would prevent a cythonization; the HasseDiagram class only has single inheritance (and cython probably has improved since when you discussed this).

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)

I know you didn't, but it first seemed like you were trying to tell me how to review this. My reply was condescending, to which I apologize as well.

I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."

I don't think we are in an open-ended discussion because I am proposing a (single) concrete/explicit alternative implementation. While I am not strictly opposed to the current implementation, I think there is a relatively easy way to improve it. I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).

comment:10 in reply to: ↑ 9 Changed 5 years ago by jmantysalo

Replying to tscrim:

I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).

Of course. I can review it then, and hopefully you can check docstrings I wrote.

Version 0, edited 5 years ago by jmantysalo (next)

comment:11 Changed 5 years ago by jmantysalo

Just pinging...

comment:12 Changed 5 years ago by jmantysalo

ping.

comment:13 Changed 5 years ago by tscrim

  • Status changed from needs_work to positive_review

So, I just haven't had time to do the algorithm change that I wanted. This works as claimed (although I was not able to completely prove its correctness). Thus this works as a first implementation, and so positive review (I can change it to a backtrak on a follow-up ticket if and when I have more time).

PS - Sorry it took so long.

Last edited 5 years ago by tscrim (previous) (diff)

comment:14 Changed 5 years ago by jmantysalo

Thanks Travis!

Here is the followup: #20921.

comment:15 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/all_sublattices to 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:16 Changed 5 years ago by tscrim

  • Commit 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488 deleted
  • Keywords lattice poset days78 added; latticeposet removed
Note: See TracTickets for help on using tickets.