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:  sage8.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: 
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 illnamed.
Change History (16)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
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 followup: ↓ 4 Changed 3 years ago by
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
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
 Branch set to u/chapoton/24846
 Commit set to 4face89d62105c7bced9a7f359f3f438cd8c2118
 Milestone changed from sage8.2 to sage8.3
 Status changed from new to needs_review
New commits:
4face89  make so that face lattice is a lattice

comment:6 Changed 3 years ago by
 Cc jmantysalo added
comment:7 Changed 3 years ago by
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
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
 Commit changed from 4face89d62105c7bced9a7f359f3f438cd8c2118 to 8ab7591cec298618ea9c5cece1884061fb84a66e
Branch pushed to git repo; I updated commit sha1. New commits:
8ab7591  fixing doctest

comment:10 Changed 3 years ago by
Please, could someone who is interested do the benchmarking ?
comment:11 Changed 3 years ago by
 Commit changed from 8ab7591cec298618ea9c5cece1884061fb84a66e to fd0d824272dec0ae3a72fc2d3044b7a6d72d88c2
Branch pushed to git repo; I updated commit sha1. New commits:
fd0d824  fixing mistake, plus fixing pyflakes warning

comment:12 Changed 3 years ago by
comment:13 Changed 3 years ago by
 Commit changed from fd0d824272dec0ae3a72fc2d3044b7a6d72d88c2 to 3ff3b60d7f573e04367f06e15e62d464052068ab
Branch pushed to git repo; I updated commit sha1. New commits:
3ff3b60  better handling of file / IOBase

comment:14 Changed 3 years ago by
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
 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
 Branch changed from u/chapoton/24846 to 3ff3b60d7f573e04367f06e15e62d464052068ab
 Resolution set to fixed
 Status changed from positive_review to closed
Is it illnamed or illimplemented, if it is in need of a revamp?)