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

[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.

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedra, dilation, precomputed data

Author: Jonathan Kliem

Branch: ea5eb69

Reviewer: Sébastien Labbé

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

[kliem]

New commits:

ea5eb69

use both Vrep and Hrep to obtain dilation

[kliem]

Branch: public/29200

[kliem]

Author: Jonathan Kliem

[kliem]

Commit: ea5eb69

[kliem]

Changed keywords from none to polyhedra, dilation, precomputed data

[seblabbe]

Reviewer: Sébastien Labbé

[vbraun]

Changed branch from public/29200 to ea5eb69

[seblabbe]

Changed commit from ea5eb69 to none

[seblabbe]

comment:4

We forgot to update one doctest, see #29300

[jplab]

comment:5

Replying to @seblabbe:

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.