Opened 5 years ago

Last modified 5 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:

Status badges

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: Changed 5 years ago by 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?

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?

comment:2 in reply to: ↑ 1 ; follow-up: Changed 5 years ago by 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.

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 5 years ago by tscrim

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: Changed 5 years ago by mkoeppe

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 5 years ago by novoselt

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 5 years ago by tscrim

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.

Last edited 5 years ago by tscrim (previous) (diff)

comment:7 Changed 5 years ago by mkoeppe

I'm visiting the normaliz people later this week. Maybe we will make a quick libnormaliz interface. Stay tuned.

comment:8 Changed 5 years ago by mkoeppe

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

  • 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
Note: See TracTickets for help on using tickets.