Opened 2 years ago

Last modified 23 months ago

#29198 closed enhancement

Set up hypercube with both Vrep and Hrep (if backend supports it) — at Version 4

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: hypercube, polyhedron, double description
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers:
Report Upstream: N/A Work issues:
Branch: public/29198-reb (Commits, GitHub, GitLab) Commit: ac0390b6f98185d8eae0e2c196cc32bc3be2b5c8
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

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

Change History (4)

comment:1 Changed 2 years ago by gh-kliem

  • Branch set to public/29198
  • Commit set to 3942824ce0bbb1c19e425e306d02b548f0f3ce43
  • Status changed from new to needs_review

New commits:

af221cbset up the hypercube with both Vrep and Hrep
486b0e1fixed doctests
3942824fixed more doctests involving order

comment:2 Changed 2 years ago by git

  • Commit changed from 3942824ce0bbb1c19e425e306d02b548f0f3ce43 to 8b8abb233a2a0c099c3554ec9cb51579fdf6ceb4

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

8b8abb2more doctests

comment:3 Changed 2 years ago by gh-kliem

  • Branch changed from public/29198 to public/29198-reb
  • Commit changed from 8b8abb233a2a0c099c3554ec9cb51579fdf6ceb4 to ac0390b6f98185d8eae0e2c196cc32bc3be2b5c8

New commits:

f9958f3set up the hypercube with both Vrep and Hrep
b2b544efixed doctests
6ca4267fixed more doctests involving order
86cca93more doctests
ac0390bfixed one more test

comment:4 Changed 23 months ago by jipilab

  • Description modified (diff)
Note: See TracTickets for help on using tickets.