Opened 10 months ago
Closed 5 months ago
#30040 closed enhancement (fixed)
Improve face iterator for simple/simplicial polytopes
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.3 |
Component: | geometry | Keywords: | face iterator, simple, simplicial, polytopes |
Cc: | jipilab, gh-LaisRast, tscrim | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 63b7bd6 (Commits, GitHub, GitLab) | Commit: | 63b7bd60cfc649e3d4448f970295eb7b7a977adf |
Dependencies: | #29676, #29681, #30428, #30429, #30458 | Stopgaps: |
Description (last modified by )
So far the face iterator for polyhedra assumes the diamond property of the lattice only. The special case of simple/simplicial polytopes is not exploited. In this case all intervals not containing zero of the lattice are boolean (for simplicial polytopes we use the dual algorithm).
We alter the algorithm to work for lattices where every interval not containing zero is a boolean sublattice. We may even drop any further conditions on the lattice. So we may apply the algorithm to lattices, where some "edges" have only one atom. Thus the algorithm can in principle be applied to simplicial complexes now in dual mode ("edges" with a single atom correspond to "ridges" only contained in one maximal face). The key observations are:
- To check whether an intersection of faces is zero, we check whether the atom-representation is zero. Although not unique (in case the diamond property is relaxed), it works to distinguish from zero.
- To intersect we now additionally unite the coatom representation. This gives the correct representation of the new face unless the intersection is zero.
- An intersection of two facets has always codimension 1, if not empty (they contain a common atom and are thus contained in a common boolean sublattice).
- To mark a face as visited, we save its coatom representation in
visited_all_coatom_rep
.
- To check whether we have seen a face already, we check containment of the coatom representation.
This algorithm performs much better and is also asymptotically better.
Before this ticket:
sage: P = polytopes.permutahedron(7) sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 85.7 ms, sys: 0 ns, total: 85.7 ms Wall time: 85.1 ms (1, 5040, 15120, 16800, 8400, 1806, 126, 1) sage: P = polytopes.associahedron(['A',9], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 1.11 s, sys: 23 µs, total: 1.11 s Wall time: 1.11 s (1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1) sage: P = polytopes.associahedron(['A',10], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 21 s, sys: 19.8 ms, total: 21 s Wall time: 21 s (1, 58786, 293930, 629850, 755820, 556920, 259896, 76440, 13650, 1365, 65, 1) sage: P = polytopes.hypercube(14, backend='field') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 5.27 s, sys: 11.9 ms, total: 5.28 s Wall time: 5.27 s (1, 16384, 114688, 372736, 745472, 1025024, 1025024, 768768, 439296, 192192, 64064, 16016, 2912, 364, 28, 1) sage: P = polytopes.hypercube(16, backend='field') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 3min 11s, sys: 152 ms, total: 3min 11s Wall time: 3min 11s (1, 65536, 524288, 1966080, 4587520, 7454720, 8945664, 8200192, 5857280, 3294720, 1464320, 512512, 139776, 29120, 4480, 480, 32, 1)
With this ticket:
sage: P = polytopes.permutahedron(7) sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 15.5 ms, sys: 0 ns, total: 15.5 ms Wall time: 15.5 ms (1, 5040, 15120, 16800, 8400, 1806, 126, 1) sage: P = polytopes.associahedron(['A',9], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 161 ms, sys: 14 µs, total: 161 ms Wall time: 161 ms (1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1) sage: P = polytopes.associahedron(['A',10], backend='normaliz') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 2.17 s, sys: 0 ns, total: 2.17 s Wall time: 2.17 s (1, 58786, 293930, 629850, 755820, 556920, 259896, 76440, 13650, 1365, 65, 1) sage: P = polytopes.hypercube(14, backend='field') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 1.1 s, sys: 0 ns, total: 1.1 s Wall time: 1.1 s (1, 16384, 114688, 372736, 745472, 1025024, 1025024, 768768, 439296, 192192, 64064, 16016, 2912, 364, 28, 1) sage: P = polytopes.hypercube(16, backend='field') sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 28 s, sys: 23.3 ms, total: 28 s Wall time: 28 s (1, 65536, 524288, 1966080, 4587520, 7454720, 8945664, 8200192, 5857280, 3294720, 1464320, 512512, 139776, 29120, 4480, 480, 32, 1)
Change History (32)
comment:1 Changed 10 months ago by
- Branch set to public/30040
- Commit set to ceab5037b843a1a65ece192d2ba8652e208d0011
- Status changed from new to needs_review
comment:2 Changed 10 months ago by
- Component changed from PLEASE CHANGE to geometry
comment:3 Changed 8 months ago by
- Cc tscrim added
comment:5 Changed 8 months ago by
- Description modified (diff)
comment:6 Changed 8 months ago by
- Description modified (diff)
comment:7 Changed 8 months ago by
- Dependencies changed from #28894 to #30428
comment:8 Changed 8 months ago by
- Dependencies changed from #30428 to #30428, #30429
comment:9 Changed 8 months ago by
- Work issues changed from There is a merge conflict with #29676. Whichever takes longer needs to be rebased. to There are merge conflicts with #29676, #29681. Whichever takes longer needs to be rebased.
comment:10 Changed 8 months ago by
- Branch changed from public/30040 to public/30040-reb
- Commit changed from ceab5037b843a1a65ece192d2ba8652e208d0011 to 7ffac00417d0143aafefec4c21e3ad59a45cac06
- Status changed from needs_work to needs_review
New commits:
39f3a38 | directly check is_simple/is_simplicial
|
fe880a4 | input of `intersection` in standard order
|
bc27cd1 | Merge branch 'public/30429' of git://trac.sagemath.org/sage into public/30040
|
4478f3c | unite and is_zero for bit_vectors
|
131c065 | add a specialized `get_next_level_simple`
|
bc00d42 | prepare slightly modified algorithm for simple/simplicial polytopes
|
4fdc787 | faster algorithm for simple/simplicial polytopes
|
4724d3c | small fixes
|
0297853 | improvements in documentation
|
7ffac00 | changes in 30429
|
comment:11 Changed 8 months ago by
Typo: intervalls
-> intervals
Bikeshedding: Personally, I find sizeof(uint64_t **)
confusing compared to sizeof(uint64_t**)
, where IMO is more indicative that it is a pointer. Feel free to ignore this comment.
I feel like #29676 and #29681 are more natural as dependencies of this ticket given their changes, but that is not a strong opinion. I am happy to do the review of those tickets as well. Also, beyond these to things above, this ticket LGTM.
comment:12 Changed 8 months ago by
- Commit changed from 7ffac00417d0143aafefec4c21e3ad59a45cac06 to 01b4154149fcc31347e8591874aa1668907aa315
Branch pushed to git repo; I updated commit sha1. New commits:
01b4154 | typo
|
comment:13 Changed 8 months ago by
- At some point I started doing it like
cdef uint64_t *foo
, hence thesizeof(uint64_t *)
.
This works well, because you can legally do
cdef uint64_t *foo, *foo2
, however I quickly stopped that because I got warnings that I'm not supposed to do this.
Once you start declaring each pointer in its own line, you can go to
cdef uint64_t* foo
, which is more natural, I agree. I just didn't yet. I think I should have a seperate ticket that gets this stuff in order in the entire folder. At the moment everything is one style, which is also desirable, I think.
comment:14 Changed 8 months ago by
- Status changed from needs_review to needs_work
Actually, there is a mistake.
To use the coatom representation to a mark a face as visited will work for polyhedra, but does require the uniqueness of the coatom representation. So this will not work for simplicial complexes.
comment:15 Changed 8 months ago by
- Status changed from needs_work to needs_review
Never mind. I should have read closely and rethought. The atom-representation is not unique. This is the entire point of worrying about the coatom representation. It's not because it is shorter, but because this is the only thing that will work for simplicial complexes.
comment:16 Changed 8 months ago by
- Commit changed from 01b4154149fcc31347e8591874aa1668907aa315 to accea52802a9bcf8f3aea69bd4489ecdcaad94e8
comment:17 Changed 8 months ago by
- Dependencies changed from #30428, #30429 to #30428, #30429, #30458
comment:18 Changed 8 months ago by
- Reviewers set to Travis Scrimshaw
comment:19 Changed 8 months ago by
- Dependencies changed from #30428, #30429, #30458 to #29676, #29681, #30428, #30429, #30458
- Status changed from needs_review to needs_work
- Work issues There are merge conflicts with #29676, #29681. Whichever takes longer needs to be rebased. deleted
comment:20 Changed 8 months ago by
- Branch changed from public/30040-reb to public/30040-reb2
- Commit changed from accea52802a9bcf8f3aea69bd4489ecdcaad94e8 to ed6e966209266875d61895cf8112672675b17960
- Status changed from needs_work to needs_review
Last 10 new commits:
5cf6261 | Merge branch 'u/gh-kliem/outsource_inclusion_maximal' of git://trac.sagemath.org/sage into public/30040-reb2
|
7f5b19f | unite and is_zero for bit_vectors
|
1496bfd | add a specialized `get_next_level_simple`
|
fc4784a | changes in 30429
|
81ba2e0 | simplify `get_next_level_simple by 30458
|
9cece74 | prepare slightly modified algorithm for simple/simplicial polytopes
|
fe5852a | typo
|
1510386 | faster algorithm for simple/simplicial polytopes
|
86c564a | small fixes
|
ed6e966 | improvements in documentation
|
comment:21 Changed 8 months ago by
Putting all five dependencies together works cleanly.
Putting in the commits of this ticket was annoying but pretty much trivial.
It's all about figuring out, where those things have moved (and that self.structure
is now structptr[0]
in the nogil
functions).
comment:22 follow-up: ↓ 24 Changed 8 months ago by
If the patchbot comes back green, you can set a positive review on my behalf.
comment:23 Changed 8 months ago by
Thank you.
comment:24 in reply to: ↑ 22 Changed 8 months ago by
- Status changed from needs_review to positive_review
Replying to tscrim:
If the patchbot comes back green, you can set a positive review on my behalf.
Startup time warning, but I'm not dealing with any startup object, so I think it's not my fault.
comment:26 Changed 7 months ago by
- Commit changed from ed6e966209266875d61895cf8112672675b17960 to 40e66678e274d9e6a45f140a8c8a1f19042582cd
Branch pushed to git repo; I updated commit sha1. New commits:
40e6667 | Merge branch 'u/gh-kliem/improved_count_atoms' of git://trac.sagemath.org/sage into public/30040-reb2
|
comment:27 Changed 7 months ago by
- Commit changed from 40e66678e274d9e6a45f140a8c8a1f19042582cd to 242cba7416b504da86d2f8f9c3712a9a9e7b6438
Branch pushed to git repo; I updated commit sha1. New commits:
242cba7 | Merge branch 'develop' of git://trac.sagemath.org/sage into public/30040-reb2
|
comment:28 Changed 7 months ago by
- Status changed from needs_work to positive_review
Tests still pass. It really appears to be a question in what order you merge.
comment:29 Changed 7 months ago by
- Commit changed from 242cba7416b504da86d2f8f9c3712a9a9e7b6438 to 63b7bd60cfc649e3d4448f970295eb7b7a977adf
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. Last 10 new commits:
5311cdf | grammar
|
eef6cf5 | unite and is_zero for bit_vectors
|
a4fa8cf | add a specialized `get_next_level_simple`
|
07b9746 | changes in 30429
|
c51fe62 | simplify `get_next_level_simple by 30458
|
f3e2ddc | prepare slightly modified algorithm for simple/simplicial polytopes
|
edad681 | typo
|
5939b5d | faster algorithm for simple/simplicial polytopes
|
f997cec | small fixes
|
63b7bd6 | improvements in documentation
|
comment:31 Changed 6 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:32 Changed 5 months ago by
- Branch changed from public/30040-reb2 to 63b7bd60cfc649e3d4448f970295eb7b7a977adf
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
important attributes of iterator in structure
src/simplification of doctests
fixed failing doctest
bad alignment causing bug noticed in #28982
Merge branch 'public/28894-reb5' of git://trac.sagemath.org/sage into develop
prepare slightly modified algorithm for simple/simplicial polytopes
faster algorithm for simple/simplicial polytopes
small fixes
improvements in documentation