Improve face iterator for simple/simplicial polytopes

[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)

Depends on #29676 Depends on #29681 Depends on #30428 Depends on #30429 Depends on #30458

CC: @jplab @LaisRast @tscrim

Component: geometry

Keywords: face iterator, simple, simplicial, polytopes

Author: Jonathan Kliem

Branch/Commit: 63b7bd6

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/30040

[kliem]

New commits:

0c44221	important attributes of iterator in structure
efb0bd3	src/simplification of doctests
53fd2a2	fixed failing doctest
142d3a8	bad alignment causing bug noticed in #28982
2b07f03	Merge branch 'public/28894-reb5' of git://trac.sagemath.org/sage into develop
33804bd	prepare slightly modified algorithm for simple/simplicial polytopes
99579b3	faster algorithm for simple/simplicial polytopes
46d1eb6	small fixes
ceab503	improvements in documentation

[kliem]

Branch: public/30040

[kliem]

Commit: ceab503

[kliem]

comment:4

Needs rebase.

[kliem]

Description changed:

--- 
+++ 
@@ -7,7 +7,7 @@

 - To intersect we now additionally unite the coatom representation. This gives the correct representation of the new face unless the intersection is zero.

-- To see whether a new face is of codimension one, we check whether the difference of the length of coatom representations is one.
+- An intersection of two facets has always codimension, 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`.

[kliem]

Description changed:

--- 
+++ 
@@ -7,7 +7,7 @@

 - 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, if not empty (they contain a common atom and are thus contained in a common boolean sublattice).
+- 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`.

[kliem]

Changed dependencies from #28894 to #30428

[kliem]

Changed dependencies from #30428 to #30428, #30429

[kliem]

Changed work issues 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.

[kliem]

Changed branch from public/30040 to public/30040-reb

[kliem]

Changed commit from ceab503 to 7ffac00

[kliem]

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

[tscrim]

comment:11

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7ffac00 to 01b4154

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

01b4154

typo

[kliem]

comment:13

• 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

[kliem]

comment:14

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.

[kliem]

comment:15

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 01b4154 to accea52

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

20a39b6	outsource inclusion maximal
b672fca	removed redundant function
f62e770	merge in #30458
accea52	missing }

[kliem]

Changed dependencies from #30428, #30429 to #30428, #30429, #30458

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:18

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.

[kliem]

Changed work issues from There are merge conflicts with #29676, #29681. Whichever takes longer needs to be rebased. to none

[kliem]

Changed dependencies from #30428, #30429, #30458 to #29676, #29681, #30428, #30429, #30458

[kliem]

Changed commit from accea52 to ed6e966

[kliem]

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

[kliem]

Changed branch from public/30040-reb to public/30040-reb2

[kliem]

comment:21

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).

[tscrim]

comment:22

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

[kliem]

comment:23

Thank you.

[kliem]

comment:24

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.

[kliem]

comment:25

merge conflict

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ed6e966 to 40e6667

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 40e6667 to 242cba7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[kliem]

comment:28

Tests still pass. It really appears to be a question in what order you merge.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 242cba7 to 63b7bd6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[kliem]

comment:30

Rebased.

[vbraun]

Changed branch from public/30040-reb2 to 63b7bd6