Frobby 0.9.5
SplitStrategy.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 "SplitStrategy.h"
19
20#include "Slice.h"
21#include "Term.h"
22#include "Ideal.h"
23#include "NameFactory.h"
24#include "TermGrader.h"
25#include "error.h"
26#include "display.h"
27
30
33
38public:
39 virtual void getPivot(Term& pivot, Slice& slice) const {
40 ASSERT(false);
41 reportInternalError("Requested pivot split of non-pivot split strategy.\n");
42 }
43
44 virtual void getPivot(Term& pivot, Slice& slice, const TermGrader& grader) const {
46 }
47
48 virtual size_t getLabelSplitVariable(const Slice& slice) const {
49 ASSERT(false);
50 reportInternalError("Requested label split of non-label split strategy.");
51 return 0; // To avoid spurious warnings from static analyses.
52 }
53
54 virtual bool isPivotSplit() const {
55 return false;
56 }
57
58 virtual bool isLabelSplit() const {
59 return false;
60 }
61
62protected:
64 slice.singleDegreeSortIdeal(var);
65 Ideal::const_iterator end = slice.getIdeal().end();
66 Ideal::const_iterator begin = slice.getIdeal().begin();
67 while ((*begin)[var] == 0) {
68 ++begin;
69 ASSERT(begin != end);
70 }
71 return (*(begin + (distance(begin, end) ) / 2))[var];
72 }
73
74 // Returns the variable that divides the most minimal generators of
75 // those where some minimal generator is divisible by the square of
76 // that variable.
78 size_t getBestVar(const Slice& slice) const {
80 co.reset(slice.getVarCount());
81 slice.getIdeal().getSupportCounts(co);
82
83 const Term& lcm = slice.getLcm();
84 for (size_t var = 0; var < slice.getVarCount(); ++var)
85 if (lcm[var] <= 1)
86 co[var] = 0;
87
88 ASSERT(!co.isIdentity());
89
90 Exponent maxCount = co[co.getFirstMaxExponent()];
91 for (size_t var = 0; var < slice.getVarCount(); ++var)
92 if (co[var] < maxCount)
93 co[var] = 0;
94
95 // Choose the middle variable among those that are best. This
96 // is better at avoiding a bad pattern than just choosing the
97 // first one.
98 return co.getMiddleNonZeroExponent();
99 }
100};
101
103protected:
104 mutable Term _counts;
105 void setCounts(const Slice& slice) const {
106 _counts.reset(slice.getVarCount());
107 slice.getIdeal().getSupportCounts(_counts);
108 }
109
111 void setOneCounts(const Slice& slice) const {
112 ASSERT(!const_cast<Slice&>(slice).adjustMultiply());
113 ASSERT(!const_cast<Slice&>(slice).baseCase(false));
114 // For each variable, count number of terms with exponent equal to 1,
115 // not counting pure powers.
116 _oneCounts.reset(slice.getVarCount());
117
118 Ideal::const_iterator end = slice.getIdeal().end();
119 for (Ideal::const_iterator it = slice.getIdeal().begin();
120 it != end; ++it) {
121 if (Term::getSizeOfSupport(*it, slice.getVarCount()) == 1)
122 continue; // Not counting pure powers.
123 for (size_t var = 0; var < slice.getVarCount(); ++var)
124 if ((*it)[var] == 1)
125 _oneCounts[var] += 1;
126 }
127 }
128
129 virtual bool isLabelSplit() const {
130 return true;
131 }
132};
133
134// Use the variable that divides the most minimal generators.
135class MaxLabelSplit : public LabelSplit {
136public:
137 virtual const char* getName() const {
138 return staticGetName();
139 }
140
141 static const char* staticGetName() {
142 return "maxlabel";
143 }
144
145 virtual size_t getLabelSplitVariable(const Slice& slice) const {
148 }
149};
150
151// Use the first variable that is valid for a label split.
152class VarLabelSplit : public LabelSplit {
153public:
154 virtual const char* getName() const {
155 return staticGetName();
156 }
157
158 static const char* staticGetName() {
159 return "varlabel";
160 }
161
162 virtual size_t getLabelSplitVariable(const Slice& slice) const {
164 for (size_t var = 0; ; ++var) {
165 ASSERT(var < slice.getVarCount());
166 if (_oneCounts[var] > 0)
167 return var;
168 }
169 }
170};
171
172// Among those variables with least number of exponents equal to one,
173// use the variable that divides the most minimal generators.
174class MinLabelSplit : public LabelSplit {
175public:
176 virtual const char* getName() const {
177 return staticGetName();
178 }
179
180 static const char* staticGetName() {
181 return "minlabel";
182 }
183
184 virtual size_t getLabelSplitVariable(const Slice& slice) const {
187
188 // Zero those variables of _counts that have more than the least number
189 // of exponent 1 minimal generators.
190 size_t mostGeneric = 0;
191 for (size_t var = 1; var < slice.getVarCount(); ++var)
192 if (mostGeneric == 0 ||
193 (mostGeneric > _oneCounts[var] && _oneCounts[var] > 0))
194 mostGeneric = _oneCounts[var];
195 for (size_t var = 0; var < slice.getVarCount(); ++var)
196 if (_oneCounts[var] != mostGeneric)
197 _counts[var] = 0;
198
200 }
201};
202
204public:
205 virtual bool isPivotSplit() const {
206 return true;
207 }
208};
209
210class MinimumSplit : public PivotSplit {
211public:
212 virtual const char* getName() const {
213 return staticGetName();
214 }
215
216 static const char* staticGetName() {
217 return "minimum";
218 }
219
220 virtual void getPivot(Term& pivot, Slice& slice) const {
221 size_t var = getBestVar(slice);
222 pivot.setToIdentity();
223 pivot[var] = 1;
224 }
225};
226
227class MedianSplit : public PivotSplit {
228public:
229 virtual const char* getName() const {
230 return staticGetName();
231 }
232
233 static const char* staticGetName() {
234 return "median";
235 }
236
237 virtual void getPivot(Term& pivot, Slice& slice) const {
238 size_t var = getBestVar(slice);
239
240 pivot.setToIdentity();
242 if (pivot[var] == slice.getLcm()[var])
243 pivot[var] -= 1;
244 }
245};
246
247class MaximumSplit : public PivotSplit {
248public:
249 virtual const char* getName() const {
250 return staticGetName();
251 }
252
253 static const char* staticGetName() {
254 return "maximum";
255 }
256
257 virtual void getPivot(Term& pivot, Slice& slice) const {
258 size_t var = getBestVar(slice);
259 pivot.setToIdentity();
260 pivot[var] = slice.getLcm()[var] - 1;
261 }
262};
263
265public:
266 virtual const char* getName() const {
267 return staticGetName();
268 }
269
270 static const char* staticGetName() {
271 return "indep";
272 }
273
274 virtual void getPivot(Term& pivot, Slice& slice) const {
275 if (slice.getVarCount() == 1) {
277 return;
278 }
279
280 for (int attempts = 0; attempts < 10; ++attempts) {
281 // Pick two distinct variables.
282 size_t var1 = rand() % slice.getVarCount();
283 size_t var2 = rand() % (slice.getVarCount() - 1);
284 if (var2 >= var1)
285 ++var2;
286
287 // Make pivot as big as it can be while making var1 and var2
288 // independent of each other.
289 bool first = true;
290 Ideal::const_iterator end = slice.getIdeal().end();
291 for (Ideal::const_iterator it = slice.getIdeal().begin();
292 it != end; ++it) {
293 if ((*it)[var1] == 0 || (*it)[var2] == 0)
294 continue;
295
296 if (first)
297 pivot = *it;
298 else {
299 for (size_t var = 0; var < slice.getVarCount(); ++var)
300 if (pivot[var] >= (*it)[var])
301 pivot[var] = (*it)[var] - 1;
302 }
303 }
304
305 if (!first && !pivot.isIdentity())
306 return;
307 }
308
310 }
311};
312
313class GcdSplit : public PivotSplit {
314public:
315 virtual const char* getName() const {
316 return staticGetName();
317 }
318
319 static const char* staticGetName() {
320 return "gcd";
321 }
322
323 virtual void getPivot(Term& pivot, Slice& slice) const {
324 size_t var = getBestVar(slice);
325
326 size_t nonDivisibleCount = 0;
327 Ideal::const_iterator end = slice.getIdeal().end();
328 for (Ideal::const_iterator it = slice.getIdeal().begin();
329 it != end; ++it)
330 if ((*it)[var] >= 2)
332
333 for (int i = 0; i < 3; ++i) {
334 size_t selected = rand() % nonDivisibleCount;
335 for (Ideal::const_iterator it = slice.getIdeal().begin(); ; ++it) {
336 ASSERT(it != end);
337 if ((*it)[var] < 2)
338 continue;
339
340 if (selected == 0) {
341 if (i == 0)
342 pivot = *it;
343 else
344 pivot.gcd(pivot, *it);
345 break;
346 }
347 --selected;
348 }
349 }
350
351 pivot.decrement();
352 }
353};
354
355class MinGenSplit : public PivotSplit {
356public:
357 virtual const char* getName() const {
358 return staticGetName();
359 }
360
361 static const char* staticGetName() {
362 return "mingen";
363 }
364
365 virtual void getPivot(Term& pivot, Slice& slice) const {
366 size_t nonSquareFreeCount = 0;
367 Ideal::const_iterator end = slice.getIdeal().end();
368 for (Ideal::const_iterator it = slice.getIdeal().begin();
369 it != end; ++it)
370 if (!Term::isSquareFree(*it, slice.getVarCount()))
372
373 size_t selected = rand() % nonSquareFreeCount;
374 for (Ideal::const_iterator it = slice.getIdeal().begin(); ; ++it) {
375 ASSERT(it != end);
376 if (Term::isSquareFree(*it, slice.getVarCount()))
377 continue;
378
379 if (selected == 0) {
380 pivot = *it;
381 break;
382 }
383 --selected;
384 }
385
386 pivot.decrement();
387 }
388};
389
390class DegreeSplit : public PivotSplit {
391public:
392 virtual const char* getName() const {
393 return staticGetName();
394 }
395
396 static const char* staticGetName() {
397 return "degree";
398 }
399
400 virtual void getPivot(Term& pivot, Slice& slice) const {
401 reportInternalError("Called getPivot directly on FrobeniusSplit.");
402 }
403
404 virtual void getPivot(Term& pivot, Slice& slice, const TermGrader& grader) const {
405 const Term& lcm = slice.getLcm();
406
407 // TODO: pick a middle variable in case of ties.
408
409 _maxDiff = -1;
410 size_t maxOffset = 0u;
411 for (size_t var = 0; var < slice.getVarCount(); ++var) {
412 if (lcm[var] <= 1)
413 continue;
414
415 Exponent base = slice.getMultiply()[var];
416 Exponent mid = base + lcm[var] / 2;
417
418 // We could be looking at an added pure power whose exponent is
419 // defined to have degree 0. We don't want to look at that.
420 if (mid == grader.getMaxExponent(var) && mid > base)
421 --mid;
422
423 _diff = grader.getGrade(var, mid) - grader.getGrade(var, base);
424
425 if (grader.getGradeSign(var) < 0)
426 _diff = -_diff;
427
428 ASSERT(_diff >= 0 || base == mid);
429
430 if (_diff > _maxDiff) {
431 maxOffset = var;
432 _maxDiff = _diff;
433 }
434 }
435
436 pivot.setToIdentity();
437 pivot[maxOffset] = lcm[maxOffset] / 2;
438 }
439
440private:
446
452};
453
458public:
461 ("The split selection strategy \"frob\" is deprecated and will be "
462 "removed in a future version of Frobby. Use the name \"degree\" "
463 "to achieve the same thing.");
464 }
465
466 virtual const char* getName() const {
467 return staticGetName();
468 }
469
470 static const char* staticGetName() {
471 return "frob";
472 }
473};
474
475namespace {
477
479 SplitFactory factory("Slice split strategy");
480
492
493 return factory;
494 }
495}
496
auto_ptr< AbstractProduct > createWithPrefix(const NameFactory< AbstractProduct > &factory, const string &prefix)
Creates the unique product that has the indicated prefix, or create the actual product that has name ...
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
mpz_class _maxDiff
This is member variable used by getPivot.
virtual const char * getName() const
Returns the name of the strategy.
mpz_class _diff
This is member variable used by getPivot.
static const char * staticGetName()
virtual void getPivot(Term &pivot, Slice &slice, const TermGrader &grader) const
Sets pivot to the pivot of a pivot split on slice.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
This class is deprecated and is only here to create the alias "frob" for the degree split.
virtual const char * getName() const
Returns the name of the strategy.
static const char * staticGetName()
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
Cont::const_iterator const_iterator
Definition Ideal.h:43
virtual const char * getName() const
Returns the name of the strategy.
static const char * staticGetName()
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
virtual bool isLabelSplit() const
If returns true, only call getLabelSplitVariable.
void setCounts(const Slice &slice) const
void setOneCounts(const Slice &slice) const
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
static const char * staticGetName()
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
virtual const char * getName() const
Returns the name of the strategy.
static const char * staticGetName()
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition NameFactory.h:33
virtual bool isPivotSplit() const
If returns true, only call getPivot.
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
This common base class provides code that is useful for writing pivot split strategies.
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
virtual bool isLabelSplit() const
If returns true, only call getLabelSplitVariable.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
size_t getBestVar(const Slice &slice) const
Exponent getMedianPositiveExponentOf(Slice &slice, size_t var) const
virtual bool isPivotSplit() const
If returns true, only call getPivot.
virtual void getPivot(Term &pivot, Slice &slice, const TermGrader &grader) const
Sets pivot to the pivot of a pivot split on slice.
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
virtual ~SplitStrategy()
static auto_ptr< SplitStrategy > createStrategy(const string &prefix)
Returns the strategy whose name has the given prefix.
A TermGrader assigns a value, the degree, to each monomial.
Definition TermGrader.h:27
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
bool isSquareFree() const
Definition Term.h:339
size_t getSizeOfSupport() const
Definition Term.h:411
static size_t getFirstMaxExponent(const Exponent *a, size_t varCount)
Returns a var such that a[var] >= a[i] for all i.
Definition Term.h:381
virtual const char * getName() const
Returns the name of the strategy.
static const char * staticGetName()
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
void displayNote(const string &msg)
Display msg to standard error in a way that indicates that this is something that the user should tak...
Definition display.cpp:135
This file contains functions for printing strings to standard error.
void reportInternalError(const string &errorMsg)
Definition error.cpp:29
unsigned int Exponent
Definition stdinc.h:89
#define ASSERT(X)
Definition stdinc.h:86