Opened 6 years ago
Last modified 6 years ago
#21041 new enhancement
Polyhedron.integral_points(): Generalize Smith form based enumeration to rational and semi-rational polytopes
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | geometry | Keywords: | |
Cc: | tscrim, novoselt, dimpase, vdelecroix, vbraun, Winfried | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As a follow-up to #21037, the method for integer point enumeration using triangulation and Smith form (a simple implementation of normaliz's method (see #20885 comment:6) in simplex_points
is limited to lattice polytopes. Normaliz is much faster and has an implementation for rational (non-lattice) polytopes. A generalization to include the case of semi-rational polytopes (i.e., possibly irrational translations of lattice polytopes) could be valuable; example:
sage: P = Polyhedron(vertices=((0, 0), (1743,3134))) + 1/1000*vector(AA, [AA(sqrt(5)), AA(sqrt(5))]) sage: P.integral_points() # takes LONG
Change History (9)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 6 years ago by
Replying to tscrim:
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
Yes, that could be a simple technique that would require only small changes of the code. The normaliz manual (https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf, page 64, section 6.1) explains an "approximation technique" similar to this idea.
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?
It is explained, for example, in http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf Lemma 11.
comment:3 in reply to: ↑ 2 Changed 6 years ago by
Replying to mkoeppe:
Replying to tscrim:
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
Yes, that could be a simple technique that would require only small changes of the code. The normaliz manual (https://www.normaliz.uni-osnabrueck.de/wp-content/uploads/2016/04/Normaliz3.1.1Documentation.pdf, page 64, section 6.1) explains an "approximation technique" similar to this idea.
The hard part, to me, of this would be constructing the approximation lattice polytope. Would we just take the convex hull of all of the cell containing each of the non-integral vertices of the original polytope? Or is there a smarter method?
I'm thinking we should implement both approaches (at least for now to see if one definitely beats the other). Plus, the approximation could be used as a general purpose technique.
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?
It is explained, for example, in http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r16/pdf Lemma 11.
Thank you for the reference. Do you think you could provide this implementation? I am pretty sure I could do the first half above.
comment:4 follow-up: ↓ 5 Changed 6 years ago by
This should have low priority until someone "really" wants to do computations with semirational polytopes. For the more common case of rational polytopes, with MUCH less effort one can make an "easy" implementation of a normaliz interface (using file passing instead of using libnormaliz).
comment:5 in reply to: ↑ 4 Changed 6 years ago by
Replying to mkoeppe:
For the more common case of rational polytopes, with MUCH less effort one can make an "easy" implementation of a normaliz interface (using file passing instead of using libnormaliz).
Note that such file passings and system calls add a considerable constant overhead (perhaps 0.1s on modern systems). This makes it horrible for large numbers of small polytopes. So it would be nice to have a library interface even though I don't volunteer to implement it ;-)
comment:6 Changed 6 years ago by
Perhaps we should split this into 2 tickets, one for the rational case(s) and one of the semirational case? I can probably get the rational case(s) done tonight.
Unfortunately I cannot write code to interface with (lib)normaliz (addendum - without taking some time to do some reading and experimenting), but I will be happy to review it.
comment:7 Changed 6 years ago by
I'm visiting the normaliz people later this week. Maybe we will make a quick libnormaliz interface. Stay tuned.
comment:8 Changed 6 years ago by
- Cc Winfried added
For the rational case, we now have an implementation using normaliz in #20885. It can handle for example this:
sage: P = Polyhedron(vertices=((0, 0), (1789345,37121))) + 1/1000*polytopes.hypercube(2) sage: V=P.vertices_list() sage: P = Polyhedron(vertices=V, backend='normaliz') sage: %timeit P.integral_points() 1 loop, best of 3: 134 ms per loop sage: len(P.integral_points()) 3654
comment:9 Changed 6 years ago by
- Summary changed from Polyhedron.integral_points(): Generalize Smith form based enumeration to semi-rational polytopes to Polyhedron.integral_points(): Generalize Smith form based enumeration to rational and semi-rational polytopes
Would it be beneficial to expand a rational polytope so that its points are integral, and then filter out the points which would not be integers upon shrinking?
I'm guessing the way to check for translates of a rational/lattice polytope is to actually look at the differences of the vertices relative to a fixed vertex?