Opened 5 months ago
Closed 4 months ago
#30946 closed enhancement (fixed)
Add "minimal=True" option to affine_hull_projection
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  geometry  Keywords:  affine_hull, polytope 
Cc:  ghkliem  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Jonathan Kliem 
Report Upstream:  N/A  Work issues:  
Branch:  d78b11b (Commits, GitHub, GitLab)  Commit:  d78b11bb5ee07cdf8b7b03ef367ae49078b467cf 
Dependencies:  Stopgaps: 
Description (last modified by )
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
.
Change History (16)
comment:1 Changed 5 months ago by
 Status changed from new to needs_review
comment:2 Changed 5 months ago by
 Description modified (diff)
comment:3 Changed 5 months ago by
comment:4 followup: ↓ 7 Changed 5 months ago by
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 5 months ago by
 Commit changed from ff5aebf80861db9ddb6a88d3c457e6217b5ef8bd to 529865b7e027d0977ca63c3d98038817138d70bb
Branch pushed to git repo; I updated commit sha1. New commits:
529865b  Added Example

comment:6 Changed 5 months ago by
... forgot to add an example. ;)
comment:7 in reply to: ↑ 4 Changed 5 months ago by
Replying to ghkliem:
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 5 months ago by
 Description modified (diff)
comment:9 Changed 5 months ago by
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 5 months ago by
Well, I would expect it to be asymptotically faster, as I was seeing those bad timings with matrix computations with AA
.
comment:11 Changed 5 months ago by
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()
comment:12 Changed 5 months ago by
 Reviewers set to Jonathan Kliem
comment:13 Changed 5 months ago by
the pyflakes warning can be fixed by adding "assert R" just after the line
comment:14 Changed 5 months ago by
 Commit changed from 529865b7e027d0977ca63c3d98038817138d70bb to d78b11bb5ee07cdf8b7b03ef367ae49078b467cf
Branch pushed to git repo; I updated commit sha1. New commits:
d78b11b  Some fixes

comment:16 Changed 4 months ago by
 Branch changed from u/jipilab/min_affhull to d78b11bb5ee07cdf8b7b03ef367ae49078b467cf
 Resolution set to fixed
 Status changed from positive_review to closed
Looks like you just outsourced the labor. But maybe in larger examples this pays of.