Opened 20 months ago
Closed 20 months ago
#31038 closed enhancement (fixed)
Improve the zonotope construction
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  geometry  Keywords:  zonotope 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  JeanPhilippe 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 3dimensional 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 3dimensional 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 3dimensional 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 followup: ↓ 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/ghkliem/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 ?