MsmStrategy.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2007 Bjarke Hammersholt Roune (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 "MsmStrategy.h"
#include "MsmSlice.h"
#include "Term.h"
#include "Ideal.h"
#include "TermTranslator.h"
#include <vector>
#include "Projection.h"
#include "TermGrader.h"
MsmStrategy::MsmStrategy(TermConsumer* consumer,
const SplitStrategy* splitStrategy):
SliceStrategyCommon(splitStrategy),
_consumer(consumer) {
ASSERT(consumer != 0);
}
MsmStrategy::MsmStrategy(TermConsumer* consumer,
const SplitStrategy* splitStrategy,
const Ideal& initialSubtract):
SliceStrategyCommon(splitStrategy),
_consumer(consumer),
_initialSubtract(new Ideal(initialSubtract)) {
ASSERT(consumer != 0);
}
void MsmStrategy::run(const Ideal& ideal) {
ASSERT(_initialSubtract.get() == 0 ||
_initialSubtract->getVarCount() == ideal.getVarCount());
_consumer->beginConsuming();
size_t varCount = ideal.getVarCount();
if (_initialSubtract.get() == 0)
_initialSubtract = unique_ptr<Ideal>(new Ideal(varCount));
Term sliceMultiply(varCount);
for (size_t var = 0; var < varCount; ++var)
sliceMultiply[var] = 1;
unique_ptr<Slice> slice
(new MsmSlice(*this, ideal, *_initialSubtract, sliceMultiply, _consumer));
simplify(*slice);
_initialSubtract.reset();
_tasks.addTask(slice.release());
_tasks.runTasks();
_consumer->doneConsuming();
}
bool MsmStrategy::processSlice(TaskEngine& tasks, unique_ptr<Slice> slice) {
ASSERT(slice.get() != 0);
if (slice->baseCase(getUseSimplification())) {
freeSlice(std::move(slice));
return true;
}
if (getUseIndependence() && _indep.analyze(*slice))
independenceSplit(std::move(slice));
else if (_split->isLabelSplit())
labelSplit(std::move(slice));
else {
ASSERT(_split->isPivotSplit());
pivotSplit(std::move(slice));
}
return false;
}
unique_ptr<MsmSlice> MsmStrategy::newMsmSlice() {
unique_ptr<Slice> slice(newSlice());
ASSERT(dynamic_cast<MsmSlice*>(slice.get()) != 0);
return unique_ptr<MsmSlice>(static_cast<MsmSlice*>(slice.release()));
}
unique_ptr<Slice> MsmStrategy::allocateSlice() {
return unique_ptr<Slice>(new MsmSlice(*this));
}
bool MsmStrategy::debugIsValidSlice(Slice* slice) {
ASSERT(slice != 0);
ASSERT(dynamic_cast<MsmSlice*>(slice) != 0);
return true;
}
void MsmStrategy::labelSplit(unique_ptr<Slice> sliceParam) {
ASSERT(sliceParam.get() != 0);
ASSERT(debugIsValidSlice(sliceParam.get()));
unique_ptr<MsmSlice> slice
(static_cast<MsmSlice*>(sliceParam.release()));
ASSERT(!slice->adjustMultiply());
ASSERT(!slice->normalize());
ASSERT(_split != 0);
size_t var = _split->getLabelSplitVariable(*slice);
Term term(slice->getVarCount());
const Term& lcm = slice->getLcm();
Ideal::const_iterator stop = slice->getIdeal().end();
Ideal::const_iterator label = stop;
bool hasTwoLabels = false;
for (Ideal::const_iterator it = slice->getIdeal().begin();
it != stop; ++it) {
if ((*it)[var] == 1) {
term = *it;
term[var] -= 1;
bool couldBeLabel = !slice->getSubtract().contains(term);
if (couldBeLabel) {
for (size_t v = 0; v < slice->getVarCount(); ++v) {
if (term[v] == lcm[v]) {
couldBeLabel = false;
break;
}
}
}
if (couldBeLabel) {
if (label == stop)
label = it;
else {
hasTwoLabels = true;
break;
}
}
}
}
unique_ptr<Slice> hasLabelSlice;
if (label != stop) {
term = *label;
term[var] -= 1;
hasLabelSlice = newSlice();
*hasLabelSlice = *slice;
hasLabelSlice->innerSlice(term);
if (hasTwoLabels)
slice->outerSlice(term);
}
if (!hasTwoLabels) {
term.setToIdentity();
term[var] = 1;
slice->innerSlice(term);
}
if (hasLabelSlice.get() != 0) {
simplify(*hasLabelSlice);
_tasks.addTask(hasLabelSlice.release());
}
simplify(*slice);
_tasks.addTask(slice.release());
}
class MsmIndependenceSplit : public TermConsumer, public Task {
public:
Task* getLeftEvent() {
return this;
}
TermConsumer* getLeftConsumer() {
return this;
}
TermConsumer* getRightConsumer() {
return &_rightConsumer;
}
const Projection& getLeftProjection() {
return _leftProjection;
}
const Projection& getRightProjection() {
return _rightProjection;
}
void reset(TermConsumer* consumer,
IndependenceSplitter& splitter) {
_consumer = consumer;
_tmpTerm.reset(splitter.getVarCount());
splitter.getBigProjection(_leftProjection);
splitter.getRestProjection(_rightProjection);
_rightConsumer._decom.clearAndSetVarCount
(_rightProjection.getRangeVarCount());
}
private:
virtual void run(TaskEngine& engine) {
dispose();
}
virtual void dispose() {
delete this;
}
virtual void beginConsuming() {
}
virtual void doneConsuming() {
}
virtual void consume(const Term& term) {
_leftProjection.inverseProject(_tmpTerm, term);
Ideal::const_iterator stop = _rightConsumer._decom.end();
for (Ideal::const_iterator it = _rightConsumer._decom.begin();
it != stop; ++it) {
_rightProjection.inverseProject(_tmpTerm, *it);
_consumer->consume(_tmpTerm);
}
}
struct RightConsumer : public TermConsumer {
virtual void beginConsuming() {
}
virtual void doneConsuming() {
}
virtual void consume(const Term& term) {
_decom.insert(term);
}
Ideal _decom;
} _rightConsumer;
TermConsumer* _consumer;
Projection _leftProjection;
Projection _rightProjection;
Term _tmpTerm;
};
void MsmStrategy::independenceSplit(unique_ptr<Slice> sliceParam) {
ASSERT(sliceParam.get() != 0);
ASSERT(debugIsValidSlice(sliceParam.get()));
unique_ptr<MsmSlice> slice
(static_cast<MsmSlice*>(sliceParam.release()));
// Construct split object
unique_ptr<MsmIndependenceSplit> autoSplit(new MsmIndependenceSplit());
autoSplit->reset(slice->getConsumer(), _indep);
MsmIndependenceSplit* split = autoSplit.release();
_tasks.addTask(split); // Runs when we are done with all of this split.
// Construct left slice.
unique_ptr<MsmSlice> leftSlice(new MsmSlice(*this));
leftSlice->setToProjOf(*slice, split->getLeftProjection(), split);
_tasks.addTask(leftSlice.release());
// Construct right slice.
unique_ptr<MsmSlice> rightSlice(new MsmSlice(*this));
rightSlice->setToProjOf(*slice, split->getRightProjection(),
split->getRightConsumer());
_tasks.addTask(rightSlice.release());
// Deal with slice.
freeSlice(std::move(slice));
}
void MsmStrategy::getPivot(Term& pivot, Slice& slice) {
ASSERT(_split != 0);
ASSERT(_split->isPivotSplit());
_split->getPivot(pivot, slice);
}
void MsmStrategy::getPivot(Term& pivot, Slice& slice, const TermGrader& grader) {
ASSERT(_split != 0);
ASSERT(_split->isPivotSplit());
_split->getPivot(pivot, slice, grader);
}
Ideal.h
MsmSlice.h
MsmStrategy.h
Projection.h
TermGrader.h
TermTranslator.h
Term.h
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
IndependenceSplitter
Definition IndependenceSplitter.h:29
IndependenceSplitter::getRestProjection
void getRestProjection(Projection &projection) const
Definition IndependenceSplitter.cpp:28
IndependenceSplitter::getVarCount
size_t getVarCount() const
Definition IndependenceSplitter.cpp:97
IndependenceSplitter::getBigProjection
void getBigProjection(Projection &projection) const
Definition IndependenceSplitter.cpp:24
MsmIndependenceSplit
Definition MsmStrategy.cpp:177
MsmIndependenceSplit::_leftProjection
Projection _leftProjection
Definition MsmStrategy.cpp:252
MsmIndependenceSplit::_rightConsumer
MsmIndependenceSplit::RightConsumer _rightConsumer
MsmIndependenceSplit::dispose
virtual void dispose()
Called when the task is no longer used but run has not and will not be called.
Definition MsmStrategy.cpp:216
MsmIndependenceSplit::beginConsuming
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition MsmStrategy.cpp:220
MsmIndependenceSplit::_rightProjection
Projection _rightProjection
Definition MsmStrategy.cpp:253
MsmIndependenceSplit::_consumer
TermConsumer * _consumer
Definition MsmStrategy.cpp:250
MsmIndependenceSplit::doneConsuming
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition MsmStrategy.cpp:223
MsmIndependenceSplit::run
virtual void run(TaskEngine &engine)
Does whatever work this task represents.
Definition MsmStrategy.cpp:212
MsmIndependenceSplit::_tmpTerm
Term _tmpTerm
Definition MsmStrategy.cpp:255
MsmIndependenceSplit::getRightProjection
const Projection & getRightProjection()
Definition MsmStrategy.cpp:195
MsmIndependenceSplit::getLeftConsumer
TermConsumer * getLeftConsumer()
Definition MsmStrategy.cpp:183
MsmIndependenceSplit::reset
void reset(TermConsumer *consumer, IndependenceSplitter &splitter)
Definition MsmStrategy.cpp:199
MsmIndependenceSplit::getLeftProjection
const Projection & getLeftProjection()
Definition MsmStrategy.cpp:191
MsmIndependenceSplit::getLeftEvent
Task * getLeftEvent()
Definition MsmStrategy.cpp:179
MsmIndependenceSplit::getRightConsumer
TermConsumer * getRightConsumer()
Definition MsmStrategy.cpp:187
MsmIndependenceSplit::consume
virtual void consume(const Term &term)
Consume a term.
Definition MsmStrategy.cpp:226
MsmSlice
Invariant: either the slice is a trivial base case, or removeDoubleLcm returns false.
Definition MsmSlice.h:33
MsmStrategy::allocateSlice
virtual unique_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
Definition MsmStrategy.cpp:93
MsmStrategy::debugIsValidSlice
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
Definition MsmStrategy.cpp:97
MsmStrategy::processSlice
virtual bool processSlice(TaskEngine &tasks, unique_ptr< Slice > slice)
Process the parameter slice.
Definition MsmStrategy.cpp:67
MsmStrategy::_indep
IndependenceSplitter _indep
Definition MsmStrategy.h:62
MsmStrategy::independenceSplit
void independenceSplit(unique_ptr< Slice > slice)
Definition MsmStrategy.cpp:258
MsmStrategy::newMsmSlice
unique_ptr< MsmSlice > newMsmSlice()
Definition MsmStrategy.cpp:87
MsmStrategy::_consumer
TermConsumer * _consumer
Definition MsmStrategy.h:63
MsmStrategy::_initialSubtract
unique_ptr< Ideal > _initialSubtract
Definition MsmStrategy.h:65
MsmStrategy::getPivot
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Definition MsmStrategy.cpp:285
MsmStrategy::labelSplit
void labelSplit(unique_ptr< Slice > slice)
Definition MsmStrategy.cpp:103
MsmStrategy::run
virtual void run(const Ideal &ideal)
Run the Slice algorithm.
Definition MsmStrategy.cpp:44
MsmStrategy::MsmStrategy
MsmStrategy(TermConsumer *consumer, const SplitStrategy *splitStrategy)
Definition MsmStrategy.cpp:28
Projection
Definition Projection.h:29
SliceStrategyCommon::getUseIndependence
bool getUseIndependence() const
Returns true if independence splits should be performed when possible.
Definition SliceStrategyCommon.cpp:113
SliceStrategyCommon::getUseSimplification
bool getUseSimplification() const
Returns true if slices should be simplified.
Definition SliceStrategyCommon.cpp:117
SliceStrategyCommon::_split
const SplitStrategy * _split
Definition SliceStrategyCommon.h:80
SliceStrategyCommon::freeSlice
virtual void freeSlice(unique_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
Definition SliceStrategyCommon.cpp:39
SliceStrategyCommon::simplify
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
Definition SliceStrategyCommon.cpp:55
SliceStrategyCommon::pivotSplit
virtual void pivotSplit(unique_ptr< Slice > slice)
Takes over ownership of slice.
Definition SliceStrategyCommon.cpp:77
SliceStrategyCommon::SliceStrategyCommon
SliceStrategyCommon(const SplitStrategy *splitStrategy)
Definition SliceStrategyCommon.cpp:24
SliceStrategyCommon::newSlice
unique_ptr< Slice > newSlice()
Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice.
Definition SliceStrategyCommon.cpp:65
SliceStrategyCommon::_tasks
TaskEngine _tasks
This keeps track of pending tasks to process.
Definition SliceStrategyCommon.h:84
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition Slice.h:77
SplitStrategy
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition SplitStrategy.h:30
TaskEngine
TaskEngine handles a list of tasks that are to be carried out.
Definition TaskEngine.h:40
Task
A Task object represents a unit of work that is performed when the method run() is called.
Definition Task.h:27
TermConsumer
This class is used to transfer terms one at a time from one part of the program to another,...
Definition TermConsumer.h:36
TermGrader
A TermGrader assigns a value, the degree, to each monomial.
Definition TermGrader.h:27
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::setToIdentity
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
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
ASSERT
#define ASSERT(X)
Definition stdinc.h:86
MsmIndependenceSplit::RightConsumer
Definition MsmStrategy.cpp:236
MsmIndependenceSplit::RightConsumer::doneConsuming
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition MsmStrategy.cpp:240
MsmIndependenceSplit::RightConsumer::consume
virtual void consume(const Term &term)
Consume a term.
Definition MsmStrategy.cpp:243
MsmIndependenceSplit::RightConsumer::_decom
Ideal _decom
Definition MsmStrategy.cpp:247
MsmIndependenceSplit::RightConsumer::beginConsuming
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition MsmStrategy.cpp:237