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 
40 bool 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.
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()) {
74  _lcm.decrement();
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 
128  pruneSubtract();
129 
131  return false;
132 }
133 
134 void MsmSlice::setToProjOf(const MsmSlice& slice,
135  const Projection& projection,
136  TermConsumer* consumer) {
137  ASSERT(consumer != 0);
138 
139  Slice::setToProjOf(slice, projection);
140  _consumer = consumer;
141 }
142 
143 bool MsmSlice::innerSlice(const Term& pivot) {
145 
146  bool changedMuch = Slice::innerSlice(pivot);
147  if (!_lcmUpdated)
148  changedMuch = removeDoubleLcm() || changedMuch;
149 
151 
152  return changedMuch;
153 }
154 
155 void MsmSlice::outerSlice(const Term& pivot) {
157 
158  Slice::outerSlice(pivot);
159  if (!_lcmUpdated)
160  removeDoubleLcm();
161 
163 }
164 
165 void MsmSlice::swap(MsmSlice& slice) {
166  Slice::swap(slice);
167  std::swap(_consumer, slice._consumer);
168 }
169 
170 // Helper class for removeDoubleLcm().
172 public:
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 
189 private:
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) {
202  DoubleLcmPredicate pred(getLcm());
203  if (!_ideal.removeIf(pred))
204  break;
205 
206  removedAny = true;
207  _lcmUpdated = false;
208  };
209 
210  return removedAny;
211 }
212 
213 bool 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
Cont::const_iterator const_iterator
Definition: Ideal.h:43
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
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
const Ideal & getIdeal() const
Returns for a slice .
Definition: Slice.h:104
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
Ideal & getSubtract()
Returns for a slice .
Definition: Slice.h:107
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 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
This class is used to transfer terms one at a time from one part of the program to another,...
Definition: TermConsumer.h:36
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
size_t getSizeOfSupport(const Word *a, size_t varCount)
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
unsigned int Exponent
Definition: stdinc.h:89
#define ASSERT(X)
Definition: stdinc.h:86