Opened 13 months ago

Closed 8 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:

Status badges

Description (last modified by gh-kliem)

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 13 months ago by gh-kliem

  • Branch set to public/30040
  • Commit set to ceab5037b843a1a65ece192d2ba8652e208d0011
  • Status changed from new to needs_review

New commits:

0c44221important attributes of iterator in structure
efb0bd3src/simplification of doctests
53fd2a2fixed failing doctest
142d3a8bad alignment causing bug noticed in #28982
2b07f03Merge branch 'public/28894-reb5' of git://trac.sagemath.org/sage into develop
33804bdprepare slightly modified algorithm for simple/simplicial polytopes
99579b3faster algorithm for simple/simplicial polytopes
46d1eb6small fixes
ceab503improvements in documentation

comment:2 Changed 13 months ago by gh-kliem

  • Component changed from PLEASE CHANGE to geometry

comment:3 Changed 12 months ago by mkoeppe

  • Cc tscrim added

comment:4 Changed 11 months ago by gh-kliem

  • Status changed from needs_review to needs_work

Needs rebase.

comment:5 Changed 11 months ago by gh-kliem

  • Description modified (diff)

comment:6 Changed 11 months ago by gh-kliem

  • Description modified (diff)

comment:7 Changed 11 months ago by gh-kliem

  • Dependencies changed from #28894 to #30428

comment:8 Changed 11 months ago by gh-kliem

  • Dependencies changed from #30428 to #30428, #30429

comment:9 Changed 11 months ago by gh-kliem

  • 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 11 months ago by gh-kliem

  • 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:

39f3a38directly check is_simple/is_simplicial
fe880a4input of `intersection` in standard order
bc27cd1Merge branch 'public/30429' of git://trac.sagemath.org/sage into public/30040
4478f3cunite and is_zero for bit_vectors
131c065add a specialized `get_next_level_simple`
bc00d42prepare slightly modified algorithm for simple/simplicial polytopes
4fdc787faster algorithm for simple/simplicial polytopes
4724d3csmall fixes
0297853improvements in documentation
7ffac00changes in 30429

comment:11 Changed 11 months ago by tscrim

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 11 months ago by git

  • Commit changed from 7ffac00417d0143aafefec4c21e3ad59a45cac06 to 01b4154149fcc31347e8591874aa1668907aa315

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

01b4154typo

comment:13 Changed 11 months ago by gh-kliem

  • At some point I started doing it like cdef uint64_t *foo, hence the sizeof(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.

  • In principal #29676 and #29681 are more natural as dependencies of this ticket than vice versa (both are somewhat nice to review at the moment). I agree. But I don't want them to be in the way (in case they are sitting there without review). I'm happy to rebase whatever makes sense

comment:14 Changed 11 months ago by gh-kliem

  • 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 11 months ago by gh-kliem

  • 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 11 months ago by git

  • Commit changed from 01b4154149fcc31347e8591874aa1668907aa315 to accea52802a9bcf8f3aea69bd4489ecdcaad94e8

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

20a39b6outsource inclusion maximal
b672fcaremoved redundant function
f62e770merge in #30458
accea52missing }

comment:17 Changed 11 months ago by gh-kliem

  • Dependencies changed from #30428, #30429 to #30428, #30429, #30458

comment:18 Changed 11 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

I just did the review of #29676 and #29681. So if you could rebase this based on those and just let me know if there are any non-trivial changes, then I should be able to finish the review of this ticket quickly.

comment:19 Changed 11 months ago by gh-kliem

  • 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 11 months ago by gh-kliem

  • 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:

5cf6261Merge branch 'u/gh-kliem/outsource_inclusion_maximal' of git://trac.sagemath.org/sage into public/30040-reb2
7f5b19funite and is_zero for bit_vectors
1496bfdadd a specialized `get_next_level_simple`
fc4784achanges in 30429
81ba2e0simplify `get_next_level_simple by 30458
9cece74prepare slightly modified algorithm for simple/simplicial polytopes
fe5852atypo
1510386faster algorithm for simple/simplicial polytopes
86c564asmall fixes
ed6e966improvements in documentation

comment:21 Changed 11 months ago by gh-kliem

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: Changed 11 months ago by tscrim

If the patchbot comes back green, you can set a positive review on my behalf.

comment:23 Changed 11 months ago by gh-kliem

Thank you.

comment:24 in reply to: ↑ 22 Changed 11 months ago by gh-kliem

  • 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 11 months ago by gh-kliem

  • Status changed from positive_review to needs_work

merge conflict

comment:26 Changed 11 months ago by git

  • Commit changed from ed6e966209266875d61895cf8112672675b17960 to 40e66678e274d9e6a45f140a8c8a1f19042582cd

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

40e6667Merge branch 'u/gh-kliem/improved_count_atoms' of git://trac.sagemath.org/sage into public/30040-reb2

comment:27 Changed 11 months ago by git

  • Commit changed from 40e66678e274d9e6a45f140a8c8a1f19042582cd to 242cba7416b504da86d2f8f9c3712a9a9e7b6438

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

242cba7Merge branch 'develop' of git://trac.sagemath.org/sage into public/30040-reb2

comment:28 Changed 11 months ago by gh-kliem

  • 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 11 months ago by git

  • 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:

5311cdfgrammar
eef6cf5unite and is_zero for bit_vectors
a4fa8cfadd a specialized `get_next_level_simple`
07b9746changes in 30429
c51fe62simplify `get_next_level_simple by 30458
f3e2ddcprepare slightly modified algorithm for simple/simplicial polytopes
edad681typo
5939b5dfaster algorithm for simple/simplicial polytopes
f997cecsmall fixes
63b7bd6improvements in documentation

comment:30 Changed 11 months ago by gh-kliem

  • Status changed from needs_review to positive_review

Rebased.

comment:31 Changed 9 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:32 Changed 8 months ago by vbraun

  • Branch changed from public/30040-reb2 to 63b7bd60cfc649e3d4448f970295eb7b7a977adf
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.