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]

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

[kliem]

Changed commit from 464f5c5 to addee64

[kliem]

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

[kliem]

Changed commit from addee64 to 2db3a70

[kliem]

Last 10 new commits:

2a08abe	small mistakes
333c4ba	wrong doctest
82c6b4a	docstring
211f4f1	Merge branch 'public/29839' of git://trac.sagemath.org/sage into public/29837-reb3
4c5433e	determine is_zero beforehand
27a1b90	use slack matrix to obtain incidence matrix quicker
764a99b	account for change in #29839
1b654c4	improve initialization of CombinatorialPolyhedron
527316d	mod2 -> integer; improve reobtainment of incidence matrix
2db3a70	do not delete columns if we do not have to

[tscrim]

comment:7

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[kliem]

comment:8

Thank you.

[vbraun]

Changed branch from public/29841-reb2 to 2db3a70