Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#22578 closed enhancement (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.6
Component: geometry Keywords: days84, days85
Cc: vdelecroix, jipilab, tscrim Merged in:
Authors: Matthias Koeppe Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 18e7a74 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (20)

comment:1 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/polyhedron_bounding_box__new_keyword_argument_integral_hull__use_it_it__integral_points

comment:2 Changed 4 years ago by mkoeppe

  • Cc vdelecroix jipilab added
  • Commit set to b82ac33abb8e7db2340db42af4e9047834d3132f
  • Keywords days84 added
  • Status changed from new to needs_review

New commits:

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

comment:3 Changed 4 years ago by mkoeppe

  • Summary changed from Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points to Polyhedron.bounding_box: New keyword argument integral_hull, use it in .integral_points

comment:4 Changed 4 years ago by mkoeppe

  • Cc tscrim added

comment:5 Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work

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

comment:6 Changed 4 years ago by mkoeppe

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

comment:7 Changed 4 years ago by git

  • Commit changed from b82ac33abb8e7db2340db42af4e9047834d3132f to 486204f7e7a5ac5f14573e006f3d6464584ef6bd

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

d08356c22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points
486204fPolyhedron.bounding_box: Handle empty bounding box

comment:8 Changed 4 years ago by mkoeppe

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?

comment:9 Changed 4 years ago by tscrim

  • Keywords days85 added
  • Reviewers set to Travis Scrimshaw

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.

comment:10 Changed 4 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:11 Changed 4 years ago by tscrim

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.

comment:12 Changed 4 years ago by mkoeppe

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.

comment:13 Changed 4 years ago by tscrim

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.

comment:14 Changed 4 years ago by mkoeppe

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...

comment:15 Changed 4 years ago by tscrim

I will do so now.

comment:16 Changed 4 years ago by tscrim

  • Branch changed 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
  • Commit changed from 486204f7e7a5ac5f14573e006f3d6464584ef6bd to 18e7a748198e1c3abc175b703a24d1010b8ee8cf

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:

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

comment:17 Changed 4 years ago by mkoeppe

  • Status changed from needs_review to positive_review

Looks good. Thanks very much!

comment:18 Changed 4 years ago by vbraun

  • Branch changed from public/geometry/polyhedron_bounding_box_integer_hull-22578 to 18e7a748198e1c3abc175b703a24d1010b8ee8cf
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:19 Changed 4 years ago by jmantysalo

  • Branch changed from 18e7a748198e1c3abc175b703a24d1010b8ee8cf to u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf

comment:20 Changed 4 years ago by jmantysalo

  • Branch changed from u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf to 18e7a748198e1c3abc175b703a24d1010b8ee8cf
  • Commit 18e7a748198e1c3abc175b703a24d1010b8ee8cf deleted

Sorry, my typo in a ticket number.

Note: See TracTickets for help on using tickets.