Frobby 0.9.5
BigattiPivotStrategy.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2009 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
20
21#include "BigattiState.h"
22#include "Ideal.h"
23#include "Term.h"
24#include "NameFactory.h"
25#include "error.h"
26
27BigattiPivotStrategy::BigattiPivotStrategy() {
28}
29
32
33namespace {
34 class MedianPivot : public BigattiPivotStrategy {
35 public:
37 _counts.reset(state.getVarCount());
38 state.getIdeal().getSupportCounts(_counts);
39 size_t var = _counts.getFirstMaxExponent();
40
41 _pivot.reset(state.getVarCount());
42 _pivot[var] = state.getMedianPositiveExponentOf(var);
43 return _pivot;
44 }
45
46 virtual const char* getName() const {
47 return staticGetName();
48 }
49
50 static const char* staticGetName() {
51 return "median";
52 }
53
54 private:
55 Term _counts;
56 Term _pivot;
57 };
58
61 class GenericPivotCommon : public BigattiPivotStrategy {
62 public:
63 virtual const Term& getPivot(BigattiState& state) {
64 _state = &state;
65 _ideal = &(state.getIdeal());
66 driveMe();
67 return _pivot;
68 }
69
70 protected:
75 virtual void driveMe() = 0;
76
77 void considerTypical() {
78 size_t count = _ideal->getTypicalExponent(_var, _exp);
79 if (count <= 1)
80 _exp = 0; // fall back to median.
81 }
82
84 _ideal->getMostNonGenericExponent(_var, _exp);
85 }
86
88 _ideal->getTypicalNonGenericExponent(_var, _exp);
89 }
90
92 _ideal->getNonGenericExponent(_var, _exp);
93 }
94
95 void selectPurePower() {
96 if (_exp == 0)
97 _pivot = getMedian();
98 else {
99 _pivot.reset(_ideal->getVarCount());
100 _pivot[_var] = _exp;
101 }
102 }
103
104 void selectGcd() {
105 if (_exp == 0)
106 _pivot = getMedian();
107 else {
108 _pivot.reset(_ideal->getVarCount());
109 _ideal->getGcdAtExponent(_pivot, _var, _exp);
110 ASSERT(!_pivot.isIdentity());
111 }
112 }
113
114 void selectTight() {
115 if (_exp == 0) {
116 _pivot = getMedian();
117 return;
118 }
119
120 _ideal->singleDegreeSort(_var);
121
122 Ideal::const_iterator blockBegin = _ideal->begin();
123 Ideal::const_iterator stop = _ideal->end();
125
126 // Find the start of the relevant block.
127 while ((*blockBegin)[_var] != _exp) {
128 ++blockBegin;
130 }
131 ASSERT((*blockBegin)[_var] == _exp);
132
134 do {
135 ++blockEnd;
136 } while (blockEnd != stop && (*blockEnd)[_var] == _exp);
137
138 // At this point the range [blockBegin, blockEnd) contains every
139 // generator that raises _var to _exp.
140
141 bool first = true;
142 _pivot.reset(_ideal->getVarCount());
143
144 Term lcm(_ideal->getVarCount()); // For a temporary value
145 for (; blockBegin != blockEnd; ++blockBegin) {
147 for (++it; it != blockEnd; ++it) {
148 lcm.lcm(*blockBegin, *it);
149 if (!_ideal->strictlyContains(lcm)) {
150 // We only need to have the pivot remove one of
151 // *blockBegin and *it. We choose to let it be *blockBegin
152 // that is included in the gcd (and thus removed for sure)
153 // just because that is easier to keep track of.
154 if (first) {
155 first = false;
156 _pivot.gcd(*blockBegin, *it);
157 } else {
158 _pivot.gcd(_pivot, *blockBegin);
159 _pivot.gcd(_pivot, *it);
160 }
161 break;
162 }
163 }
164 }
165
166 if (first)
167 _pivot[_var] = _exp;
168
169 ASSERT(!_pivot.isIdentity());
170 }
171
172 private:
173 Term _pivot;
174 BigattiState* _state;
175 Ideal* _ideal;
176 size_t _var;
177 Exponent _exp;
178
186 const Term& getMedian() {
187 return _median.getPivot(*_state);
188 }
189
191 MedianPivot _median;
192 };
193
194 class MostNGPurePivot : public GenericPivotCommon {
195 public:
196 virtual void driveMe() {
199 }
200
201 virtual const char* getName() const {
202 return staticGetName();
203 }
204
205 static const char* staticGetName() {
206 return "mostNGPure";
207 }
208 };
209
210 class MostNGGcdPivot : public GenericPivotCommon {
211 public:
212 virtual void driveMe() {
214 selectGcd();
215 }
216
217 virtual const char* getName() const {
218 return staticGetName();
219 }
220
221 static const char* staticGetName() {
222 return "mostNGGcd";
223 }
224 };
225
226 class MostNGTightPivot : public GenericPivotCommon {
227 public:
228 virtual void driveMe() {
230 selectTight();
231 }
232
233 virtual const char* getName() const {
234 return staticGetName();
235 }
236
237 static const char* staticGetName() {
238 return "mostNGTight";
239 }
240 };
241
242 class TypicalNGPurePivot : public GenericPivotCommon {
243 public:
244 virtual void driveMe() {
247 }
248
249 virtual const char* getName() const {
250 return staticGetName();
251 }
252
253 static const char* staticGetName() {
254 return "typicalNGPure";
255 }
256 };
257
258 class TypicalNGGcdPivot : public GenericPivotCommon {
259 public:
260 virtual void driveMe() {
262 selectGcd();
263 }
264
265 virtual const char* getName() const {
266 return staticGetName();
267 }
268
269 static const char* staticGetName() {
270 return "typicalNGGcd";
271 }
272 };
273
274 class TypicalNGTightPivot : public GenericPivotCommon {
275 public:
276 virtual void driveMe() {
278 selectTight();
279 }
280
281 virtual const char* getName() const {
282 return staticGetName();
283 }
284
285 static const char* staticGetName() {
286 return "typicalNGTight";
287 }
288 };
289
290 class TypicalPurePivot : public GenericPivotCommon {
291 public:
292 virtual void driveMe() {
295 }
296
297 virtual const char* getName() const {
298 return staticGetName();
299 }
300
301 static const char* staticGetName() {
302 return "typicalPure";
303 }
304 };
305
306 class TypicalGcdPivot : public GenericPivotCommon {
307 public:
308 virtual void driveMe() {
310 selectGcd();
311 }
312
313 virtual const char* getName() const {
314 return staticGetName();
315 }
316
317 static const char* staticGetName() {
318 return "typicalGcd";
319 }
320 };
321
322 class TypicalTightPivot : public GenericPivotCommon {
323 public:
324 virtual void driveMe() {
326 selectTight();
327 }
328
329 virtual const char* getName() const {
330 return staticGetName();
331 }
332
333 static const char* staticGetName() {
334 return "typicalTight";
335 }
336 };
337
338 class SomeNGPurePivot : public GenericPivotCommon {
339 public:
340 virtual void driveMe() {
343 }
344
345 virtual const char* getName() const {
346 return staticGetName();
347 }
348
349 static const char* staticGetName() {
350 return "someNGPure";
351 }
352 };
353
354 class SomeNGGcdPivot : public GenericPivotCommon {
355 public:
356 virtual void driveMe() {
358 selectGcd();
359 }
360
361 virtual const char* getName() const {
362 return staticGetName();
363 }
364
365 static const char* staticGetName() {
366 return "someNGGcd";
367 }
368 };
369
370 class SomeNGTightPivot : public GenericPivotCommon {
371 public:
372 virtual void driveMe() {
374 selectTight();
375 }
376
377 virtual const char* getName() const {
378 return staticGetName();
379 }
380
381 static const char* staticGetName() {
382 return "someNGTight";
383 }
384 };
385
388 class WidenPivot : public BigattiPivotStrategy {
389 public:
391 _strategy(strategy) {
392 _name = _strategy->getName();
393 _name += " (wide)";
394 }
395
397 const Term& pivot = _strategy->getPivot(state);
398 _widePivot.reset(state.getVarCount());
399 state.getIdeal().getGcdOfMultiplesOf(_widePivot, pivot);
400 return _widePivot;
401 }
402
403 virtual const char* getName() const {
404 return _name.c_str();
405 }
406
407 private:
409 string _name;
410 Term _widePivot;
411 };
412
414
416 StrategyFactory factory("Bigatti et.al. pivot strategy");
417
419
424
429
434
435 return factory;
436 }
437}
438
439auto_ptr<BigattiPivotStrategy> BigattiPivotStrategy::
440createStrategy(const string& prefix, bool widen) {
443 ASSERT(strategy.get() != 0);
444
445 if (widen)
447
448 return strategy;
449}
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...
A BigattiPivotStrategy is an implementation of a pivot selection strategy for the Hilbert series algo...
virtual const char * getName() const =0
Returns the name of the strategy.
virtual const Term & getPivot(BigattiState &state)=0
Returns the pivot of a pivot split of state.
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Cont::const_iterator const_iterator
Definition Ideal.h:43
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition NameFactory.h:33
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
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
unsigned int Exponent
Definition stdinc.h:89
#define ASSERT(X)
Definition stdinc.h:86