#29198 closed enhancement (fixed)

Set up hypercube with both Vrep and Hrep (if backend supports it)

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: Jean-Philippe Labbé, Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: 91ae9ba (Commits, GitHub, GitLab) Commit: 91ae9baed801970849814fcf7d035204dd48686d
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 (11)

comment:1 Changed 21 months 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 21 months 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 20 months 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 20 months ago by jipilab

  • Description modified (diff)

comment:5 Changed 20 months ago by git

  • Commit changed from ac0390b6f98185d8eae0e2c196cc32bc3be2b5c8 to 53b54e26eb7a1707c69103d6b39f68f24870f22e

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

53b54e2a new failing doctest

comment:6 Changed 20 months ago by jipilab

Ok, that's the doctest from the bots. I also only got that one on my machine.

Let's see what the bots say. It looks good apart from that.

comment:7 Changed 20 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to positive_review

comment:8 Changed 20 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:9 Changed 20 months ago by gh-kliem

  • Branch changed from public/29198-reb to public/29198-reb2
  • Commit changed from 53b54e26eb7a1707c69103d6b39f68f24870f22e to 91ae9baed801970849814fcf7d035204dd48686d
  • Status changed from needs_work to needs_review

New commits:

357fcd1set up the hypercube with both Vrep and Hrep
91ae9bafixed doctests

comment:10 Changed 20 months ago by slabbe

  • Reviewers changed from Jean-Philippe Labbé to Jean-Philippe Labbé, Sébastien Labbé
  • Status changed from needs_review to positive_review

I confirm the timing improvements. I get all tests passed in src/sage/geometry and src/sage/plot except src/sage/geometry/polyhedron/base.py which still has a "killed due to abort" issue which is independent of this ticket.

comment:11 Changed 20 months ago by vbraun

  • Branch changed from public/29198-reb2 to 91ae9baed801970849814fcf7d035204dd48686d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.