#29200 closed enhancement (fixed)
Dilation of polyhedron with both Vrep and Hrep (if backend supports it)
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.1 |
Component: | geometry | Keywords: | polyhedra, dilation, precomputed data |
Cc: | jipilab, gh-LaisRast | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | Sébastien Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | ea5eb69 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Change History (5)
comment:1 Changed 2 years ago by
- Branch set to public/29200
- Commit set to ea5eb69ceedf16452ae5a2673a05089f6e0d41d5
- Description modified (diff)
- Keywords polyhedra dilation precomputed data added
- Status changed from new to needs_review
comment:2 Changed 2 years ago by
- Reviewers set to Sébastien Labbé
- Status changed from needs_review to positive_review
comment:3 Changed 2 years ago by
- Branch changed from public/29200 to ea5eb69ceedf16452ae5a2673a05089f6e0d41d5
- Resolution set to fixed
- Status changed from positive_review to closed
comment:4 follow-up: ↓ 5 Changed 2 years ago by
- Commit ea5eb69ceedf16452ae5a2673a05089f6e0d41d5 deleted
We forgot to update one doctest, see #29300
New commits:
use both Vrep and Hrep to obtain dilation