Opened 19 months ago
Closed 14 months ago
#30040 closed enhancement (fixed)
Improve face iterator for simple/simplicial polytopes
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  geometry  Keywords:  face iterator, simple, simplicial, polytopes 
Cc:  jipilab, ghLaisRast, 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 atomrepresentation 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 19 months ago by
 Branch set to public/30040
 Commit set to ceab5037b843a1a65ece192d2ba8652e208d0011
 Status changed from new to needs_review
comment:2 Changed 19 months ago by
 Component changed from PLEASE CHANGE to geometry
comment:3 Changed 17 months ago by
 Cc tscrim added
comment:5 Changed 17 months ago by
 Description modified (diff)
comment:6 Changed 17 months ago by
 Description modified (diff)
comment:7 Changed 17 months ago by
 Dependencies changed from #28894 to #30428
comment:8 Changed 17 months ago by
 Dependencies changed from #30428 to #30428, #30429
comment:9 Changed 17 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 17 months ago by
 Branch changed from public/30040 to public/30040reb
 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 17 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 17 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 17 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 17 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 17 months ago by
 Status changed from needs_work to needs_review
Never mind. I should have read closely and rethought. The atomrepresentation 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 17 months ago by
 Commit changed from 01b4154149fcc31347e8591874aa1668907aa315 to accea52802a9bcf8f3aea69bd4489ecdcaad94e8
comment:17 Changed 17 months ago by
 Dependencies changed from #30428, #30429 to #30428, #30429, #30458
comment:18 Changed 17 months ago by
 Reviewers set to Travis Scrimshaw
comment:19 Changed 17 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 17 months ago by
 Branch changed from public/30040reb to public/30040reb2
 Commit changed from accea52802a9bcf8f3aea69bd4489ecdcaad94e8 to ed6e966209266875d61895cf8112672675b17960
 Status changed from needs_work to needs_review
Last 10 new commits:
5cf6261  Merge branch 'u/ghkliem/outsource_inclusion_maximal' of git://trac.sagemath.org/sage into public/30040reb2

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 17 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 followup: ↓ 24 Changed 17 months ago by
If the patchbot comes back green, you can set a positive review on my behalf.
comment:23 Changed 17 months ago by
Thank you.
comment:24 in reply to: ↑ 22 Changed 17 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:25 Changed 17 months ago by
 Status changed from positive_review to needs_work
merge conflict
comment:26 Changed 17 months ago by
 Commit changed from ed6e966209266875d61895cf8112672675b17960 to 40e66678e274d9e6a45f140a8c8a1f19042582cd
Branch pushed to git repo; I updated commit sha1. New commits:
40e6667  Merge branch 'u/ghkliem/improved_count_atoms' of git://trac.sagemath.org/sage into public/30040reb2

comment:27 Changed 17 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/30040reb2

comment:28 Changed 17 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 17 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 15 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:32 Changed 14 months ago by
 Branch changed from public/30040reb2 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/28894reb5' 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