loki.analyse.util_polyhedron

Classes

Polyhedron(A, b[, variables])

Halfspace representation of a (convex) polyhedron.

class Polyhedron(A, b, variables=None)

Bases: object

Halfspace representation of a (convex) polyhedron.

A polyhedron P c R^d is described by a set of inequalities, in matrix form ` P = { x=[x1,...,xd]^T c R^d | Ax <= b } ` with n-by-d matrix A and d-dimensional right hand side b.

In loop transformations, polyhedrons are used to represent iteration spaces of d-deep loop nests.

Parameters:

A (numpy.array) – The representation matrix A.
b (numpy.array) – The right hand-side vector b.
variables (list, optional) – List of variables representing the dimensions in the polyhedron.

A

The representation matrix A.

Type:: numpy.array

b

The right hand-side vector b.

Type:: numpy.array

variables

Type:: list, optional, default = None

is_empty()

Determine whether a polyhedron is empty.

A polyhedron is considered empty under the following conditions: 1. It contains no inequalities. 2. It spans no space, which is a nontrivial problem. The simplest case is when it has an empty matrix A and does not satisfy the constant restrictions 0 <= b.

Notes

An empty polyhedron implies that it has no valid solutions or feasible points within its boundaries. This function is expected to be called only for polyhedrons with an empty matrix.

Returns:: True if the polyhedron is empty; False if it is not.
Return type:: bool

variable_to_index(variable)

lower_bounds(index_or_variable, ignore_variables=None)

Return all lower bounds imposed on a variable.

The lower bounds for the variable j are given by the index set:

`` L = {i | A_ij < 0, i in {0, …, d-1}} ``

Parameters:

index_or_variable (int or str or sym.Array or sym.Scalar) – The index, name, or expression symbol for which the lower bounds are produced.
ignore_variables (list or None, optional) – A list of variable names, indices, or symbols for which constraints should be ignored if they depend on one of them.

Returns:

The bounds for the specified variable.

Return type:

list

upper_bounds(index_or_variable, ignore_variables=None)

Return all upper bounds imposed on a variable.

The upper bounds for the variable j are given by the index set: `` U = {i | A_ij > 0, i in {0, …, d-1}} ``

Parameters:

index_or_variable (int or str or sym.Array or sym.Scalar) – The index, name, or expression symbol for which the upper bounds are produced.
ignore_variables (list or None, optional) – A list of variable names, indices, or symbols for which constraints should be ignored if they depend on one of them.

Returns:

The bounds for the specified variable.

Return type:

list

static generate_entries_for_lower_bound(bound, variables, index)

Helper routine to generate matrix and right-hand side entries for a given lower bound.

Note that this routine can only handle affine bounds, which means expressions that are constant or can be reduced to a linear polynomial.

Upper bounds can be derived from this by multiplying the left-hand side and right-hand side with -1.

Parameters:

bound (int or str or sym.Array or sym.Scalar) – The expression representing the lower bound.
variables (list of str) – The list of variable names.
index (int) – The index of the variable constrained by this bound.

Returns:

The pair (lhs, rhs) of the row in the matrix inequality, where lhs is the left-hand side and rhs is the right-hand side.

Return type:

tuple(np.array, np.array)

classmethod from_loop_ranges(loop_variables, loop_ranges): Create polyhedron from a list of loop ranges and associated variables.

classmethod from_nested_loops(nested_loops: List[Loop]): Helper function, for creating a polyhedron from a list of loops.