Another improvement for face iterator of simple/simplicial polytopes

[kliem]

Follow up on #30040:

If we are in a lattice, such that all intervals [F, G] are boolean, if F is not the lower bound, then any face except the lower bound, has a unique representation as meet of coatoms.

This means that we do not need to mark a face as visited, when removing it from the coatoms.

Before (benchmarks without parallelization):

sage: P = polytopes.cyclic_polytope(10, 22)
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
43.2 ms ± 40 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.associahedron(['A', 8])
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
20.1 ms ± 69.3 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.hypercube(12, backend='field')
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
38.6 ms ± 464 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.Birkhoff_polytope(5)  # neither simple nor simplicial
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
275 ms ± 531 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

After (benchmarks without parallelization):

sage: P = polytopes.cyclic_polytope(10, 22)
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
38.6 ms ± 1.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.associahedron(['A', 8])
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
18.3 ms ± 23.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: P = polytopes.hypercube(12, backend='field')
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
30.9 ms ± 40 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.Birkhoff_polytope(5)  # neither simple nor simplicial
sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
274 ms ± 410 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

CC: @tscrim @yuan-zhou

Component: geometry

Author: Jonathan Kliem

Branch/Commit: 04ca6fb

Reviewer: Travis Scrimshaw

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

[kliem]

Author: Jonathan Kliem

[kliem]

New commits:

04ca6fb

further improvement for face iterator over simple/simplicial polytopes

[kliem]

Branch: public/33645

[kliem]

Commit: 04ca6fb

[kliem]

Description changed:

--- 
+++ 
@@ -2,4 +2,38 @@
 
 If we are in a lattice, such that all intervals `[F, G]` are boolean, if `F` is not the lower bound, then any face except the lower bound, has a unique representation as meet of coatoms.
 
-This means that we do not need to mark a face as visited, but simple removing suffices.
+This means that we do not need to mark a face as visited, when removing it from the coatoms.
+
+Before (benchmarks without parallelization):
+
+```
+sage: P = polytopes.cyclic_polytope(10, 22)
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+43.2 ms ± 40 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
+sage: P = polytopes.associahedron(['A', 8])
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+20.1 ms ± 69.3 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
+sage: P = polytopes.hypercube(12, backend='field')
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+38.6 ms ± 464 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
+sage: P = polytopes.Birkhoff_polytope(5)  # neither simple nor simplicial
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+275 ms ± 531 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
+```
+
+After (benchmarks without parallelization):
+
+```
+sage: P = polytopes.cyclic_polytope(10, 22)
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+38.6 ms ± 1.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
+sage: P = polytopes.associahedron(['A', 8])
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+18.3 ms ± 23.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
+sage: P = polytopes.hypercube(12, backend='field')
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+30.9 ms ± 40 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
+sage: P = polytopes.Birkhoff_polytope(5)  # neither simple nor simplicial
+sage: %timeit C = CombinatorialPolyhedron(P); C.f_vector(1, 0)
+274 ms ± 410 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
+```

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:2

LGTM.

[kliem]

comment:3

Thank you.