Opened 19 months ago

Closed 18 months ago

Last modified 18 months ago

#29324 closed enhancement (fixed)

Translation with both Vrep and Hrep

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polyhedra, translation
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Laith Rastanawi
Report Upstream: N/A Work issues:
Branch: ffda483 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

We set up translation of polyhedra with both Vrepresentation and Hrepresentation, if the backend supports it.

This might be faster, when the Hrepresentation is shorter (previously translation was computed from Vrepresentation). Also this is much faster, when the backend supports precomputed data (currently field).

Before this ticket:

sage: P = polytopes.hypercube(14, 'zero_one')
sage: %time Q = P - P.center()
CPU times: user 3.42 s, sys: 2 µs, total: 3.42 s
Wall time: 3.42 s

sage: P = polytopes.hypercube(8, 'zero_one', backend='field')
sage: %time Q = P - P.center()
CPU times: user 13.8 s, sys: 8 µs, total: 13.8 s
Wall time: 13.8 s

sage: P = polytopes.cross_polytope(12)
sage: %timeit Q = P - P.vertices()[0].vector()
10 loops, best of 5: 149 ms per loop

sage: P = polytopes.cross_polytope(6, backend='field')
sage: %time Q = P - P.vertices()[0].vector()
CPU times: user 744 ms, sys: 4 µs, total: 744 ms
Wall time: 744 ms

With this ticket:

# Hrep is shorter.
sage: P = polytopes.hypercube(14)
sage: %time Q = P - P.center()
CPU times: user 1.01 s, sys: 16 ms, total: 1.02 s
Wall time: 1.02 s

# Completely precomputed.
sage: P = polytopes.hypercube(8, 'zero_one', backend='field')
sage: %time Q = P - P.center()
CPU times: user 16.9 ms, sys: 0 ns, total: 16.9 ms
Wall time: 16.8 ms

# A bit slower (precomputed data is discarded).
sage: P = polytopes.cross_polytope(12)
sage: %timeit Q = P - P.vertices()[0].vector()
10 loops, best of 5: 172 ms per loop

# Completely precomputed.
sage: P = polytopes.cross_polytope(6, backend='field')
sage: %time Q = P - P.vertices()[0].vector()
CPU times: user 2.12 ms, sys: 30 µs, total: 2.15 ms
Wall time: 2.15 ms

# With precomputed data translations are what they should be -- trivial.
sage: P = polytopes.hypercube(14, 'zero_one', backend='field')
sage: %time Q = P - P.center()
CPU times: user 404 ms, sys: 3.97 ms, total: 408 ms
Wall time: 408 ms

Change History (6)

comment:1 Changed 19 months ago by gh-kliem

  • Branch set to public/29324
  • Commit set to ffda483f08c0ddf129b8f5a02fe3f0c83b3a0113
  • Status changed from new to needs_review

New commits:

ffda483precomputed data for translations

comment:2 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:3 Changed 18 months ago by gh-LaisRast

  • Reviewers set to Laith Rastanawi
  • Status changed from needs_review to positive_review

It looks good to me. Tests passed except for pycodestyle errors which are not caused by this ticket

comment:4 Changed 18 months ago by vbraun

  • Branch changed from public/29324 to ffda483f08c0ddf129b8f5a02fe3f0c83b3a0113
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:5 Changed 18 months ago by gh-kliem

  • Commit ffda483f08c0ddf129b8f5a02fe3f0c83b3a0113 deleted

I think the milestone is incorrect here and maybe in a lot of other tickets as well. This ticket is part of 9.1.rc1.

comment:6 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.