Cone Class

This class handles all computations relating to rational polyhedral cones, such cone duality and extremal ray computations. It is mainly used for the study of Kähler and Mori cones.

warning

This class is primarily tailored to pointed (i.e. strongly convex) cones. There are a few computations, such as finding extremal rays, that may produce some unexpected results when working with non-pointed cones. Additionally, cones that are not pointed, and whose dual is also not pointed, are not supported since they are uncommon and difficult to deal with.

Constructor

`cytools.cone.Cone`

Description: Constructs a Cone object. This is handled by the hidden __init__ function.

Arguments:

rays (array_like, optional): A list of rays that generates the cone. If it is not specified then the hyperplane normals must be specified.
hyperplanes (array_like, optional): A list of inward-pointing hyperplane normals that define the cone. If it is not specified then the generating rays must be specified.
check (bool, optional, default=True): Whether to check the input. Recommended if constructing a cone directly.

note

Exactly one of rays or hyperplanes must be specified. Otherwise an exception is raised.

Example

We construct a cone in two different ways. First from a list of rays then from a list of hyperplane normals. We verify that the two inputs result in the same cone.

from cytools import Cone
c1 = Cone([[0,1],[1,1]]) # Create a cone using rays. It can also be done with Cone(rays=[[0,1],[1,1]])
c2 = Cone(hyperplanes=[[1,0],[-1,1]]) # Create a cone using hyperplane normals.
c1 == c2 # We verify that the two cones are the same.
# True

Functions

`ambient_dimension`

Description: Returns the dimension of the ambient lattice.

Arguments: None.

Returns: (int) The dimension of the ambient lattice.

Aliases: ambient_dim.

Example

We construct a cone and find the dimension of the ambient lattice.

c = Cone([[0,1,0],[1,1,0]])
c.ambient_dimension()
# 3

`clear_cache`

Description: Clears the cached results of any previous computation.

Arguments: None.

Returns: Nothing.

Example

We construct a cone, compute its extremal rays, clear the cache and then compute them again.

c = Cone([[1,0],[1,1],[0,1]])
c.extremal_rays()
# array([[0, 1],
#        [1, 0]])
c.clear_cache() # Clears the cached result
c.extremal_rays() # The extremal rays recomputed
# array([[0, 1],
#        [1, 0]])

`contains`

Description: Checks if a point is in the (strict) interior.

Arguments:

other: The object to check containment of. Can be a 1D array, which is treated as a point. Can be a 2D array, which is treated as a list of points. Can be a Cone.
eps: Check H@pt >= eps.

Returns: Whether pt is in the (strict) interior.

`dimension`

Description: Returns the dimension of the cone.

Arguments: None.

Returns: (int) The dimension of the cone.

Aliases: dim.

Example

We construct a cone and find its dimension.

c = Cone([[0,1,0],[1,1,0]])
c.dimension()
# 2

`dual_cone`

Description: Returns the dual cone.

Arguments: None.

Returns: (Cone) The dual cone.

Aliases: dual.

Example

We construct a cone and find its dual cone.

c = Cone([[0,1],[1,1]])
c.dual_cone()
# A rational polyhedral cone in RR^2 defined by 2 hyperplanes normals
c.dual_cone().rays()
# array([[ 1,  0],
#        [-1,  1]])

`extremal_hyperplanes`

Description: Returns the extremal hyperplanes of the cone.

Arguments:

tol: Specifies the tolerance for deciding whether a hyperplane is extremal or not. Only used if method=="nnls".
minimal: Whether to return a minimal generating set of hyperplane. For duals of pointed cones, there is a unique minimal generating set -- the extremal hyperplanes. For non-pointed cones, one can have a collection of extremal hyperplanes defining the cone that is not minimal with respect to hyperplane count.
method: If calling is_extremal, this sets the method used for extremality checking. Can be "lp" or "nnls". Recommendation is "lp".
verbose: When set to True it show the progress while finding the extremal hyperplanes.

Returns: The list of extremal hyperplanes of the cone.

`extremal_rays`

Description: Returns the extremal rays of the cone.

note

By default, this function will use as many CPU threads as there are available. To fix the number of threads, you can set the n_threads variable in the config submodule.

Arguments:

tol: Specifies the tolerance for deciding whether a ray is extremal or not. Only used if method=="nnls".
minimal: Whether to return a minimal generating set of rays. For pointed cones, there is a unique minimal generating set -- the extremal rays. For non-pointed cones, one can have a collection of extremal rays generating the cone that is not minimal with respect to ray count.
method: If calling is_extremal, this sets the method used for extremality checking. Can be "lp" or "nnls". Recommendation is "lp".
verbose: When set to True it show the progress while finding the extremal rays.

Returns: The list of extremal rays of the cone.

Example

We construct a cone and find its extremal_rays.

c = Cone([[0,1],[1,1],[1,0]])
c.extremal_rays()
# array([[0, 1],
#        [1, 0]])

`facets`

Description: Get the facets of the cone.

This is easy if: -) the cone is simplicial OR -) the cone is solid and the extremal hyperplanes can be computed. Otherwise, the computation uses both rays and hyperplanes... this is semi-expensive to compute...

Arguments:

verbosity: The verbosity level.

Returns: The facets of the cone.

`find_grading_vector`

r

`find_interior_point`

r

`find_lattice_points`

Description: Finds lattice points in the cone. The points are found in the region bounded by the cone, and by a cutoff surface given by the grading vector. Note that this requires the cone to be pointed. The minimum number of points to find can be specified, or if working with a preferred grading vector it is possible to specify the maximum degree.

Arguments:

min_point (int, optional): Specifies the minimum number of points to find. The degree will be increased until this minimum number is achieved.
max_deg (int, optional): The maximum degree of the points to find. This is useful when working with a preferred grading.
grading_vector (array_like, optional): The grading vector that will be used. If it is not specified then it is computed.
max_coord (int, optional, default=1000): The maximum magnitude of the coordinates of the points.
deg_window (int, optional): If using min_points, search for lattice points with degrees in range [n(deg_window+1), n(deg_window+1)+deg_window] for 0<=n
filter_function (function, optional): A function to use as a filter of the points that will be kept. It should return a boolean indicating whether to keep the point. Note that min_points does not take the filtering into account.
process_function (function, optional): A function to process the points as they are found. This is useful to avoid first constructing a large list of points and then processing it.
verbose (boolean, optional): Whether to print extra diagnostic information (True) or not (False).

Returns: (numpy.ndarray) The list of points.

Example

We construct a cone and find at least 20 lattice points in it.

c = Cone([[3,2],[5,3]])
pts = c.find_lattice_points(min_points=20)
print(len(pts)) # We see that it found 21 points
# 21

Let's also give an example where we use a function to apply some filtering. This can be something very complicated, but here we just pick the points where all coordinates are odd.

def filter_function(pt):
    return all(c%2 for c in pt)

c = Cone([[3,2],[5,3]])
pts = c.find_lattice_points(min_points=20, filter_function=filter_function)
print(len(pts)) # Now we get only 6 points instead of 21
# 6

Finally, let's give an example where we process the data as it comes instead of first constructing a list. In this simple example we just print each point with odd coordinates, but in general it can be a complex algorithm.

def process_function(pt):
    if all(c%2 for c in pt):
        print(f"Processing point {pt}")

c = Cone([[3,2],[5,3]])
c.find_lattice_points(min_points=20, process_function=process_function)
# Processing point (5, 3)
# Processing point (11, 7)
# Processing point (15, 9)
# Processing point (17, 11)
# Processing point (21, 13)
# Processing point (25, 15)

`hilbert_basis`

Description: Returns the Hilbert basis of the cone. Normaliz is used for the computation.

Arguments: None.

Returns: (numpy.ndarray) The list of vectors forming the Hilbert basis.

Example

We compute the Hilbert basis of a two-dimensional cone.

c = Cone([[1,3],[2,1]])
c.hilbert_basis()
# array([[1, 1],
#        [1, 2],
#        [1, 3],
#        [2, 1]])

`hyperplanes`

Description: Returns the inward-pointing normals to the hyperplanes that define the cone.

Arguments:

use_extremal_rays :Whether to use extremal rays in this computation, or just any rays.
verbosity: The verbosity level.

Returns: (numpy.ndarray) The list of inward-pointing normals to the hyperplanes that define the cone.

Example

We construct two cones and find their hyperplane normals.

c1 = Cone([[0,1],[1,1]])
c2 = Cone(hyperplanes=[[0,1],[1,1]])
c1.hyperplanes()
# array([[ 1,  0],
#        [-1,  1]])
c2.hyperplanes()
# array([[0, 1],
#        [1, 1]])

`intersection`

Description: Computes the intersection with another cone, or with a list of cones.

Arguments:

other (Cone or array_like): The other cone that is being intersected, or a list of cones to intersect with.

Returns: (Cone) The cone that results from the intersection.

Example

We construct two cones and find their intersection.

c1 = Cone([[1,0],[1,2]])
c2 = Cone([[0,1],[2,1]])
c3 = c1.intersection(c2)
c3.rays()
# array([[2, 1],
#        [1, 2]])

`is_degenerate`

Description: Checks if a cone {x : H@x>=0} is degenerate. I.e., does any x in this cone saturate >=d+1 hyperplanes simultaneously, for d the ambient dim? If so, the cone is degenerate.

This is representation-sensitive. Just because the cone is degenerate for a certain representation matrix, H, doesn't mean that it's degenerate for all representation matrices. Probably best to use H as the extremal hyperplanes.

Application: It is more difficult to compute the (extremal or not) rays of a degenerate cone.

Arguments:

use_extremal_hyperplanes: Whether the check the extremal hyperplanes for degeneracy. If False, the naive self.hyperplanes() will be used.
M: The (absolute value of the) bounds on variables considered.
certificate: Whether to return a certificate x as well as the hyperplanes the solver claims it saturates
verbosity: The verbosity level.

Returns: The maximum number of hyperplanes that a single x can saturate simultaneously.

If certificate==True, also return (x,z)

`is_pointed`

Description: Returns True if the cone is pointed (i.e. strongly convex). A cone is pointed if no x exists such that both x and -x are in the cone.

If one has hyperplanes, this check is as simple as not full_rank(H) since, if H is not full rank, then some x has H@x==0. I.e., H@(+x)>=0 and H@(-x)>=0.

If one has rays, this check can be done either via 1) finding some psi such that psi.r > 0 for all rays r 2) checking if some lmbda!=0 exist such that R.T@lmbda = 0

The backends are, in order of preference, 1) (backend='dual') check if dual is solid 2) (backend='null') hyperplane rank 3) (backend='lp') rays@lmbda=0 via LP 4) (backend='nnls') rays@lmbda=0 via nnls

Arguments:

backend: Specifies which backend to use. Available options are "dual", "null", "lp", and "nnls".
tol: The tolerance for determining when a linear subspace is found. This is only used for the NNLS backend.

Returns: The truth value of the cone being pointed.

Aliases: is_strongly_convex.

Example

We construct two cones and check if they are pointed.

c1 = Cone([[1,0],[0,1]])
c2 = Cone([[1,0],[0,1],[-1,0]])
c1.is_pointed()
# True
c2.is_pointed()
# False

`is_simplicial`

Description: Returns True if the cone is simplicial.

N.B.: if c is solid, then c is simplicial <=> c.dual() is simplicial.

A sometimes-simpler check if c is solid, then, is to check if #(extremal hyperplanes) = dim.

Arguments: None.

Returns: (bool) The truth value of the cone being simplicial.

Example

We construct two cones and check if they are simplicial.

c1 = Cone([[1,0,0],[0,1,0],[0,0,1]])
c2 = Cone([[1,0,0],[0,1,0],[0,0,1],[1,1,-1]])
c1.is_simplicial()
# True
c2.is_simplicial()
# False

`is_smooth`

Description: Returns True if the cone is smooth, i.e. its extremal rays either form a basis of the ambient lattice, or they can be extended into one.

Arguments: None.

Returns: (bool) The truth value of the cone being smooth.

Example

We construct two cones and check if they are smooth.

c1 = Cone([[1,0,0],[0,1,0],[0,0,1]])
c2 = Cone([[2,0,1],[0,1,0],[1,0,2]])
c1.is_smooth()
# True
c2.is_smooth()
# False

`is_solid`

Description: Returns True if the cone is solid, i.e. if it is full-dimensional.

note

If the generating rays are known then this can simply be checked by computing the dimension of the linear space that they span. However, when only the hyperplane inequalities are known this can be a difficult problem. When using PPL as the backend, the convex hull is explicitly constructed and checked. The other backends try to find a point in the strict interior of the cone, which fails if the cone is not solid. The latter approach is much faster, but there could be extremely narrow cones where the optimization fails and this function returns a false negative.

Arguments:

backend (str, optional): Specifies which backend to use. Available options are "ppl", and any backends available for the find_interior_point function. If not specified, it uses the default backend of the find_interior_point function.

Returns: (bool) The truth value of the cone being solid.

Aliases: is_full_dimensional.

Example

We construct two cones and check if they are solid.

c1 = Cone([[1,0],[0,1]])
c2 = Cone([[1,0,0],[0,1,0]])
c1.is_solid()
# True
c2.is_solid()
# False

`lineality_space`

Description: Returns the lineality space as a formal cone object.

This Cone object a bit odd since, by definition, the lineality space is the largest linear subspace in the cone, so it allows coefficients of any sign. Regardless, it's convenient to package this as a Cone

Arguments: None.

Returns: (Cone) A cone defining the lineality space.

`pointed_space`

Description: A cone can be decomposed into its lineality space and its pointed component.

The pointed component is obtained by intersection of the cone with the orthogonal complement of the lineality space. I.e., want to impose H@x=0 for any x in the lineality space.

Arguments: None.

Returns: (Cone) The pointed part of the cone.

`rays`

Description: Returns the (not necessarily extremal) rays that generate the cone.

Arguments:

use_extremal_hyperplanes: Whether to use extremal hyperplanes in this computation, or just any hyperplanes.
verbosity: The verbosity level.

Returns: (numpy.ndarray) The list of rays that generate the cone.

Example

We construct two cones and find their generating rays.

c1 = Cone([[0,1],[1,1]])
c2 = Cone(hyperplanes=[[0,1],[1,1]])
c1.rays()
# array([[0, 1],
#        [1, 1]])
c2.rays()
# array([[ 1,  0],
#        [-1,  1]])

`tip_of_stretched_cone`

r

Hidden Functions

`eq`

Description: Implements comparison of cones with ==.

note

The comparison of cones that are not pointed, and whose duals are also not pointed, is not supported.

Arguments:

other (Cone): The other cone that is being compared.

Returns: (bool) The truth value of the cones being equal.

Example

We construct two cones and compare them.

c1 = Cone([[0,1],[1,1]])
c2 = Cone(hyperplanes=[[1,0],[-1,1]])
c1 == c2
# True

`hash`

Description: Implements the ability to obtain hash values from cones.

note

Cones that are not pointed, and whose duals are also not pointed, are not supported.

Arguments: None.

Returns: (int) The hash value of the cone.

Example

We compute the hash value of a cone. Also, we construct a set and a dictionary with a cone, which make use of the hash function.

c = Cone([[0,1],[1,1]])
h = hash(c) # Obtain hash value
d = {c: 1} # Create dictionary with cone keys
s = {c} # Create a set of cones

`init`

Description: Initializes a Cone object.

Arguments:

rays: A list of rays that generates the cone. If it is not specified then the hyperplane normals must be specified.
hyperplanes: A list of inward-pointing hyperplane normals that define the cone. If it is not specified then the generating rays must be specified.
check: Whether to check the input. Recommended if constructing a cone directly.
copy: Whether to ensure we copy the input rays/hyperplanes. ecommended.
ambient_dim: The ambient dimension of the cone, if not inferrable.

note

Exactly one of rays or hyperplanes must be specified. Otherwise, an exception is raised.

Returns: Nothing.

Example

This is the function that is called when creating a new Cone object. We construct a cone in two different ways. First from a list of rays then from a list of hyperplane normals. We verify that the two inputs result in the same cone.

from cytools import Cone
c1 = Cone([[0,1],[1,1]]) # Create a cone using rays. It can also be done with Cone(rays=[[0,1],[1,1]])
c2 = Cone(hyperplanes=[[1,0],[-1,1]]) # Create a cone using hyperplane normals.
c1 == c2 # We verify that the two cones are the same.
# True

`ne`

Description: Implements comparison of cones with !=.

note

The comparison of cones that are not pointed, and whose duals are also not pointed, is not supported.

Arguments:

other (Cone): The other cone that is being compared.

Returns: (bool) The truth value of the cones being different.

Example

We construct two cones and compare them.

c1 = Cone([[0,1],[1,1]])
c2 = Cone(hyperplanes=[[1,0],[-1,1]])
c1 != c2
# False

`repr`

Description: Returns a string describing the polytope.

Arguments: None.

Returns: (str) A string describing the polytope.

Example

This function can be used to convert the Cone to a string or to print information about the cone.

c = Cone([[1,0],[1,1],[0,1]])
cone_info = str(c) # Converts to string
print(c) # Prints cone info
# A 2-dimensional rational polyhedral cone in RR^2 generated by 3 rays

Constructor​

cytools.cone.Cone​

Functions​

ambient_dimension​

clear_cache​

contains​

dimension​

dual_cone​

extremal_hyperplanes​

extremal_rays​

facets​

find_grading_vector​

r​

find_interior_point​

r​

find_lattice_points​

hilbert_basis​

hyperplanes​

intersection​

is_degenerate​

is_pointed​

is_simplicial​

is_smooth​

is_solid​

lineality_space​

pointed_space​

rays​

tip_of_stretched_cone​

r​

Hidden Functions​

__eq__​

__hash__​

__init__​

__ne__​

__repr__​

Constructor

`cytools.cone.Cone`

Functions

`ambient_dimension`

`clear_cache`

`contains`

`dimension`

`dual_cone`

`extremal_hyperplanes`

`extremal_rays`

`facets`

`find_grading_vector`

r

`find_interior_point`

r

`find_lattice_points`

`hilbert_basis`

`hyperplanes`

`intersection`

`is_degenerate`

`is_pointed`

`is_simplicial`

`is_smooth`

`is_solid`

`lineality_space`

`pointed_space`

`rays`

`tip_of_stretched_cone`

r

Hidden Functions

`eq`

`hash`

`init`

`ne`

`repr`