Improve obtaining combinatorial polyhedron

[kliem]

This ticket improves obtaining the CombinatorialPolyhedron from an incidence matrix.

Along the way we also improve the method CombinatorialPolyhedron.incidence_matrix that reobtains the incidence matrix.

Note that #29837 greatly speeds up obtainment of incidence matrices in Polyhedron_base.

Without this ticket:

sage: P = polytopes.permutahedron(7)
sage: _ = P.incidence_matrix()
sage: %time C = CombinatorialPolyhedron(P)
CPU times: user 821 ms, sys: 19.4 ms, total: 840 ms
Wall time: 842 ms
sage: C.incidence_matrix.clear_cache()
sage: %time _ = C.incidence_matrix()
CPU times: user 24.8 ms, sys: 22 µs, total: 24.8 ms
Wall time: 24.6 ms

sage: P = polytopes.associahedron(['A', 9])
sage: _ = P.incidence_matrix()
sage: %time C = CombinatorialPolyhedron(P)
CPU times: user 1.08 s, sys: 36.1 ms, total: 1.11 s
Wall time: 1.11 s
sage: C.incidence_matrix.clear_cache()
sage: %time _ = C.incidence_matrix()
CPU times: user 94.2 ms, sys: 0 ns, total: 94.2 ms
Wall time: 93.8 ms

With this ticket:

sage: P = polytopes.permutahedron(7)
sage: _ = P.incidence_matrix()
sage: %time C = CombinatorialPolyhedron(P)
CPU times: user 77.6 ms, sys: 12 ms, total: 89.6 ms
Wall time: 88 ms
sage: C.incidence_matrix.clear_cache()
sage: %time _ = C.incidence_matrix()
CPU times: user 17 ms, sys: 14 µs, total: 17 ms
Wall time: 16.7 ms

sage: P = polytopes.associahedron(['A', 9])
sage: _ = P.incidence_matrix()
sage: %time C = CombinatorialPolyhedron(P)
CPU times: user 110 ms, sys: 0 ns, total: 110 ms
Wall time: 109 ms
sage: C.incidence_matrix.clear_cache()
sage: %time _ = C.incidence_matrix()
CPU times: user 65.3 ms, sys: 18 µs, total: 65.3 ms
Wall time: 64.3 ms

Depends on #29837

CC: @jplab @LaisRast

Component: geometry

Keywords: combinatorial polyhedron

Author: Jonathan Kliem

Branch/Commit: 2db3a70

Reviewer: Travis Scrimshaw

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

[kliem]

Branch: public/29841

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

7b70830	rename
47a19c6	implement slack matrix
54755d7	Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb
a4576d6	set up incidence/adjacency matrix with GF(2)
30c4715	Merge branch 'public/29840' of git://trac.sagemath.org/sage into public/29837-reb
fcd62d2	determine is_zero beforehand
13b8583	small fix
89aeab3	obtain incidence matrix from slack matrix
d8e4153	improve initialization of CombinatorialPolyhedron
464f5c5	reobtain incidence matrix more quickly

[sagetrac-git]

Commit: 464f5c5

[kliem]

New commits:

62f1ff9	use integer matrix for zero_pattern_matrix
88f6025	Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb2
7cee020	determine is_zero beforehand
3d28d09	small fix
7ef6a11	use slack matrix to obtain incidence matrix quicker
7ff9f92	improve initialization of CombinatorialPolyhedron
20d22a8	mod2 -> integer; improve reobtainment of incidence matrix
addee64	do not delete columns if we do not have to

[kliem]

Description changed:

--- 
+++ 
@@ -31,18 +31,18 @@
 sage: P = polytopes.permutahedron(7)
 sage: _ = P.incidence_matrix()
 sage: %time C = CombinatorialPolyhedron(P)
-CPU times: user 36.4 ms, sys: 3.87 ms, total: 40.3 ms
-Wall time: 39.7 ms
+CPU times: user 77.6 ms, sys: 12 ms, total: 89.6 ms
+Wall time: 88 ms
 sage: %time _ = C.incidence_matrix()
-CPU times: user 5.26 ms, sys: 50 µs, total: 5.31 ms
-Wall time: 5.35 ms
+CPU times: user 17 ms, sys: 14 µs, total: 17 ms
+Wall time: 16.7 ms
 
 sage: P = polytopes.associahedron(['A', 9])
 sage: _ = P.incidence_matrix()
 sage: %time C = CombinatorialPolyhedron(P)
-CPU times: user 115 ms, sys: 57 µs, total: 115 ms
-Wall time: 114 ms
+CPU times: user 110 ms, sys: 0 ns, total: 110 ms
+Wall time: 109 ms
 sage: %time _ = C.incidence_matrix()
-CPU times: user 34.2 ms, sys: 0 ns, total: 34.2 ms
-Wall time: 34.2 ms
+CPU times: user 65.3 ms, sys: 18 µs, total: 65.3 ms
+Wall time: 64.3 ms
 ```

[kliem]

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

[kliem]

Changed commit from 464f5c5 to addee64