Opened 4 years ago
Closed 4 years ago
#22562 closed enhancement (fixed)
Lattice point count with preprocessing
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  geometry  Keywords:  days84 
Cc:  jipilab, vdelecroix, tscrim  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 4 years ago by
 Dependencies set to #22497
comment:2 Changed 4 years ago by
 Cc jipilab vdelecroix added
comment:3 Changed 4 years ago by
 Branch set to u/mkoeppe/lattice_point_count_with_preprocessing
comment:4 Changed 4 years ago by
 Commit set to 04f728639677cf615627e4aa713f4207dd61ec80
 Dependencies changed from #22497 to #22497, #22577, #22568
comment:5 Changed 4 years ago by
 Commit changed from 04f728639677cf615627e4aa713f4207dd61ec80 to 48520a90a56268be6bb98de607522eb4eb42408c
comment:6 Changed 4 years ago by
This feature is now complete  but the branch needs to be rebased onto its prereq tickets.
comment:7 Changed 4 years ago by
 Dependencies changed from #22497, #22577, #22568 to #22497, #22577, #22568, #22578
comment:8 Changed 4 years ago by
 Commit changed from 48520a90a56268be6bb98de607522eb4eb42408c to 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 4 years ago by
 Cc tscrim added
 Dependencies changed from #22497, #22577, #22568, #22578 to #22568, #22578
 Description modified (diff)
comment:10 Changed 4 years ago by
 Commit changed from 579b6beddfbafdcabd1e55710c6f1f9a6e8e9b1a to 69f0f888f730d702d3404dd2cc668ff12fe41eec
Branch pushed to git repo; I updated commit sha1. New commits:
69f0f88  Add documentation and example for preprocess

comment:11 Changed 4 years ago by
 Status changed from new to needs_review
comment:12 Changed 4 years ago by
 Commit changed from 69f0f888f730d702d3404dd2cc668ff12fe41eec to 1c9ccf7308475264d51bc82c6f4984dd027e0e08
comment:13 Changed 4 years ago by
Patch bot is green now, needs review
comment:14 Changed 4 years ago by
 Milestone changed from sage7.6 to sage8.0
comment:15 Changed 4 years ago by
All tests passed on 7.6 using optional=4ti2,latte_int,lrslib,mpir,normaliz,pynormaliz,topcom
.
comment:16 Changed 4 years ago by
 Reviewers set to 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 4 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:18 Changed 4 years ago by
That code is from the prereq ticket #22578, by the way.
comment:19 Changed 4 years ago by
 Description modified (diff)
comment:20 Changed 4 years ago by
 Commit changed from 1c9ccf7308475264d51bc82c6f4984dd027e0e08 to 540a09775b8c50f0acfae130226e2ec5d5ba782f
comment:21 Changed 4 years ago by
 Dependencies #22568, #22578 deleted
comment:22 in reply to: ↑ 17 Changed 4 years ago by
 Status changed from needs_review to 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 4 years ago by
 Branch changed from u/mkoeppe/lattice_point_count_with_preprocessing to 540a09775b8c50f0acfae130226e2ec5d5ba782f
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
22497: generic interface to LattE integrale count
WIP