Frobby
0.10.0
Toggle main menu visibility
Loading...
Searching...
No Matches
src
Ideal.h
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
#ifndef IDEAL_GUARD
18
#define IDEAL_GUARD
19
20
class
Term
;
21
22
#include <vector>
23
#include <algorithm>
24
#include <ostream>
25
27
class
Ideal
{
28
typedef
vector<Exponent*> Cont;
29
30
public
:
32
Ideal
(
size_t
varCount = 0);
33
35
explicit
Ideal
(
const
Term
& term);
36
38
Ideal
(
const
Ideal
& ideal);
39
~Ideal
();
40
41
// *** Accessors
42
43
typedef
Cont::const_iterator const_iterator;
44
typedef
Cont::iterator iterator;
45
typedef
Cont::const_reverse_iterator const_reverse_iterator;
46
typedef
Cont::reverse_iterator reverse_iterator;
47
48
const_iterator begin()
const
{
return
_terms.begin();}
49
const_iterator end()
const
{
return
_terms.end();}
50
const
Exponent* operator[](
size_t
index)
const
{
return
_terms[index];}
51
52
iterator begin() {
return
_terms.begin();}
53
iterator end() {
return
_terms.end();}
54
Exponent*& operator[](
size_t
index) {
return
_terms[index];}
55
56
size_t
getVarCount()
const
{
return
_varCount;}
57
size_t
getGeneratorCount()
const
{
return
_terms.size();}
58
59
bool
isIncomparable(
const
Exponent* term)
const
;
60
61
// Returns true if any generator divides term.
62
bool
contains(
const
Exponent* term)
const
;
63
64
// Returns true if the identity is one of the generators.
65
bool
containsIdentity()
const
;
66
67
// Returns true if some minimal generator strictly divides term.
68
bool
strictlyContains(
const
Exponent* term)
const
;
69
70
// Returns true if no generator divides another.
71
bool
isMinimallyGenerated()
const
;
72
73
// Returns true if there are no generators.
74
bool
isZeroIdeal()
const
;
75
76
// Returns true if all generators are pure powers. This only
77
// corresponds to the mathematical definition of an irreducible
78
// polynomial ideal if the ideal is minimally generated.
79
bool
isIrreducible()
const
;
80
81
// Returns true if all generators are square free.
82
bool
isSquareFree()
const
;
83
84
// Returns true if no non-zero exponent of the same variable appears
85
// in two distinct generators. This only corresponds to the
86
// mathematical definition of strongly generic if the ideal is
87
// minimally generated. This method is not const because it permutes
88
// the generators.
89
bool
isStronglyGeneric();
90
91
// Returns true if for every pair of distinct generators a and b
92
// with a[i]=b[i]>0 there is some third generator that strictly
93
// divides lcm(a,b). This only corresponds to the mathematical
94
// definition of weak genericity if the ideal is minimally
95
// generated.
96
bool
isWeaklyGeneric()
const
;
97
101
bool
disjointSupport
()
const
;
102
105
void
getLcm
(Exponent* lcm)
const
;
106
109
void
getGcd
(Exponent* gcd)
const
;
110
115
void
getGcdAtExponent
(Exponent* gcd,
size_t
var, Exponent exp);
116
121
void
getGcdOfMultiplesOf
(Exponent* gcd,
const
Exponent* divisor);
122
123
// least[var] will be the smallest non-zero exponent of var that
124
// appears among the generators.
125
void
getLeastExponents(Exponent* least)
const
;
126
130
void
getSupportCounts
(Exponent* counts)
const
;
131
143
size_t
getTypicalExponent
(
size_t
& var, Exponent& exp);
144
161
size_t
getMostNonGenericExponent
(
size_t
& var, Exponent& exp);
162
179
size_t
getTypicalNonGenericExponent
(
size_t
& var, Exponent& exp);
180
188
bool
getNonGenericExponent
(
size_t
& var, Exponent& exp);
189
190
// returns the first generator that var divides or end() if no such
191
// generator exists.
192
const_iterator getMultiple(
size_t
var)
const
;
193
197
bool
operator==
(
const
Ideal
& ideal)
const
;
198
199
void
print(FILE* file)
const
;
200
void
print(ostream& out)
const
;
201
202
// *** Mutators
203
204
// Insert generators into the ideal.
205
void
insert(
const
Exponent* term);
206
void
insert(
const
Ideal
& ideal);
207
void
insert(
size_t
var, Exponent e);
208
209
// This is equivalent to calling insert and then minimize.
210
void
insertReminimize(
const
Exponent* term);
211
void
insertReminimize(
size_t
var, Exponent e);
212
213
// Remove non-redundant generators.
214
void
minimize();
215
216
// Sorts the generators in the specified order
217
void
sortReverseLex();
// reverse lexicographic order
218
void
sortLex();
// lexicographic order from left
219
220
// Sort the generators in ascending order according to the exponent of var.
221
void
singleDegreeSort(
size_t
var);
222
223
// Replace each generator g by g * term.
224
void
product(
const
Exponent* term);
225
226
// Replace each generator g by g : by. The second overload has by
227
// equal to var raised to e.
228
void
colon(
const
Exponent* by);
229
void
colon(
size_t
var, Exponent e);
230
231
// Equivalent to calling colon(by) and then minimize. The second
232
// overload has by equal to var raised to e. Returns true if the support
233
// of any generator was changed.
234
bool
colonReminimize(
const
Exponent* colon);
235
bool
colonReminimize(
size_t
var, Exponent e);
236
237
// Swaps it and the last element, and then removes the last element,
238
// which is the element originally pointed to by it.
239
void
remove(const_iterator it);
240
241
// Removes those generators that are multiples of term. The second
242
// overload has term equal to var raised to e.
243
void
removeMultiples(
const
Exponent* term);
244
void
removeMultiples(
size_t
var, Exponent e);
245
246
// Insert those generators of ideal that are not multiples of
247
// term. The second overload has term equal to var raised to e.
248
void
insertNonMultiples(
const
Exponent* term,
const
Ideal
& ideal);
249
void
insertNonMultiples(
size_t
var, Exponent e,
const
Ideal
& ideal);
250
251
// Removes those generators that are strict multiples of term.
252
void
removeStrictMultiples(
const
Exponent* term);
253
254
// Remove duplicate generators.
255
void
removeDuplicates();
256
257
// Removes all generators, and optionally sets the number of variables.
258
void
clear();
259
void
clearAndSetVarCount(
size_t
varCount);
260
266
void
mapExponentsToZeroNoMinimize
(
const
Term
& zeroExponents);
267
271
void
takeRadicalNoMinimize
();
272
273
Ideal
& operator=(
const
Ideal
& ideal);
274
275
void
swap(
Ideal
& ideal);
276
280
template
<
class
Predicate>
281
bool
removeIf
(Predicate pred);
282
287
static
void
clearStaticCache
();
288
289
protected
:
290
class
ExponentAllocator {
291
public
:
292
ExponentAllocator(
size_t
varCount);
293
~ExponentAllocator();
294
295
Exponent* allocate();
296
void
reset(
size_t
newVarCount);
297
298
void
swap(ExponentAllocator& allocator);
299
300
private
:
301
ExponentAllocator(
const
ExponentAllocator&);
302
ExponentAllocator& operator=(
const
ExponentAllocator&);
303
304
bool
useSingleChunking()
const
;
305
306
size_t
_varCount;
307
308
Exponent* _chunk;
309
Exponent* _chunkIterator;
310
Exponent* _chunkEnd;
311
312
vector<Exponent*> _chunks;
313
};
314
315
size_t
_varCount;
316
vector<Exponent*> _terms;
317
ExponentAllocator
_allocator;
318
};
319
320
template
<
class
Predicate>
321
inline
bool
Ideal::removeIf
(Predicate pred) {
322
iterator newEnd = std::remove_if(_terms.begin(), _terms.end(), pred);
323
324
if
(newEnd != _terms.end()) {
325
_terms.erase(newEnd, _terms.end());
326
return
true
;
327
}
else
328
return
false
;
329
}
330
331
inline
ostream& operator<<(ostream& out,
const
Ideal
& ideal) {
332
ideal.print(out);
333
return
out;
334
}
335
336
#endif
Ideal::ExponentAllocator
Definition
Ideal.h:290
Ideal
Represents a monomial ideal with int exponents.
Definition
Ideal.h:27
Ideal::getGcdOfMultiplesOf
void getGcdOfMultiplesOf(Exponent *gcd, const Exponent *divisor)
Definition
Ideal.cpp:197
Ideal::getGcd
void getGcd(Exponent *gcd) const
Definition
Ideal.cpp:164
Ideal::getMostNonGenericExponent
size_t getMostNonGenericExponent(size_t &var, Exponent &exp)
Definition
Ideal.cpp:272
Ideal::getLcm
void getLcm(Exponent *lcm) const
Definition
Ideal.cpp:157
Ideal::takeRadicalNoMinimize
void takeRadicalNoMinimize()
Definition
Ideal.cpp:660
Ideal::getNonGenericExponent
bool getNonGenericExponent(size_t &var, Exponent &exp)
Definition
Ideal.cpp:379
Ideal::clearStaticCache
static void clearStaticCache()
Definition
Ideal.cpp:810
Ideal::mapExponentsToZeroNoMinimize
void mapExponentsToZeroNoMinimize(const Term &zeroExponents)
Definition
Ideal.cpp:652
Ideal::getTypicalExponent
size_t getTypicalExponent(size_t &var, Exponent &exp)
Definition
Ideal.cpp:237
Ideal::disjointSupport
bool disjointSupport() const
Definition
Ideal.cpp:142
Ideal::removeIf
bool removeIf(Predicate pred)
Definition
Ideal.h:321
Ideal::getSupportCounts
void getSupportCounts(Exponent *counts) const
Definition
Ideal.cpp:227
Ideal::Ideal
Ideal(size_t varCount=0)
Definition
Ideal.cpp:31
Ideal::getTypicalNonGenericExponent
size_t getTypicalNonGenericExponent(size_t &var, Exponent &exp)
Definition
Ideal.cpp:326
Ideal::getGcdAtExponent
void getGcdAtExponent(Exponent *gcd, size_t var, Exponent exp)
Definition
Ideal.cpp:177
Ideal::operator==
bool operator==(const Ideal &ideal) const
Definition
Ideal.cpp:424
Term
Definition
Term.h:49
Generated by
1.17.0