Opened 6 years ago
Closed 5 years ago
#22524 closed enhancement (fixed)
Optimize computing points of lattice polytopes
Reported by:  Andrey Novoseltsev  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  geometry  Keywords:  sd91 
Cc:  Merged in:  
Authors:  Andrey Novoseltsev  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  e37e8f7 (Commits, GitHub, GitLab)  Commit:  e37e8f7a3280a89ee1328f39fc2e92b045397401 
Dependencies:  #22391, #22400  Stopgaps: 
Description
A follow up to #22391. My original problem was too slow computation of zero via
Delta3 = LatticePolytope([(1,0,0), (0,1,0), (0,0,1), (1,4,6)]) sum(len(e.interior_points()) * len(e.dual().interior_points()) for e in Delta3.edges())
Sage 7.6.beta4 gives
 timeit: 5 loops, best of 3: 1.73 s per loop
 profiler: 71844 function calls (71620 primitive calls) in 1.841 seconds
With #22391
 timeit: 5 loops, best of 3: 451 ms per loop
 profiler: 46502 function calls (46434 primitive calls) in 0.570 seconds
With this one
 timeit: 25 loops, best of 3: 11.3 ms per loop
 profiler: 7793 function calls (7747 primitive calls) in 0.031 seconds
As a less contrived example, it now takes 0.41s to get ReflexivePolytopes(3)
(cached afterwards) instead of 7.61s. Part of the speed up is due to omitting some precomputation, but it is possible to do so because of speed up on demand.
Next goal is not to rely on PALP for computing points of standalone polytopes at all, although for large sets of polytopes it still may be the fastest option.
Change History (16)
comment:1 Changed 6 years ago by
Branch:  → u/novoselt/points_without_PALP 

comment:2 Changed 6 years ago by
Commit:  → 356cca4cd1c4491af6a7b0f0101b57b4ef414aff 

Status:  new → needs_review 
comment:3 Changed 6 years ago by
For large enough lattice point listing problems, considering using normaliz. Recent tickets have added it as a backend for Polyhedron
.
comment:4 Changed 6 years ago by
Sure, but in toric geometry especially related to mirror symmetry it is important to handle very simple cases fast (e.g. all reflexive polytopes have precisely one interior lattice point, the origin).
Of course, it would be nice to handle all cases efficiently, and to be able to choose new methods appropriately I tried to first optimize existing one as much as possible, in particular not to take too much time just to convert data between different types.
Thanks for taking a look!
comment:5 Changed 6 years ago by
Summary:  Optimize computing points of lattice plytopes → Optimize computing points of lattice polytopes 

comment:6 Changed 5 years ago by
Commit:  356cca4cd1c4491af6a7b0f0101b57b4ef414aff → d1eec1bc9534cb71856868cb92e51e1b8335bd1c 

Branch pushed to git repo; I updated commit sha1. New commits:
d1eec1b  Fix print syntax

comment:7 Changed 5 years ago by
Keywords:  sd91 added 

comment:8 Changed 5 years ago by
Commit:  d1eec1bc9534cb71856868cb92e51e1b8335bd1c → dd6a61608c882d6ef018fcc39abecd953294181e 

Branch pushed to git repo; I updated commit sha1. New commits:
dd6a616  Merge tag '8.1.rc0' into t/22524/points_without_PALP

comment:9 Changed 5 years ago by
Milestone:  sage7.6 → sage8.2 

Reviewers:  → Travis Scrimshaw 
I think an even faster way than
n = N.zero_vector() for i, coef in enumerate(c.coefficients()): n[i] = coef n.set_immutable() normals.append(n)
would be
n = N.element_class(N, c.coefficients(), coerce=False, copy=False) n.set_immutable()
(although perhaps the coerce and copy are unnecessary). In general, if you know your input is good, you can bypass the extra overhead of __call__
and _element_constructor_
(there are a few places where you can do this I believe).
Also, it might be better to do
 points = list(p.vertices())  for j in range(nv, m.ncols()):  current = M.zero_vector()  for i in range(M.rank()):  current[i] = m[i, j]  current.set_immutable()  points.append(current) + points = list(p.vertices()) + m.columns(copy=False) p._points = PointCollection(points, M)
Although I have not checked if the columns are longer than M.rank()
.
Otherwise LGTM.
comment:10 Changed 5 years ago by
Commit:  dd6a61608c882d6ef018fcc39abecd953294181e → 15e7043ed344dbd26a56774bd51c10f5a5981bc4 

Branch pushed to git repo; I updated commit sha1. New commits:
15e7043  Use element_class instead of zero_vector

comment:11 Changed 5 years ago by
Thank you for the pointer, element_class
does lead to better timing and fewer function calls.
Regarding using matrix columns  that code deals with only some part of a matrix and, more importantly, is only used in "bad" cases: when dealing with nonfulldimensional polytopes or with a separate PALP call for a single polytope rather than sequence. My quick attempts to improve them now just broke things and I don't think they are worthy of more effort  the real solution is to rely on different backend. On the other hand, for computing points of many fulldimensional polytopes at once PALP interface still may be the fastest.
comment:12 Changed 5 years ago by
I see. Well, you can do the same element_class
trick for
current = M.zero_vector() for i in range(M.rank()): current[i] = m[i, j]
(there are 2 of these) and
p = lattice.zero_vector() for j, e in enumerate(f.readline().split()): p[j] = int(e)
comment:13 Changed 5 years ago by
Commit:  15e7043ed344dbd26a56774bd51c10f5a5981bc4 → e37e8f7a3280a89ee1328f39fc2e92b045397401 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e37e8f7  Use element_class instead of zero_vector

comment:14 followup: 15 Changed 5 years ago by
Travis  many many many thanks for reviewing all these tickets, making suggestions, and pushing me to implement them! I got 3fold reduction in function calls for lattice_polytope.all_points(ReflexivePolytopes(3))
and the actual call to PALP is now responsible for a half of the time.
Regarding using columns of matrices  it is kind of incompatible with element_constructor
since it expects lists or tuples, not vectors. Constructing a vector and then converting it to a list takes 3 times longer than just constructing this list directly from matrix elements.
I have also dropped copy=False, coerce=False
since they do not seem to be used in the code and (while I cannot use vectors...) I can feed strings directly into element_constructor
without converting them to int
first.
comment:15 Changed 5 years ago by
Status:  needs_review → positive_review 

Replying to novoselt:
Travis  many many many thanks for reviewing all these tickets, making suggestions, and pushing me to implement them! I got 3fold reduction in function calls for
lattice_polytope.all_points(ReflexivePolytopes(3))
and the actual call to PALP is now responsible for a half of the time.
Not a problem. I'm sorry to took me a while to get through them all.
Regarding using columns of matrices  it is kind of incompatible with
element_constructor
since it expects lists or tuples, not vectors. Constructing a vector and then converting it to a list takes 3 times longer than just constructing this list directly from matrix elements.
I see.
I have also dropped
copy=False, coerce=False
since they do not seem to be used in the code and (while I cannot use vectors...) I can feed strings directly intoelement_constructor
without converting them toint
first.
Yea, that's not too surprising. I didn't think they were being used considering the datatypes, but it was more justincase.
LGTM. Positive review.
comment:16 Changed 5 years ago by
Branch:  u/novoselt/points_without_PALP → e37e8f7a3280a89ee1328f39fc2e92b045397401 

Resolution:  → fixed 
Status:  positive_review → closed 
Had to fix a doctest, results of
sage t long src/sage/schemes/toric/fano_variety.py
Last 10 new commits:
Compute edge points directly
Optimize point creation using zero_vector
Transpose databases of small reflexive polytopes
Merge transpose_lattice_polytopes into points_without_PALP
Read/write PointCollection in PALP format directly
Do not precompute all polars of reflexive polytopes
Use zero_vector when constructing normals for speed
Fix normal form computation
Optimize getting points from PALP without embedding
Fix doctest depending on normals order and drop long time