Set up hypercube with both Vrep and Hrep (if backend supports it)

[kliem]

Currently, the hypercube is set up with the vertices. This is slow, as the vertices grow exponentially with dimension:

sage: %time _ = polytopes.hypercube(8)
CPU times: user 58.6 ms, sys: 0 ns, total: 58.6 ms
Wall time: 58.2 ms
sage: %time _ = polytopes.hypercube(14)
CPU times: user 2.74 s, sys: 19.1 ms, total: 2.76 s
Wall time: 2.76 s

With #28880 at hand, we can set up the hypercube with both Vrep and Hrep. If the backend supports it (as in backend='field'), then the double description does not need to be computed. If the backend does not support it (as in backend='ppl'), then the hypercube is set up from the inequalities, which is much faster:

sage: %time _ = polytopes.hypercube(8)   # uses ppl
CPU times: user 47.8 ms, sys: 3.19 ms, total: 51 ms
Wall time: 50 ms
sage: %time _ = polytopes.hypercube(14)  # uses ppl
CPU times: user 421 ms, sys: 4.7 ms, total: 426 ms
Wall time: 425 ms
sage: %time _ = polytopes.hypercube(14, backend='field')  # uses both descriptions
CPU times: user 168 ms, sys: 124 µs, total: 169 ms
Wall time: 168 ms

CC: @jplab @LaisRast

Component: geometry

Keywords: hypercube, polyhedron, double description

Author: Jonathan Kliem

Branch/Commit: 91ae9ba

Reviewer: Jean-Philippe Labbé, Sébastien Labbé

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

[kliem]

Branch: public/29198

[kliem]

Commit: 3942824

[kliem]

New commits:

af221cb	set up the hypercube with both Vrep and Hrep
486b0e1	fixed doctests
3942824	fixed more doctests involving order

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8b8abb2

more doctests

[sagetrac-git]

Changed commit from 3942824 to 8b8abb2

[kliem]

Changed commit from 8b8abb2 to ac0390b

[kliem]

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

[kliem]

New commits:

f9958f3	set up the hypercube with both Vrep and Hrep
b2b544e	fixed doctests
6ca4267	fixed more doctests involving order
86cca93	more doctests
ac0390b	fixed one more test

[sagetrac-git]

Changed commit from ac0390b to 53b54e2

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

53b54e2

a new failing doctest

[jplab]

comment:6

Ok, that's the doctest from the bots. I also only got that one on my machine.

Let's see what the bots say. It looks good apart from that.

[jplab]

Reviewer: Jean-Philippe Labbé

[vbraun]

comment:8

Merge conflict

[kliem]

Changed commit from 53b54e2 to 91ae9ba

[kliem]

New commits:

357fcd1	set up the hypercube with both Vrep and Hrep
91ae9ba	fixed doctests

[kliem]

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

[seblabbe]

Changed reviewer from Jean-Philippe Labbé to Jean-Philippe Labbé, Sébastien Labbé

[seblabbe]

comment:10

I confirm the timing improvements. I get all tests passed in src/sage/geometry and src/sage/plot except src/sage/geometry/polyhedron/base.py which still has a "killed due to abort" issue which is independent of this ticket.

[vbraun]

Changed branch from public/29198-reb2 to 91ae9ba