Opened 20 months ago
Closed 20 months ago
#31038 closed enhancement (fixed)
Improve the zonotope construction
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.3 |
Component: | geometry | Keywords: | zonotope |
Cc: | jipilab, gh-LaisRast | Merged in: | |
Authors: | Jean-Philippe Labbé, Jonathan Kliem | Reviewers: | Jonathan Kliem, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | 90a0d60 (Commits, GitHub, GitLab) | Commit: | 90a0d6022670062cf14a64c3a64f24235aa6b172 |
Dependencies: | Stopgaps: |
Description
Currently the zonotope just takes the convex hull of the sum of all combinations of the input. With n
generators it takes therefor the convex hull of 2^n
points.
However, most of those points, will be redundant. Reducing via the Minkowski sum, allows to use this.
Before this ticket:
sage: from itertools import combinations sage: cu = polytopes.cube() sage: sgmt = [p.vector()-q.vector() for p,q in combinations(cu.vertices(),2)] sage: sgmt2 = set(tuple(x) for x in sgmt) sage: # %time polytopes.zonotope(sgmt) # killed due to memory overflow sage: %time polytopes.zonotope(sgmt2) CPU times: user 2.06 s, sys: 23.9 ms, total: 2.09 s Wall time: 2.09 s A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices
With this ticket:
sage: from itertools import combinations sage: cu = polytopes.cube() sage: sgmt = [p.vector()-q.vector() for p,q in combinations(cu.vertices(),2)] sage: sgmt2 = set(tuple(x) for x in sgmt) sage: %time polytopes.zonotope(sgmt) CPU times: user 138 ms, sys: 0 ns, total: 138 ms Wall time: 138 ms A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices sage: %time polytopes.zonotope(sgmt2) CPU times: user 58 ms, sys: 0 ns, total: 58 ms Wall time: 57.6 ms A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices
Change History (8)
comment:1 Changed 20 months ago by
- Status changed from new to needs_review
comment:2 Changed 20 months ago by
- Summary changed from Improve the zonotope to Improve the zonotope construction
comment:3 follow-up: ↓ 7 Changed 20 months ago by
comment:4 Changed 20 months ago by
- Commit changed from a2d1fc5a3e7fa6976fea832b3c90cb3be5c62be7 to 90a0d6022670062cf14a64c3a64f24235aa6b172
Branch pushed to git repo; I updated commit sha1. New commits:
90a0d60 | use sum
|
comment:5 Changed 20 months ago by
Yes, much easier.
comment:6 Changed 20 months ago by
- Reviewers changed from Jonathan Kliem to Jonathan Kliem, Frédéric Chapoton
- Status changed from needs_review to positive_review
ok, looks good.
comment:7 in reply to: ↑ 3 Changed 20 months ago by
Replying to chapoton:
hmm,
reduce
is not very pythonic. Why not use sum ?
Ah oui? I once discovered it in a python magazine about "tricks" that go unnoticed. Perhaps it is made for more technical things than +
?
comment:8 Changed 20 months ago by
- Branch changed from u/gh-kliem/improve_zonotope to 90a0d6022670062cf14a64c3a64f24235aa6b172
- Resolution set to fixed
- Status changed from positive_review to closed
hmm,
reduce
is not very pythonic. Why not use sum ?