Opened 10 months ago

Closed 9 months ago

#29843 closed enhancement (fixed)

Set up linear transformation with precomputed data if injective

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords:
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 28819ea (Commits, GitHub, GitLab) Commit: 28819ea12c90d3a9c268f0913ef0bc21ec3c0ff3
Dependencies: Stopgaps:

Status badges

Description

We set up linear transformation with double description, if it preserves the polytope.

Also we slightly modify the affine hull projection to make use of this.

Before this ticket:

(Run tests twice to obtain the real timinigs. The first time it computes twice to populate the coercion model, see https://groups.google.com/d/msg/sage-devel/UAvbXKSN_JU/vcVN2AVQBQAJ)

sage: P = polytopes.permutahedron(6)
sage: %time Q = P.affine_hull_projection()
CPU times: user 94.1 ms, sys: 2 µs, total: 94.1 ms
Wall time: 93.5 ms

sage: P = polytopes.permutahedron(7)
sage: %time Q = P.affine_hull_projection()
CPU times: user 2.21 s, sys: 1 µs, total: 2.21 s
Wall time: 2.21 s

sage: P = polytopes.permutahedron(4)
sage: %time Q = P.affine_hull_projection(orthonormal=True, extend=True)
CPU times: user 1.36 s, sys: 2 µs, total: 1.36 s
Wall time: 1.36 s

sage: P = polytopes.hypercube(13)*Polyhedron(vertices=[[0]])
sage: %time Q = P.affine_hull_projection()
CPU times: user 1.84 s, sys: 5 µs, total: 1.84 s
Wall time: 1.84 s

With this ticket on top of #29841 (this tickets new implementation uses CombinatorialPolyhedron which is much faster obtained with #29841):

sage: P = polytopes.permutahedron(6)
sage: %time Q = P.affine_hull_projection()
CPU times: user 78.9 ms, sys: 0 ns, total: 78.9 ms
Wall time: 77.7 ms
sage: P = polytopes.permutahedron(7)
sage: %time Q = P.affine_hull_projection()
CPU times: user 1.23 s, sys: 35 µs, total: 1.23 s
Wall time: 1.23 s

sage: P = polytopes.permutahedron(7)
sage: P = P.base_extend(P.base_ring(), backend='field')
sage: %time Q = P.affine_hull_projection()
CPU times: user 366 ms, sys: 3.98 ms, total: 370 ms
Wall time: 369 ms

sage: P = polytopes.permutahedron(4) 
sage: %time Q = P.affine_hull_projection(orthonormal=True, extend=True)
CPU times: user 187 ms, sys: 10.8 ms, total: 198 ms
Wall time: 196 ms

sage: P = polytopes.hypercube(13)*Polyhedron(vertices=[[0]])
sage: %time Q = P.affine_hull_projection()
CPU times: user 847 ms, sys: 36 µs, total: 848 ms
Wall time: 846 ms

Change History (4)

comment:1 Changed 10 months ago by gh-kliem

  • Branch set to public/29843
  • Commit set to 28819ea12c90d3a9c268f0913ef0bc21ec3c0ff3
  • Status changed from new to needs_review

New commits:

28819easet up linear transformation with both Vrep and Hrep, if possible

comment:2 Changed 9 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:3 Changed 9 months ago by gh-kliem

Thank you.

comment:4 Changed 9 months ago by vbraun

  • Branch changed from public/29843 to 28819ea12c90d3a9c268f0913ef0bc21ec3c0ff3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.