Dilation of polyhedron with both Vrep and Hrep (if backend supports it)

[gh-kliem]

Currently the dilation of a polyhedron is done by computing the new double description from the new vertices.

With #28880 at hand, we can specify both Vrep and Hrep and the backend will use both (if available) or the shorter description. Either way, this will improve performance of polyhedra with many vertices but few facets (e.g. a hypercube).

Before this ticket we had the following timings:

sage: P = polytopes.hypercube(14)
sage: %time _ = 2*P
CPU times: user 2.77 s, sys: 19.8 ms, total: 2.79 s
Wall time: 2.79 s
sage: P = polytopes.hypercube(7, backend='field')
sage: %time _ = 2*P
CPU times: user 3.58 s, sys: 35 µs, total: 3.58 s
Wall time: 3.58 s
sage: P = polytopes.cross_polytope(8, backend='field')
sage: %time _ = 2*P
CPU times: user 15.5 s, sys: 23.9 ms, total: 15.6 s
Wall time: 15.6 s
sage: P = polytopes.cross_polytope(13)
sage: %time _ = 2*P
CPU times: user 395 ms, sys: 0 ns, total: 395 ms
Wall time: 394 ms

With this ticket we have:

sage: P = polytopes.hypercube(14)
sage: %time _ = 2*P
CPU times: user 589 ms, sys: 6 µs, total: 589 ms
Wall time: 588 ms
sage: P = polytopes.hypercube(7, backend='field')
sage: %time _ = 2*P
CPU times: user 14.1 ms, sys: 0 ns, total: 14.1 ms
Wall time: 14.1 ms
sage: P = polytopes.cross_polytope(8, backend='field')
sage: %time _ = 2*P
CPU times: user 49.2 ms, sys: 0 ns, total: 49.2 ms
Wall time: 48.3 ms
sage: P = polytopes.cross_polytope(13)
sage: %time _ = 2*P
CPU times: user 428 ms, sys: 8.08 ms, total: 436 ms
Wall time: 436 ms

Note that for the last timing, the choice of only specifying Vrep was already good (at least for backend ppl). So with the new setup, thinks take a bit more time, as dilation computes the new Hrep, which ppl discards then.

[gh-kliem]

New commits:

​ea5eb69

use both Vrep and Hrep to obtain dilation

[slabbe]

We forgot to update one doctest, see #29300

[jipilab]

Replying to slabbe:

We forgot to update one doctest, see #29300

Yep, for such changes, it is important to test with and without optional packages... otherwise, we tend to forget this. Good catch.