Add "minimal=True" option to affine_hull_projection

[jplab]

Currently, the computation of the affine_hull_projection is done by default in AA which is not optimal sometimes.

Currently:

sage: A=[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1],[1/4,1/4,1/4,1/4]]
sage: n=len(A)
sage: A=[vector(v) for v in A]
sage: AP = Polyhedron(vertices=A)
sage: M,b=AP.affine_hull_projection(orthonormal=True,extend=True,as_affine_map=True)
sage: V=[] 
....: for i in range(n):
....:     for j in range(i+1,n):
....:             V.append((A[i]-A[j])/2)
sage: Z=polytopes.zonotope(V)
sage: T = M.matrix().transpose()
sage: timeit('T*Z')
5 loops, best of 3: 78.5 ms per loop

With this ticket:

sage: A=[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1],[1/4,1/4,1/4,1/4]]
sage: n=len(A)
sage: A=[vector(v) for v in A]
sage: AP = Polyhedron(vertices=A)
sage: M,b=AP.affine_hull_projection(orthonormal=True,extend=True,as_affine_map=True,minimal=True)
sage: V=[]
....: for i in range(n): 
....:     for j in range(i+1,n): 
....:             V.append((A[i]-A[j])/2) 
sage: Z=polytopes.zonotope(V)
sage: T = M.matrix().transpose()
sage: timeit('T*Z')
25 loops, best of 3: 18 ms per loop

The idea behind this ticket is that applying T (the matrix transforming AP is applied to a different polytope Z, so it might pay off to make T minimal so that for a large Z the computation of the transformation is not slowed by operations in AA.

CC: @kliem

Component: geometry

Keywords: affine_hull, polytope

Author: Jean-Philippe Labbé

Branch/Commit: d78b11b

Reviewer: Jonathan Kliem

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

[kliem]

comment:3

sage: %timeit M,b=AP.affine_hull_projection(orthonormal=True,extend=True,minimal=True,as_affine_map=True)                                                                           
49 ms ± 203 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Looks like you just outsourced the labor. But maybe in larger examples this pays of.

[kliem]

comment:4

Apparently it is at least better asymptotically.

sage: P = polytopes.permutahedron(5)                                                                                                                                                
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True)                                                                                                                
78.9 ms ± 216 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True,minimal=True)                                                                                                   
119 ms ± 362 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.permutahedron(6)                                                                                                                                                
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True)                                                                                                                
334 ms ± 2.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True,minimal=True)                                                                                                   
276 ms ± 1.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

[sagetrac-git]

Changed commit from ff5aebf to 529865b

[sagetrac-git]

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

529865b

Added Example

[jplab]

comment:6

... forgot to add an example. ;)

[jplab]

comment:7

Replying to @kliem:

Apparently it is at least better asymptotically.

sage: P = polytopes.permutahedron(5)                                                                                                                                                
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True)                                                                                                                
78.9 ms ± 216 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True,minimal=True)                                                                                                   
119 ms ± 362 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: P = polytopes.permutahedron(6)                                                                                                                                                
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True)                                                                                                                
334 ms ± 2.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit P.affine_hull_projection(orthonormal=True,extend=True,minimal=True)                                                                                                   
276 ms ± 1.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Yes, I am outsourcing of course. The point is of course to apply the matrix to other potential polytopes as it was the idea behind the problem that led to this ticket.

Further, it is an "unfair" comparison, since minimal=True does more, since it really computes the minimal polynomial (which is not done for polytopes if I am not mistaken, you might disagree here, it has been a while).

But cool that it seems to be a bit faster for larger stuff. :)

[jplab]

comment:9

I modified the description of the ticket to make this more clear that the option "minimal=True" does not have the goal to be faster, but rather to simply provide a different type of output.

[kliem]

comment:10

Well, I would expect it to be asymptotically faster, as I was seeing those bad timings with matrix computations with AA.

[kliem]

comment:11

Could you perhaps fix this:

-found 0 pyflakes errors in the modified files
+src/sage/geometry/polyhedron/base.py:4793:17 local variable 'R' is assigned to but never used

Instead of adopting this syntax

+        - ``minimal`` (boolean, default = False) --

I would propse changing affine_hull_projection to standard syntax.

Forgot spaces:

-                    new_ring = number_field_elements_from_algebraics(A.list(),embedded=True,minimal=True)[0]
+                    new_ring = number_field_elements_from_algebraics(A.list(), embedded=True, minimal=True)[0]

Also the previous is a super long line. Maybe you can change this along with

 return linear_transformation(matrix(self.base_ring(), self.dim(), self.dim(), self.base_ring().one())), self.ambient_space().zero()

[kliem]

Reviewer: Jonathan Kliem

[fchapoton]

comment:13

the pyflakes warning can be fixed by adding "assert R" just after the line

[sagetrac-git]

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

d78b11b

Some fixes

[sagetrac-git]

Changed commit from 529865b to d78b11b

[kliem]

comment:15

LGTM.

[vbraun]

Changed branch from u/jipilab/min_affhull to d78b11b