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)[source]

Bases: Polyhedron_normaliz, Polyhedron_QQ

Polyhedra over \(\QQ\) with normaliz.

INPUT:

  • Vrep – list [vertices, rays, lines] or None

  • Hrep – 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()

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))],
...                rays=[(Integer(1),Integer(1))], lines=[],
...                backend='normaliz', base_ring=QQ)
>>> TestSuite(p).run()

p = Polyhedron(vertices=[(0,0), (1,0), (0,1)],
               rays=[(1,1)], lines=[],
               backend='normaliz', base_ring=QQ)
TestSuite(p).run()
ehrhart_series(variable='t')[source]

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

>>> from sage.all import *
>>> S = Polyhedron(vertices=[[Integer(0),Integer(1)], [Integer(1),Integer(0)]], backend='normaliz')
>>> ES = S.ehrhart_series()
>>> ES.numerator()
1
>>> ES.denominator().factor()
(t - 1)^2

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

S = Polyhedron(vertices=[[0,1], [1,0]], backend='normaliz')
ES = S.ehrhart_series()
ES.numerator()
ES.denominator().factor()
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')
ES = C.ehrhart_series()
ES.numerator()
ES.denominator().factor()

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)

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

rat_poly = Polyhedron(vertices=[[1/2,1/2], [-1/3,-1/3], [1/4,-1/2]],
                      backend='normaliz')
ES = rat_poly.ehrhart_series()
ES.numerator()
ES.denominator().factor()

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

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

C = Polyhedron(rays=[[1,2], [2,1]], backend='normaliz')
C.ehrhart_series()

See also

hilbert_series()

hilbert_series(grading, variable='t')[source]

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)

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

C = Polyhedron(backend='normaliz',
               rays=[[0,0,1], [0,1,1], [1,0,1], [1,1,1]])
HS = C.hilbert_series([1,1,1])
HS.numerator()
HS.denominator().factor()

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)

>>> from sage.all import *
>>> C.hilbert_series([Integer(0),Integer(0),Integer(1)])
(t + 1)/(-t^3 + 3*t^2 - 3*t + 1)

C.hilbert_series([0,0,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)

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

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

C = Polyhedron(backend='normaliz', rays=[[1,3], [2,1]])
HS = C.hilbert_series([1,1])
HS.numerator()
HS.denominator().factor()
HS = C.hilbert_series([1,2])
HS.numerator()
HS.denominator().factor()

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)

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

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]]
magic_square = (Polyhedron(eqns=eq, backend='normaliz')
                & Polyhedron(rays=identity_matrix(9).rows()))
grading = [1,1,1,0,0,0,0,0,0]
magic_square.hilbert_series(grading)

See also

ehrhart_series()

integral_points(threshold=10000)[source]

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

>>> from sage.all import *
>>> Polyhedron(vertices=[(-Integer(1),-Integer(1)), (Integer(1),Integer(0)), (Integer(1),Integer(1)), (Integer(0),Integer(1))],
...            backend='normaliz').integral_points()
((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))

>>> simplex = Polyhedron([(Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(3),Integer(7)), (-Integer(2),-Integer(3),-Integer(11))],
...                      backend='normaliz')
>>> simplex.integral_points()
((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))

Polyhedron(vertices=[(-1,-1), (1,0), (1,1), (0,1)],
           backend='normaliz').integral_points()
simplex = Polyhedron([(1,2,3), (2,3,7), (-2,-3,-11)],
                     backend='normaliz')
simplex.integral_points()

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

>>> from sage.all import *
>>> simplex = Polyhedron([(Integer(1),Integer(2),Integer(3),Integer(5)), (Integer(2),Integer(3),Integer(7),Integer(5)), (-Integer(2),-Integer(3),-Integer(11),Integer(5))],
...                      backend='normaliz')
>>> simplex.integral_points()
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))

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

>>> empty = Polyhedron(backend='normaliz')
>>> empty.integral_points()
()

simplex = Polyhedron([(1,2,3,5), (2,3,7,5), (-2,-3,-11,5)],
                     backend='normaliz')
simplex.integral_points()
point = Polyhedron([(2,3,7)],
                   backend='normaliz')
point.integral_points()
empty = Polyhedron(backend='normaliz')
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

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

v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
simplex = Polyhedron(v, backend='normaliz'); simplex
len(simplex.integral_points())

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

>>> from sage.all import *
>>> P = Polyhedron(vertices=((Integer(0), Integer(0)), (Integer(178933),Integer(37121)))) + Integer(1)/Integer(1000)*polytopes.hypercube(Integer(2))
>>> P = Polyhedron(vertices=P.vertices_list(),
...                backend='normaliz')
>>> len(P.integral_points())
434

P = Polyhedron(vertices=((0, 0), (178933,37121))) + 1/1000*polytopes.hypercube(2)
P = Polyhedron(vertices=P.vertices_list(),
               backend='normaliz')
len(P.integral_points())

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

>>> from sage.all import *
>>> v = [(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),-Integer(1)), (Integer(0),-Integer(2),Integer(1)),
...      (-Integer(1),Integer(2),-Integer(1)), (-Integer(1),Integer(2),-Integer(2)), (-Integer(1),Integer(1),-Integer(2)), (-Integer(1),-Integer(1),Integer(2)), (-Integer(1),-Integer(3),Integer(2))]
>>> P = Polyhedron(v, backend='normaliz')
>>> pts1 = P.integral_points()
>>> all(P.contains(p) for p in pts1)
True
>>> pts2 = LatticePolytope(v).points()                                    # needs palp
>>> for p in pts1: p.set_immutable()
>>> set(pts1) == set(pts2)                                                # needs palp
True

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

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)]
P = Polyhedron(v, backend='normaliz')
pts1 = P.integral_points()
all(P.contains(p) for p in pts1)
pts2 = LatticePolytope(v).points()                                    # needs palp
for p in pts1: p.set_immutable()
set(pts1) == set(pts2)                                                # needs palp
timeit('Polyhedron(v, backend='normaliz').integral_points()')  # not tested - random
timeit('LatticePolytope(v).points()')                          # not tested - random
integral_points_generators()[source]

Return the integral points generators of the polyhedron.

Every integral point in the polyhedron can be written as a (unique) nonnegative 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),))

>>> from sage.all import *
>>> P = Polyhedron(backend='normaliz', lines=[[Integer(2),Integer(2)]])
>>> P.integral_points_generators()
(((0, 0),), (), ((1, 1),))

P = Polyhedron(backend='normaliz', lines=[[2,2]])
P.integral_points_generators()

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

>>> from sage.all import *
>>> C = Polyhedron(backend='normaliz', rays=[[Integer(1),Integer(2)], [Integer(2),Integer(1)]])
>>> C.integral_points_generators()
(((0, 0),), ((1, 1), (1, 2), (2, 1)), ())

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

Empty polyhedron:

sage: P = Polyhedron(backend='normaliz')
sage: P.integral_points_generators()
((), (), ())

>>> from sage.all import *
>>> P = Polyhedron(backend='normaliz')
>>> P.integral_points_generators()
((), (), ())

P = Polyhedron(backend='normaliz')
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)[source]

Bases: Polyhedron_QQ_normaliz, Polyhedron_ZZ

Polyhedra over \(\ZZ\) with normaliz.

INPUT:

  • Vrep – list [vertices, rays, lines] or None

  • Hrep – 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()

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))],
...                rays=[(Integer(1),Integer(1))], lines=[],
...                backend='normaliz', base_ring=ZZ)
>>> TestSuite(p).run()

p = Polyhedron(vertices=[(0,0), (1,0), (0,1)],
               rays=[(1,1)], lines=[],
               backend='normaliz', base_ring=ZZ)
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)[source]

Bases: Polyhedron_base_number_field

Polyhedra with normaliz.

INPUT:

  • parent – Polyhedra the parent

  • Vrep – list [vertices, rays, lines] or None; the V-representation of the polyhedron; if None, the polyhedron is determined by the H-representation

  • Hrep – 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()

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))],
...                rays=[(Integer(1),Integer(1))], lines=[],
...                backend='normaliz')
>>> TestSuite(p).run()

p = Polyhedron(vertices=[(0,0), (1,0), (0,1)],
               rays=[(1,1)], lines=[],
               backend='normaliz')
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

>>> from sage.all import *
>>> Polyhedron(eqns=[[Integer(0), Integer(0), Integer(0)]], backend='normaliz')
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 lines
>>> Polyhedron(ieqs=[[Integer(0), Integer(0), Integer(0)]], backend='normaliz')
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 lines

Polyhedron(eqns=[[0, 0, 0]], backend='normaliz')
Polyhedron(ieqs=[[0, 0, 0]], backend='normaliz')

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

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(1), Integer(1))], rays=[(Integer(0), Integer(1))],
...                backend='normaliz')
>>> P.n_inequalities()
1
>>> P.equations()
(An equation (1, 0) x - 1 == 0,)

P = Polyhedron(vertices=[(1, 1)], rays=[(0, 1)],
               backend='normaliz')
P.n_inequalities()
P.equations()

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

>>> from sage.all import *
>>> P = Polyhedron(ieqs=[[-Integer(2), Integer(1), Integer(1)], [-Integer(3), -Integer(1), -Integer(1)], [-Integer(4), Integer(1), -Integer(2)]],
...                backend='normaliz')
>>> P
The empty polyhedron in QQ^2
>>> P.Vrepresentation()
()
>>> P.Hrepresentation()
(An equation -1 == 0,)

P = Polyhedron(ieqs=[[-2, 1, 1], [-3, -1, -1], [-4, 1, -2]],
               backend='normaliz')
P
P.Vrepresentation()
P.Hrepresentation()
integral_hull()[source]

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

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

P = Polyhedron(ieqs=[[1, 0, 2], [3, 0, -2], [3, 2, -2]],
               backend='normaliz')
PI = P.integral_hull()
P.plot(color='yellow') + PI.plot(color='green')                       # needs sage.plot
PI.Vrepresentation()

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

>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(1)/Integer(3)]], rays=[[Integer(1), Integer(1)]],
...                lines=[[-Integer(1), Integer(1)]], backend='normaliz')
>>> PI = P.integral_hull()
>>> PI.Vrepresentation()
(A vertex at (1, 0),
 A ray in the direction (1, 0),
 A line in the direction (1, -1))

P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]],
               lines=[[-1, 1]], backend='normaliz')
PI = P.integral_hull()
PI.Vrepresentation()

Empty polyhedron:

sage: P = Polyhedron(backend='normaliz')
sage: PI = P.integral_hull()
sage: PI.Vrepresentation()
()

>>> from sage.all import *
>>> P = Polyhedron(backend='normaliz')
>>> PI = P.integral_hull()
>>> PI.Vrepresentation()
()

P = Polyhedron(backend='normaliz')
PI = P.integral_hull()
PI.Vrepresentation()