The Normaliz backend for polyhedral computations

Note

This backend requires PyNormaliz. To install PyNormaliz, type sage -i pynormaliz in the terminal.

AUTHORS:

  • Matthias Köppe (2016-12): initial version
class sage.geometry.polyhedron.backend_normaliz.Polyhedron_QQ_normaliz(parent, Vrep, Hrep, normaliz_cone=None, **kwds)

Bases: sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz, sage.geometry.polyhedron.base_QQ.Polyhedron_QQ

Polyhedra over \(\QQ\) with normaliz.

INPUT:

  • Vrep – a list [vertices, rays, lines] or None
  • Hrep – a list [ieqs, eqns] or None

EXAMPLES:

sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)],                 # optional - pynormaliz
....:                rays=[(1,1)], lines=[],
....:                backend='normaliz', base_ring=QQ)
sage: TestSuite(p).run(skip='_test_pickling')                      # optional - pynormaliz
class sage.geometry.polyhedron.backend_normaliz.Polyhedron_ZZ_normaliz(parent, Vrep, Hrep, normaliz_cone=None, **kwds)

Bases: sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz, sage.geometry.polyhedron.base_ZZ.Polyhedron_ZZ

Polyhedra over \(\ZZ\) with normaliz.

INPUT:

  • Vrep – a list [vertices, rays, lines] or None
  • Hrep – a list [ieqs, eqns] or None

EXAMPLES:

sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)],                 # optional - pynormaliz
....:                rays=[(1,1)], lines=[],
....:                backend='normaliz', base_ring=ZZ)
sage: TestSuite(p).run(skip='_test_pickling')                      # optional - pynormaliz
class sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz(parent, Vrep, Hrep, normaliz_cone=None, **kwds)

Bases: sage.geometry.polyhedron.base.Polyhedron_base

Polyhedra with normaliz

INPUT:

  • parentPolyhedra the parent
  • Vrep – a list [vertices, rays, lines] or None; the V-representation of the polyhedron; if None, the polyhedron is determined by the H-representation
  • Hrep – a list [ieqs, eqns] or None; the H-representation of the polyhedron; if None, the polyhedron is determined by the V-representation
  • normaliz_cone – a PyNormaliz wrapper of a normaliz cone

Only one of Vrep, Hrep, or normaliz_cone can be different from None.

EXAMPLES:

sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], rays=[(1,1)],   # optional - pynormaliz
....:                lines=[], backend='normaliz')
sage: TestSuite(p).run(skip='_test_pickling')                      # optional - pynormaliz

Two ways to get the full space:

sage: Polyhedron(eqns=[[0, 0, 0]], backend='normaliz')             # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 lines
sage: Polyhedron(ieqs=[[0, 0, 0]], backend='normaliz')             # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 lines

A lower-dimensional affine cone; we test that there are no mysterious inequalities coming in from the homogenization:

sage: P = Polyhedron(vertices=[(1, 1)], rays=[(0, 1)],             # optional - pynormaliz
....:                backend='normaliz')
sage: P.n_inequalities()                                           # optional - pynormaliz
1
sage: P.equations()                                                # optional - pynormaliz
(An equation (1, 0) x - 1 == 0,)

The empty polyhedron:

sage: P=Polyhedron(ieqs=[[-2, 1, 1], [-3, -1, -1], [-4, 1, -2]],   # optional - pynormaliz
....:              backend='normaliz')
sage: P                                                            # optional - pynormaliz
The empty polyhedron in QQ^2
sage: P.Vrepresentation()                                          # optional - pynormaliz
()
sage: P.Hrepresentation()                                          # optional - pynormaliz
(An equation -1 == 0,)
integral_hull()

Return the integral hull in the polyhedron.

This is a new polyhedron that is the convex hull of all integral points.

EXAMPLES:

Unbounded example from Normaliz manual, “a dull polyhedron”:

sage: P = Polyhedron(ieqs=[[1, 0, 2], [3, 0, -2], [3, 2, -2]], # optional - pynormaliz
....:              backend='normaliz')
sage: PI = P.integral_hull()                                   # optional - pynormaliz
sage: P.plot(color='yellow') + PI.plot(color='green')          # optional - pynormaliz
Graphics object consisting of 10 graphics primitives
sage: PI.Vrepresentation()                                     # optional - pynormaliz
(A vertex at (-1, 0), A vertex at (0, 1), A ray in the direction (1, 0))

Nonpointed case:

sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]],     # optional - pynormaliz
....:              lines=[[-1, 1]], backend='normaliz')
sage: PI = P.integral_hull()                                   # optional - pynormaliz
sage: PI.Vrepresentation()                                     # optional - pynormaliz
(A vertex at (1, 0),
 A ray in the direction (1, 0),
 A line in the direction (1, -1))

Empty polyhedron:

sage: P = Polyhedron(backend='normaliz')                       # optional - pynormaliz
sage: PI = P.integral_hull()                                   # optional - pynormaliz
sage: PI.Vrepresentation()                                     # optional - pynormaliz
()
integral_points(threshold=10000)

Return the integral points in the polyhedron.

Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.

INPUT:

  • threshold – integer (default: 10000); use the naïve algorithm as long as the bounding box is smaller than this

OUTPUT:

The list of integral points in the polyhedron. If the polyhedron is not compact, a ValueError is raised.

EXAMPLES:

sage: Polyhedron(vertices=[(-1,-1), (1,0), (1,1), (0,1)],      # optional - pynormaliz
....:            backend='normaliz').integral_points()
((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))

sage: simplex = Polyhedron([(1,2,3), (2,3,7), (-2,-3,-11)],    # optional - pynormaliz
....:                      backend='normaliz')
sage: simplex.integral_points()                                # optional - pynormaliz
((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))

The polyhedron need not be full-dimensional:

sage: simplex = Polyhedron([(1,2,3,5), (2,3,7,5), (-2,-3,-11,5)],   # optional - pynormaliz
....:                      backend='normaliz')
sage: simplex.integral_points()                                # optional - pynormaliz
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))

sage: point = Polyhedron([(2,3,7)],                            # optional - pynormaliz
....:                    backend='normaliz')
sage: point.integral_points()                                  # optional - pynormaliz
((2, 3, 7),)

sage: empty = Polyhedron(backend='normaliz')                   # optional - pynormaliz
sage: empty.integral_points()                                  # optional - pynormaliz
()

Here is a simplex where the naive algorithm of running over all points in a rectangular bounding box no longer works fast enough:

sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
sage: simplex = Polyhedron(v, backend='normaliz'); simplex     # optional - pynormaliz
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
sage: len(simplex.integral_points())                           # optional - pynormaliz
49

A rather thin polytope for which the bounding box method would be a very bad idea (note this is a rational (non-lattice) polytope, so the other backends use the bounding box method):

sage: P = Polyhedron(vertices=((0, 0), (178933,37121))) + 1/1000*polytopes.hypercube(2)
sage: P = Polyhedron(vertices=P.vertices_list(),               # optional - pynormaliz
....:                backend='normaliz')
sage: len(P.integral_points())                                 # optional - pynormaliz
434

Finally, the 3-d reflexive polytope number 4078:

sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1),
....:      (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)]
sage: P = Polyhedron(v, backend='normaliz')                    # optional - pynormaliz
sage: pts1 = P.integral_points()                               # optional - pynormaliz
sage: all(P.contains(p) for p in pts1)                         # optional - pynormaliz
True
sage: pts2 = LatticePolytope(v).points()          # PALP
sage: for p in pts1: p.set_immutable()                         # optional - pynormaliz
sage: set(pts1) == set(pts2)                                   # optional - pynormaliz
True

sage: timeit('Polyhedron(v, backend='normaliz').integral_points()')   # not tested - random
625 loops, best of 3: 1.41 ms per loop
sage: timeit('LatticePolytope(v).points()')       # not tested - random
25 loops, best of 3: 17.2 ms per loop