Opened 3 years ago

Closed 3 years ago

#22562 closed enhancement (fixed)

Lattice point count with preprocessing

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-8.0
Component: geometry Keywords: days84
Cc: jipilab, vdelecroix, tscrim Merged in:
Authors: Matthias Koeppe Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 540a097 (Commits) Commit: 540a09775b8c50f0acfae130226e2ec5d5ba782f
Dependencies: Stopgaps:

Description (last modified by mkoeppe)

This ticket

  • provides a trivial Polyhedron_base.integral_points_count implementation that delegates to integral_points
  • moves the LattE-based integral_points_count implementation to Polyhedron_QQ
  • adds preprocessing (bounds tightening) to it and uses explicit enumeration when that is expected to be faster

Change History (23)

comment:1 Changed 3 years ago by mkoeppe

  • Dependencies set to #22497

comment:2 Changed 3 years ago by mkoeppe

  • Cc jipilab vdelecroix added

comment:3 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/lattice_point_count_with_preprocessing

comment:4 Changed 3 years ago by mkoeppe

  • Commit set to 04f728639677cf615627e4aa713f4207dd61ec80
  • Dependencies changed from #22497 to #22497, #22577, #22568

New commits:

d5ff15422497: generic interface to LattE integrale count
04f7286WIP

comment:5 Changed 3 years ago by git

  • Commit changed from 04f728639677cf615627e4aa713f4207dd61ec80 to 48520a90a56268be6bb98de607522eb4eb42408c

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

e0ce5a1count: Handle a case in which LattE prints no output
3ba2603Polyhedron_base.integral_points: Use bounding_box(integral_hull=True)
48520a9Move fancy integral_points_count into Polyhedron_QQ

comment:6 Changed 3 years ago by mkoeppe

This feature is now complete -- but the branch needs to be rebased onto its prereq tickets.

comment:7 Changed 3 years ago by mkoeppe

  • Dependencies changed from #22497, #22577, #22568 to #22497, #22577, #22568, #22578

comment:8 Changed 3 years ago by git

  • Commit changed from 48520a90a56268be6bb98de607522eb4eb42408c to 579b6beddfbafdcabd1e55710c6f1f9a6e8e9b1a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

67eb1d7Change Polyhedron_ZZ to inherit from Polyhedron_QQ, not Polyhedron_base
79dd166Merge remote-tracking branch 'trac/u/mkoeppe/polyhedron_zz_should_inherit_from_polyhedron_qq__not_polyhedron_base' into 7.6.rc1+22568+22578
d08356c22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points
486204fPolyhedron.bounding_box: Handle empty bounding box
18e7a74Fixing doctests and doing it so the order doesn't change in the future.
ac0ecd8Merge remote-tracking branch 'trac/public/geometry/polyhedron_bounding_box_integer_hull-22578' into 7.6.rc1+22568+22578
579b6bePolyhedron.integral_points_count: For QQ, use LattE with preprocessing. Otherwise delegate to integral_points.

comment:9 Changed 3 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Cc tscrim added
  • Dependencies changed from #22497, #22577, #22568, #22578 to #22568, #22578
  • Description modified (diff)

Rebased on top of 7.6.rc1 and #22568, #22578.

comment:10 Changed 3 years ago by git

  • Commit changed from 579b6beddfbafdcabd1e55710c6f1f9a6e8e9b1a to 69f0f888f730d702d3404dd2cc668ff12fe41eec

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

69f0f88Add documentation and example for preprocess

comment:11 Changed 3 years ago by mkoeppe

  • Status changed from new to needs_review

comment:12 Changed 3 years ago by git

  • Commit changed from 69f0f888f730d702d3404dd2cc668ff12fe41eec to 1c9ccf7308475264d51bc82c6f4984dd027e0e08

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

639c956integral_points_count: Fix wrong test
1c9ccf7Merge tag '7.6' into t/22562/lattice_point_count_with_preprocessing

comment:13 Changed 3 years ago by mkoeppe

Patch bot is green now, needs review

comment:14 Changed 3 years ago by mkoeppe

  • Milestone changed from sage-7.6 to sage-8.0

comment:15 Changed 3 years ago by jipilab

All tests passed on 7.6 using optional=4ti2,latte_int,lrslib,mpir,normaliz,pynormaliz,topcom.

comment:16 Changed 3 years ago by jipilab

  • Reviewers set to Jean-Philippe 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 follow-up: Changed 3 years ago by mkoeppe

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 3 years ago by mkoeppe

That code is from the prereq ticket #22578, by the way.

comment:19 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:20 Changed 3 years ago by git

  • Commit changed from 1c9ccf7308475264d51bc82c6f4984dd027e0e08 to 540a09775b8c50f0acfae130226e2ec5d5ba782f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

37e9c66Polyhedron.integral_points_count: For QQ, use LattE with preprocessing. Otherwise delegate to integral_points.
540a097Add documentation and example for preprocess

comment:21 Changed 3 years ago by mkoeppe

  • Dependencies #22568, #22578 deleted

Rebased on 8.0.beta0 (which merged #22568, #22578).

comment:22 in reply to: ↑ 17 Changed 3 years ago by jipilab

  • 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 3 years ago by vbraun

  • Branch changed from u/mkoeppe/lattice_point_count_with_preprocessing to 540a09775b8c50f0acfae130226e2ec5d5ba782f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.