Opened 4 months ago

Closed 4 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:

Status badges

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 4 months ago by gh-kliem

  • Status changed from new to needs_review

comment:2 Changed 4 months ago by jipilab

  • Summary changed from Improve the zonotope to Improve the zonotope construction

comment:3 follow-up: Changed 4 months ago by chapoton

hmm, reduce is not very pythonic. Why not use sum ?

comment:4 Changed 4 months ago by git

  • Commit changed from a2d1fc5a3e7fa6976fea832b3c90cb3be5c62be7 to 90a0d6022670062cf14a64c3a64f24235aa6b172

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

​90a0d60use sum

comment:5 Changed 4 months ago by gh-kliem

Yes, much easier.

comment:6 Changed 4 months ago by chapoton

  • 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 4 months ago by jipilab

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 4 months ago by vbraun

  • Branch changed from u/gh-kliem/improve_zonotope to 90a0d6022670062cf14a64c3a64f24235aa6b172
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.