Changes between Initial Version and Version 1 of Ticket #29200


Ignore:
Timestamp:
02/15/20 16:16:18 (2 years ago)
Author:
gh-kliem
Comment:

New commits:

ea5eb69use both Vrep and Hrep to obtain dilation

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #29200

    • Property Status changed from new to needs_review
    • Property Authors changed from to Jonathan Kliem
    • Property Branch changed from to public/29200
    • Property Keywords polyhedra dilation precomputed data added
    • Property Commit changed from to ea5eb69ceedf16452ae5a2673a05089f6e0d41d5
  • Ticket #29200 – Description

    initial v1  
    22
    33With #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).
     4
     5Before this ticket we had the following timings:
     6
     7{{{
     8sage: P = polytopes.hypercube(14)
     9sage: %time _ = 2*P
     10CPU times: user 2.77 s, sys: 19.8 ms, total: 2.79 s
     11Wall time: 2.79 s
     12sage: P = polytopes.hypercube(7, backend='field')
     13sage: %time _ = 2*P
     14CPU times: user 3.58 s, sys: 35 µs, total: 3.58 s
     15Wall time: 3.58 s
     16sage: P = polytopes.cross_polytope(8, backend='field')
     17sage: %time _ = 2*P
     18CPU times: user 15.5 s, sys: 23.9 ms, total: 15.6 s
     19Wall time: 15.6 s
     20sage: P = polytopes.cross_polytope(13)
     21sage: %time _ = 2*P
     22CPU times: user 395 ms, sys: 0 ns, total: 395 ms
     23Wall time: 394 ms
     24}}}
     25
     26With this ticket we have:
     27
     28{{{
     29sage: P = polytopes.hypercube(14)
     30sage: %time _ = 2*P
     31CPU times: user 589 ms, sys: 6 µs, total: 589 ms
     32Wall time: 588 ms
     33sage: P = polytopes.hypercube(7, backend='field')
     34sage: %time _ = 2*P
     35CPU times: user 14.1 ms, sys: 0 ns, total: 14.1 ms
     36Wall time: 14.1 ms
     37sage: P = polytopes.cross_polytope(8, backend='field')
     38sage: %time _ = 2*P
     39CPU times: user 49.2 ms, sys: 0 ns, total: 49.2 ms
     40Wall time: 48.3 ms
     41sage: P = polytopes.cross_polytope(13)
     42sage: %time _ = 2*P
     43CPU times: user 428 ms, sys: 8.08 ms, total: 436 ms
     44Wall time: 436 ms
     45}}}
     46
     47Note 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.