Obtain product with both Vrep and Hrep (if backend supports it)

[kliem]

We set up the product of two polyhedra with both Vrepresentation and Hrepresentation. This a great improvement, if the backend supports precomputed data (currently field). Otherwise, it can be an improvement, if the Hrepresentation is much shorter than the Vrepresentation.

Before this ticket:

sage: Cb = polytopes.hypercube(7, backend='ppl')
sage: Cr = polytopes.cross_polytope(7, backend='ppl')
sage: %time _ = Cb*Cb
CPU times: user 2.58 s, sys: 16 ms, total: 2.6 s
Wall time: 2.59 s
sage: %time _ = Cr*Cr
CPU times: user 99.9 ms, sys: 0 ns, total: 99.9 ms
Wall time: 99.6 ms

sage: Cr_field = polytopes.cross_polytope(4, backend='field')
sage: Cb_field = polytopes.hypercube(4, backend='field')
sage: %time _ = Cb_field*Cr_field
CPU times: user 4.83 s, sys: 11 µs, total: 4.83 s
Wall time: 4.83 s

With this ticket:

sage: Cb = polytopes.hypercube(7, backend='ppl')
sage: Cr = polytopes.cross_polytope(7, backend='ppl')
sage: %time _ = Cb*Cb
CPU times: user 393 ms, sys: 20 ms, total: 413 ms
Wall time: 412 ms
sage: %time _ = Cr*Cr
CPU times: user 42.3 ms, sys: 62 µs, total: 42.3 ms
Wall time: 42 ms
sage: %time _ = Cr*Cb
CPU times: user 164 ms, sys: 0 ns, total: 164 ms
Wall time: 164 ms

sage: Cr_field = polytopes.cross_polytope(8, backend='field')
sage: Cb_field = polytopes.hypercube(8, backend='field')
sage: %time _ = Cb_field*Cr_field
CPU times: user 67.2 ms, sys: 0 ns, total: 67.2 ms
Wall time: 66.9 ms
sage: %time _ = Cr_field*Cr_field
CPU times: user 51 ms, sys: 132 µs, total: 51.1 ms
Wall time: 50.2 ms
sage: %time _ = Cb_field*Cb_field
CPU times: user 986 ms, sys: 15.7 ms, total: 1 s
Wall time: 1 s

CC: @jplab @LaisRast

Component: geometry

Keywords: polytopes, product, sd109

Author: Jonathan Kliem

Branch: dfb3144

Reviewer: Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/29583

[kliem]

Branch: public/29583

[kliem]

New commits:

fa0cd15

set up product with both Vrep and Hrep

[kliem]

Commit: fa0cd15

[jplab]

comment:2

Some timings in the description are repeated, probably you forgot "Cr*Cb" in the status quo and didn't show it in the new times...

If you can fix this quickly, that'd be helpful!

Spaces between binary operation:

-           sage: P*P1 == Q*Q1
+           sage: P * P1 == Q * Q1
+           True
-           sage: P.polar(in_affine_span=True)*P1 == Q.polar(in_affine_span=True)*Q1
+           sage: P.polar(in_affine_span=True) * P1 == Q.polar(in_affine_span=True) * Q1
+           True

and

-        new_vertices = (tuple(x)+tuple(y)
+        new_vertices = (tuple(x) + tuple(y)
+                        for x in self.vertex_generator() for y in other.vertex_generator())

Might be nice to correct the coding styles with the multiple statements on one line with the : ?

[kliem]

Description changed:

--- 
+++ 
@@ -31,9 +31,9 @@
 sage: %time _ = Cr*Cr
 CPU times: user 42.3 ms, sys: 62 µs, total: 42.3 ms
 Wall time: 42 ms
-sage: %time _ = Cr*Cr
-CPU times: user 42.2 ms, sys: 87 µs, total: 42.3 ms
-Wall time: 42 ms
+sage: %time _ = Cr*Cb
+CPU times: user 164 ms, sys: 0 ns, total: 164 ms
+Wall time: 164 ms
 
 sage: Cr_field = polytopes.cross_polytope(8, backend='field')
 sage: Cb_field = polytopes.hypercube(8, backend='field')

[kliem]

Changed commit from fa0cd15 to b4ec8de

[kliem]

Changed branch from public/29583 to public/29583-reb

[kliem]

New commits:

80766a2	set up product with both Vrep and Hrep
bda2219	spaces between binary operators
b4ec8de	coding style