Frobby 0.9.5
BigIdeal.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
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 2 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#include "stdinc.h"
18#include "BigIdeal.h"
19
20#include "VarNames.h"
21#include "TermTranslator.h"
22#include "Ideal.h"
23#include "VarSorter.h"
24#include "RawSquareFreeTerm.h"
25#include "SquareFreeIdeal.h"
26#include <sstream>
27
29public:
30 OffsetTermCompare(const BigIdeal& ideal): _ideal(ideal) {
31 }
32
33 bool operator()(size_t aa, size_t bb) const {
34 const vector<mpz_class>& a = _ideal.getTerm(aa);
35 const vector<mpz_class>& b = _ideal.getTerm(bb);
36
37 ASSERT(a.size() == b.size());
38 for (size_t i = 0; i < a.size(); ++i) {
39 if (a[i] > b[i])
40 return true;
41 if (a[i] < b[i])
42 return false;
43 }
44 return false;
45 }
46
47private:
48 void operator=(const OffsetTermCompare&); // To make this inaccessible.
49
51};
52
54}
55
57 _names(names) {
58}
59
60void BigIdeal::insert(const Ideal& ideal) {
62
63 Ideal::const_iterator it = ideal.begin();
64 for (; it != ideal.end(); ++it) {
66 for (size_t var = 0; var < _names.getVarCount(); ++var)
67 getLastTermExponentRef(var) = (*it)[var];
68 }
69}
70
71void BigIdeal::insert(const Ideal& ideal,
72 const TermTranslator& translator) {
74
75 Ideal::const_iterator it = ideal.begin();
76 for (; it != ideal.end(); ++it) {
78 for (size_t var = 0; var < _names.getVarCount(); ++var)
79 getLastTermExponentRef(var) = translator.getExponent(var, (*it)[var]);
80 }
81}
82
85
87 for (; it != ideal.end(); ++it) {
89 for (size_t var = 0; var < _names.getVarCount(); ++var)
91 }
92}
93
94void BigIdeal::insert(const vector<mpz_class>& term) {
96 getLastTermRef() = term;
97}
98
99void BigIdeal::renameVars(const VarNames& names) {
100 ASSERT(names.getVarCount() == _names.getVarCount());
101 _names = names;
102}
103
105 if (_terms.size() == _terms.capacity())
106 reserve(getVarCount() * _terms.size());
107
108 _terms.resize(_terms.size() + 1);
109 _terms.back().resize(_names.getVarCount());
110}
111
112void BigIdeal::reserve(size_t capacity) {
113 // std::vector can do reallocations by itself, but the version here
114 // is much faster.
115 if (capacity <= _terms.capacity())
116 return;
117
118 // We grow the capacity at a rate of getVarCount() instead of a
119 // doubling because each *used* entry allocates at least
120 // getVarCount() memory anyway, so we will still only use at most
121 // double the memory than we need.
122 //
123 // We make tmp have the capacity we need, then we move the data
124 // entry by entry to tmp, and then we swap tmp and _terms. This
125 // will also swap the excess capacity into _terms. If allowed to
126 // reallocate by itself, the implementation of STL (GCC 3.4.4) I'm
127 // using will *copy* the data instead of swapping it, which is
128 // very bad.
129 vector<vector<mpz_class> > tmp;
130 size_t newCapacity = getVarCount() * _terms.size();
131 if (capacity > newCapacity)
132 newCapacity = capacity;
133
134 tmp.reserve(newCapacity);
135 tmp.resize(_terms.size());
136
137 size_t size = _terms.size();
138 for (size_t i = 0; i < size; ++i)
139 tmp[i].swap(_terms[i]);
140 tmp.swap(_terms);
141}
142
143void BigIdeal::getLcm(vector<mpz_class>& lcm) const {
144 lcm.clear();
145 lcm.resize(getVarCount());
146
147 for (vector<vector<mpz_class> >::const_iterator it = _terms.begin();
148 it != _terms.end(); ++it)
149 for (size_t var = 0; var < getVarCount(); ++var)
150 if (lcm[var] < (*it)[var])
151 lcm[var] = (*it)[var];
152}
153
154bool BigIdeal::operator==(const BigIdeal& b) const {
155 return _terms == b._terms;
156}
157
158void BigIdeal::projectVar(size_t var) {
159 ASSERT(var < getVarCount());
160
161 for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
162 _terms[gen].erase(_terms[gen].begin() + var);
163 _names.projectVar(var);
164}
165
166bool BigIdeal::operator<(const BigIdeal& ideal) const {
167 if (getNames() < ideal.getNames())
168 return true;
169 if (ideal.getNames() < getNames())
170 return false;
171
172 for (size_t t = 0; t < _terms.size(); ++t) {
173 if (t == ideal._terms.size())
174 return true;
175
176 const vector<mpz_class>& a = _terms[t];
177 const vector<mpz_class>& b = ideal._terms[t];
178
179 ASSERT(a.size() == b.size());
180
181 for (size_t i = 0; i < a.size(); ++i) {
182 if (a[i] > b[i])
183 return true;
184 if (a[i] < b[i])
185 return false;
186 }
187 }
188
189 return false;
190}
191
192bool BigIdeal::empty() const {
193 return _terms.empty();
194}
195
197 for (size_t gen = 0; gen < getGeneratorCount(); ++gen) {
198 for (size_t var = 0; var < getVarCount(); ++var)
199 if (_terms[gen][var] != 0)
200 goto notIdentity;
201 return true;
202 notIdentity:;
203 }
204 return false;
205}
206
207bool BigIdeal::contains(const vector<mpz_class>& term) const {
208 for (size_t gen = 0; gen < getGeneratorCount(); ++gen) {
209 for (size_t var = 0; var < getVarCount(); ++var)
210 if (_terms[gen][var] > term[var])
211 goto notDivisor;
212 return true;
213 notDivisor:;
214 }
215 return false;
216}
217
219 _terms.clear();
220}
221
223 clear();
224 _names = names;
225}
226
227bool BigIdeal::addVarToClearedIdeal(const char* var) {
229
230 return _names.addVar(var);
231}
232
233void BigIdeal::eraseVar(size_t varToErase) {
234 ASSERT(varToErase < getVarCount());
235
236 VarNames newNames;
237 for (size_t var = 0; var < getVarCount(); ++var)
238 if (var != varToErase)
239 newNames.addVar(_names.getName(var));
240
241 try {
242 _names = newNames;
243 for (size_t term = 0; term < getGeneratorCount(); ++term)
244 _terms[term].erase(_terms[term].begin() + varToErase);
245 } catch (...) {
246 // To leave in valid state, which requires that _names has the same
247 // number of variables as each generator.
248 clear();
249 throw;
250 }
251}
252
254 return _names;
255}
256
258 for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
259 for (size_t var = 0; var < getVarCount(); ++var)
260 if (_terms[gen][var] > 0)
261 _terms[gen][var] = _terms[gen][var] * getGeneratorCount() + gen;
262}
263
265 vector<vector<mpz_class> >::iterator end = _terms.end();
266 for (vector<vector<mpz_class> >::iterator it = _terms.begin();
267 it != end; ++it)
268 for (size_t var = 0; var < getVarCount(); ++var)
269 if ((*it)[var] > 1)
270 (*it)[var] = 1;
271}
272
275 vector<vector<mpz_class> >::iterator newEnd =
276 unique(_terms.begin(), _terms.end());
277 _terms.erase(newEnd, _terms.end());
278}
279
281 size_t size = _terms.size();
282 vector<size_t> sortedOffsets(size);
283 for (size_t term = 0; term < size; ++term)
284 sortedOffsets[term] = term;
285
286 std::sort(sortedOffsets.begin(), sortedOffsets.end(),
287 OffsetTermCompare(*this));
288
289 vector<vector<mpz_class> > sorted;
290 sorted.reserve(_terms.capacity());
291 sorted.resize(size);
292 for (size_t term = 0; term < size; ++term)
293 sorted[term].swap(_terms[sortedOffsets[term]]);
294
295 _terms.swap(sorted);
296}
297
299 VarSorter sorter(_names);
300 sorter.getOrderedNames(_names);
301 for (size_t i = 0; i < _terms.size(); ++i)
302 sorter.permute(_terms[i]);
303}
304
306 _terms.swap(ideal._terms);
307 _names.swap(ideal._names);
308}
309
310void BigIdeal::print(FILE* file) const {
311 ostringstream out;
312 out << *this;
313 fputs(out.str().c_str(), file);
314}
315
316void BigIdeal::print(ostream& out) const {
317 out << "/---- BigIdeal of " << _terms.size() << " terms:\n";
318 for (vector<vector<mpz_class> >::const_iterator it = _terms.begin();
319 it != _terms.end(); ++it) {
320 for (vector<mpz_class>::const_iterator entry = it->begin();
321 entry != it->end(); ++entry)
322 out << *entry << ' ';
323 out << '\n';
324 }
325 out << "----/ End of list.\n";
326}
327
328const mpz_class& BigIdeal::getExponent(size_t term, size_t var) const {
329 ASSERT(term < _terms.size());
330 ASSERT(var < _names.getVarCount());
331
332 return _terms[term][var];
333}
334
335mpz_class& BigIdeal::getExponent(size_t term, size_t var) {
336 ASSERT(term < _terms.size());
337 ASSERT(var < _names.getVarCount());
338
339 return _terms[term][var];
340}
341
342void BigIdeal::setExponent(size_t term, size_t var, const mpz_class& exp) {
343 ASSERT(term < _terms.size());
344 ASSERT(var < _names.getVarCount());
345
346 _terms[term][var] = exp;
347}
348
349bool BigIdeal::bigTermCompare(const vector<mpz_class>& a,
350 const vector<mpz_class>& b) {
351 ASSERT(a.size() == b.size());
352 for (size_t i = 0; i < a.size(); ++i) {
353 if (a[i] > b[i])
354 return true;
355 if (a[i] < b[i])
356 return false;
357 }
358 return false;
359}
360
361ostream& operator<<(ostream& out, const BigIdeal& ideal) {
362 ideal.print(out);
363 return out;
364}
365
366ostream& operator<<(ostream& out, const vector<BigIdeal>& ideals) {
367 out << "List of " << ideals.size() << " ideals:\n";
368 for (size_t i = 0; i < ideals.size(); ++i)
369 out << ideals[i];
370 return out;
371}
ostream & operator<<(ostream &out, const BigIdeal &ideal)
Definition: BigIdeal.cpp:361
void reserve(size_t capacity)
Definition: BigIdeal.cpp:112
void eraseVar(size_t var)
Definition: BigIdeal.cpp:233
void sortGenerators()
Definition: BigIdeal.cpp:280
void clearAndSetNames(const VarNames &names)
Definition: BigIdeal.cpp:222
void newLastTerm()
Definition: BigIdeal.cpp:104
void swap(BigIdeal &ideal)
Definition: BigIdeal.cpp:305
static bool bigTermCompare(const vector< mpz_class > &a, const vector< mpz_class > &b)
Definition: BigIdeal.cpp:349
bool empty() const
Definition: BigIdeal.cpp:192
void sortGeneratorsUnique()
Definition: BigIdeal.cpp:273
const vector< mpz_class > & getTerm(size_t term) const
Definition: BigIdeal.h:139
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
void renameVars(const VarNames &names)
Definition: BigIdeal.cpp:99
void getLcm(vector< mpz_class > &lcm) const
Definition: BigIdeal.cpp:143
bool contains(const vector< mpz_class > &term) const
Definition: BigIdeal.cpp:207
vector< vector< mpz_class > > _terms
Definition: BigIdeal.h:107
void deform()
Definition: BigIdeal.cpp:257
size_t getVarCount() const
Definition: BigIdeal.h:148
void clear()
Definition: BigIdeal.cpp:218
bool operator==(const BigIdeal &b) const
Definition: BigIdeal.cpp:154
VarNames _names
Definition: BigIdeal.h:108
void insert(const Ideal &ideal)
Definition: BigIdeal.cpp:60
const VarNames & getNames() const
Definition: BigIdeal.cpp:253
size_t getGeneratorCount() const
Definition: BigIdeal.h:144
BigIdeal()
Definition: BigIdeal.cpp:53
void projectVar(size_t var)
Definition: BigIdeal.cpp:158
void sortVariables()
Definition: BigIdeal.cpp:298
bool operator<(const BigIdeal &ideal) const
Definition: BigIdeal.cpp:166
void print(FILE *file) const
Definition: BigIdeal.cpp:310
void takeRadical()
Definition: BigIdeal.cpp:264
bool containsIdentity() const
Definition: BigIdeal.cpp:196
const mpz_class & getExponent(size_t term, size_t var) const
Definition: BigIdeal.cpp:328
bool addVarToClearedIdeal(const char *var)
Definition: BigIdeal.cpp:227
vector< mpz_class > & getLastTermRef()
Definition: BigIdeal.h:133
void setExponent(size_t term, size_t var, const mpz_class &exp)
Definition: BigIdeal.cpp:342
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
size_t getGeneratorCount() const
Definition: Ideal.h:57
Cont::const_iterator const_iterator
Definition: Ideal.h:43
const_iterator end() const
Definition: Ideal.h:49
const_iterator begin() const
Definition: Ideal.h:48
OffsetTermCompare(const BigIdeal &ideal)
Definition: BigIdeal.cpp:30
const BigIdeal & _ideal
Definition: BigIdeal.cpp:50
bool operator()(size_t aa, size_t bb) const
Definition: BigIdeal.cpp:33
void operator=(const OffsetTermCompare &)
const_iterator doesn't have all it needs to be a proper STL iterator.
iterator begin()
size_t getGeneratorCount() const
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
const mpz_class & getExponent(size_t variable, Exponent exponent) const
This method translates from IDs to arbitrary precision integers.
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
bool addVar(const string &name)
Adds the variable and returns true if name is not already a variable.
Definition: VarNames.cpp:44
size_t getVarCount() const
Returns the current number of variables.
Definition: VarNames.h:113
const string & getName(size_t index) const
The returned reference can become invalid next time addVar is called.
Definition: VarNames.cpp:100
void swap(VarNames &names)
Definition: VarNames.cpp:190
void projectVar(size_t index)
Definition: VarNames.cpp:161
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
#define ASSERT(X)
Definition: stdinc.h:86
void getOrderedNames(VarNames &names)
Definition: VarSorter.cpp:50
void permute(vector< mpz_class > &term)
Definition: VarSorter.cpp:56