MLIR
20.0.0git

Classes  
class  GeneratingFunction 
Typedefs  
using  PolyhedronH = IntegerRelation 
A polyhedron in Hrepresentation is a set of inequalities in d variables with integer coefficients. More...  
using  PolyhedronV = IntMatrix 
A polyhedron in Vrepresentation 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 Hrepresentation, return its dual. More...  
ConeH  getDual (ConeV cone) 
Given a cone in Vrepresentation, 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...  
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.
using mlir::presburger::detail::ConeV = typedef PolyhedronV 
Definition at line 49 of file Barvinok.h.
using mlir::presburger::detail::ParamPoint = typedef FracMatrix 
Definition at line 28 of file GeneratingFunction.h.
using mlir::presburger::detail::Point = typedef SmallVector<Fraction> 
Definition at line 31 of file GeneratingFunction.h.
using mlir::presburger::detail::PolyhedronH = typedef IntegerRelation 
A polyhedron in Hrepresentation is a set of inequalities in d variables with integer coefficients.
Definition at line 40 of file Barvinok.h.
using mlir::presburger::detail::PolyhedronV = typedef IntMatrix 
A polyhedron in Vrepresentation is a set of rays and points, i.e., vectors, stored as rows of a matrix.
Definition at line 44 of file Barvinok.h.
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 ClaussLoechner 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().
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:
Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 3766.
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().
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:
Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 3766.
Definition at line 313 of file Barvinok.cpp.
References mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::Matrix< T >::addToRow(), computeChamberDecomposition(), computeUnimodularConeGeneratingFunction(), defineHRep(), mlir::presburger::IntegerRelation::getInequalities(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::IntegerRelation::getNumRangeVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), mlir::presburger::PresburgerSpace::getRelationSpace(), mlir::presburger::Matrix< T >::getRow(), mlir::presburger::Matrix< T >::setRow(), solveParametricEquations(), and mlir::presburger::Matrix< T >::splitByBitset().
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 assertfails 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.
References mlir::presburger::abs(), mlir::presburger::FracMatrix::determinant(), getDual(), getIndex(), mlir::presburger::IntegerRelation::getInequalities(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::IntegerRelation::getNumVars(), mlir::presburger::Matrix< T >::getRow(), mlir::presburger::Matrix< T >::negateRow(), mlir::presburger::Matrix< T >::preMultiplyWithRow(), mlir::presburger::Matrix< T >::removeRow(), mlir::presburger::Matrix< T >::setRow(), and mlir::presburger::Matrix< T >::transpose().
Referenced by computePolytopeGeneratingFunction().

inline 
Definition at line 51 of file Barvinok.h.
References mlir::presburger::PresburgerSpace::getSetSpace().
Referenced by computePolytopeGeneratingFunction(), and getDual().
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)[ri] * Q[i])}/(Q[0]) We therefore recursively call getCoefficientInRationalFunction
on all i \in [0, power).
https://math.ucdavis.edu/~deloera/researchsummary/ barvinokalgorithmlatte1.pdf, p. 1285
Definition at line 515 of file Barvinok.cpp.
Given a cone in Hrepresentation, return its dual.
Assuming that the input cone is pointed at the origin, converts it to its dual in Vrepresentation.
The dual cone is in Vrepresentation. This assumes that the input is pointed at the origin; it assertfails otherwise.
Essentially we just remove the allzeroes 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().
Given a cone in Vrepresentation, return its dual.
Converts a cone in Vrepresentation to the Hrepresentation of its dual, pointed at the origin (not at the original vertex).
The dual cone is in Hrepresentation. 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.
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 Vrepresentation.
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().
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, ... n1, 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[:d1], vs> + x_i[d]*v != 0 => v !=  <x_i[:d1], 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().
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.
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().