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, normaliz_field=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

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')  # optional - pynormaliz
sage: ES = S.ehrhart_series()                                     # optional - pynormaliz
sage: ES.numerator()                                              # optional - pynormaliz
1
sage: ES.denominator().factor()                                   # optional - pynormaliz
(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') # optional - pynormaliz
sage: ES = C.ehrhart_series()            # optional - pynormaliz
sage: ES.numerator()                     # optional - pynormaliz
t^2 + 4*t + 1
sage: ES.denominator().factor()          # optional - pynormaliz
(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') # optional - pynormaliz
sage: ES = rat_poly.ehrhart_series()                                       # optional - pynormaliz
sage: ES.numerator()                                                       # optional - pynormaliz
2*t^6 + 3*t^5 + 4*t^4 + 3*t^3 + t^2 + t + 1
sage: ES.denominator().factor()                                            # optional - pynormaliz
(-1) * (t + 1)^2 * (t - 1)^3 * (t^2 + 1) * (t^2 + t + 1)

The polyhedron should be compact:

sage: C = Polyhedron(backend='normaliz',rays=[[1,2],[2,1]])  # optional - pynormaliz
sage: C.ehrhart_series()                                     # optional - pynormaliz
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]]) # optional - pynormaliz
sage: HS = C.hilbert_series([1,1,1]) # optional - pynormaliz
sage: HS.numerator() # optional - pynormaliz
t^2 + 1
sage: HS.denominator().factor() # optional - pynormaliz
(-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]) # optional - pynormaliz
(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]]) # optional - pynormaliz
sage: HS = C.hilbert_series([1,1]) # optional - pynormaliz
sage: HS.numerator() # optional - pynormaliz
t^5 + t^4 + t^3 + t^2 + 1
sage: HS.denominator().factor() # optional - pynormaliz
(t + 1) * (t - 1)^2 * (t^2 + 1) * (t^2 + t + 1)

sage: HS = C.hilbert_series([1,2]) # optional - pynormaliz
sage: HS.numerator() # optional - pynormaliz
t^8 + t^6 + t^5 + t^3 + 1
sage: HS.denominator().factor() # optional - pynormaliz
(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()) # optional - pynormaliz
sage: grading = [1,1,1,0,0,0,0,0,0]
sage: magic_square.hilbert_series(grading) # optional - pynormaliz
(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)],      # 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

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]])  # optional - pynormaliz
sage: P.integral_points_generators()                    # optional - pynormaliz
(((0, 0),), (), ((1, 1),))

A recession cone generated by two rays:

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

Empty polyhedron:

sage: P = Polyhedron(backend='normaliz')  # optional - pynormaliz
sage: P.integral_points_generators()      # optional - pynormaliz
((), (), ())

class sage.geometry.polyhedron.backend_normaliz.Polyhedron_ZZ_normaliz(parent, Vrep, Hrep, normaliz_cone=None, normaliz_data=None, normaliz_field=None, **kwds)

Bases: sage.geometry.polyhedron.backend_normaliz.Polyhedron_QQ_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, normaliz_data=None, normaliz_field=None, **kwds)

Bases: sage.geometry.polyhedron.base.Polyhedron_base

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)],   # 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,)

ehrhart_quasipolynomial(variable='t')

Return the Ehrhart quasi-polynomial of a compact rational polyhedron using Normaliz.

INPUT:

• variable – string (default: 't')

OUTPUT:

If it is a polynomial, returns the polynomial. Otherwise, returns a tuple of rational polynomials whose length is the quasi-period of the quasi-polynomial and each rational polynomial describes a residue class.

EXAMPLES:

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') # optional - pynormaliz
sage: C.ehrhart_quasipolynomial()  # optional - pynormaliz
t^3 + 3*t^2 + 3*t + 1

sage: P = Polyhedron(vertices=[[0,0],[3/2,0],[0,3/2],[1,1]],backend='normaliz')  # optional - pynormaliz
sage: P.ehrhart_quasipolynomial()  # optional - pynormaliz
(3/2*t^2 + 2*t + 1, 3/2*t^2 + 2*t + 1/2)
sage: P.ehrhart_quasipolynomial('x')  # optional - pynormaliz
(3/2*x^2 + 2*x + 1, 3/2*x^2 + 2*x + 1/2)

The quasi-polynomial evaluated at i counts the integral points in the i-th dilate:

sage: Q = Polyhedron(vertices = [[-1/3],[2/3]],backend='normaliz')  # optional - pynormaliz
sage: p0,p1,p2 = Q.ehrhart_quasipolynomial()  # optional - pynormaliz
sage: r0 = [p0(i) for i in range(15)]         # optional - pynormaliz
sage: r1 = [p1(i) for i in range(15)]         # optional - pynormaliz
sage: r2 = [p2(i) for i in range(15)]         # optional - pynormaliz
sage: result = [None]*15                      # optional - pynormaliz
sage: result[::3] = r0[::3]                   # optional - pynormaliz
sage: result[1::3] = r1[1::3]                 # optional - pynormaliz
sage: result[2::3] = r2[2::3]                 # optional - pynormaliz
sage: result == [(i*Q).integral_points_count() for i in range(15)]  # optional - pynormaliz
True

The polyhedron should be compact:

sage: C = Polyhedron(backend='normaliz',rays=[[1,2],[2,1]])  # optional - pynormaliz
sage: C.ehrhart_quasipolynomial()                            # optional - pynormaliz
Traceback (most recent call last):
...
NotImplementedError: Ehrhart quasi-polynomial can only be computed for compact polyhedron

See also

hilbert_series(), ehrhart_series()

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
()