Opened 3 years ago

Closed 3 years ago

#24846 closed enhancement (fixed)

Make the face lattice of a polyhedron a lattice

Reported by: jipilab Owned by:
Priority: major Milestone: sage-8.3
Component: geometry Keywords: days93, poset, polytope
Cc: vdelecroix, moritz, mkoeppe, chapoton, jmantysalo Merged in:
Authors: Frédéric Chapoton Reviewers: Jori Mäntysalo
Report Upstream: N/A Work issues:
Branch: 3ff3b60 (Commits, GitHub, GitLab) Commit: 3ff3b60d7f573e04367f06e15e62d464052068ab
Dependencies: Stopgaps:

Status badges

Description

Currently, the output object of the method face_lattice is not a lattice but a finite poset. This is also a good opportunity to revamp the method Hasse_diagram_from_incidences which is ill-named.

Change History (16)

comment:1 Changed 3 years ago by novoselt

Is it ill-named or ill-implemented, if it is in need of a revamp?-)

comment:2 Changed 3 years ago by jipilab

I'd say it is not an exclusive "or" in this case...!

The Hasse diagram is an oriented acyclic graph, whereas what is returned is a poset, not the Hasse diagram of that poset... So this is misleading. And I do not see why we could not readily return a LatticePoset? object if it is already. (Maybe there are some reasons not to do this?)

This function is very handy sometimes and could be used for (abstract) combinatorial polytopes.

comment:3 follow-up: Changed 3 years ago by novoselt

I'm not aware of any reasons to avoid LatticePoset. The current output is either inherited from the old implementation or it was the best I found when rewriting it. One thing I do remember however - some tricks were necessary to construct the poset object fast, naive call to the constructor was taking several times more time than computing that acyclic graph itself.

comment:4 in reply to: ↑ 3 Changed 3 years ago by jipilab

Replying to novoselt:

I'm not aware of any reasons to avoid LatticePoset. The current output is either inherited from the old implementation or it was the best I found when rewriting it. One thing I do remember however - some tricks were necessary to construct the poset object fast, naive call to the constructor was taking several times more time than computing that acyclic graph itself.

Ah! Ok, good to know! It will be worth benchmarking the difference.

comment:5 Changed 3 years ago by chapoton

  • Branch set to u/chapoton/24846
  • Commit set to 4face89d62105c7bced9a7f359f3f438cd8c2118
  • Milestone changed from sage-8.2 to sage-8.3
  • Status changed from new to needs_review

New commits:

4face89make so that face lattice is a lattice

comment:6 Changed 3 years ago by chapoton

  • Cc jmantysalo added

comment:7 Changed 3 years ago by novoselt

So since I mentioned it before - was there any benchmarking/profiling looking into the speed of creating this lattice? It used to matter a lot to me when I was working with thousands of (quite small) polytopes.

comment:8 Changed 3 years ago by jmantysalo

The comment

# In principle, it is recommended to use Poset or in this case perhaps
# even LatticePoset, but it seems to take several times more time
# than the above computation, makes unnecessary copies, and crashes.

can now be removed.

I suppose this is not going to change the speed (meets and joins will be lazy evaluated), but haven't tested that.

comment:9 Changed 3 years ago by git

  • Commit changed from 4face89d62105c7bced9a7f359f3f438cd8c2118 to 8ab7591cec298618ea9c5cece1884061fb84a66e

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

8ab7591fixing doctest

comment:10 Changed 3 years ago by chapoton

Please, could someone who is interested do the benchmarking ?

comment:11 Changed 3 years ago by git

  • Commit changed from 8ab7591cec298618ea9c5cece1884061fb84a66e to fd0d824272dec0ae3a72fc2d3044b7a6d72d88c2

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

fd0d824fixing mistake, plus fixing pyflakes warning

comment:12 Changed 3 years ago by chapoton

  • Authors set to Frédéric Chapoton

comment:13 Changed 3 years ago by git

  • Commit changed from fd0d824272dec0ae3a72fc2d3044b7a6d72d88c2 to 3ff3b60d7f573e04367f06e15e62d464052068ab

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

3ff3b60better handling of file / IOBase

comment:14 Changed 3 years ago by chapoton

timings, before:

sage: P = polytopes.hypercube(4)
sage: %time P.face_lattice()
CPU times: user 44.7 ms, sys: 4.22 ms, total: 48.9 ms
Wall time: 40.8 ms
Finite poset containing 82 elements with distinguished linear extension
sage: P = polytopes.associahedron(['A',4])
sage: %time P.face_lattice()
CPU times: user 95.7 ms, sys: 8.17 ms, total: 104 ms
Wall time: 98.6 ms
Finite poset containing 198 elements with distinguished linear extension

and after

sage: P = polytopes.hypercube(4)
sage: %time P.face_lattice()
CPU times: user 33.4 ms, sys: 8.65 ms, total: 42.1 ms
Wall time: 37.9 ms
Finite lattice containing 82 elements with distinguished linear extension
sage: P = polytopes.associahedron(['A',4])
sage: %time P.face_lattice()
CPU times: user 96.1 ms, sys: 3.9 ms, total: 100 ms
Wall time: 95.6 ms
Finite lattice containing 198 elements with distinguished linear extension

comment:15 Changed 3 years ago by jmantysalo

  • Reviewers set to Jori Mäntysalo
  • Status changed from needs_review to positive_review

All seems to be OK.

comment:16 Changed 3 years ago by vbraun

  • Branch changed from u/chapoton/24846 to 3ff3b60d7f573e04367f06e15e62d464052068ab
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.