Opened 11 months ago

Last modified 11 months ago

#30946 closed enhancement

Add "minimal=True" option to affine_hull_projection — at Version 8

Reported by: jipilab Owned by:
Priority: major Milestone: sage-9.3
Component: geometry Keywords: affine_hull, polytope
Cc: gh-kliem Merged in:
Authors: Jean-Philippe Labbé Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jipilab/min_affhull (Commits, GitHub, GitLab) Commit: 529865b7e027d0977ca63c3d98038817138d70bb
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

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 (8)

comment:1 Changed 11 months ago by jipilab

  • Status changed from new to needs_review

comment:2 Changed 11 months ago by jipilab

  • Description modified (diff)

comment:3 Changed 11 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: Changed 11 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 11 months ago by git

  • Commit changed from ff5aebf80861db9ddb6a88d3c457e6217b5ef8bd to 529865b7e027d0977ca63c3d98038817138d70bb

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

529865bAdded Example

comment:6 Changed 11 months ago by jipilab

... forgot to add an example. ;)

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

Replying to 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)

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

  • Description modified (diff)
Note: See TracTickets for help on using tickets.