Opened 6 years ago
Closed 6 years ago
#22562 closed enhancement (fixed)
Lattice point count with preprocessing
Reported by:  Matthias Köppe  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  geometry  Keywords:  days84 
Cc:  JeanPhilippe Labbé, Vincent Delecroix, Travis Scrimshaw  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  540a097 (Commits, GitHub, GitLab)  Commit:  540a09775b8c50f0acfae130226e2ec5d5ba782f 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket
 provides a trivial
Polyhedron_base.integral_points_count
implementation that delegates tointegral_points
 moves the LattEbased
integral_points_count
implementation toPolyhedron_QQ
 adds preprocessing (bounds tightening) to it and uses explicit enumeration when that is expected to be faster
Change History (23)
comment:1 Changed 6 years ago by
Dependencies:  → #22497 

comment:2 Changed 6 years ago by
Cc:  JeanPhilippe Labbé Vincent Delecroix added 

comment:3 Changed 6 years ago by
Branch:  → u/mkoeppe/lattice_point_count_with_preprocessing 

comment:4 Changed 6 years ago by
Commit:  → 04f728639677cf615627e4aa713f4207dd61ec80 

Dependencies:  #22497 → #22497, #22577, #22568 
comment:5 Changed 6 years ago by
Commit:  04f728639677cf615627e4aa713f4207dd61ec80 → 48520a90a56268be6bb98de607522eb4eb42408c 

comment:6 Changed 6 years ago by
This feature is now complete  but the branch needs to be rebased onto its prereq tickets.
comment:7 Changed 6 years ago by
Dependencies:  #22497, #22577, #22568 → #22497, #22577, #22568, #22578 

comment:8 Changed 6 years ago by
Commit:  48520a90a56268be6bb98de607522eb4eb42408c → 579b6beddfbafdcabd1e55710c6f1f9a6e8e9b1a 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
67eb1d7  Change Polyhedron_ZZ to inherit from Polyhedron_QQ, not Polyhedron_base

79dd166  Merge remotetracking branch 'trac/u/mkoeppe/polyhedron_zz_should_inherit_from_polyhedron_qq__not_polyhedron_base' into 7.6.rc1+22568+22578

d08356c  22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points

486204f  Polyhedron.bounding_box: Handle empty bounding box

18e7a74  Fixing doctests and doing it so the order doesn't change in the future.

ac0ecd8  Merge remotetracking branch 'trac/public/geometry/polyhedron_bounding_box_integer_hull22578' into 7.6.rc1+22568+22578

579b6be  Polyhedron.integral_points_count: For QQ, use LattE with preprocessing. Otherwise delegate to integral_points.

comment:9 Changed 6 years ago by
Authors:  → Matthias Koeppe 

Cc:  Travis Scrimshaw added 
Dependencies:  #22497, #22577, #22568, #22578 → #22568, #22578 
Description:  modified (diff) 
comment:10 Changed 6 years ago by
Commit:  579b6beddfbafdcabd1e55710c6f1f9a6e8e9b1a → 69f0f888f730d702d3404dd2cc668ff12fe41eec 

Branch pushed to git repo; I updated commit sha1. New commits:
69f0f88  Add documentation and example for preprocess

comment:11 Changed 6 years ago by
Status:  new → needs_review 

comment:12 Changed 6 years ago by
Commit:  69f0f888f730d702d3404dd2cc668ff12fe41eec → 1c9ccf7308475264d51bc82c6f4984dd027e0e08 

comment:14 Changed 6 years ago by
Milestone:  sage7.6 → sage8.0 

comment:15 Changed 6 years ago by
All tests passed on 7.6 using optional=4ti2,latte_int,lrslib,mpir,normaliz,pynormaliz,topcom
.
comment:16 Changed 6 years ago by
Reviewers:  → JeanPhilippe Labbé 

Dear Matthias,
Having in mind the doc description of integral_hull
, I do not really get the following output,
sage: Polyhedron([ (1/3,2/3), (3/3, 4/3) ]).bounding_box(integral_hull=True) ((1, 1), (1, 1))
The polyhedron does not have integral points but it returns a box, which is just a point in this case and is not contained in the polytope. I guess this is just because the example is too small to interpret the utility of bounding_box
, so it's okay...
Probably the description of integral_hull
in the doc should then be adapted/rephrased to say that it returns the integral hull of a bounding box, because it is confusing with the example... maybe add a "seealso" to point to integral_points
to explain the usage of that parameter?
Otherwise, it looks good to me!
comment:17 followup: 22 Changed 6 years ago by
No, bounding_box(integral_hull=True)
returns a bounding box for the integral hull, rather than the integral hull of a bounding box.
comment:19 Changed 6 years ago by
Description:  modified (diff) 

comment:20 Changed 6 years ago by
Commit:  1c9ccf7308475264d51bc82c6f4984dd027e0e08 → 540a09775b8c50f0acfae130226e2ec5d5ba782f 

comment:21 Changed 6 years ago by
Dependencies:  #22568, #22578 

comment:22 Changed 6 years ago by
Status:  needs_review → positive_review 

Replying to mkoeppe:
No,
bounding_box(integral_hull=True)
returns a bounding box for the integral hull, rather than the integral hull of a bounding box.
Oh! I see. My bad.
Thanks for the rebase! It looks good to me.
comment:23 Changed 6 years ago by
Branch:  u/mkoeppe/lattice_point_count_with_preprocessing → 540a09775b8c50f0acfae130226e2ec5d5ba782f 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
22497: generic interface to LattE integrale count
WIP