Opened 4 years ago
Closed 4 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: |
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 4 years ago by
comment:2 Changed 4 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 follow-up: ↓ 4 Changed 4 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 4 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 4 years ago by
- 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:
4face89 | make so that face lattice is a lattice
|
comment:6 Changed 4 years ago by
- Cc jmantysalo added
comment:7 Changed 4 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 4 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 4 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 4 years ago by
Please, could someone who is interested do the benchmarking ?
comment:11 Changed 4 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 4 years ago by
comment:13 Changed 4 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 4 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 4 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 4 years ago by
- Branch changed from u/chapoton/24846 to 3ff3b60d7f573e04367f06e15e62d464052068ab
- Resolution set to fixed
- Status changed from positive_review to closed
Is it ill-named or ill-implemented, if it is in need of a revamp?-)