MLIR  20.0.0git
Barvinok.h
Go to the documentation of this file.
1 //===- Barvinok.h - Barvinok's Algorithm ------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of Barvinok's algorithm and related utility functions.
10 // Currently a work in progress.
11 // These include functions to manipulate cones (define a cone object, get its
12 // dual, and find its index).
13 //
14 // The implementation is based on:
15 // 1. Barvinok, Alexander, and James E. Pommersheim. "An algorithmic theory of
16 // lattice points in polyhedra." New perspectives in algebraic combinatorics
17 // 38 (1999): 91-147.
18 // 2. Verdoolaege, Sven, et al. "Counting integer points in parametric
19 // polytopes using Barvinok's rational functions." Algorithmica 48 (2007):
20 // 37-66.
21 //
22 //===----------------------------------------------------------------------===//
23
24 #ifndef MLIR_ANALYSIS_PRESBURGER_BARVINOK_H
25 #define MLIR_ANALYSIS_PRESBURGER_BARVINOK_H
26
27
30
32 #include <optional>
33
34 namespace mlir {
35 namespace presburger {
36 namespace detail {
37
38 /// A polyhedron in H-representation is a set of inequalities
39 /// in d variables with integer coefficients.
41
42 /// A polyhedron in V-representation is a set of rays and points, i.e.,
43 /// vectors, stored as rows of a matrix.
45
46 /// A cone in either representation is a special case of
47 /// a polyhedron in that representation.
50
51 inline PolyhedronH defineHRep(int numVars, int numSymbols = 0) {
52  // We don't distinguish between domain and range variables, so
53  // we set the number of domain variables as 0 and the number of
54  // range variables as the number of actual variables.
55  //
56  // numSymbols is the number of parameters.
57  //
58  // There are no local (existentially quantified) variables.
59  //
60  // The number of symbols is the number of parameters. By default, we consider
61  // nonparametric polyhedra.
62  //
63  // Once the cone is defined, we use addInequality() to set inequalities.
64  return PolyhedronH(PresburgerSpace::getSetSpace(/*numDims=*/numVars,
65  /*numSymbols=*/numSymbols,
66  /*numLocals=*/0));
67 }
68
69 /// Get the index of a cone, i.e., the volume of the parallelepiped
70 /// spanned by its generators, which is equal to the number of integer
71 /// points in its fundamental parallelepiped.
72 /// If the index is 1, the cone is unimodular.
73 /// Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice
74 /// points in polyhedra." p. 107 If it has more rays than the dimension, return
75 /// 0.
76 DynamicAPInt getIndex(const ConeV &cone);
77
78 /// Given a cone in H-representation, return its dual. The dual cone is in
79 /// V-representation.
80 /// This assumes that the input is pointed at the origin; it assert-fails
81 /// otherwise.
82 ConeV getDual(ConeH cone);
83
84 /// Given a cone in V-representation, return its dual. The dual cone is in
85 /// H-representation.
86 /// The returned cone is pointed at the origin.
87 ConeH getDual(ConeV cone);
88
89 /// Compute the generating function for a unimodular cone.
90 /// The input cone must be unimodular; it assert-fails otherwise.
91 GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex,
92  int sign,
93  const ConeH &cone);
94
95 /// Find the solution of a set of equations that express affine constraints
96 /// between a set of variables and a set of parameters. The solution expresses
97 /// each variable as an affine function of the parameters.
98 ///
99 /// If there is no solution, return null.
100 std::optional<ParamPoint> solveParametricEquations(FracMatrix equations);
101
102 /// Given a list of possibly intersecting regions (PresburgerSet) and the
103 /// generating functions active in each region, produce a pairwise disjoint
104 /// list of regions (chambers) and identify the generating function of the
105 /// polytope in each chamber.
106 ///
107 /// "Disjoint" here means that the intersection of two chambers is no full-
108 /// dimensional.
109 ///
110 /// The returned list partitions the universe into parts depending on which
111 /// subset of GFs is active there, and gives the sum of active GFs for each
112 /// part.
113 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
115  unsigned numSymbols, ArrayRef<std::pair<PresburgerSet, GeneratingFunction>>
116  regionsAndGeneratingFunctions);
117
118 /// Compute the generating function corresponding to a polytope.
119 ///
120 /// All tangent cones of the polytope must be unimodular.
121 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
123
124 /// Find a vector that is not orthogonal to any of the given vectors,
125 /// i.e., has nonzero dot product with those of the given vectors
126 /// that are not null.
127 /// If any of the vectors is null, it is ignored.
129
130 /// Find the coefficient of a given power of s in a rational function
131 /// given by P(s)/Q(s), where
132 /// P is a polynomial, in which the coefficients are QuasiPolynomials
133 /// over d parameters (distinct from s), and
134 /// and Q is a polynomial with Fraction coefficients.
137  ArrayRef<Fraction> den);
138
139 /// Find the number of terms in a generating function, as
140 /// a quasipolynomial in the parameter space of the input function.
141 /// The generating function must be such that for all values of the
142 /// parameters, the number of terms is finite.
143 QuasiPolynomial computeNumTerms(const GeneratingFunction &gf);
144
145 } // namespace detail
146 } // namespace presburger
147 } // namespace mlir
148
149 #endif // MLIR_ANALYSIS_PRESBURGER_BARVINOK_H
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
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 ...
Definition: Barvinok.cpp:240
std::optional< ParamPoint > solveParametricEquations(FracMatrix equations)
Find the solution of a set of equations that express affine constraints between a set of variables an...
Definition: Barvinok.cpp:162
SmallVector< Fraction > Point
ConeV getDual(ConeH cone)
Given a cone in H-representation, return its dual.
Definition: Barvinok.cpp:21
QuasiPolynomial computeNumTerms(const GeneratingFunction &gf)
Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the...
Definition: Barvinok.cpp:690
PolyhedronH ConeH
A cone in either representation is a special case of a polyhedron in that representation.
Definition: Barvinok.h:48
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 ...
Definition: Barvinok.cpp:472
GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex, int sign, const ConeH &cone)
Compute the generating function for a unimodular cone.
Definition: Barvinok.cpp:80
PolyhedronH defineHRep(int numVars, int numSymbols=0)
Definition: Barvinok.h:51
IntMatrix PolyhedronV
A polyhedron in V-representation is a set of rays and points, i.e., vectors, stored as rows of a matr...
Definition: Barvinok.h:44
IntegerRelation PolyhedronH
A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients.
Definition: Barvinok.h:40
std::vector< std::pair< PresburgerSet, GeneratingFunction > > computePolytopeGeneratingFunction(const PolyhedronH &poly)
Compute the generating function corresponding to a polytope.
Definition: Barvinok.cpp:313
DynamicAPInt getIndex(const ConeV &cone)
Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators,...
Definition: Barvinok.cpp:63
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),...
Definition: Barvinok.cpp:515
Include the generated interface declarations.