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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b4ec8de to dfb3144

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8802873	Forgot 1 pyflake
dfb3144	More pep8

[jplab]

comment:7

It looks good to me. I added some more pep8 cleaning.

If the bot is happy and you agree with my changes, I would say it can be put on positive review. Hopefully, the changes won't cause too many conflicts.

[kliem]

comment:8

LGTM. Thank you.

[kliem]

Reviewer: Jean-Philippe Labbé

[vbraun]

comment:10

Merge conflict

[kliem]

comment:11

Replying to @vbraun:

Merge conflict

@vbraun: I believe this is no longer an issue.

The merge conflict appears to be with #28982, which was just rejected because it needs to be rebased (due to failing doctests). IMO we should just rebase #28982 and leave this ticket as it is.

[jplab]

comment:13

This looks reasonable to me.

@Volker: Let us know if there are still further problems with merging this ticket based as it is. It seems to work for us.

[mkoeppe]

Changed keywords from polytopes. product to polytopes. product, sd109

[kliem]

comment:15

I just pulled this in to 9.2.beta0 and it appears to work fine.

[vbraun]

Changed branch from public/29583-reb to dfb3144

[fchapoton]

Changed keywords from polytopes. product, sd109 to polytopes, product, sd109

[fchapoton]

Changed commit from dfb3144 to none