MLIR  19.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 <bitset>
33 #include <optional>
34
35 namespace mlir {
36 namespace presburger {
37 namespace detail {
38
39 /// A polyhedron in H-representation is a set of inequalities
40 /// in d variables with integer coefficients.
42
43 /// A polyhedron in V-representation is a set of rays and points, i.e.,
44 /// vectors, stored as rows of a matrix.
46
47 /// A cone in either representation is a special case of
48 /// a polyhedron in that representation.
51
52 inline PolyhedronH defineHRep(int numVars, int numSymbols = 0) {
53  // We don't distinguish between domain and range variables, so
54  // we set the number of domain variables as 0 and the number of
55  // range variables as the number of actual variables.
56  //
57  // numSymbols is the number of parameters.
58  //
59  // There are no local (existentially quantified) variables.
60  //
61  // The number of symbols is the number of parameters. By default, we consider
62  // nonparametric polyhedra.
63  //
64  // Once the cone is defined, we use addInequality() to set inequalities.
65  return PolyhedronH(PresburgerSpace::getSetSpace(/*numDims=*/numVars,
66  /*numSymbols=*/numSymbols,
67  /*numLocals=*/0));
68 }
69
70 /// Get the index of a cone, i.e., the volume of the parallelepiped
71 /// spanned by its generators, which is equal to the number of integer
72 /// points in its fundamental parallelepiped.
73 /// If the index is 1, the cone is unimodular.
74 /// Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice
75 /// points in polyhedra." p. 107 If it has more rays than the dimension, return
76 /// 0.
77 MPInt getIndex(const ConeV &cone);
78
79 /// Given a cone in H-representation, return its dual. The dual cone is in
80 /// V-representation.
81 /// This assumes that the input is pointed at the origin; it assert-fails
82 /// otherwise.
83 ConeV getDual(ConeH cone);
84
85 /// Given a cone in V-representation, return its dual. The dual cone is in
86 /// H-representation.
87 /// The returned cone is pointed at the origin.
88 ConeH getDual(ConeV cone);
89
90 /// Compute the generating function for a unimodular cone.
91 /// The input cone must be unimodular; it assert-fails otherwise.
92 GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex,
93  int sign,
94  const ConeH &cone);
95
96 /// Find the solution of a set of equations that express affine constraints
97 /// between a set of variables and a set of parameters. The solution expresses
98 /// each variable as an affine function of the parameters.
99 ///
100 /// If there is no solution, return null.
101 std::optional<ParamPoint> solveParametricEquations(FracMatrix equations);
102
103 /// Given a list of possibly intersecting regions (PresburgerSet) and the
104 /// generating functions active in each region, produce a pairwise disjoint
105 /// list of regions (chambers) and identify the generating function of the
106 /// polytope in each chamber.
107 ///
108 /// "Disjoint" here means that the intersection of two chambers is no full-
109 /// dimensional.
110 ///
111 /// The returned list partitions the universe into parts depending on which
112 /// subset of GFs is active there, and gives the sum of active GFs for each
113 /// part.
114 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
116  unsigned numSymbols, ArrayRef<std::pair<PresburgerSet, GeneratingFunction>>
117  regionsAndGeneratingFunctions);
118
119 /// Compute the generating function corresponding to a polytope.
120 ///
121 /// All tangent cones of the polytope must be unimodular.
122 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
124
125 /// Find a vector that is not orthogonal to any of the given vectors,
126 /// i.e., has nonzero dot product with those of the given vectors
127 /// that are not null.
128 /// If any of the vectors is null, it is ignored.
130
131 /// Find the coefficient of a given power of s in a rational function
132 /// given by P(s)/Q(s), where
133 /// P is a polynomial, in which the coefficients are QuasiPolynomials
134 /// over d parameters (distinct from s), and
135 /// and Q is a polynomial with Fraction coefficients.
138  ArrayRef<Fraction> den);
139
140 /// Find the number of terms in a generating function, as
141 /// a quasipolynomial in the parameter space of the input function.
142 /// The generating function must be such that for all values of the
143 /// parameters, the number of terms is finite.
144 QuasiPolynomial computeNumTerms(const GeneratingFunction &gf);
145
146 } // namespace detail
147 } // namespace presburger
148 } // namespace mlir
149
150 #endif // MLIR_ANALYSIS_PRESBURGER_BARVINOK_H
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
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:241
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:163
SmallVector< Fraction > Point
ConeV getDual(ConeH cone)
Given a cone in H-representation, return its dual.
Definition: Barvinok.cpp:22
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:49
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:473
GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex, int sign, const ConeH &cone)
Compute the generating function for a unimodular cone.
Definition: Barvinok.cpp:81
PolyhedronH defineHRep(int numVars, int numSymbols=0)
Definition: Barvinok.h:52
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:45
IntegerRelation PolyhedronH
A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients.
Definition: Barvinok.h:41
std::vector< std::pair< PresburgerSet, GeneratingFunction > > computePolytopeGeneratingFunction(const PolyhedronH &poly)
Compute the generating function corresponding to a polytope.
Definition: Barvinok.cpp:314
MPInt getIndex(const ConeV &cone)
Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators,...
Definition: Barvinok.cpp:64
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:516
Include the generated interface declarations.