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_QQPolyhedra over \(\QQ\) with normaliz.
INPUT:
Vrep– a list[vertices, rays, lines]orNoneHrep– a list[ieqs, eqns]orNone
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_ZZPolyhedra over \(\ZZ\) with normaliz.
INPUT:
Vrep– a list[vertices, rays, lines]orNoneHrep– a list[ieqs, eqns]orNone
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_basePolyhedra with normaliz
INPUT:
parent–Polyhedrathe parentVrep– a list[vertices, rays, lines]orNone; the V-representation of the polyhedron; ifNone, the polyhedron is determined by the H-representationHrep– a list[ieqs, eqns]orNone; the H-representation of the polyhedron; ifNone, the polyhedron is determined by the V-representationnormaliz_cone– a PyNormaliz wrapper of a normaliz cone
Only one of
Vrep,Hrep, ornormaliz_conecan be different fromNone.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') # not tested # optional - pynormaliz sage: set(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: set(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
ValueErroris 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