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

[mkoeppe]

An amazing insight is that if one wants to know to bounding box of the integer points, rather than of all points, then one can round down upper bounds and round up lower bounds.

This can make a huge difference for integer points enumeration.

CC: @videlec @jplab @tscrim

Component: geometry

Keywords: days84, days85

Author: Matthias Koeppe

Branch: 18e7a74

Reviewer: Travis Scrimshaw

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

[mkoeppe]

Branch: u/mkoeppe/polyhedron_bounding_box__new_keyword_argument_integral_hull__use_it_it__integral_points

[mkoeppe]

New commits:

b82ac33

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

[mkoeppe]

Commit: b82ac33

[mkoeppe]

Changed keywords from none to days84

[tscrim]

comment:5

This causes doctest failures in sandpiles. My guess is something is now returning a None that is fed to a zip.

[mkoeppe]

comment:6

Thanks for catching this. I'm preparing a fix.

[sagetrac-git]

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

d08356c	22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points
486204f	Polyhedron.bounding_box: Handle empty bounding box

[sagetrac-git]

Changed commit from b82ac33 to 486204f

[mkoeppe]

comment:8

Fixed the failures that resulted from empty bounding boxes;
but there remain failures that result from different sorting orders of integral_points.
Should I change all these doctests so that they become independent of the sorting order?

[tscrim]

comment:9

If the output of integral_points is not subject to location in memory, then you don't have to. I'm prepared to set a positive review once addressed.

[tscrim]

Changed keywords from days84 to days84, days85

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:11

It looks like the order of some doctests in sandpiles have either changes or does depend on the machine/memory location (which is the case if they pass on your machine). I do agree that they are all trivial failures and can be easily fixed, but I just need an answer to which of the above cases we are in.

[mkoeppe]

comment:12

I think the order has changed because a different enumeration strategy is selected. I don't think it's machine or address specific.
In my opinion, doctests should not rely on the order of lists whose ordering is unspecified by documentation; they should be rewritten using sort or set.

[tscrim]

comment:13

If you want to change the tests so that the order is sorted, go ahead. I would avoid using set since (unfortunately) the output may not be in a specific order. However, we can just change the output for now too. I can also make these changes if you want me to.

[mkoeppe]

comment:14

I would strongly suggest to adjust the tests to use sort then; because it is very likely that future changes to the lattice point enumeration code (such as automatic selection of the normaliz backend if it is available) will change the order again. If you'd like to go ahead with this change, that would be great...

[tscrim]

comment:15

I will do so now.

[tscrim]

comment:16

All tests now pass, and they are now checked by sorting the output. If my changes look good to you, then you can set a positive review.

---

New commits:

18e7a74

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

[tscrim]

Changed commit from 486204f to 18e7a74

[tscrim]

Changed branch from u/mkoeppe/polyhedron_bounding_box__new_keyword_argument_integral_hull__use_it_it__integral_points to public/geometry/polyhedron_bounding_box_integer_hull-22578

[mkoeppe]

comment:17

Looks good. Thanks very much!

[vbraun]

Changed branch from public/geometry/polyhedron_bounding_box_integer_hull-22578 to 18e7a74

[jm58660]

Changed branch from 18e7a74 to u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf

[jm58660]

Changed commit from 18e7a74 to none

[jm58660]

Changed branch from u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf to 18e7a74

[jm58660]

comment:20

Sorry, my typo in a ticket number.