Lattice point count with preprocessing

[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

CC: @jplab @videlec @tscrim

Component: geometry

Keywords: days84

Author: Matthias Koeppe

Branch/Commit: 540a097

Reviewer: Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/22562

[mkoeppe]

Dependencies: #22497

[mkoeppe]

Branch: u/mkoeppe/lattice_point_count_with_preprocessing

[mkoeppe]

Changed dependencies from #22497 to #22497, #22577, #22568

[mkoeppe]

Commit: 04f7286

[mkoeppe]

New commits:

d5ff154	22497: generic interface to LattE integrale count
04f7286	WIP

[sagetrac-git]

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

e0ce5a1	count: Handle a case in which LattE prints no output
3ba2603	Polyhedron_base.integral_points: Use bounding_box(integral_hull=True)
48520a9	Move fancy integral_points_count into Polyhedron_QQ

[sagetrac-git]

Changed commit from 04f7286 to 48520a9

[mkoeppe]

comment:6

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

[mkoeppe]

Changed dependencies from #22497, #22577, #22568 to #22497, #22577, #22568, #22578

[sagetrac-git]

Changed commit from 48520a9 to 579b6be

[sagetrac-git]

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 remote-tracking 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 remote-tracking branch 'trac/public/geometry/polyhedron_bounding_box_integer_hull-22578' into 7.6.rc1+22568+22578
579b6be	Polyhedron.integral_points_count: For QQ, use LattE with preprocessing. Otherwise delegate to integral_points.

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

Changed dependencies from #22497, #22577, #22568, #22578 to #22568, #22578

[mkoeppe]

comment:9

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

[sagetrac-git]

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

69f0f88

Add documentation and example for preprocess

[sagetrac-git]

Changed commit from 579b6be to 69f0f88

[sagetrac-git]

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

639c956	integral_points_count: Fix wrong test
1c9ccf7	Merge tag '7.6' into t/22562/lattice_point_count_with_preprocessing

[sagetrac-git]

Changed commit from 69f0f88 to 1c9ccf7

[mkoeppe]

comment:13

Patch bot is green now, needs review

[jplab]

comment:15

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

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:16

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!

[mkoeppe]

comment:17

No, bounding_box(integral_hull=True) returns a bounding box for the integral hull, rather than the integral hull of a bounding box.

[mkoeppe]

comment:18

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

[sagetrac-git]

Changed commit from 1c9ccf7 to 540a097

[sagetrac-git]

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

37e9c66	Polyhedron.integral_points_count: For QQ, use LattE with preprocessing. Otherwise delegate to integral_points.
540a097	Add documentation and example for preprocess

[mkoeppe]

comment:21

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

[mkoeppe]

Changed dependencies from #22568, #22578 to none

[jplab]

comment:22

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.

[vbraun]

Changed branch from u/mkoeppe/lattice_point_count_with_preprocessing to 540a097