CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

Views: 418425
1
/*
2
* Normaliz
3
* Copyright (C) 2007-2014 Winfried Bruns, Bogdan Ichim, Christof Soeger
4
* This program is free software: you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License as published by
6
* the Free Software Foundation, either version 3 of the License, or
7
* (at your option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful,
10
* but WITHOUT ANY WARRANTY; without even the implied warranty of
11
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
* GNU General Public License for more details.
13
*
14
* You should have received a copy of the GNU General Public License
15
* along with this program. If not, see <http://www.gnu.org/licenses/>.
16
*
17
* As an exception, when this program is distributed through (i) the App Store
18
* by Apple Inc.; (ii) the Mac App Store by Apple Inc.; or (iii) Google Play
19
* by Google Inc., then that store may impose any digital rights management,
20
* device limits and/or redistribution restrictions that are required by its
21
* terms of service.
22
*/
23
24
/*
25
* HilbertSeries represents a Hilbert series of a (ZZ_+)-graded algebra
26
* with generators of different degrees.
27
* It is represented as a polynomial divided by a product of (1-t^i).
28
* The numerator is represented as vector of coefficients, the h-vector
29
* h vector repr.: sum of h[i]*t^i
30
* and the denominator is represented as a map d of the exponents of (1-t^i)
31
* d vector repr.: product of (1-t^i)^d[i] over i in d
32
* Input of the denominator is also possible as a vector of degrees of the
33
* generators.
34
*
35
* The class offers basic operations on the series, a simplification and
36
* different forms of representation of the series.
37
*
38
* Furthermore this file include operations for the polynomials used.
39
*/
40
41
//---------------------------------------------------------------------------
42
43
#ifndef HILBERT_SERIES_H
44
#define HILBERT_SERIES_H
45
46
//---------------------------------------------------------------------------
47
48
#include <vector>
49
#include <map>
50
#include <ostream>
51
#include <string>
52
53
#include <libnormaliz/general.h>
54
55
//---------------------------------------------------------------------------
56
57
namespace libnormaliz {
58
using std::vector;
59
using std::map;
60
using std::ostream;
61
using std::string;
62
using std::pair;
63
64
class HilbertSeries;
65
66
// write a readable representation to the stream
67
ostream& operator<< (ostream& out, const HilbertSeries& HS);
68
69
typedef long long num_t; //integer type for numerator
70
typedef long denom_t; //integer type for denominator
71
72
class HilbertSeries {
73
74
public:
75
// Constructor, creates 0/1
76
HilbertSeries();
77
// Constructor, creates num/denom, see class description for format
78
HilbertSeries(const vector<num_t>& num, const vector<denom_t>& gen_degrees);
79
// Constructor, creates num/denom, see class description for format
80
HilbertSeries(const vector<mpz_class>& num, const map<long, denom_t>& denom);
81
// Constructor, string as created by to_string_rep
82
HilbertSeries(const string& str);
83
84
// resets to 0/1
85
void reset();
86
87
// add another HilbertSeries to this
88
HilbertSeries& operator+=(const HilbertSeries& other);
89
90
// add another HilbertSeries to this
91
void add(const vector<num_t>& num, const vector<denom_t>& gen_degrees);
92
93
// simplify, see class description
94
// it changes the representation of the series, but not the series itself
95
// therefore it is declared const
96
void simplify() const;
97
// collect data from the denom_classes
98
void collectData() const;
99
100
// returns the numerator, repr. as vector of coefficients, the h-vector
101
const vector<mpz_class>& getNum() const;
102
// returns the denominator, repr. as a map of the exponents of (1-t^i)^e
103
const map<long, denom_t>& getDenom() const;
104
105
// returns the numerator, repr. as vector of coefficients
106
const vector<mpz_class>& getCyclotomicNum() const;
107
// returns the denominator, repr. as a map of the exponents of the cyclotomic polynomials
108
const map<long, denom_t>& getCyclotomicDenom() const;
109
110
void setHSOPDenom(vector<denom_t> new_denom);
111
void setHSOPDenom(map<long,denom_t> new_denom);
112
113
// returns the numerator, repr. as vector of coefficients
114
const vector<mpz_class>& getHSOPNum() const;
115
// returns the denominator, repr. as a map of the exponents of (1-t^i)^e
116
const map<long, denom_t>& getHSOPDenom() const;
117
118
long getDegreeAsRationalFunction() const;
119
120
long getPeriod() const;
121
122
void computeHilbertQuasiPolynomial() const;
123
bool isHilbertQuasiPolynomialComputed() const;
124
vector< vector<mpz_class> > getHilbertQuasiPolynomial() const;
125
mpz_class getHilbertQuasiPolynomialDenom() const;
126
127
// setting the shift will not change the numerator directly, only its interpretation
128
// the shift will be considered in the computation of the (quasi) polynomial
129
void setShift(long s);
130
// adjust the shift so that the series starts in degree 0
131
// it does not change the (quasi) polynomial
132
void adjustShift();
133
// returns the shift of the Hilbert series, that is the lowest degree of an element
134
long getShift() const;
135
136
// methods for textual transfer of a Hilbert Series
137
string to_string_rep() const;
138
void from_string_rep(const string&);
139
140
void setVerbose(bool v) { verbose = v; }
141
142
// compute the new numerator by multiplying the HS with a denominator
143
// of the form (1-t^i)
144
void compute_hsop_num() const;
145
146
void set_nr_coeff_quasipol(long nr_coeff);
147
long get_nr_coeff_quasipol() const;
148
149
void set_period_bounded(bool on_off) const;
150
bool get_period_bounded() const;
151
152
private:
153
154
void initialize();
155
156
// collected data in denominator classes
157
mutable map< vector<denom_t>, vector<num_t> > denom_classes;
158
// add the classes if they get too many
159
static const size_t DENOM_CLASSES_BOUND = 50000;
160
static const long PERIOD_BOUND = 1000000;
161
mutable bool period_bounded;
162
163
// the numerator, repr. as vector of coefficients, the h-vector
164
mutable vector<mpz_class> num;
165
// the denominator, repr. as a map of the exponents of (1-t^i)^e
166
mutable map<long, denom_t> denom;
167
168
// the numerator, repr. as vector of coefficients
169
mutable vector<mpz_class> cyclo_num;
170
// the denominator, repr. as a map of the exponents of the cyclotomic polynomials
171
mutable map<long, denom_t> cyclo_denom;
172
173
// the numerator, repr. as vector of coefficients
174
mutable vector<mpz_class> hsop_num;
175
// the denominator, repr. as a map of the exponents of the cyclotomic polynomials
176
mutable map<long, denom_t> hsop_denom;
177
178
mutable bool is_simplified;
179
mutable long dim;
180
mutable long period;
181
mutable long degree; // as rational function
182
long shift;
183
184
// the quasi polynomial, can have big coefficients
185
mutable vector< vector<mpz_class> > quasi_poly;
186
mutable mpz_class quasi_denom;
187
mutable long nr_coeff_quasipol; // limits the computation of coefficients of the computeHilbertQuasiPolynomial
188
// <0: all coeff, =0: no coeff
189
190
bool verbose;
191
192
// these are only const when used properly!!
193
void performAdd(const vector<num_t>& num, const vector<denom_t>& gen_degrees) const;
194
void performAdd(vector<mpz_class>& num, const map<long, denom_t>& denom) const;
195
196
void computeDegreeAsRationalFunction() const;
197
198
199
friend ostream& operator<< (ostream& out, const HilbertSeries& HS);
200
201
};
202
//class end *****************************************************************
203
204
205
//---------------------------------------------------------------------------
206
// polynomial operations, for polynomials repr. as vector of coefficients
207
//---------------------------------------------------------------------------
208
209
// a += b
210
template<typename Integer>
211
void poly_add_to (vector<Integer>& a, const vector<Integer>& b);
212
213
// a += b*t^m
214
template<typename Integer>
215
void poly_add_to_tm (vector<Integer>& a, const vector<Integer>& b,long m);
216
217
// a -= b
218
template<typename Integer>
219
void poly_sub_to (vector<Integer>& a, const vector<Integer>& b);
220
221
222
// a * b
223
template<typename Integer>
224
vector<Integer> poly_mult(const vector<Integer>& a, const vector<Integer>& b);
225
226
// a*b via Karatsuba
227
template<typename Integer>
228
vector<Integer> karatsubamult(const vector<Integer>& a, const vector<Integer>& b);
229
230
// a *= (1-t^d)^e
231
template<typename Integer>
232
void poly_mult_to(vector<Integer>& a, long d, long e = 1);
233
234
// a *= t^m
235
template<typename Integer>
236
void poly_mult_by_tm(vector<Integer>& a, long m);
237
238
239
// division with remainder, a = q * b + r
240
template<typename Integer>
241
void poly_div(vector<Integer>& q, vector<Integer>& r, const vector<Integer>& a, const vector<Integer>&b);
242
243
244
// remove leading zero coefficients, 0 polynomial leads to empty list
245
template<typename Integer>
246
void remove_zeros(vector<Integer>& a);
247
248
249
// Returns the n-th cyclotomic polynomial, all smaller are computed and stored.
250
// The n-th cyclotomic polynomial is the product of (X-w) over all
251
// n-th primitive roots of unity w.
252
template<typename Integer>
253
vector<Integer> cyclotomicPoly(long n);
254
255
// returns the coefficient vector of 1-t^i
256
template<typename Integer>
257
vector<Integer> coeff_vector(size_t i);
258
259
// substitutes t by (t-a), overwrites the polynomial!
260
template<typename Integer>
261
void linear_substitution(vector<Integer>& poly, const Integer& a);
262
263
//---------------------------------------------------------------------------
264
// computing the Hilbert polynomial from h-vector
265
//---------------------------------------------------------------------------
266
267
template<typename Integer>
268
vector<Integer> compute_e_vector(vector<Integer> h_vector, int dim);
269
270
template<typename Integer>
271
vector<Integer> compute_polynomial(vector<Integer> h_vector, int dim);
272
273
//---------------------------------------------------------------------------
274
// A class collecting integrals and weighted Ehrhart series
275
//---------------------------------------------------------------------------
276
277
class IntegrationData{
278
279
string polynomial;
280
long degree_of_polynomial;
281
bool polynomial_is_homogeneous;
282
mpq_class integral, virtual_multiplicity;
283
pair<HilbertSeries, mpz_class> weighted_Ehrhart_series; // the second component holds the common
284
// denominator of the coefficients in the numerator
285
public:
286
287
void setIntegral(const mpq_class I);
288
void setVirtualMultiplicity(const mpq_class I);
289
void setWeightedEhrhartSeries(const pair<HilbertSeries, mpz_class>& E);
290
void setHomogeneity(const bool hom);
291
// void setCommonDenom(const mpq_class D);
292
void setDegreeOfPolynomial(const long d);
293
void set_nr_coeff_quasipol(long nr_coeff);
294
295
string getPolynomial() const;
296
long getDegreeOfPolynomial() const;
297
mpq_class getIntegral() const;
298
mpq_class getVirtualMultiplicity() const;
299
const pair<HilbertSeries, mpz_class>& getWeightedEhrhartSeries() const;
300
bool isPolynomialHomogeneous() const;
301
mpz_class getNumeratorCommonDenom() const;
302
303
const vector<mpz_class>& getNum_ZZ() const;
304
// returns the denominator, repr. as a map of the exponents of (1-t^i)^e
305
const map<long, denom_t>& getDenom() const;
306
307
const vector<mpz_class>& getCyclotomicNum_ZZ() const;
308
// returns the denominator, repr. as a map of the exponents of the cyclotomic polynomials
309
const map<long, denom_t>& getCyclotomicDenom() const;
310
311
void computeWeightedEhrhartQuasiPolynomial() const;
312
bool isWeightedEhrhartQuasiPolynomialComputed() const;
313
vector< vector<mpz_class> > getWeightedEhrhartQuasiPolynomial() const;
314
void computeWeightedEhrhartQuasiPolynomial();
315
mpz_class getWeightedEhrhartQuasiPolynomialDenom() const;
316
317
IntegrationData(const string& poly);
318
IntegrationData();
319
}; // class end
320
321
} //end namespace libnormaliz
322
323
//---------------------------------------------------------------------------
324
#endif
325
//---------------------------------------------------------------------------
326
327
328