# Add "minimal=True" option to affine_hull_projection

Reported by: Owned by: jipilab major sage-9.3 geometry affine_hull, polytope gh-kliem Jean-Philippe Labbé Jonathan Kliem N/A d78b11b d78b11bb5ee07cdf8b7b03ef367ae49078b467cf

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`.

### comment:1 Changed 21 months ago by jipilab

• Status changed from new to needs_review

### comment:2 Changed 21 months ago by jipilab

• Description modified (diff)

### comment:3 Changed 21 months ago by gh-kliem

```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.

### comment:4 follow-up: ↓ 7 Changed 21 months ago by gh-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)
```

### comment:5 Changed 21 months ago by git

• Commit changed from ff5aebf80861db9ddb6a88d3c457e6217b5ef8bd to 529865b7e027d0977ca63c3d98038817138d70bb

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

 ​529865b `Added Example`

### comment:6 Changed 21 months ago by jipilab

... forgot to add an example. ;)

### comment:7 in reply to: ↑ 4 Changed 21 months ago by jipilab

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. :)

### comment:8 Changed 21 months ago by jipilab

• Description modified (diff)

### comment:9 Changed 21 months ago by jipilab

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.

### comment:10 Changed 21 months ago by gh-kliem

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

### comment:11 Changed 21 months ago by gh-kliem

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
```

```+        - ``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()
```

### comment:12 Changed 21 months ago by gh-kliem

• Reviewers set to Jonathan Kliem

### comment:13 Changed 21 months ago by chapoton

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

### comment:14 Changed 21 months ago by git

• Commit changed from 529865b7e027d0977ca63c3d98038817138d70bb to d78b11bb5ee07cdf8b7b03ef367ae49078b467cf

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

 ​d78b11b `Some fixes`

### comment:15 Changed 21 months ago by gh-kliem

• Status changed from needs_review to positive_review

LGTM.

### comment:16 Changed 21 months ago by vbraun

• Branch changed from u/jipilab/min_affhull to d78b11bb5ee07cdf8b7b03ef367ae49078b467cf
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.