Improve edges/ridges for simple/simplicial polytopes

[kliem]

In #30040 we have improved the face iterator for simple/simplicial polytopes, but have not applied this to our heuristic, whether we should find edges/ridges in dual/non-dual mode.

This is noticeable for edges of the permutahedron (and theoretically also for other edges of simple polytopes) and does not make a difference otherwise.

Before:

sage: C = polytopes.hypercube(12).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 86.1 ms, sys: 9 µs, total: 86.1 ms
Wall time: 86 ms
sage: %time _ = C.ridges()
CPU times: user 617 µs, sys: 3 µs, total: 620 µs
Wall time: 622 µs
sage: C = polytopes.cyclic_polytope(6, 20).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 114 µs, sys: 0 ns, total: 114 µs
Wall time: 117 µs
sage: %time _ = C.ridges()
CPU times: user 1.09 ms, sys: 5 µs, total: 1.09 ms
Wall time: 1.1 ms
sage: C = polytopes.permutahedron(7).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
Wall time: 16.1 s
sage: %time _ = C.ridges()
CPU times: user 2.35 ms, sys: 0 ns, total: 2.35 ms
Wall time: 2.36 ms

After:

sage: C = polytopes.hypercube(12).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 39.5 ms, sys: 0 ns, total: 39.5 ms
Wall time: 39.4 ms
sage:  %time _ = C.ridges()
CPU times: user 725 µs, sys: 60 µs, total: 785 µs
Wall time: 791 µs
sage: C = polytopes.cyclic_polytope(6, 20).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 154 µs, sys: 12 µs, total: 166 µs
Wall time: 168 µs
sage: %time _ = C.ridges()
CPU times: user 1.16 ms, sys: 95 µs, total: 1.25 ms
Wall time: 1.26 ms
sage: C = polytopes.permutahedron(7).combinatorial_polyhedron()
sage: %time _ = C.edges()
CPU times: user 63.2 ms, sys: 0 ns, total: 63.2 ms
Wall time: 63.2 ms
sage: %time _ = C.ridges()
CPU times: user 4.56 ms, sys: 0 ns, total: 4.56 ms
Wall time: 4.57 ms

The heuristic isn't perfect, but if it fails, you can now select a better algorithm:

sage: P = polytopes.permutahedron(7) 
sage: P1 = P.stack(next(P.face_generator(1)))
sage: %time P1.vertex_adjacency_matrix()
CPU times: user 20.6 s, sys: 7.96 ms, total: 20.6 s
Wall time: 20.6 s
5041 x 5041 dense matrix over Integer Ring (use the '.str()' method to see the entries)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: %time P1.vertex_adjacency_matrix(algorithm='primal')
CPU times: user 206 ms, sys: 16 ms, total: 222 ms
Wall time: 222 ms
5041 x 5041 dense matrix over Integer Ring (use the '.str()' method to see the entries)

Depends on #33644
Depends on #33646

CC: @tscrim @yuan-zhou

Component: geometry

Author: Jonathan Kliem

Branch/Commit: 3bccc27

Reviewer: Travis Scrimshaw, Yuan Zhou

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

[kliem]

Branch: u/gh-kliem/improved_edges_ridges_heuristic

[kliem]

Description changed:

--- 
+++ 
@@ -1 +1,48 @@
 In #30040 we have improved the face iterator for simple/simplicial polytopes, but have not applied this to our heuristic, whether we should find edges/ridges in dual/non-dual mode.
+
+This is noticeable for edges of the permutahedron (and theoretically also for other edges of simple polytopes) and does not make a difference otherwise.
+
+Before:
+
+```
+sage: C = polytopes.hypercube(12).combinatorial_polyhedron()
+sage: %time _ = C.edges()
+CPU times: user 86.1 ms, sys: 9 µs, total: 86.1 ms
+Wall time: 86 ms
+sage: %time _ = C.ridges()
+CPU times: user 617 µs, sys: 3 µs, total: 620 µs
+Wall time: 622 µs
+sage: C = polytopes.cyclic_polytope(6, 20).combinatorial_polyhedron()
+sage: %time _ = C.edges()
+CPU times: user 114 µs, sys: 0 ns, total: 114 µs
+Wall time: 117 µs
+sage: %time _ = C.ridges()
+CPU times: user 1.09 ms, sys: 5 µs, total: 1.09 ms
+Wall time: 1.1 ms
+sage: C = polytopes.permutahedron(7).combinatorial_polyhedron()
+sage: %time _ = C.edges()
+CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
+Wall time: 16.1 s
+sage: %time _ = C.ridges()
+CPU times: user 2.35 ms, sys: 0 ns, total: 2.35 ms
+Wall time: 2.36 ms
+```
+
+After:
+
+```
+sage: C = polytopes.cyclic_polytope(6, 20).combinatorial_polyhedron()
+sage: %time _ = C.edges()
+CPU times: user 120 µs, sys: 1 µs, total: 121 µs
+Wall time: 124 µs
+sage: %time _ = C.ridges()
+CPU times: user 1.12 ms, sys: 13 µs, total: 1.13 ms
+Wall time: 1.13 ms
+sage: C = polytopes.permutahedron(7).combinatorial_polyhedron()
+sage: %time _ = C.edges()
+CPU times: user 14.9 ms, sys: 32 µs, total: 14.9 ms
+Wall time: 15 ms
+sage: %time _ = C.ridges()
+CPU times: user 2.41 ms, sys: 0 ns, total: 2.41 ms
+Wall time: 2.41 ms
+```

[kliem]

New commits:

a0b541b

apply #30040 to edges/ridges heuristic

[kliem]

Changed branch from u/gh-kliem/improved_edges_ridges_heuristic to u/gh-kliem/improved_edge_ridge_heuristic

[kliem]

Commit: a0b541b

[yuan-zhou]

comment:5

Maybe irrelevant to this ticket, but are there better criteria than n_Vrepresentation > (n_facets)² (or n_Vrepresentation² < n_facets) in which cases one knows that the primal (or the dual) algorithm is faster?

"Wild estimates" plus special treatment for simple/simplicial polytopes does not seem optimal to me.

If we don't know a better criterion, does it make sense to leave the choice to the user, as an optional input?

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

I also think it would be good to answer that question and +1 for adding an option for the user to select. However, that can be left to another ticket.

For the change in this ticket. LGTM modulo the order of the checks. How expensive is the is_simple() compared to the other and how frequently do you expect it to get to that test? This is quite a micro-optimization, so if you don't want to be bothered with it, you can set a positive review.

[kliem]

comment:7

I think it is a good idea to expose the primal/dual or automatic options. I really don't know, when the algorithm is faster which way. Like I know for fixed polyhedra, but I have no clue in general. It is surprising how the primal algorithm even to generate edges is much better than the dual algorithm in many cases.

What do you think is better:

• a keyword algorithm, with options 'primal', 'dual' or None or
• a kewword dual with options True, False and None?

At the moment the Polyhedron_base method face_generator already exposes the keyword dual. But if this is not intuitive we should maybe switch to algorithm= instead.