Opened 14 months ago

Closed 13 months ago

Last modified 13 months ago

#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:

Status badges

Description (last modified by 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.

Change History (5)

comment:1 Changed 14 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • 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

New commits:

ea5eb69use both Vrep and Hrep to obtain dilation

comment:2 Changed 14 months ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to positive_review

comment:3 Changed 13 months ago by vbraun

  • Branch changed from public/29200 to ea5eb69ceedf16452ae5a2673a05089f6e0d41d5
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:4 follow-up: Changed 13 months ago by slabbe

  • Commit ea5eb69ceedf16452ae5a2673a05089f6e0d41d5 deleted

We forgot to update one doctest, see #29300

comment:5 in reply to: ↑ 4 Changed 13 months ago by 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.

Note: See TracTickets for help on using tickets.