BigattiPivotStrategy.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2009 University of Aarhus
Contact Bjarke Hammersholt Roune for license information (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#include "stdinc.h"
#include "BigattiPivotStrategy.h"
#include "BigattiState.h"
#include "Ideal.h"
#include "Term.h"
#include "NameFactory.h"
#include "error.h"
BigattiPivotStrategy::BigattiPivotStrategy() {
}
BigattiPivotStrategy::~BigattiPivotStrategy() {
}
namespace {
class MedianPivot : public BigattiPivotStrategy {
public:
const Term& getPivot(BigattiState& state) {
_counts.reset(state.getVarCount());
state.getIdeal().getSupportCounts(_counts);
size_t var = _counts.getFirstMaxExponent();
_pivot.reset(state.getVarCount());
_pivot[var] = state.getMedianPositiveExponentOf(var);
return _pivot;
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "median";
}
private:
Term _counts;
Term _pivot;
};
class GenericPivotCommon : public BigattiPivotStrategy {
public:
virtual const Term& getPivot(BigattiState& state) {
_state = &state;
_ideal = &(state.getIdeal());
driveMe();
return _pivot;
}
protected:
virtual void driveMe() = 0;
void considerTypical() {
size_t count = _ideal->getTypicalExponent(_var, _exp);
if (count <= 1)
_exp = 0; // fall back to median.
}
void considerMostNonGeneric() {
_ideal->getMostNonGenericExponent(_var, _exp);
}
void considerTypicalNonGeneric() {
_ideal->getTypicalNonGenericExponent(_var, _exp);
}
void considerSomeNonGeneric() {
_ideal->getNonGenericExponent(_var, _exp);
}
void selectPurePower() {
if (_exp == 0)
_pivot = getMedian();
else {
_pivot.reset(_ideal->getVarCount());
_pivot[_var] = _exp;
}
}
void selectGcd() {
if (_exp == 0)
_pivot = getMedian();
else {
_pivot.reset(_ideal->getVarCount());
_ideal->getGcdAtExponent(_pivot, _var, _exp);
ASSERT(!_pivot.isIdentity());
}
}
void selectTight() {
if (_exp == 0) {
_pivot = getMedian();
return;
}
_ideal->singleDegreeSort(_var);
Ideal::const_iterator blockBegin = _ideal->begin();
Ideal::const_iterator stop = _ideal->end();
ASSERT(blockBegin != stop);
// Find the start of the relevant block.
while ((*blockBegin)[_var] != _exp) {
++blockBegin;
ASSERT(blockBegin != stop);
}
ASSERT((*blockBegin)[_var] == _exp);
Ideal::const_iterator blockEnd = blockBegin;
do {
++blockEnd;
} while (blockEnd != stop && (*blockEnd)[_var] == _exp);
// At this point the range [blockBegin, blockEnd) contains every
// generator that raises _var to _exp.
bool first = true;
_pivot.reset(_ideal->getVarCount());
Term lcm(_ideal->getVarCount()); // For a temporary value
for (; blockBegin != blockEnd; ++blockBegin) {
Ideal::const_iterator it = blockBegin;
for (++it; it != blockEnd; ++it) {
lcm.lcm(*blockBegin, *it);
if (!_ideal->strictlyContains(lcm)) {
// We only need to have the pivot remove one of
// *blockBegin and *it. We choose to let it be *blockBegin
// that is included in the gcd (and thus removed for sure)
// just because that is easier to keep track of.
if (first) {
first = false;
_pivot.gcd(*blockBegin, *it);
} else {
_pivot.gcd(_pivot, *blockBegin);
_pivot.gcd(_pivot, *it);
}
break;
}
}
}
if (first)
_pivot[_var] = _exp;
ASSERT(!_pivot.isIdentity());
}
private:
Term _pivot;
BigattiState* _state;
Ideal* _ideal;
size_t _var;
Exponent _exp;
const Term& getMedian() {
return _median.getPivot(*_state);
}
MedianPivot _median;
};
class MostNGPurePivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerMostNonGeneric();
selectPurePower();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "mostNGPure";
}
};
class MostNGGcdPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerMostNonGeneric();
selectGcd();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "mostNGGcd";
}
};
class MostNGTightPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerMostNonGeneric();
selectTight();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "mostNGTight";
}
};
class TypicalNGPurePivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypicalNonGeneric();
selectPurePower();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalNGPure";
}
};
class TypicalNGGcdPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypicalNonGeneric();
selectGcd();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalNGGcd";
}
};
class TypicalNGTightPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypicalNonGeneric();
selectTight();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalNGTight";
}
};
class TypicalPurePivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypical();
selectPurePower();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalPure";
}
};
class TypicalGcdPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypical();
selectGcd();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalGcd";
}
};
class TypicalTightPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerTypical();
selectTight();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "typicalTight";
}
};
class SomeNGPurePivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerSomeNonGeneric();
selectPurePower();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "someNGPure";
}
};
class SomeNGGcdPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerSomeNonGeneric();
selectGcd();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "someNGGcd";
}
};
class SomeNGTightPivot : public GenericPivotCommon {
public:
virtual void driveMe() {
considerSomeNonGeneric();
selectTight();
}
virtual const char* getName() const {
return staticGetName();
}
static const char* staticGetName() {
return "someNGTight";
}
};
class WidenPivot : public BigattiPivotStrategy {
public:
WidenPivot(unique_ptr<BigattiPivotStrategy> strategy):
_strategy(std::move(strategy)) {
_name = _strategy->getName();
_name += " (wide)";
}
const Term& getPivot(BigattiState& state) {
const Term& pivot = _strategy->getPivot(state);
_widePivot.reset(state.getVarCount());
state.getIdeal().getGcdOfMultiplesOf(_widePivot, pivot);
return _widePivot;
}
virtual const char* getName() const {
return _name.c_str();
}
private:
unique_ptr<BigattiPivotStrategy> _strategy;
string _name;
Term _widePivot;
};
typedef NameFactory<BigattiPivotStrategy> StrategyFactory;
StrategyFactory makeStrategyFactory() {
StrategyFactory factory("Bigatti et.al. pivot strategy");
nameFactoryRegister<MedianPivot>(factory);
nameFactoryRegister<TypicalPurePivot>(factory);
nameFactoryRegister<TypicalNGPurePivot>(factory);
nameFactoryRegister<MostNGPurePivot>(factory);
nameFactoryRegister<SomeNGPurePivot>(factory);
nameFactoryRegister<TypicalGcdPivot>(factory);
nameFactoryRegister<TypicalNGGcdPivot>(factory);
nameFactoryRegister<MostNGGcdPivot>(factory);
nameFactoryRegister<SomeNGGcdPivot>(factory);
nameFactoryRegister<TypicalTightPivot>(factory);
nameFactoryRegister<TypicalNGTightPivot>(factory);
nameFactoryRegister<MostNGTightPivot>(factory);
nameFactoryRegister<SomeNGTightPivot>(factory);
return factory;
}
}
unique_ptr<BigattiPivotStrategy> BigattiPivotStrategy::
createStrategy(const string& prefix, bool widen) {
unique_ptr<BigattiPivotStrategy> strategy =
createWithPrefix(makeStrategyFactory(), prefix);
ASSERT(strategy.get() != 0);
if (widen)
strategy = unique_ptr<BigattiPivotStrategy>(new WidenPivot(std::move(strategy)));
return strategy;
}
BigattiPivotStrategy.h
BigattiState.h
Ideal.h
NameFactory.h
nameFactoryRegister
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
Definition NameFactory.h:142
createWithPrefix
unique_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 ...
Definition NameFactory.h:154
Term.h
BigattiPivotStrategy
A BigattiPivotStrategy is an implementation of a pivot selection strategy for the Hilbert series algo...
Definition BigattiPivotStrategy.h:28
BigattiPivotStrategy::~BigattiPivotStrategy
virtual ~BigattiPivotStrategy()
Definition BigattiPivotStrategy.cpp:30
BigattiState
Definition BigattiState.h:27
BigattiState::getVarCount
size_t getVarCount() const
Definition BigattiState.cpp:49
BigattiState::getIdeal
const Ideal & getIdeal() const
Definition BigattiState.cpp:33
BigattiState::getMedianPositiveExponentOf
Exponent getMedianPositiveExponentOf(size_t var)
Definition BigattiState.cpp:54
Ideal::getGcdOfMultiplesOf
void getGcdOfMultiplesOf(Exponent *gcd, const Exponent *divisor)
Sets gcd to the greatest common divisor of those generators that are divisible by divisor.
Definition Ideal.cpp:197
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::getSupportCounts
void getSupportCounts(Exponent *counts) const
counts[var] will be the number of generators divisible by var.
Definition Ideal.cpp:227
NameFactory
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition NameFactory.h:33
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::reset
void reset(size_t newVarCount)
Definition Term.h:551
error.h
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition RawSquareFreeTerm.cpp:251
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
Exponent
unsigned int Exponent
Definition stdinc.h:89
ASSERT
#define ASSERT(X)
Definition stdinc.h:86