Frobby 0.9.5
Slice.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 "Slice.h"
19
20#include "Projection.h"
21#include "TaskEngine.h"
22#include "SliceStrategy.h"
23
24// The lcm is technically correct, but _lcmUpdated defaulting to false
25// is still a sensible choice.
27 _varCount(0),
28 _lcmUpdated(false),
29 _lowerBoundHint(0),
30 _strategy(strategy) {
31}
32
34 const Ideal& ideal, const Ideal& subtract, const Term& multiply):
35 _ideal(ideal),
36 _subtract(subtract),
37 _multiply(multiply),
38 _varCount(multiply.getVarCount()),
39 _lcm(multiply.getVarCount()),
40 _lcmUpdated(false),
41 _lowerBoundHint(0),
42 _strategy(strategy) {
43 ASSERT(multiply.getVarCount() == ideal.getVarCount());
44 ASSERT(multiply.getVarCount() == subtract.getVarCount());
45}
46
48 // We are defining this do-nothing destructor in order to make it
49 // virtual.
50}
51
52const Term& Slice::getLcm() const {
53#ifdef DEBUG
54 if (_lcmUpdated) {
55 Term tmp(_varCount);
56 _ideal.getLcm(tmp);
57 ASSERT(tmp == _lcm);
58 }
59#endif
60
61 if (!_lcmUpdated) {
63 _lcmUpdated = true;
64 }
65 return _lcm;
66}
67
68void Slice::print(FILE* file) const {
69 fputs("Slice (multiply: ", file);
70 _multiply.print(file);
71 fputs("\n ideal: ", file);
72 getIdeal().print(file);
73 fputs(" subtract: ", file);
74 _subtract.print(file);
75}
76
78 _varCount = slice._varCount;
79 _ideal = slice._ideal;
80 _subtract = slice._subtract;
81 _multiply = slice._multiply;
82 _lcm = slice._lcm;
85
86 return *this;
87}
88
89void Slice::resetAndSetVarCount(size_t varCount) {
90 _varCount = varCount;
93 _multiply.reset(varCount);
94 _lcm.reset(varCount);
95 _lcmUpdated = false;
97}
98
100 _ideal.clear();
102 _lcmUpdated = false;
103 _lowerBoundHint = 0;
104}
105
108}
109
110bool Slice::innerSlice(const Term& pivot) {
111 ASSERT(getVarCount() == pivot.getVarCount());
112
113 size_t count = _ideal.getGeneratorCount();
114
116 bool idealChanged = _ideal.colonReminimize(pivot);
117 bool subtractChanged = _subtract.colonReminimize(pivot);
118 bool changed = idealChanged || subtractChanged;
119 if (changed) {
120 normalize();
122 }
123
124 if (_ideal.getGeneratorCount() == count)
125 _lcm.colon(_lcm, pivot);
126 else
127 _lcmUpdated = false;
128
129 return changed;
130}
131
132void Slice::outerSlice(const Term& pivot) {
133 ASSERT(getVarCount() == pivot.getVarCount());
134
135 size_t count = getIdeal().getGeneratorCount();
137 if (getIdeal().getGeneratorCount() != count)
138 _lcmUpdated = false;
139
140 if (pivot.getSizeOfSupport() > 1)
142
144}
145
146// Helper class for normalize().
148public:
149 StrictMultiplePredicate(const Exponent* term, size_t varCount):
150 _term(term), _varCount(varCount) {
151 }
152
153 bool operator()(const Exponent* term) {
155 }
156
157private:
159 size_t _varCount;
160};
161
163 bool changed = false;
164 while (true) {
165 Term lowerBound(_varCount);
166
168 for (Ideal::const_iterator it = getIdeal().begin(); it != end; ++it) {
169 for (size_t var = 0; var < _varCount; ++var) {
170 if ((*it)[var] == 0)
171 continue;
172 if (lowerBound[var] == 0 || lowerBound[var] > (*it)[var])
173 lowerBound[var] = (*it)[var];
174 }
175 }
176 lowerBound.decrement();
177
178 if (lowerBound.isIdentity())
179 break;
180
181 changed = true;
182 bool sawRealChange = innerSlice(lowerBound);
183 if (!sawRealChange)
184 break;
185 }
186 return changed;
187}
188
190 bool removedAny = false;
191
193 for (Ideal::const_iterator it = _subtract.begin(); it != stop; ++it) {
195 if (_ideal.removeIf(pred)) {
196 removedAny = true;
197 _lcmUpdated = false;
198 }
199 }
200
201 return removedAny;
202}
203
205 ASSERT(!normalize());
206
207 bool lowerBoundChange = applyLowerBound();
208 bool pruneSubtractChange = pruneSubtract();
209
210 ASSERT(!normalize());
213
214 return lowerBoundChange || pruneSubtractChange;
215}
216
218(const Slice& slice, const Projection& projection) {
220
221 Ideal::const_iterator stop = slice.getIdeal().end();
222 for (Ideal::const_iterator it = slice.getIdeal().begin();
223 it != stop; ++it) {
224
225 size_t var = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
226 if (var == slice.getVarCount() || projection.domainVarHasProjection(var)) {
227 // Use _lcm as temporary.
228 projection.project(_lcm, *it);
230 }
231 }
232
233 stop = slice.getSubtract().end();
234 for (Ideal::const_iterator it = slice.getSubtract().begin();
235 it != stop; ++it) {
236
237 size_t var = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
238 if (var == slice.getVarCount() || projection.domainVarHasProjection(var)) {
239 projection.project(_lcm, *it);
241 }
242 }
243
244 projection.project(getMultiply(), slice.getMultiply());
245 if (slice._lcmUpdated) {
246 projection.project(_lcm, slice._lcm);
247 _lcmUpdated = true;
248 } else
249 _lcmUpdated = false;
250}
251
252void Slice::swap(Slice& slice) {
253 std::swap(_varCount, slice._varCount);
254 _multiply.swap(slice._multiply);
255 _lcm.swap(slice._lcm);
256 std::swap(_lcmUpdated, slice._lcmUpdated);
257 _ideal.swap(slice._ideal);
258 _subtract.swap(slice._subtract);
259 std::swap(_lowerBoundHint, slice._lowerBoundHint);
260}
261
262namespace {
264 class PruneSubtractPredicate {
265 public:
266 PruneSubtractPredicate(const Ideal& ideal, const Term& lcm):
267 _ideal(ideal), _lcm(lcm) {}
268
269 bool operator()(const Exponent* term) {
270 return
271 !Term::strictlyDivides(term, _lcm, _lcm.getVarCount()) ||
272 _ideal.contains(term);
273 }
274
275 private:
276 const Ideal& _ideal;
277 const Term& _lcm;
278 };
279}
280
282 if (_subtract.getGeneratorCount() == 0)
283 return false;
284
285 PruneSubtractPredicate pred(getIdeal(), getLcm());
286 return _subtract.removeIf(pred);
287}
288
290 if (_ideal.getGeneratorCount() == 0)
291 return false;
292 if (getVarCount() == 1)
293 return adjustMultiply();
294
295 bool changed = false;
296 size_t stepsWithNoChange = 0;
297
298 Term bound(_varCount);
299 size_t var = _lowerBoundHint;
300 while (stepsWithNoChange < _varCount) {
301 if (!getLowerBound(bound, var)) {
303 return true;
304 }
305
306 if (!bound.isIdentity()) {
307 changed = true;
308 if (innerSlice(bound))
309 stepsWithNoChange = 0;
310 else
311 ++stepsWithNoChange;
312 } else
313 ++stepsWithNoChange;
314
315 var = (var + 1) % _varCount;
316 }
317
318 return changed;
319}
320
321void Slice::run(TaskEngine& tasks) {
322 _strategy.processSlice(tasks, auto_ptr<Slice>(this));
323}
324
326 _strategy.freeSlice(auto_ptr<Slice>(this));
327}
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
void removeStrictMultiples(const Exponent *term)
Definition Ideal.cpp:622
void singleDegreeSort(size_t var)
Definition Ideal.cpp:518
size_t getGeneratorCount() const
Definition Ideal.h:57
void clearAndSetVarCount(size_t varCount)
Definition Ideal.cpp:646
void getLcm(Exponent *lcm) const
Sets lcm to the least common multiple of all generators.
Definition Ideal.cpp:157
void clear()
Definition Ideal.cpp:641
void insert(const Exponent *term)
Definition Ideal.cpp:455
void insertReminimize(const Exponent *term)
Definition Ideal.cpp:484
const_iterator end() const
Definition Ideal.h:49
bool removeIf(Predicate pred)
Removes those generators m such that pred(m) evaluates to true.
Definition Ideal.h:321
void print(FILE *file) const
Definition Ideal.cpp:440
void swap(Ideal &ideal)
Definition Ideal.cpp:683
const_iterator begin() const
Definition Ideal.h:48
bool colonReminimize(const Exponent *colon)
Definition Ideal.cpp:550
Cont::const_iterator const_iterator
Definition Ideal.h:43
size_t getVarCount() const
Definition Ideal.h:56
bool domainVarHasProjection(size_t var) const
void project(Exponent *to, const Exponent *from) const
size_t getRangeVarCount() const
This class describes the interface of a strategy object for the Slice Algorithm.
virtual void freeSlice(auto_ptr< Slice > slice)=0
It is allowed to delete returned slices directly, but it is better to use freeSlice.
virtual bool processSlice(TaskEngine &tasks, auto_ptr< Slice > slice)=0
Process the parameter slice.
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
size_t _varCount
The number of variables in the ambient polynomial ring.
Definition Slice.h:275
Ideal _ideal
The of a slice .
Definition Slice.h:266
void resetAndSetVarCount(size_t varCount)
Resets this slice to in an ambient polynomial ring of varCount variables.
Definition Slice.cpp:89
SliceStrategy & _strategy
Definition Slice.h:303
bool normalize()
Removes those generators of getIdeal() that are strictly divisible by some generator of getSubtract()...
Definition Slice.cpp:189
void singleDegreeSortIdeal(size_t var)
Calls Ideal::singleDegreeSort on getIdeal().
Definition Slice.cpp:106
void print(FILE *file) const
Write a text representation of this object to file in a format appropriate for debugging.
Definition Slice.cpp:68
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition Slice.cpp:110
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition Slice.cpp:132
size_t _lowerBoundHint
A hint that starting simplification through a lower bound at the variable indicated by _lowerBoundHin...
Definition Slice.h:301
virtual Slice & operator=(const Slice &slice)=0
Performs a deep copy of slice into this object.
Definition Slice.cpp:77
bool adjustMultiply()
Ensure that for each var, var appears to the first power in some generator of getIdeal().
Definition Slice.cpp:162
void setToProjOf(const Slice &slice, const Projection &projection)
Set this object to be the projection of slice according to projection.
Definition Slice.cpp:218
Term _multiply
The of a slice .
Definition Slice.h:272
void swap(Slice &slice)
Simultaneously set the value of this object to that of slice and vice versa.
Definition Slice.cpp:252
Slice(SliceStrategy &strategy)
Construct the slice in a ring of zero variables.
Definition Slice.cpp:26
Term & getMultiply()
Returns for a slice .
Definition Slice.h:113
bool pruneSubtract()
Removes those generators of subtract that do not strictly divide the lcm of getIdeal(),...
Definition Slice.cpp:281
virtual void run(TaskEngine &tasks)
Does whatever work this task represents.
Definition Slice.cpp:321
Term _lcm
The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind.
Definition Slice.h:285
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition Slice.cpp:99
bool applyLowerBound()
Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with ...
Definition Slice.cpp:289
virtual bool getLowerBound(Term &bound, size_t var) const =0
Calculates a lower bound that depends on var.
const Ideal & getIdeal() const
Returns for a slice .
Definition Slice.h:104
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition Slice.cpp:52
bool _lcmUpdated
Indicates whether _lcm is correct.
Definition Slice.h:293
Ideal _subtract
The of a slice .
Definition Slice.h:269
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition Slice.h:96
virtual ~Slice()
Definition Slice.cpp:47
virtual void dispose()
Called when the task is no longer used but run has not and will not be called.
Definition Slice.cpp:325
Ideal & getSubtract()
Returns for a slice .
Definition Slice.h:107
virtual bool simplify()
Simplifies this object such that it may become simpler without changing the content.
Definition Slice.cpp:204
bool operator()(const Exponent *term)
Definition Slice.cpp:153
StrictMultiplePredicate(const Exponent *term, size_t varCount)
Definition Slice.cpp:149
const Exponent * _term
Definition Slice.cpp:158
TaskEngine handles a list of tasks that are to be carried out.
Definition TaskEngine.h:40
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
void reset(size_t newVarCount)
Definition Term.h:551
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition Term.h:532
static size_t getSizeOfSupport(const Exponent *a, size_t varCount)
Returns the number of variables such that divides .
Definition Term.h:402
static void product(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the product of a and b.
Definition Term.h:280
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
Definition Term.h:196
size_t getVarCount() const
Definition Term.h:85
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
Definition Term.cpp:110
static void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
Definition Term.h:476
void swap(Term &term)
Definition Term.h:543
static size_t getFirstNonZeroExponent(const Exponent *a, size_t varCount)
Returns least var such that a[var] is non-zero.
Definition Term.h:346
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition Term.h:316
size_t getFirstNonZeroExponent() const
Definition Term.h:354
This header file includes common definitions and is included as the first line of code in every imple...
unsigned int Exponent
Definition stdinc.h:89
#define ASSERT(X)
Definition stdinc.h:86