Improvement for incidence matrix of polyhedra

[kliem]

This ticket collects some improvements for obtaining incidence matrices:

• The method self._is_zero is called many times and we can save plenty of time by obtaining it beforehand.

• We can obtain the slack matrix by multiplying the Vrepresentation matrix with the homogenous Vrepresentation. From this we can obtain the incidence matrix (strangely this last step takes up most of the time).

  Unfortunately, matrix multiplication for algebraic fields isn't very efficient. So we need to keep the old method in this case.

Before this ticket:

sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 751 ms, sys: 7.95 ms, total: 759 ms
Wall time: 758 ms
sage: P = polytopes.associahedron(['A', 9])
sage: %time _ = P.incidence_matrix()
CPU times: user 1.94 s, sys: 4.03 ms, total: 1.94 s
Wall time: 1.94 s
sage: P = polytopes.hypercube(14)
sage: %time _ = P.incidence_matrix()
CPU times: user 670 ms, sys: 0 ns, total: 670 ms
Wall time: 669 ms
sage: K.<sqrt2> = QuadraticField(2)
sage: P = polytopes.permutahedron(7).dilation(sqrt2)
sage: %time _ = P.incidence_matrix()
CPU times: user 3.82 s, sys: 0 ns, total: 3.82 s
Wall time: 3.82 s

With this ticket:

sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 64.4 ms, sys: 7 µs, total: 64.4 ms
Wall time: 63.6 ms
sage: P = polytopes.associahedron(['A', 9])
sage: %time _ = P.incidence_matrix()
CPU times: user 325 ms, sys: 12.1 ms, total: 337 ms
Wall time: 335 ms
sage: P = polytopes.hypercube(14)
sage: %time _ = P.incidence_matrix()
CPU times: user 139 ms, sys: 12 ms, total: 151 ms
Wall time: 149 ms
sage: K.<sqrt2> = QuadraticField(2)
sage: P = polytopes.permutahedron(7).dilation(sqrt2)
sage: %time _ = P.incidence_matrix()
CPU times: user 3.69 s, sys: 3.69 ms, total: 3.69 s
Wall time: 3.69 s

Depends on #29838
Depends on #29839

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedra, incidence matrix

Author: Jonathan Kliem

Branch/Commit: 955f12b

Reviewer: Travis Scrimshaw

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

[kliem]

New commits:

42b5c42	determine is_zero beforehand
02a8a2f	small fix
6dbe5d2	use matrix multiplication to obtain incidence matrix

[kliem]

Commit: 6dbe5d2

[kliem]

Branch: public/29837

[kliem]

comment:2

This should be rebased on #29838 and another ticket that speeds up getting the incidence matrix from the slack matrix.

[kliem]

Dependencies: #29838

[kliem]

Changed dependencies from #29838 to #29838, #29839

[kliem]

Changed dependencies from #29838, #29839 to #29838, #29839, #29840

[kliem]

Description changed:

--- 
+++ 
@@ -32,21 +32,21 @@
 ```
 sage: P = polytopes.permutahedron(7)
 sage: %time _ = P.incidence_matrix()
-CPU times: user 236 ms, sys: 15.8 ms, total: 252 ms
-Wall time: 251 ms
+CPU times: user 77.5 ms, sys: 11.9 ms, total: 89.3 ms
+Wall time: 88.3 ms
 sage: P = polytopes.associahedron(['A', 9])
 sage: %time _ = P.incidence_matrix()
-CPU times: user 1.21 s, sys: 52.1 ms, total: 1.27 s
-Wall time: 1.27 s
+CPU times: user 390 ms, sys: 3.98 ms, total: 394 ms
+Wall time: 393 ms
 sage: P = polytopes.hypercube(14)
 sage: %time _ = P.incidence_matrix()
-CPU times: user 247 ms, sys: 8.1 ms, total: 256 ms
-Wall time: 255 ms
+CPU times: user 138 ms, sys: 7.84 ms, total: 146 ms
+Wall time: 144 ms
 sage: K.<sqrt2> = QuadraticField(2)
 sage: P = polytopes.permutahedron(7).dilation(sqrt2)
 sage: %time _ = P.incidence_matrix()
-CPU times: user 3.77 s, sys: 3.81 ms, total: 3.77 s
-Wall time: 3.77 s
+CPU times: user 3.85 s, sys: 59 µs, total: 3.85 s
+Wall time: 3.85 s
 ```
 
 Possible follow up: Set up incidence matrix etc. with base ring `GF(2)`.