Improve the zonotope construction

[kliem]

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

CC: @jplab @LaisRast

Component: geometry

Keywords: zonotope

Author: Jean-Philippe Labbé, Jonathan Kliem

Branch/Commit: 90a0d60

Reviewer: Jonathan Kliem, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/31038

[fchapoton]

comment:3

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

[sagetrac-git]

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

90a0d60

use sum

[sagetrac-git]

Changed commit from a2d1fc5 to 90a0d60

[kliem]

comment:5

Yes, much easier.

[fchapoton]

comment:6

ok, looks good.

[fchapoton]

Changed reviewer from Jonathan Kliem to Jonathan Kliem, Frédéric Chapoton

[jplab]

comment:7

Replying to @fchapoton:

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

[vbraun]

Changed branch from u/gh-kliem/improve_zonotope to 90a0d60