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

  • Jean-Philippe Labbé (2019-04): Expose normaliz features and added functionalities

class sage.geometry.polyhedron.backend_normaliz.Polyhedron_QQ_normaliz(parent, Vrep, Hrep, normaliz_cone=None, normaliz_data=None, internal_base_ring=None, **kwds)#

Bases: Polyhedron_normaliz, 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)],
....:                rays=[(1,1)], lines=[],
....:                backend='normaliz', base_ring=QQ)
sage: TestSuite(p).run()
ehrhart_series(variable='t')#

Return the Ehrhart series of a compact rational polyhedron.

The Ehrhart series is the generating function where the coefficient of \(t^k\) is number of integer lattice points inside the \(k\)-th dilation of the polytope.

INPUT:

  • variable – string (default: 't')

OUTPUT:

A rational function.

EXAMPLES:

sage: S = Polyhedron(vertices=[[0,1], [1,0]], backend='normaliz')
sage: ES = S.ehrhart_series()
sage: ES.numerator()
1
sage: ES.denominator().factor()
(t - 1)^2

sage: C = Polyhedron(vertices=[[0,0,0], [0,0,1], [0,1,0], [0,1,1],
....:                          [1,0,0], [1,0,1], [1,1,0], [1,1,1]],
....:                backend='normaliz')
sage: ES = C.ehrhart_series()
sage: ES.numerator()
t^2 + 4*t + 1
sage: ES.denominator().factor()
(t - 1)^4

The following example is from the Normaliz manual contained in the file rational.in:

sage: rat_poly = Polyhedron(vertices=[[1/2,1/2], [-1/3,-1/3], [1/4,-1/2]],
....:                       backend='normaliz')
sage: ES = rat_poly.ehrhart_series()
sage: ES.numerator()
2*t^6 + 3*t^5 + 4*t^4 + 3*t^3 + t^2 + t + 1
sage: ES.denominator().factor()
(-1) * (t + 1)^2 * (t - 1)^3 * (t^2 + 1) * (t^2 + t + 1)

The polyhedron should be compact:

sage: C = Polyhedron(rays=[[1,2], [2,1]], backend='normaliz')
sage: C.ehrhart_series()
Traceback (most recent call last):
...
NotImplementedError: Ehrhart series can only be computed for compact polyhedron

See also

hilbert_series()

hilbert_series(grading, variable='t')#

Return the Hilbert series of the polyhedron with respect to grading.

INPUT:

  • grading – vector. The grading to use to form the Hilbert series

  • variable – string (default: 't')

OUTPUT:

A rational function.

EXAMPLES:

sage: C = Polyhedron(backend='normaliz',
....:                rays=[[0,0,1], [0,1,1], [1,0,1], [1,1,1]])
sage: HS = C.hilbert_series([1,1,1])
sage: HS.numerator()
t^2 + 1
sage: HS.denominator().factor()
(-1) * (t + 1) * (t - 1)^3 * (t^2 + t + 1)

By changing the grading, you can get the Ehrhart series of the square lifted at height 1:

sage: C.hilbert_series([0,0,1])
(t + 1)/(-t^3 + 3*t^2 - 3*t + 1)

Here is an example 2cone.in from the Normaliz manual:

sage: C = Polyhedron(backend='normaliz', rays=[[1,3], [2,1]])
sage: HS = C.hilbert_series([1,1])
sage: HS.numerator()
t^5 + t^4 + t^3 + t^2 + 1
sage: HS.denominator().factor()
(t + 1) * (t - 1)^2 * (t^2 + 1) * (t^2 + t + 1)

sage: HS = C.hilbert_series([1,2])
sage: HS.numerator()
t^8 + t^6 + t^5 + t^3 + 1
sage: HS.denominator().factor()
(t + 1) * (t - 1)^2 * (t^2 + 1) * (t^6 + t^5 + t^4 + t^3 + t^2 + t + 1)

Here is the magic square example form the Normaliz manual:

sage: eq = [[0,1,1,1,-1,-1,-1, 0, 0, 0],
....:       [0,1,1,1, 0, 0, 0,-1,-1,-1],
....:       [0,0,1,1,-1, 0, 0,-1, 0, 0],
....:       [0,1,0,1, 0,-1, 0, 0,-1, 0],
....:       [0,1,1,0, 0, 0,-1, 0, 0,-1],
....:       [0,0,1,1, 0,-1, 0, 0, 0,-1],
....:       [0,1,1,0, 0,-1, 0,-1, 0, 0]]
sage: magic_square = (Polyhedron(eqns=eq, backend='normaliz')
....:                 & Polyhedron(rays=identity_matrix(9).rows()))
sage: grading = [1,1,1,0,0,0,0,0,0]
sage: magic_square.hilbert_series(grading)
(t^6 + 2*t^3 + 1)/(-t^9 + 3*t^6 - 3*t^3 + 1)

See also

ehrhart_series()

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)],
....:            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)],
....:                      backend='normaliz')
sage: simplex.integral_points()
((-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)],
....:                      backend='normaliz')
sage: simplex.integral_points()
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))

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

sage: empty = Polyhedron(backend='normaliz')
sage: empty.integral_points()
()

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
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
sage: len(simplex.integral_points())
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(),
....:                backend='normaliz')
sage: len(P.integral_points())
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')
sage: pts1 = P.integral_points()
sage: all(P.contains(p) for p in pts1)
True
sage: pts2 = LatticePolytope(v).points()                                    # needs palp
sage: for p in pts1: p.set_immutable()
sage: set(pts1) == set(pts2)                                                # needs palp
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
integral_points_generators()#

Return the integral points generators of the polyhedron.

Every integral point in the polyhedron can be written as a (unique) non-negative linear combination of integral points contained in the three defining parts of the polyhedron: the integral points (the compact part), the recession cone, and the lineality space.

OUTPUT:

A tuple consisting of the integral points, the Hilbert basis of the recession cone, and an integral basis for the lineality space.

EXAMPLES:

Normaliz gives a nonnegative integer basis of the lineality space:

sage: P = Polyhedron(backend='normaliz', lines=[[2,2]])
sage: P.integral_points_generators()
(((0, 0),), (), ((1, 1),))

A recession cone generated by two rays:

sage: C = Polyhedron(backend='normaliz', rays=[[1,2], [2,1]])
sage: C.integral_points_generators()
(((0, 0),), ((1, 1), (1, 2), (2, 1)), ())

Empty polyhedron:

sage: P = Polyhedron(backend='normaliz')
sage: P.integral_points_generators()
((), (), ())
class sage.geometry.polyhedron.backend_normaliz.Polyhedron_ZZ_normaliz(parent, Vrep, Hrep, normaliz_cone=None, normaliz_data=None, internal_base_ring=None, **kwds)#

Bases: Polyhedron_QQ_normaliz, 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)],
....:                rays=[(1,1)], lines=[],
....:                backend='normaliz', base_ring=ZZ)
sage: TestSuite(p).run()
class sage.geometry.polyhedron.backend_normaliz.Polyhedron_normaliz(parent, Vrep, Hrep, normaliz_cone=None, normaliz_data=None, internal_base_ring=None, **kwds)#

Bases: Polyhedron_base_number_field

Polyhedra with normaliz

INPUT:

  • parent – Polyhedra 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)], lines=[],
....:                backend='normaliz')
sage: TestSuite(p).run()

Two ways to get the full space:

sage: Polyhedron(eqns=[[0, 0, 0]], backend='normaliz')
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')
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)],
....:                backend='normaliz')
sage: P.n_inequalities()
1
sage: P.equations()
(An equation (1, 0) x - 1 == 0,)

The empty polyhedron:

sage: P = Polyhedron(ieqs=[[-2, 1, 1], [-3, -1, -1], [-4, 1, -2]],
....:                backend='normaliz')
sage: P
The empty polyhedron in QQ^2
sage: P.Vrepresentation()
()
sage: P.Hrepresentation()
(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]],
....:                backend='normaliz')
sage: PI = P.integral_hull()
sage: P.plot(color='yellow') + PI.plot(color='green')                       # needs sage.plot
Graphics object consisting of 10 graphics primitives
sage: PI.Vrepresentation()
(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]],
....:                lines=[[-1, 1]], backend='normaliz')
sage: PI = P.integral_hull()
sage: PI.Vrepresentation()
(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')
sage: PI = P.integral_hull()
sage: PI.Vrepresentation()
()