Opened 4 months ago

Closed 3 months ago

#29583 closed enhancement (fixed)

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

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: polytopes. product, sd109
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: dfb3144 (Commits) Commit: dfb3144ac1aeef57e97aa4ac6e5b4f710d1d118b
Dependencies: Stopgaps:

Description (last modified by gh-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

Change History (16)

comment:1 Changed 4 months ago by gh-kliem

  • Branch set to public/29583
  • Commit set to fa0cd1513ec9c80fe2545735db434873de528cbd
  • Status changed from new to needs_review

New commits:

fa0cd15set up product with both Vrep and Hrep

comment:2 Changed 3 months ago by jipilab

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 : ?

comment:3 Changed 3 months ago by jipilab

  • Status changed from needs_review to needs_work

comment:4 Changed 3 months ago by gh-kliem

  • Description modified (diff)

comment:5 Changed 3 months ago by gh-kliem

  • Branch changed from public/29583 to public/29583-reb
  • Commit changed from fa0cd1513ec9c80fe2545735db434873de528cbd to b4ec8dea6bfca5a98095af0b764db3b1790e45e3
  • Status changed from needs_work to needs_review

New commits:

80766a2set up product with both Vrep and Hrep
bda2219spaces between binary operators
b4ec8decoding style

comment:6 Changed 3 months ago by git

  • Commit changed from b4ec8dea6bfca5a98095af0b764db3b1790e45e3 to dfb3144ac1aeef57e97aa4ac6e5b4f710d1d118b

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

8802873Forgot 1 pyflake
dfb3144More pep8

comment:7 Changed 3 months ago by jipilab

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.

comment:8 Changed 3 months ago by gh-kliem

LGTM. Thank you.

comment:9 Changed 3 months ago by gh-kliem

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to positive_review

comment:10 follow-up: Changed 3 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:11 in reply to: ↑ 10 Changed 3 months ago by gh-kliem

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.

comment:12 Changed 3 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:13 Changed 3 months ago by jipilab

  • Status changed from needs_review to positive_review

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.

comment:14 Changed 3 months ago by mkoeppe

  • Keywords sd109 added

comment:15 Changed 3 months ago by gh-kliem

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

Last edited 3 months ago by gh-kliem (previous) (diff)

comment:16 Changed 3 months ago by vbraun

  • Branch changed from public/29583-reb to dfb3144ac1aeef57e97aa4ac6e5b4f710d1d118b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.