Frobby 0.9.5
MsmSlice.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 "MsmSlice.h"
19
20#include "TermConsumer.h"
21#include "MsmStrategy.h"
22
24 Slice(strategy),
25 _consumer(0) {
26}
27
29 const Ideal& ideal,
30 const Ideal& subtract,
31 const Term& multiply,
32 TermConsumer* consumer):
33 Slice(strategy, ideal, subtract, multiply),
34 _consumer(consumer) {
35 ASSERT(consumer != 0);
36
38}
39
40bool MsmSlice::baseCase(bool simplified) {
41 ASSERT(_consumer != 0);
42
43 if (getIdeal().getGeneratorCount() < _varCount)
44 return true;
45
46 // Check that each variable appears in some minimal generator.
47 if (getLcm().getSizeOfSupport() < _varCount)
48 return true;
49
51
52 if (_varCount == 0) {
53 if (getIdeal().isZeroIdeal())
55 return true;
56 }
57
58 if (_varCount == 1) {
60 return true;
61 }
62
63 if (!simplified) {
64 if (getLcm().isSquareFree()) {
65 // We know this since !removeDoubleLcm().
66 ASSERT(getIdeal().isIrreducible());
67
69 return true;
70 }
71
72 if (getIdeal().getGeneratorCount() == _varCount) {
73 if (getSubtract().isZeroIdeal()) {
76 } else {
77 Term tmp(getLcm());
78 tmp.decrement();
79 innerSlice(tmp);
80 if (getIdeal().getGeneratorCount() < _varCount)
81 return true;
82 }
84 return true;
85 }
86
87 return false;
88 }
89
90 if (_varCount == 2) {
92 return true;
93 }
94
95 if (getIdeal().getGeneratorCount() > _varCount) {
96 if (getIdeal().getGeneratorCount() == _varCount + 1) {
98 return true;
99 }
100 if (twoNonMaxBaseCase())
101 return true;
102
103 return false;
104 }
105
106 // These things are ensured since the slice is simplified.
107 ASSERT(getLcm().isSquareFree());
108 ASSERT(getIdeal().isIrreducible());
109
111 return true;
112}
113
115 ASSERT(dynamic_cast<const MsmSlice*>(&slice) != 0);
116
117 Slice::operator=(slice);
118 _consumer = ((MsmSlice&)slice)._consumer;
119 return *this;
120}
121
124
125 if (applyLowerBound())
126 return true;
127
129
131 return false;
132}
133
135 const Projection& projection,
136 TermConsumer* consumer) {
137 ASSERT(consumer != 0);
138
139 Slice::setToProjOf(slice, projection);
140 _consumer = consumer;
141}
142
143bool MsmSlice::innerSlice(const Term& pivot) {
145
146 bool changedMuch = Slice::innerSlice(pivot);
147 if (!_lcmUpdated)
148 changedMuch = removeDoubleLcm() || changedMuch;
149
150 ASSERT(getLcm().getSizeOfSupport() < getVarCount() || !removeDoubleLcm());
151
152 return changedMuch;
153}
154
155void MsmSlice::outerSlice(const Term& pivot) {
157
158 Slice::outerSlice(pivot);
159 if (!_lcmUpdated)
161
163}
164
166 Slice::swap(slice);
167 std::swap(_consumer, slice._consumer);
168}
169
170// Helper class for removeDoubleLcm().
172public:
174 _lcm(lcm) {
175 }
176
177 bool operator()(const Exponent* term) {
178 bool seenMatch = false;
179 for (size_t var = 0; var < _lcm.getVarCount(); ++var) {
180 if (term[var] == _lcm[var]) {
181 if (seenMatch)
182 return true;
183 seenMatch = true;
184 }
185 }
186 return false;
187 }
188
189private:
190 void operator=(const DoubleLcmPredicate&); // To make it inaccessible.
191
192 const Term& _lcm;
193};
194
196 if (_ideal.getGeneratorCount() == 0)
197 return false;
198
199 bool removedAny = false;
200
201 while (true) {
203 if (!_ideal.removeIf(pred))
204 break;
205
206 removedAny = true;
207 _lcmUpdated = false;
208 };
209
210 return removedAny;
211}
212
213bool MsmSlice::getLowerBound(Term& bound, size_t var) const {
214 const Term& lcm = getLcm();
215 bound = lcm;
216
218 for (Ideal::const_iterator it = getIdeal().begin(); it != stop; ++it) {
219 Exponent* term = *it;
220 if (term[var] == 0)
221 continue;
222
223 // Use the fact that terms with a maximal exponent somewhere not
224 // at var cannot be a var-label.
225 for (size_t var2 = 0; var2 < _varCount; ++var2)
226 if (term[var2] == lcm[var2] && var2 != var)
227 goto skip;
228
229 bound.gcd(bound, *it);
230 skip:;
231 }
232
233 ASSERT(_varCount >= 2);
234 if (bound[0] == lcm[0] && bound[1] == lcm[1]) {
235 // No possible var-label, so the content is empty.
236 return false;
237 }
238
239 ASSERT(bound[var] >= 1);
240 bound[var] -= 1;
241 return true;
242}
243
245 ASSERT(_varCount == 2);
246
248
249 // We use _lcm to store the maximal standard monomial in, since we
250 // are not going to be using _lcm later anyway, and this way we
251 // avoid having to do a potentially costly allocation of an array of
252 // size 2 in this method that can be called a lot on small ideals.
253 _lcmUpdated = false;
254
257 if (it == stop)
258 return;
259
260 while (true) {
261 _lcm[1] = (*it)[1] - 1;
262
263 ++it;
264 if (it == stop)
265 break;
266
267 _lcm[0] = (*it)[0] - 1;
268
269 ASSERT(!getIdeal().contains(_lcm));
270
271 if (!_subtract.contains(_lcm)) {
272 _lcm[0] += _multiply[0];
273 _lcm[1] += _multiply[1];
274
276 }
277 }
278}
279
281 ASSERT(_varCount + 1 == getIdeal().getGeneratorCount());
282
283 // Since the slice is fully simplified, we must be dealing with an
284 // artinian power in each variable, and then a single generator
285 // whose support is at least 2. We can then simply run through all
286 // the possibilities for that generator to be a label.
287
289 while (Term::getSizeOfSupport(*it, _varCount) == 1) {
290 ++it;
291 ASSERT(it != getIdeal().end());
292 }
293
294 Term msm(_varCount);
295 for (size_t var = 0; var < _varCount; ++var) {
296 ASSERT((*it)[var] <= 1);
297 ASSERT((*it)[var] < getLcm()[var]);
298 msm[var] = getLcm()[var] - 1;
299 _multiply[var] += msm[var];
300 }
301
302 for (size_t var = 0; var < _varCount; ++var) {
303 if ((*it)[var] == 1) {
304 msm[var] = 0; // try *it as var-label
305 if (!getSubtract().contains(msm)) {
306 _multiply[var] -= getLcm()[var] - 1;
308 _multiply[var] += getLcm()[var] - 1;
309 }
310 msm[var] = getLcm()[var] - 1;
311 }
312 }
313}
314
315// Helper function for the method twoNonMaxBaseCase.
317 const Exponent*& first,
318 const Exponent*& second,
320 const Term& lcm) {
321 size_t count = 0;
322 for (; it != end; ++it) {
323 bool nonMax = true;
324 for (size_t var = 0; var < lcm.getVarCount(); ++var) {
325 if ((*it)[var] == lcm[var]) {
326 nonMax = false;
327 break;
328 }
329 }
330 if (nonMax) {
331 if (count == 0)
332 first = *it;
333 else if (count == 1)
334 second = *it;
335 else
336 return false;
337 ++count;
338 }
339 }
340 return count == 2;
341}
342
344 const Term& lcm = getLcm();
346
347 const Exponent* nonMax1;
348 const Exponent* nonMax2;
349 if (!getTheOnlyTwoNonMax(getIdeal().begin(), nonMax1, nonMax2, stop, lcm))
350 return false;
351
352 Term msm(_lcm);
353 for (size_t var = 0; var < _varCount; ++var)
354 msm[var] -= 1;
355 Term tmp(_varCount);
356
357 for (size_t var1 = 0; var1 < _varCount; ++var1) {
358 if (nonMax1[var1] == 0)
359 continue;
360 if (nonMax1[var1] <= nonMax2[var1])
361 continue;
362
363 for (size_t var2 = 0; var2 < _varCount; ++var2) {
364 if (var1 == var2 || nonMax2[var2] == 0)
365 continue;
366 if (nonMax2[var2] <= nonMax1[var2])
367 continue;
368
369 // Use tmp to record those variables for which labels have been
370 // found. If some variable has no label, then we are not dealing
371 // with an actual maximal standard monomial.
372 tmp.setToIdentity();
373 tmp[var1] = true;
374 tmp[var2] = true;
375 for (Ideal::const_iterator it = getIdeal().begin(); it != stop; ++it) {
376 if ((*it)[var1] >= nonMax1[var1] ||
377 (*it)[var2] >= nonMax2[var2])
378 continue;
379
380 for (size_t var = 0; var < lcm.getVarCount(); ++var) {
381 if ((*it)[var] == lcm[var]) {
382 tmp[var] = true;
383 break;
384 }
385 }
386 }
387
388 if (tmp.getSizeOfSupport() < _varCount)
389 continue;
390
391 msm[var1] = nonMax1[var1] - 1;
392 msm[var2] = nonMax2[var2] - 1;
393 if (!getSubtract().contains(msm)) {
394 tmp.product(msm, _multiply);
395 _consumer->consume(tmp);
396 }
397 msm[var2] = lcm[var2] - 1;
398 msm[var1] = lcm[var1] - 1;
399 }
400 }
401
402 for (size_t var = 0; var < _varCount; ++var) {
403 Exponent e;
404 if (nonMax1[var] < nonMax2[var])
405 e = nonMax1[var];
406 else
407 e = nonMax2[var];
408 if (e == 0)
409 continue;
410
411 msm[var] = e - 1;
412 if (!getSubtract().contains(msm)) {
413 tmp.product(msm, _multiply);
414 _consumer->consume(tmp);
415 }
416 msm[var] = lcm[var] - 1;
417 }
418
419 return true;
420}
bool getTheOnlyTwoNonMax(Ideal::const_iterator it, const Exponent *&first, const Exponent *&second, Ideal::const_iterator end, const Term &lcm)
Definition MsmSlice.cpp:316
void operator=(const DoubleLcmPredicate &)
bool operator()(const Exponent *term)
Definition MsmSlice.cpp:177
const Term & _lcm
Definition MsmSlice.cpp:192
DoubleLcmPredicate(const Term &lcm)
Definition MsmSlice.cpp:173
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
size_t getGeneratorCount() const
Definition Ideal.h:57
bool contains(const Exponent *term) const
Definition Ideal.cpp:57
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
const_iterator begin() const
Definition Ideal.h:48
Cont::const_iterator const_iterator
Definition Ideal.h:43
Invariant: either the slice is a trivial base case, or removeDoubleLcm returns false.
Definition MsmSlice.h:33
virtual bool getLowerBound(Term &bound, size_t var) const
Calculates a lower bound that depends on var.
Definition MsmSlice.cpp:213
MsmSlice(MsmStrategy &strategy)
Definition MsmSlice.cpp:23
TermConsumer * _consumer
Definition MsmSlice.h:98
void twoVarBaseCase()
Definition MsmSlice.cpp:244
virtual bool baseCase(bool simplified)
Returns true if this slice is a base case slice, and in that case produces output in a derivative-spe...
Definition MsmSlice.cpp:40
void setToProjOf(const MsmSlice &slice, const Projection &projection, TermConsumer *consumer)
Definition MsmSlice.cpp:134
virtual Slice & operator=(const Slice &slice)
Performs a deep copy of slice into this object.
Definition MsmSlice.cpp:114
bool removeDoubleLcm()
Definition MsmSlice.cpp:195
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition MsmSlice.cpp:155
void oneMoreGeneratorBaseCase()
Definition MsmSlice.cpp:280
virtual bool simplifyStep()
Like simplify(), except that only one simplification step is performed.
Definition MsmSlice.cpp:122
void swap(MsmSlice &slice)
Definition MsmSlice.cpp:165
bool twoNonMaxBaseCase()
Definition MsmSlice.cpp:343
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition MsmSlice.cpp:143
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 singleDegreeSortIdeal(size_t var)
Calls Ideal::singleDegreeSort on getIdeal().
Definition Slice.cpp:106
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
virtual Slice & operator=(const Slice &slice)=0
Performs a deep copy of slice into this object.
Definition Slice.cpp:77
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
bool pruneSubtract()
Removes those generators of subtract that do not strictly divide the lcm of getIdeal(),...
Definition Slice.cpp:281
Term _lcm
The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind.
Definition Slice.h:285
bool applyLowerBound()
Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with ...
Definition Slice.cpp:289
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
Ideal & getSubtract()
Returns for a slice .
Definition Slice.h:107
This class is used to transfer terms one at a time from one part of the program to another,...
virtual void consume(const Term &term)=0
Consume a term.
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
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
size_t getVarCount() const
Definition Term.h:85
static void gcd(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the greatest common divisor of a and b.
Definition Term.h:255
size_t getSizeOfSupport() const
Definition Term.h:411
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition Term.h:304
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