Improve face iterator for simple/simplicial polytopes

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

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

[gh-kliem]

Needs rebase.

[gh-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]

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.

[git]

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

​01b4154

typo

[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

[gh-kliem]

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.

[gh-kliem]

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.

[git]

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 }

[tscrim]

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.

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

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

[tscrim]

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

[gh-kliem]

Thank you.

[gh-kliem]

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.

[gh-kliem]

merge conflict

[git]

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

[git]

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

[gh-kliem]

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

[git]

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

[gh-kliem]

Rebased.