Classes
class	GeneratingFunction

Typedefs
using	PolyhedronH = IntegerRelation
	A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients. More...

using	PolyhedronV = IntMatrix
	A polyhedron in V-representation is a set of rays and points, i.e., vectors, stored as rows of a matrix. More...

using	ConeH = PolyhedronH
	A cone in either representation is a special case of a polyhedron in that representation. More...

using	ConeV = PolyhedronV

using	ParamPoint = FracMatrix

using	Point = SmallVector< Fraction >

Functions
PolyhedronH	defineHRep (int numVars, int numSymbols=0)

DynamicAPInt	getIndex (const ConeV &cone)
	Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators, which is equal to the number of integer points in its fundamental parallelepiped. More...

ConeV	getDual (ConeH cone)
	Given a cone in H-representation, return its dual. More...

ConeH	getDual (ConeV cone)
	Given a cone in V-representation, return its dual. More...

GeneratingFunction	computeUnimodularConeGeneratingFunction (ParamPoint vertex, int sign, const ConeH &cone)
	Compute the generating function for a unimodular cone. More...

std::optional< ParamPoint >	solveParametricEquations (FracMatrix equations)
	Find the solution of a set of equations that express affine constraints between a set of variables and a set of parameters. More...

std::vector< std::pair< PresburgerSet, GeneratingFunction > >	computeChamberDecomposition (unsigned numSymbols, ArrayRef< std::pair< PresburgerSet, GeneratingFunction >> regionsAndGeneratingFunctions)
	Given a list of possibly intersecting regions (PresburgerSet) and the generating functions active in each region, produce a pairwise disjoint list of regions (chambers) and identify the generating function of the polytope in each chamber. More...

std::vector< std::pair< PresburgerSet, GeneratingFunction > >	computePolytopeGeneratingFunction (const PolyhedronH &poly)
	Compute the generating function corresponding to a polytope. More...

Point	getNonOrthogonalVector (ArrayRef< Point > vectors)
	Find a vector that is not orthogonal to any of the given vectors, i.e., has nonzero dot product with those of the given vectors that are not null. More...

QuasiPolynomial	getCoefficientInRationalFunction (unsigned power, ArrayRef< QuasiPolynomial > num, ArrayRef< Fraction > den)
	Find the coefficient of a given power of s in a rational function given by P(s)/Q(s), where P is a polynomial, in which the coefficients are QuasiPolynomials over d parameters (distinct from s), and and Q is a polynomial with Fraction coefficients. More...

QuasiPolynomial	computeNumTerms (const GeneratingFunction &gf)
	Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the input function. More...

Typedef Documentation

◆ ConeH

using mlir::presburger::detail::ConeH = typedef PolyhedronH

A cone in either representation is a special case of a polyhedron in that representation.

Definition at line 48 of file Barvinok.h.

◆ ConeV

using mlir::presburger::detail::ConeV = typedef PolyhedronV

Definition at line 49 of file Barvinok.h.

◆ ParamPoint

using mlir::presburger::detail::ParamPoint = typedef FracMatrix

Definition at line 28 of file GeneratingFunction.h.

◆ Point

using mlir::presburger::detail::Point = typedef SmallVector<Fraction>

Definition at line 31 of file GeneratingFunction.h.

◆ PolyhedronH

using mlir::presburger::detail::PolyhedronH = typedef IntegerRelation

A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients.

Definition at line 40 of file Barvinok.h.

◆ PolyhedronV

using mlir::presburger::detail::PolyhedronV = typedef IntMatrix

A polyhedron in V-representation is a set of rays and points, i.e., vectors, stored as rows of a matrix.

Definition at line 44 of file Barvinok.h.

Function Documentation

◆ computeChamberDecomposition()

std::vector< std::pair< PresburgerSet, GeneratingFunction > > mlir::presburger::detail::computeChamberDecomposition	(	unsigned	numSymbols,
		ArrayRef< std::pair< PresburgerSet, GeneratingFunction >>	regionsAndGeneratingFunctions
	)

Given a list of possibly intersecting regions (PresburgerSet) and the generating functions active in each region, produce a pairwise disjoint list of regions (chambers) and identify the generating function of the polytope in each chamber.

This is an implementation of the Clauss-Loechner algorithm for chamber decomposition.

"Disjoint" here means that the intersection of two chambers is no full- dimensional.

The returned list partitions the universe into parts depending on which subset of GFs is active there, and gives the sum of active GFs for each part.

We maintain a list of pairwise disjoint chambers and the generating functions corresponding to each one. We iterate over the list of regions, each time adding the current region's generating function to the chambers where it is active and separating the chambers where it is not.

Given the region each generating function is active in, for each subset of generating functions the region that (the sum of) precisely this subset is in, is the intersection of the regions that these are active in, intersected with the complements of the remaining regions.

Definition at line 240 of file Barvinok.cpp.

References mlir::presburger::PresburgerSpace::getSetSpace(), mlir::presburger::PresburgerSet::getUniverse(), mlir::presburger::PresburgerSet::intersect(), and mlir::presburger::PresburgerRelation::isFullDim().

Referenced by computePolytopeGeneratingFunction().

◆ computeNumTerms()

QuasiPolynomial mlir::presburger::detail::computeNumTerms ( const GeneratingFunction & gf )

Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the input function.

We have a generating function of the form f_p(x) = \sum_i sign_i * (x^n_i(p)) / (\prod_j (1 - x^d_{ij})

The generating function must be such that for all values of the parameters, the number of terms is finite.

where sign_i is ±1, n_i \in Q^p -> Q^d is the sum of the vectors d_{ij}, weighted by the floors of d affine functions on p parameters. d_{ij} \in Q^d are vectors.

We need to find the number of terms of the form x^t in the expansion of this function. However, direct substitution (x = (1, ..., 1)) causes the denominator to become zero.

We therefore use the following procedure instead:

Substitute x_i = (s+1)^μ_i for some vector μ. This makes the generating function a function of a scalar s.
Write each term in this function as P(s)/Q(s), where P and Q are polynomials. P has coefficients as quasipolynomials in d parameters, while Q has coefficients as scalars.
Find the constant term in the expansion of each term P(s)/Q(s). This is equivalent to substituting s = 0.

Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 37-66.

Definition at line 690 of file Barvinok.cpp.

References mlir::presburger::abs(), mlir::presburger::detail::GeneratingFunction::getDenominators(), getNonOrthogonalVector(), mlir::presburger::detail::GeneratingFunction::getNumerators(), mlir::presburger::detail::GeneratingFunction::getNumParams(), mlir::presburger::detail::GeneratingFunction::getSigns(), normalizeDenominatorExponents(), and substituteMuInTerm().

◆ computePolytopeGeneratingFunction()

std::vector< std::pair< PresburgerSet, GeneratingFunction > > mlir::presburger::detail::computePolytopeGeneratingFunction ( const PolyhedronH & poly )

Compute the generating function corresponding to a polytope.

For a polytope expressed as a set of n inequalities, compute the generating function corresponding to the lattice points included in the polytope.

All tangent cones of the polytope must be unimodular.

This algorithm has three main steps:

Enumerate the vertices, by iterating over subsets of inequalities and checking for satisfiability. For each d-subset of inequalities (where d is the number of variables), we solve to obtain the vertex in terms of the parameters, and then check for the region in parameter space where this vertex satisfies the remaining (n - d) inequalities.
For each vertex, identify the tangent cone and compute the generating function corresponding to it. The generating function depends on the parametric expression of the vertex and the (non-parametric) generators of the tangent cone.
[Clauss-Loechner decomposition] Identify the regions in parameter space (chambers) where each vertex is active, and accordingly compute the GF of the polytope in each chamber.

Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 37-66.

Definition at line 313 of file Barvinok.cpp.

◆ computeUnimodularConeGeneratingFunction()

GeneratingFunction mlir::presburger::detail::computeUnimodularConeGeneratingFunction	(	ParamPoint	vertex,
		int	sign,
		const ConeH &	cone
	)

Compute the generating function for a unimodular cone.

The input cone must be unimodular; it assert-fails otherwise.

This consists of a single term of the form sign * x^num / prod_j (1 - x^den_j)

sign is either +1 or -1. den_j is defined as the set of generators of the cone. num is computed by expressing the vertex as a weighted sum of the generators, and then taking the floor of the coefficients.

Definition at line 80 of file Barvinok.cpp.

Referenced by computePolytopeGeneratingFunction().

◆ defineHRep()

PolyhedronH mlir::presburger::detail::defineHRep	(	int	numVars,
		int	numSymbols = `0`
	)

inline

Definition at line 51 of file Barvinok.h.

References mlir::presburger::PresburgerSpace::getSetSpace().

Referenced by computePolytopeGeneratingFunction(), and getDual().

◆ getCoefficientInRationalFunction()

QuasiPolynomial mlir::presburger::detail::getCoefficientInRationalFunction	(	unsigned	power,
		ArrayRef< QuasiPolynomial >	num,
		ArrayRef< Fraction >	den
	)

Find the coefficient of a given power of s in a rational function given by P(s)/Q(s), where P is a polynomial, in which the coefficients are QuasiPolynomials over d parameters (distinct from s), and and Q is a polynomial with Fraction coefficients.

We use the following recursive formula to find the coefficient of s^power in the rational function given by P(s)/Q(s).

Let P[i] denote the coefficient of s^i in the polynomial P(s). (P/Q)[r] = if (r == 0) then P[0]/Q[0] else (P[r] - {Σ_{i=1}^r (P/Q)[r-i] * Q[i])}/(Q[0]) We therefore recursively call getCoefficientInRationalFunction on all i \in [0, power).

https://math.ucdavis.edu/~deloera/researchsummary/ barvinokalgorithm-latte1.pdf, p. 1285

Definition at line 515 of file Barvinok.cpp.

◆ getDual() [1/2]

ConeV mlir::presburger::detail::getDual ( ConeH cone )

Given a cone in H-representation, return its dual.

Assuming that the input cone is pointed at the origin, converts it to its dual in V-representation.

The dual cone is in V-representation. This assumes that the input is pointed at the origin; it assert-fails otherwise.

Essentially we just remove the all-zeroes constant column.

Definition at line 21 of file Barvinok.cpp.

References mlir::presburger::Matrix< T >::at(), mlir::presburger::IntegerRelation::atIneq(), mlir::presburger::IntegerRelation::getNumCols(), and mlir::presburger::IntegerRelation::getNumInequalities().

Referenced by computeUnimodularConeGeneratingFunction().

◆ getDual() [2/2]

ConeH mlir::presburger::detail::getDual ( ConeV cone )

Given a cone in V-representation, return its dual.

Converts a cone in V-representation to the H-representation of its dual, pointed at the origin (not at the original vertex).

The dual cone is in H-representation. The returned cone is pointed at the origin.

Essentially adds a column consisting only of zeroes to the end.

Definition at line 46 of file Barvinok.cpp.

References mlir::presburger::IntegerRelation::addInequality(), defineHRep(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::Matrix< T >::getRow(), mlir::presburger::Matrix< T >::insertColumn(), and rows.

◆ getIndex()

DynamicAPInt mlir::presburger::detail::getIndex ( const ConeV & cone )

Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators, which is equal to the number of integer points in its fundamental parallelepiped.

Find the index of a cone in V-representation.

If the index is 1, the cone is unimodular. Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice points in polyhedra." p. 107 If it has more rays than the dimension, return 0.

Definition at line 63 of file Barvinok.cpp.

References mlir::presburger::IntMatrix::determinant(), mlir::presburger::Matrix< T >::getNumColumns(), and mlir::presburger::Matrix< T >::getNumRows().

Referenced by computeUnimodularConeGeneratingFunction().

◆ getNonOrthogonalVector()

Point mlir::presburger::detail::getNonOrthogonalVector ( ArrayRef< Point > vectors )

Find a vector that is not orthogonal to any of the given vectors, i.e., has nonzero dot product with those of the given vectors that are not null.

We use an iterative procedure to find a vector not orthogonal to a given set, ignoring the null vectors.

If any of the vectors is null, it is ignored.

Let the inputs be {x_1, ..., x_k}, all vectors of length n.

In the following, vs[:i] means the elements of vs up to and including the i'th one, <vs, us> means the dot product of vs and us, vs ++ [v] means the vector vs with the new element v appended to it.

We proceed iteratively; for steps d = 0, ... n-1, we construct a vector which is not orthogonal to any of {x_1[:d], ..., x_n[:d]}, ignoring the null vectors. At step d = 0, we let vs = [1]. Clearly this is not orthogonal to any vector in the set {x_1[0], ..., x_n[0]}, except the null ones, which we ignore. At step d > 0 , we need a number v s.t. <x_i[:d], vs++[v]> != 0 for all i. => <x_i[:d-1], vs> + x_i[d]*v != 0 => v != - <x_i[:d-1], vs> / x_i[d] We compute this value for all x_i, and then set v to be the maximum element of this set plus one. Thus v is outside the set as desired, and we append it to vs to obtain the result of the d'th step.

Definition at line 472 of file Barvinok.cpp.

References mlir::presburger::dotProduct(), and max().

Referenced by computeNumTerms().

◆ solveParametricEquations()

std::optional< ParamPoint > mlir::presburger::detail::solveParametricEquations ( FracMatrix equations )

Find the solution of a set of equations that express affine constraints between a set of variables and a set of parameters.

We use Gaussian elimination to find the solution to a set of d equations of the form a_1 x_1 + ...

The solution expresses each variable as an affine function of the parameters.

If there is no solution, return null.

a_d x_d + b_1 m_1 + ... + b_p m_p + c = 0 where x_i are variables, m_i are parameters and a_i, b_i, c are rational coefficients.

The solution expresses each x_i as an affine function of the m_i, and is therefore represented as a matrix of size d x (p+1). If there is no solution, we return null.

Definition at line 162 of file Barvinok.cpp.

References mlir::presburger::Matrix< T >::addToRow(), mlir::presburger::FracMatrix::determinant(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::Matrix< T >::getSubMatrix(), mlir::presburger::Matrix< T >::negateMatrix(), mlir::presburger::Matrix< T >::scaleRow(), and mlir::presburger::Matrix< T >::swapRows().

Referenced by computePolytopeGeneratingFunction().

Classes

Typedefs

Functions

Typedef Documentation

◆ ConeH

◆ ConeV

◆ ParamPoint

◆ Point

◆ PolyhedronH

◆ PolyhedronV

Function Documentation

◆ computeChamberDecomposition()

◆ computeNumTerms()

◆ computePolytopeGeneratingFunction()

◆ computeUnimodularConeGeneratingFunction()

◆ defineHRep()

◆ getCoefficientInRationalFunction()

◆ getDual() [1/2]

◆ getDual() [2/2]

◆ getIndex()

◆ getNonOrthogonalVector()

◆ solveParametricEquations()