Frobby 0.9.5
PivotStrategy.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2011 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 "PivotStrategy.h"
19
20#include "EulerState.h"
21#include "NameFactory.h"
22#include "RawSquareFreeTerm.h"
23#include "ElementDeleter.h"
24#include "PivotEulerAlg.h"
25
26#include <sstream>
27#include <limits>
28
29namespace Ops = SquareFreeTermOps;
30
31namespace {
32 inline size_t getPopVar(const size_t* divCounts, const size_t varCount) {
33 return max_element(divCounts, divCounts + varCount) - divCounts;
34 }
35
36 inline size_t getRareVar(const size_t* divCounts, const size_t varCount) {
37 const size_t* end = divCounts + varCount;
38 const size_t* rare = divCounts;
39 while (*rare == 0) {
40 ++rare;
41 ASSERT(rare != end); // not all zero
42 }
43
44 const size_t* it = rare + 1;
45 for (; it != end; ++it)
46 if (*it > 0 && *it < *rare)
47 rare = it;
48
49 return rare - divCounts;
50 }
51
52 inline void makeRareVarsMask
53 (Word* mask, const size_t* divCounts, const size_t varCount) {
54 const size_t rareVar = getRareVar(divCounts, varCount);
55 ASSERT(rareVar < varCount); // not all zero
56 const size_t maxCount = divCounts[rareVar];
57 Ops::setToIdentity(mask, varCount);
58 for (size_t var = 0; var < varCount; ++var)
59 if (divCounts[var] == maxCount)
60 Ops::setExponent(mask, var, true);
61 }
62
63 class RawSquareFreeTerm {
64 public:
65 RawSquareFreeTerm(): _term(0), _capacity(0) {}
66 ~RawSquareFreeTerm() {delete _term;}
67
68 operator Word*() {return _term;}
69 operator const Word*() const {return _term;}
70
71 void reserve(const size_t varCount) {
72 if (varCount > _capacity) {
73 Ops::deleteTerm(_term);
74 _term = Ops::newTerm(varCount);
75 _capacity = varCount;
76 }
77 }
78
79 private:
80 Word* _term;
81 size_t _capacity;
82 };
83
84 class WithPivotTerm : public PivotStrategy {
85 protected:
86 Word* termWithCapacity(const size_t varCount) {
87 _term.reserve(varCount);
88 return _term;
89 }
90
91 private:
92 RawSquareFreeTerm _term;
93 };
94
95 class StdStrategy : public WithPivotTerm {
96 public:
97 virtual Word* getPivot(const EulerState& state,
98 const size_t* divCounts) = 0;
99 virtual void computationCompleted(const PivotEulerAlg& alg) {}
100 virtual bool shouldTranspose(const EulerState& state) const {
101 return state.getVarCount() > state.getIdeal().getGeneratorCount();
102 }
103 };
104
105 class StdPopVar : public StdStrategy {
106 public:
107 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
108 const size_t varCount = state.getVarCount();
109 return state.inPlaceStdSplit(getPopVar(divCounts, varCount));
110 }
111
112 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
113 const size_t varCount = state.getVarCount();
114 Word* pivot = termWithCapacity(varCount);
115 Ops::setToIdentity(pivot, varCount);
116 Ops::setExponent(pivot, getPopVar(divCounts, varCount), 1);
117 return pivot;
118 }
119
120 static const char* staticGetName() {
121 return "popvar";
122 }
123
124 virtual void getName(ostream& out) const {
125 out << staticGetName();
126 }
127 };
128
129 class StdRareVar : public StdStrategy {
130 public:
131 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
132 const size_t varCount = state.getVarCount();
133 return state.inPlaceStdSplit(getRareVar(divCounts, varCount));
134 }
135
136 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
137 const size_t varCount = state.getVarCount();
138 Word* pivot = termWithCapacity(varCount);
139 Ops::setToIdentity(pivot, varCount);
140 Ops::setExponent(pivot, getRareVar(divCounts, varCount), 1);
141 return pivot;
142 }
143
144 static const char* staticGetName() {
145 return "rarevar";
146 }
147
148 virtual void getName(ostream& out) const {
149 out << staticGetName();
150 }
151 };
152
153 class StdPopGcd : public StdStrategy {
154 public:
155 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
156 return state.inPlaceStdSplit(getPivot(state, divCounts));
157 }
158
159 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
160 const size_t varCount = state.getVarCount();
161 const size_t popVar = getPopVar(divCounts, varCount);
162 Word* pivot = termWithCapacity(varCount);
163
164 if (divCounts[popVar] == 1) {
165 Ops::setToIdentity(pivot, varCount);
166 Ops::setExponent(pivot, getPopVar(divCounts, varCount), 1);
167 return pivot;
168 }
169
170 size_t seen = 0;
173 for (; it != end; ++it) {
174 if (Ops::getExponent(*it, popVar) != 0) {
175 if (seen == 0)
176 Ops::assign(pivot, *it, varCount);
177 else
178 Ops::gcdInPlace(pivot, *it, varCount);
179 ++seen;
180 if (seen == 3)
181 break;
182 }
183 }
184 ASSERT(seen > 1);
185 return pivot;
186 }
187
188 static const char* staticGetName() {
189 return "popgcd";
190 }
191
192 virtual void getName(ostream& out) const {
193 out << staticGetName();
194 }
195 };
196
197 class StdRandom : public StdStrategy {
198 public:
199 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
200 const size_t random = getRandomNotEliminatedVar(state);
201 return state.inPlaceStdSplit(random);
202 }
203
204 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
205 const size_t varCount = state.getVarCount();
206 const size_t random = getRandomNotEliminatedVar(state);
207 Word* pivot = termWithCapacity(varCount);
208 Ops::setToIdentity(pivot, varCount);
209 Ops::setExponent(pivot, random, 1);
210 return pivot;
211 }
212
213 static const char* staticGetName() {
214 return "random";
215 }
216
217 virtual void getName(ostream& out) const {
218 out << staticGetName();
219 }
220
221 private:
222 size_t getRandomNotEliminatedVar(const EulerState& state) {
223 while (true) {
224 size_t random = rand() % state.getVarCount();
225 if (Ops::getExponent(state.getEliminatedVars(), random) == 0)
226 return random;
227 }
228 }
229 };
230
231 class StdAny : public StdStrategy {
232 public:
233 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
234 const size_t any = getAnyNotEliminatedVar(state);
235 return state.inPlaceStdSplit(any);
236 }
237
238 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
239 const size_t varCount = state.getVarCount();
240 const size_t any = getAnyNotEliminatedVar(state);
241 Word* pivot = termWithCapacity(varCount);
242 Ops::setToIdentity(pivot, varCount);
243 Ops::setExponent(pivot, any, 1);
244 return pivot;
245 }
246
247 static const char* staticGetName() {
248 return "any";
249 }
250
251 virtual void getName(ostream& out) const {
252 out << staticGetName();
253 }
254
255 private:
256 size_t getAnyNotEliminatedVar(const EulerState& state) {
257 for (size_t var = 0; ; ++var) {
258 ASSERT(var < state.getVarCount());
259 if (Ops::getExponent(state.getEliminatedVars(), var) == 0)
260 return var;
261 }
262 }
263 };
264
265 class StdWiden : public WithPivotTerm {
266 public:
267 StdWiden(auto_ptr<StdStrategy> strat):
268 _strat(strat) {
269 ASSERT(_strat.get() != 0);
270 }
271
272 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
273 const size_t varCount = state.getVarCount();
274 Word* narrow = _strat->getPivot(state, divCounts);
275 Word* wide = termWithCapacity(varCount);
276 state.getIdeal().getGcdOfMultiples(wide, narrow);
277 return state.inPlaceStdSplit(wide);
278 }
279
280 virtual void getName(ostream& out) const {
281 out << "widen_";
282 _strat->getName(out);
283 }
284
285 virtual void computationCompleted(const PivotEulerAlg& alg) {
286 _strat->computationCompleted(alg);
287 }
288
289 virtual bool shouldTranspose(const EulerState& state) const {
290 return _strat->shouldTranspose(state);
291 }
292
293 private:
294 auto_ptr<StdStrategy> _strat;
295 };
296
297 class GenStrategy : public WithPivotTerm {
298 public:
299 typedef RawSquareFreeIdeal::iterator iterator;
300
301 virtual iterator filter(iterator begin, iterator end,
302 const size_t* divCounts,
303 const size_t varCount) = 0;
304 virtual void computationCompleted(const PivotEulerAlg& alg) {}
305 virtual bool shouldTranspose(const EulerState& state) const {
306 return state.getVarCount() < state.getIdeal().getGeneratorCount();
307 }
308 };
309
310 class GenPopVar : public GenStrategy {
311 public:
312 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
313 const size_t varCount = state.getVarCount();
314 size_t pivotIndex =
315 state.getIdeal().getMultiple(getPopVar(divCounts, varCount));
316 return state.inPlaceGenSplit(pivotIndex);
317 }
318
319 virtual iterator filter(iterator begin, iterator end,
320 const size_t* divCounts,
321 const size_t varCount) {
322 size_t popVar = getPopVar(divCounts, varCount);
323 Word* term = termWithCapacity(varCount);
324 Ops::setToIdentity(term, varCount);
325 for (size_t var = 0; var < varCount; ++var)
326 if (divCounts[var] == divCounts[popVar])
327 Ops::setExponent(term, var, 1);
328
329 iterator newEnd = begin;
330 for (iterator it = begin; it != end; ++it) {
331 if (Ops::isRelativelyPrime(term, *it, varCount))
332 continue;
333 Ops::swap(*it, *newEnd, varCount);
334 ++newEnd;
335 }
336 return newEnd;
337 }
338
339 static const char* staticGetName() {
340 return "popvar";
341 }
342
343 virtual void getName(ostream& out) const {
344 out << staticGetName();
345 }
346 };
347
348 class GenRareMax : public GenStrategy {
349 public:
350 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
351 typedef RawSquareFreeIdeal::const_iterator const_iterator;
352 const RawSquareFreeIdeal& ideal = state.getIdeal();
353 const size_t varCount = state.getVarCount();
354 const size_t rareVar = getRareVar(divCounts, varCount);
355
356 const const_iterator end = ideal.end();
357 size_t bestSupport = 0;
358 const_iterator best = end;
359 for (const_iterator it = ideal.begin(); it != end; ++it) {
360 if (!Ops::getExponent(*it, rareVar))
361 continue;
362 const size_t support = Ops::getSizeOfSupport(*it, varCount);
363 if (bestSupport < support) {
364 bestSupport = support;
365 best = it;
366 }
367 }
368 ASSERT(best != end);
369 return state.inPlaceGenSplit(best - ideal.begin());
370 }
371
372 virtual iterator filter(iterator begin, iterator end,
373 const size_t* divCounts,
374 const size_t varCount) {
375 const size_t rareVar = getRareVar(divCounts, varCount);
376
377 size_t bestSupport = 0;
378 iterator newEnd = begin;
379 for (iterator it = begin; it != end; ++it) {
380 if (!Ops::getExponent(*it, rareVar))
381 continue;
382 const size_t support = Ops::getSizeOfSupport(*it, varCount);
383 if (bestSupport > support)
384 continue;
385 if (bestSupport < support) {
386 newEnd = begin;
387 bestSupport = support;
388 }
389 Ops::swap(*it, *newEnd, varCount);
390 ++newEnd;
391 }
392 return newEnd;
393 }
394
395 static const char* staticGetName() {
396 return "raremax";
397 }
398
399 virtual void getName(ostream& out) const {
400 out << staticGetName();
401 }
402 };
403
404 class GenRareVar : public GenStrategy {
405 public:
406 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
407 const size_t varCount = state.getVarCount();
408 size_t pivotIndex =
409 state.getIdeal().getMultiple(getRareVar(divCounts, varCount));
410 return state.inPlaceGenSplit(pivotIndex);
411 }
412
413 virtual iterator filter(iterator begin, iterator end,
414 const size_t* divCounts,
415 const size_t varCount) {
416 size_t rareVar = getRareVar(divCounts, varCount);
417
418 iterator newEnd = begin;
419 for (iterator it = begin; it != end; ++it) {
420 if (Ops::getExponent(*it, rareVar) == 0)
421 continue;
422 Ops::swap(*it, *newEnd, varCount);
423 ++newEnd;
424 }
425 return newEnd;
426 }
427
428 static const char* staticGetName() {
429 return "rarevar";
430 }
431
432 virtual void getName(ostream& out) const {
433 out << staticGetName();
434 }
435 };
436
437 class GenComposite : public PivotStrategy {
438 public:
439 GenComposite():
440 _filters(0),
441 _filtersDeleter(_filters) {
442 }
443
444 typedef RawSquareFreeIdeal::iterator iterator;
445
446 void addStrategy(auto_ptr<GenStrategy> strat) {
447 exceptionSafePushBack(_filters, strat);
448 }
449
450 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
451 const size_t varCount = state.getVarCount();
452 const iterator begin = state.getIdeal().begin();
453 iterator end = state.getIdeal().end();
454 ASSERT(end - begin > 0);
455
456 for (size_t i = 0; i < _filters.size(); ++i)
457 end = _filters[i]->filter(begin, end, divCounts, varCount);
458 ASSERT(end - begin > 0);
459
460 return state.inPlaceGenSplit(0);
461 }
462
463 virtual void getName(ostream& out) const {
464 for (size_t i = 0; i < _filters.size(); ++i) {
465 if (i > 0)
466 out << '_';
467 _filters[i]->getName(out);
468 }
469 }
470
471 virtual void computationCompleted(const PivotEulerAlg& alg) {
472 for (size_t i = 0; i < _filters.size(); ++i)
473 _filters[i]->computationCompleted(alg);
474 }
475
476 virtual bool shouldTranspose(const EulerState& state) const {
477 return _filters.front()->shouldTranspose(state);
478 }
479
480 private:
481 vector<GenStrategy*> _filters;
482 ElementDeleter<vector<GenStrategy*> > _filtersDeleter;
483 };
484
485 class GenRarestVars : public GenStrategy {
486 public:
487 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
488 const size_t varCount = state.getVarCount();
489 filter(state.getIdeal().begin(), state.getIdeal().end(),
490 divCounts, varCount);
491 return state.inPlaceGenSplit(0);
492 }
493
494 virtual iterator filter(iterator begin, iterator end,
495 const size_t* divCounts,
496 const size_t varCount) {
497 size_t lastDivCount = 0;
498 while (end - begin > 1) {
499 size_t minDivCount = numeric_limits<size_t>::max();
500 for (size_t var = 0; var < varCount; ++var)
501 if (divCounts[var] > lastDivCount && minDivCount > divCounts[var])
502 minDivCount = divCounts[var];
503 if (minDivCount == numeric_limits<size_t>::max())
504 break;
505
506 end = filter(begin, end, divCounts, varCount, minDivCount);
507 lastDivCount = minDivCount;
508 }
509 return end;
510 }
511
512 static const char* staticGetName() {
513 return "rarest";
514 }
515
516 virtual void getName(ostream& out) const {
517 out << staticGetName();
518 }
519
520 private:
521 iterator filter(iterator begin, iterator end,
522 const size_t* divCounts,
523 const size_t varCount,
524 size_t divCount) {
525 // Set the support of term to be the vars of the specified rarity
526 Word* term = termWithCapacity(varCount);
527 Ops::setToIdentity(term, varCount);
528 for (size_t var = 0; var < varCount; ++var)
529 if (divCounts[var] == divCount)
530 Ops::setExponent(term, var, 1);
531
532 // Select the generators that are divisible by the most vars with
533 // the specified rarity.
534 iterator newEnd = begin;
535 size_t maxRareCount = 0;
536 _tmp.reserve(varCount);
537 Word* tmp = _tmp;
538 for (iterator it = begin; it != end; ++it) {
539 if (Ops::isRelativelyPrime(term, *it, varCount))
540 continue; // no rare vars in *it
541
542 Ops::gcd(tmp, term, *it, varCount);
543 const size_t rareCount = Ops::getSizeOfSupport(tmp, varCount);
544
545 if (maxRareCount > rareCount)
546 continue;
547 if (maxRareCount < rareCount) {
548 maxRareCount = rareCount;
549 newEnd = begin;
550 }
551 Ops::swap(*newEnd, *it, varCount);
552 ++newEnd;
553 }
554 if (newEnd != begin)
555 return newEnd;
556 else
557 return end; // no rare vars in any generator, so we can't discard any
558 }
559
560 size_t getRarest(const RawSquareFreeIdeal& ideal, const size_t* divCounts) {
561 const size_t varCount = ideal.getVarCount();
563 const RawSquareFreeIdeal::const_iterator stop = ideal.end();
565
566 for (; it != stop; ++it)
567 if (rarer(*it, *rarest, divCounts, varCount))
568 rarest = it;
569 return rarest - ideal.begin();
570 }
571
575 pair<size_t, size_t> getRarity(const Word* const term,
576 const size_t* divCounts,
577 const size_t varCount,
578 size_t above) {
579 size_t rarity = varCount;
580 size_t multiplicity = 0;
581 for (size_t var = 0; var < varCount; ++var) {
582 const size_t co = divCounts[var];
583 if (Ops::getExponent(term, var) != 0 && co <= rarity && co > above) {
584 ASSERT(divCounts[var] != 0);
585 if (co == rarity)
586 ++multiplicity;
587 else {
588 rarity = divCounts[var];
589 multiplicity = 1;
590 }
591 }
592 }
593 return make_pair(rarity, multiplicity);
594 }
595
596 bool rarer(const Word* const a, const Word* const b,
597 const size_t* divCounts,
598 const size_t varCount) {
599 size_t lookAbove = 0;
600 while (true) {
601 pair<size_t, size_t> rarityA =
602 getRarity(a, divCounts, varCount, lookAbove);
603 pair<size_t, size_t> rarityB =
604 getRarity(b, divCounts, varCount, lookAbove);
605
606 if (rarityA.first < rarityB.first)
607 return true;
608 if (rarityA.first > rarityB.first)
609 return false;
610
611 if (rarityA.second > rarityB.second)
612 return true;
613 if (rarityA.second < rarityB.second)
614 return false;
615
616 if (rarityA.second == 0)
617 return false; // a and b are equally rare
618
619 lookAbove = rarityA.first;
620 }
621 }
622
623 RawSquareFreeTerm _tmp;
624 };
625
626 class GenMaxSupport : public GenStrategy {
627 public:
628 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
629 return state.inPlaceGenSplit(state.getIdeal().getMaxSupportGen());
630 }
631
632 virtual iterator filter(iterator begin, iterator end,
633 const size_t* divCounts,
634 const size_t varCount) {
635 size_t maxSupp = 0;
636 iterator newEnd = begin;
637 for (iterator it = begin; it != end; ++it) {
638 const size_t supp = Ops::getSizeOfSupport(*it, varCount);
639 if (maxSupp > supp)
640 continue;
641 if (maxSupp < supp) {
642 maxSupp = supp;
643 newEnd = begin;
644 }
645 Ops::swap(*newEnd, *it, varCount);
646 ++newEnd;
647 }
648 return newEnd;
649 }
650
651 static const char* staticGetName() {
652 return "maxsupp";
653 }
654
655 virtual void getName(ostream& out) const {
656 out << staticGetName();
657 }
658 };
659
660 class GenMinSupport : public GenStrategy {
661 public:
662 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
663 return state.inPlaceGenSplit(state.getIdeal().getMinSupportGen());
664 }
665
666 virtual iterator filter(iterator begin, iterator end,
667 const size_t* divCounts,
668 const size_t varCount) {
669 size_t minSupp = varCount;
670 iterator newEnd = begin;
671 for (iterator it = begin; it != end; ++it) {
672 const size_t supp = Ops::getSizeOfSupport(*it, varCount);
673 if (minSupp < supp)
674 continue;
675 if (minSupp > supp) {
676 minSupp = supp;
677 newEnd = begin;
678 }
679 Ops::swap(*newEnd, *it, varCount);
680 ++newEnd;
681 }
682 return newEnd;
683 }
684
685 static const char* staticGetName() {
686 return "minsupp";
687 }
688
689 virtual void getName(ostream& out) const {
690 out << staticGetName();
691 }
692 };
693
694 class GenAny : public GenStrategy {
695 public:
696 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
697 return state.inPlaceGenSplit(0);
698 }
699
700 virtual iterator filter(iterator begin, iterator end,
701 const size_t* divCounts,
702 const size_t varCount) {
703 return ++begin;
704 }
705
706 static const char* staticGetName() {
707 return "any";
708 }
709
710 virtual void getName(ostream& out) const {
711 out << staticGetName();
712 }
713 };
714
715 class GenRandom : public GenStrategy {
716 public:
717 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
718 size_t pivotIndex = rand() % state.getIdeal().getGeneratorCount();
719 return state.inPlaceGenSplit(pivotIndex);
720 }
721
722 virtual iterator filter(iterator begin, iterator end,
723 const size_t* divCounts,
724 const size_t varCount) {
725 const size_t genCount = end - begin;
726 const size_t choice = rand() % genCount;
727 Ops::swap(*begin, *(begin + choice), varCount);
728 return ++begin;
729 }
730
731 static const char* staticGetName() {
732 return "random";
733 }
734
735 virtual void getName(ostream& out) const {
736 out << staticGetName();
737 }
738 };
739
740 class HybridPivotStrategy : public PivotStrategy {
741 public:
742 HybridPivotStrategy(auto_ptr<PivotStrategy> stdStrat,
743 auto_ptr<PivotStrategy> genStrat):
744 _stdStrat(stdStrat), _genStrat(genStrat) {}
745
746 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
747 if (state.getNonEliminatedVarCount() <
748 state.getIdeal().getGeneratorCount())
749 return _stdStrat->doPivot(state, divCounts);
750 else
751 return _genStrat->doPivot(state, divCounts);
752 }
753
754 virtual void getName(ostream& out) const {
755 out << "hybrid (";
756 _stdStrat->getName(out);
757 out << ", ";
758 _genStrat->getName(out);
759 out << ')';
760 }
761
762 virtual void computationCompleted(const PivotEulerAlg& alg) {
763 _stdStrat->computationCompleted(alg);
764 _genStrat->computationCompleted(alg);
765 }
766
767 virtual bool shouldTranspose(const EulerState& state) const {
768 return false;
769 }
770
771 private:
772 auto_ptr<PivotStrategy> _stdStrat;
773 auto_ptr<PivotStrategy> _genStrat;
774 };
775
776 class DebugStrategy : public PivotStrategy {
777 public:
778 DebugStrategy(auto_ptr<PivotStrategy> strat, FILE* out):
779 _strat(strat), _out(out) {}
780
781 virtual EulerState* doPivot(EulerState& state,
782 const size_t* divCounts) {
783 const char* str1 = "\n\n\n"
784 "********************************(debug output)********************************\n"
785 "********** Processing this simplified state that is not a base case **********\n";
786 fputs(str1, _out);
787 state.print(_out);
788
789 EulerState* subState = _strat->doPivot(state, divCounts);
790 ASSERT(subState != 0);
791
792 const char* str2 =
793 "<<<<<<<<<<<<<<<<<<<<<<<<<<<< Substate 1 of 2 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n";
794 fputs(str2, _out);
795 state.print(_out);
796
797 const char* str3 =
798 "<<<<<<<<<<<<<<<<<<<<<<<<<<<< Substate 2 of 2 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n";
799 fputs(str3, _out);
800 subState->print(_out);
801
802 return subState;
803 }
804
805 virtual void getName(ostream& out) const {
806 _strat->getName(out);
807 }
808
809 virtual void computationCompleted(const PivotEulerAlg& alg) {
810 _strat->computationCompleted(alg);
811 fputs("Debug: Euler characteristic computation completed.\n", _out);
812 gmp_fprintf(_out, "Debug: Computed Euler characteristics was %Zd.\n",
813 alg.getComputedEulerCharacteristic().get_mpz_t());
814 }
815
816 virtual bool shouldTranspose(const EulerState& state) const {
817 return _strat->shouldTranspose(state);
818 }
819
820 private:
821 auto_ptr<PivotStrategy> _strat;
822 FILE* _out;
823 };
824
825 class StatisticsStrategy : public PivotStrategy {
826 public:
827 StatisticsStrategy(auto_ptr<PivotStrategy> strat, FILE* out):
828 _strat(strat), _out(out), _statesSplit(0), _transposes(0) {}
829
830 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
831 ++_statesSplit;
832 return _strat->doPivot(state, divCounts);
833 }
834
835 virtual void getName(ostream& out) const {
836 _strat->getName(out);
837 }
838
839 virtual void computationCompleted(const PivotEulerAlg& alg) {
840 _strat->computationCompleted(alg);
841 fputs("******** Statistics for Euler characteristic computation *****\n", _out);
842 fprintf(_out, "* Using unique div simplify: %s\n",
843 alg.getUseUniqueDivSimplify() ? "yes" : "no");
844 fprintf(_out, "* Using many div simplify: %s\n",
845 alg.getUseManyDivSimplify() ? "yes" : "no");
846 fprintf(_out, "* Using implied div simplify: %s\n",
847 alg.getUseAllPairsSimplify() ? "yes" : "no");
848 fprintf(_out, "* Do initial autotranspose: %s\n",
849 alg.getInitialAutoTranspose() ? "yes" : "no");
850 fprintf(_out, "* Do autotranspose at each step: %s\n",
851 alg.getAutoTranspose() ? "yes" : "no");
852 ostringstream strategyName;
853 getName(strategyName);
854 fprintf(_out, "* Pivot strategy: %s\n", strategyName.str().c_str());
855
856 // The computation is a binary tree and we only see the internal
857 // nodes that each generate two more nodes. The number of leaves
858 // in a binary tree is one plus the number of internal nodes.
859 unsigned long totalStates = 2 * _statesSplit + 1;
860 fprintf(_out, "* States processed: %lu\n", (unsigned long)totalStates);
861 fprintf(_out, "* Transposes taken: %lu\n", (unsigned long)_transposes);
862 fputs("********\n", _out);
863 }
864
865 virtual bool shouldTranspose(const EulerState& state) const {
866 const bool should = _strat->shouldTranspose(state);
867 if (should)
868 ++_transposes;
869 return should;
870 }
871
872 private:
873 auto_ptr<PivotStrategy> _strat;
874 FILE* _out;
875 unsigned long _statesSplit;
876 mutable unsigned long _transposes;
877 };
878
879 typedef NameFactory<StdStrategy> StdFactory;
880 StdFactory getStdStratFactory() {
881 StdFactory factory("standard pivot strategy");
882 nameFactoryRegister<StdRandom>(factory);
883 nameFactoryRegister<StdAny>(factory);
884 nameFactoryRegister<StdPopVar>(factory);
885 nameFactoryRegister<StdPopGcd>(factory);
886 nameFactoryRegister<StdRareVar>(factory);
887 return factory;
888 }
889
890 typedef NameFactory<GenStrategy> GenFactory;
891 GenFactory getGenStratFactory() {
892 GenFactory factory("generator pivot strategy");
893 nameFactoryRegister<GenRareMax>(factory);
894 nameFactoryRegister<GenRareVar>(factory);
895 nameFactoryRegister<GenRarestVars>(factory);
896 nameFactoryRegister<GenPopVar>(factory);
897 nameFactoryRegister<GenMaxSupport>(factory);
898 nameFactoryRegister<GenMinSupport>(factory);
899 nameFactoryRegister<GenAny>(factory);
900 nameFactoryRegister<GenRandom>(factory);
901 return factory;
902 }
903}
904
905auto_ptr<PivotStrategy> newStdPivotStrategy(const string& name) {
906 if (name.compare(0, 6, "widen_") != 0) {
907 auto_ptr<StdStrategy> strat = getStdStratFactory().create(name);
908 return auto_ptr<PivotStrategy>(strat.release());
909 }
910
911 auto_ptr<StdStrategy> subStrat =
912 getStdStratFactory().create(name.substr(6, name.size() - 6));
913 return auto_ptr<PivotStrategy>(new StdWiden(subStrat));
914}
915
916auto_ptr<PivotStrategy> newGenPivotStrategy(const string& name) {
917 GenFactory factory = getGenStratFactory();
918 if (name.find('_') == string::npos) {
919 auto_ptr<GenStrategy> strat = factory.create(name);
920 return auto_ptr<PivotStrategy>(strat.release());
921 }
922
923 auto_ptr<GenComposite> composite(new GenComposite());
924
925 size_t pos = 0;
926 string part;
927 do {
928 size_t nextPos = name.find('_', pos);
929 if (nextPos == string::npos) {
930 part = name.substr(pos, string::npos);
931 pos = string::npos;
932 } else {
933 part = name.substr(pos, nextPos - pos);
934 pos = nextPos + 1;
935 }
936
937 auto_ptr<GenStrategy> strat = factory.create(part);
938 composite->addStrategy(strat);
939 } while (pos != string::npos);
940 return auto_ptr<PivotStrategy>(composite.release());
941}
942
943auto_ptr<PivotStrategy> newHybridPivotStrategy
944(auto_ptr<PivotStrategy> stdStrat, auto_ptr<PivotStrategy> genStrat) {
945 PivotStrategy* strat = new HybridPivotStrategy(stdStrat, genStrat);
946 return auto_ptr<PivotStrategy>(strat);
947}
948
949auto_ptr<PivotStrategy> newDebugPivotStrategy(auto_ptr<PivotStrategy> strat,
950 FILE* out) {
951 return auto_ptr<PivotStrategy>(new DebugStrategy(strat, out));
952}
953
954auto_ptr<PivotStrategy> newStatisticsPivotStrategy
955(auto_ptr<PivotStrategy> strat, FILE* out) {
956 return auto_ptr<PivotStrategy>(new StatisticsStrategy(strat, out));
957}
958
959auto_ptr<PivotStrategy> newDefaultPivotStrategy() {
960 return newStdPivotStrategy("pivot");
961}
void exceptionSafePushBack(Container &container, auto_ptr< Element > pointer)
auto_ptr< PivotStrategy > newStdPivotStrategy(const string &name)
auto_ptr< PivotStrategy > newHybridPivotStrategy(auto_ptr< PivotStrategy > stdStrat, auto_ptr< PivotStrategy > genStrat)
auto_ptr< PivotStrategy > newStatisticsPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newDefaultPivotStrategy()
auto_ptr< PivotStrategy > newDebugPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newGenPivotStrategy(const string &name)
DebugStrategy(SliceStrategy *strategy, FILE *out)
Debug information is written to out, and every call is delegated to strategy.
EulerState * inPlaceGenSplit(size_t pivotIndex)
Definition: EulerState.cpp:95
RawSquareFreeIdeal & getIdeal()
Definition: EulerState.h:49
size_t getVarCount() const
Definition: EulerState.h:52
EulerState * inPlaceStdSplit(size_t pivotVar)
Definition: EulerState.cpp:81
void print(FILE *out)
Definition: EulerState.cpp:206
const Word * getEliminatedVars() const
Definition: EulerState.h:51
size_t getNonEliminatedVarCount() const
Definition: EulerState.cpp:240
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition: NameFactory.h:33
bool getInitialAutoTranspose() const
Definition: PivotEulerAlg.h:43
bool getUseUniqueDivSimplify() const
Definition: PivotEulerAlg.h:49
bool getUseAllPairsSimplify() const
Definition: PivotEulerAlg.h:55
bool getUseManyDivSimplify() const
Definition: PivotEulerAlg.h:52
const mpz_class & getComputedEulerCharacteristic() const
Definition: PivotEulerAlg.h:36
bool getAutoTranspose() const
Definition: PivotEulerAlg.h:46
A pivot selection strategy for the Euler algorithm.
Definition: PivotStrategy.h:28
const_iterator doesn't have all it needs to be a proper STL iterator.
iterator doesn't have all it needs to be a proper STL iterator.
A bit packed square free ideal placed in a pre-allocated buffer.
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var.
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
size_t getVarCount() const
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
size_t getGeneratorCount() const
A wrapper for a SliceStrategy that collects statistics on what is going on, while delegating everythi...
void setExponent(Word *a, size_t var, bool value)
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
size_t getSizeOfSupport(const Word *a, size_t varCount)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToIdentity(Word *res, const Word *resEnd)
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:93
#define ASSERT(X)
Definition: stdinc.h:86