Slice.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 "Slice.h"
#include "Projection.h"
#include "TaskEngine.h"
#include "SliceStrategy.h"
// The lcm is technically correct, but _lcmUpdated defaulting to false
// is still a sensible choice.
Slice::Slice(SliceStrategy& strategy):
_varCount(0),
_lcmUpdated(false),
_lowerBoundHint(0),
_strategy(strategy) {
}
Slice::Slice(SliceStrategy& strategy,
const Ideal& ideal, const Ideal& subtract, const Term& multiply):
_ideal(ideal),
_subtract(subtract),
_multiply(multiply),
_varCount(multiply.getVarCount()),
_lcm(multiply.getVarCount()),
_lcmUpdated(false),
_lowerBoundHint(0),
_strategy(strategy) {
ASSERT(multiply.getVarCount() == ideal.getVarCount());
ASSERT(multiply.getVarCount() == subtract.getVarCount());
}
Slice::~Slice() {
// We are defining this do-nothing destructor in order to make it
// virtual.
}
const Term& Slice::getLcm() const {
#ifdef DEBUG
if (_lcmUpdated) {
Term tmp(_varCount);
_ideal.getLcm(tmp);
ASSERT(tmp == _lcm);
}
#endif
if (!_lcmUpdated) {
getIdeal().getLcm(_lcm);
_lcmUpdated = true;
}
return _lcm;
}
void Slice::print(FILE* file) const {
fputs("Slice (multiply: ", file);
_multiply.print(file);
fputs("\n ideal: ", file);
getIdeal().print(file);
fputs(" subtract: ", file);
_subtract.print(file);
}
Slice& Slice::operator=(const Slice& slice) {
_varCount = slice._varCount;
_ideal = slice._ideal;
_subtract = slice._subtract;
_multiply = slice._multiply;
_lcm = slice._lcm;
_lcmUpdated = slice._lcmUpdated;
_lowerBoundHint = slice._lowerBoundHint;
return *this;
}
void Slice::resetAndSetVarCount(size_t varCount) {
_varCount = varCount;
_ideal.clearAndSetVarCount(varCount);
_subtract.clearAndSetVarCount(varCount);
_multiply.reset(varCount);
_lcm.reset(varCount);
_lcmUpdated = false;
_lowerBoundHint = 0;
}
void Slice::clearIdealAndSubtract() {
_ideal.clear();
_subtract.clear();
_lcmUpdated = false;
_lowerBoundHint = 0;
}
void Slice::singleDegreeSortIdeal(size_t var) {
_ideal.singleDegreeSort(var);
}
bool Slice::innerSlice(const Term& pivot) {
ASSERT(getVarCount() == pivot.getVarCount());
size_t count = _ideal.getGeneratorCount();
_multiply.product(_multiply, pivot);
bool idealChanged = _ideal.colonReminimize(pivot);
bool subtractChanged = _subtract.colonReminimize(pivot);
bool changed = idealChanged || subtractChanged;
if (changed) {
normalize();
_lowerBoundHint = pivot.getFirstNonZeroExponent();
}
if (_ideal.getGeneratorCount() == count)
_lcm.colon(_lcm, pivot);
else
_lcmUpdated = false;
return changed;
}
void Slice::outerSlice(const Term& pivot) {
ASSERT(getVarCount() == pivot.getVarCount());
size_t count = getIdeal().getGeneratorCount();
_ideal.removeStrictMultiples(pivot);
if (getIdeal().getGeneratorCount() != count)
_lcmUpdated = false;
if (pivot.getSizeOfSupport() > 1)
getSubtract().insertReminimize(pivot);
_lowerBoundHint = pivot.getFirstNonZeroExponent();
}
// Helper class for normalize().
class StrictMultiplePredicate {
public:
StrictMultiplePredicate(const Exponent* term, size_t varCount):
_term(term), _varCount(varCount) {
}
bool operator()(const Exponent* term) {
return Term::strictlyDivides(_term, term, _varCount);
}
private:
const Exponent* _term;
size_t _varCount;
};
bool Slice::adjustMultiply() {
bool changed = false;
while (true) {
Term lowerBound(_varCount);
Ideal::const_iterator end = getIdeal().end();
for (Ideal::const_iterator it = getIdeal().begin(); it != end; ++it) {
for (size_t var = 0; var < _varCount; ++var) {
if ((*it)[var] == 0)
continue;
if (lowerBound[var] == 0 || lowerBound[var] > (*it)[var])
lowerBound[var] = (*it)[var];
}
}
lowerBound.decrement();
if (lowerBound.isIdentity())
break;
changed = true;
bool sawRealChange = innerSlice(lowerBound);
if (!sawRealChange)
break;
}
return changed;
}
bool Slice::normalize() {
bool removedAny = false;
Ideal::const_iterator stop = _subtract.end();
for (Ideal::const_iterator it = _subtract.begin(); it != stop; ++it) {
StrictMultiplePredicate pred(*it, _varCount);
if (_ideal.removeIf(pred)) {
removedAny = true;
_lcmUpdated = false;
}
}
return removedAny;
}
bool Slice::simplify() {
ASSERT(!normalize());
bool lowerBoundChange = applyLowerBound();
bool pruneSubtractChange = pruneSubtract();
ASSERT(!normalize());
ASSERT(!pruneSubtract());
ASSERT(!applyLowerBound());
return lowerBoundChange || pruneSubtractChange;
}
void Slice::setToProjOf
(const Slice& slice, const Projection& projection) {
resetAndSetVarCount(projection.getRangeVarCount());
Ideal::const_iterator stop = slice.getIdeal().end();
for (Ideal::const_iterator it = slice.getIdeal().begin();
it != stop; ++it) {
size_t var = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
if (var == slice.getVarCount() || projection.domainVarHasProjection(var)) {
// Use _lcm as temporary.
projection.project(_lcm, *it);
_ideal.insert(_lcm);
}
}
stop = slice.getSubtract().end();
for (Ideal::const_iterator it = slice.getSubtract().begin();
it != stop; ++it) {
size_t var = Term::getFirstNonZeroExponent(*it, slice.getVarCount());
if (var == slice.getVarCount() || projection.domainVarHasProjection(var)) {
projection.project(_lcm, *it);
getSubtract().insert(_lcm);
}
}
projection.project(getMultiply(), slice.getMultiply());
if (slice._lcmUpdated) {
projection.project(_lcm, slice._lcm);
_lcmUpdated = true;
} else
_lcmUpdated = false;
}
void Slice::swap(Slice& slice) {
std::swap(_varCount, slice._varCount);
_multiply.swap(slice._multiply);
_lcm.swap(slice._lcm);
std::swap(_lcmUpdated, slice._lcmUpdated);
_ideal.swap(slice._ideal);
_subtract.swap(slice._subtract);
std::swap(_lowerBoundHint, slice._lowerBoundHint);
}
namespace {
class PruneSubtractPredicate {
public:
PruneSubtractPredicate(const Ideal& ideal, const Term& lcm):
_ideal(ideal), _lcm(lcm) {}
bool operator()(const Exponent* term) {
return
!Term::strictlyDivides(term, _lcm, _lcm.getVarCount()) ||
_ideal.contains(term);
}
private:
const Ideal& _ideal;
const Term& _lcm;
};
}
bool Slice::pruneSubtract() {
if (_subtract.getGeneratorCount() == 0)
return false;
PruneSubtractPredicate pred(getIdeal(), getLcm());
return _subtract.removeIf(pred);
}
bool Slice::applyLowerBound() {
if (_ideal.getGeneratorCount() == 0)
return false;
if (getVarCount() == 1)
return adjustMultiply();
bool changed = false;
size_t stepsWithNoChange = 0;
Term bound(_varCount);
size_t var = _lowerBoundHint;
while (stepsWithNoChange < _varCount) {
if (!getLowerBound(bound, var)) {
clearIdealAndSubtract();
return true;
}
if (!bound.isIdentity()) {
changed = true;
if (innerSlice(bound))
stepsWithNoChange = 0;
else
++stepsWithNoChange;
} else
++stepsWithNoChange;
var = (var + 1) % _varCount;
}
return changed;
}
void Slice::run(TaskEngine& tasks) {
_strategy.processSlice(tasks, unique_ptr<Slice>(this));
}
void Slice::dispose() {
_strategy.freeSlice(unique_ptr<Slice>(this));
}
Projection.h
SliceStrategy.h
Slice.h
TaskEngine.h
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition Ideal.h:57
Ideal::getLcm
void getLcm(Exponent *lcm) const
Sets lcm to the least common multiple of all generators.
Definition Ideal.cpp:157
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::insert
void insert(const Exponent *term)
Definition Ideal.cpp:455
Ideal::insertReminimize
void insertReminimize(const Exponent *term)
Definition Ideal.cpp:484
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::print
void print(FILE *file) const
Definition Ideal.cpp:440
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
Projection
Definition Projection.h:29
Projection::domainVarHasProjection
bool domainVarHasProjection(size_t var) const
Definition Projection.cpp:89
Projection::project
void project(Exponent *to, const Exponent *from) const
Definition Projection.cpp:72
Projection::getRangeVarCount
size_t getRangeVarCount() const
Definition Projection.cpp:24
SliceStrategy
This class describes the interface of a strategy object for the Slice Algorithm.
Definition SliceStrategy.h:33
Slice::_varCount
size_t _varCount
The number of variables in the ambient polynomial ring.
Definition Slice.h:275
Slice::_ideal
Ideal _ideal
The of a slice .
Definition Slice.h:266
Slice::resetAndSetVarCount
void resetAndSetVarCount(size_t varCount)
Resets this slice to in an ambient polynomial ring of varCount variables.
Definition Slice.cpp:89
Slice::_strategy
SliceStrategy & _strategy
Definition Slice.h:303
Slice::normalize
bool normalize()
Removes those generators of getIdeal() that are strictly divisible by some generator of getSubtract()...
Definition Slice.cpp:189
Slice::singleDegreeSortIdeal
void singleDegreeSortIdeal(size_t var)
Calls Ideal::singleDegreeSort on getIdeal().
Definition Slice.cpp:106
Slice::print
void print(FILE *file) const
Write a text representation of this object to file in a format appropriate for debugging.
Definition Slice.cpp:68
Slice::innerSlice
virtual bool innerSlice(const Term &pivot)
Sets this object to the inner slice according to pivot.
Definition Slice.cpp:110
Slice::outerSlice
virtual void outerSlice(const Term &pivot)
Sets this object to the outer slice according to pivot.
Definition Slice.cpp:132
Slice::_lowerBoundHint
size_t _lowerBoundHint
A hint that starting simplification through a lower bound at the variable indicated by _lowerBoundHin...
Definition Slice.h:301
Slice::operator=
virtual Slice & operator=(const Slice &slice)=0
Performs a deep copy of slice into this object.
Definition Slice.cpp:77
Slice::adjustMultiply
bool adjustMultiply()
Ensure that for each var, var appears to the first power in some generator of getIdeal().
Definition Slice.cpp:162
Slice::setToProjOf
void setToProjOf(const Slice &slice, const Projection &projection)
Set this object to be the projection of slice according to projection.
Definition Slice.cpp:218
Slice::_multiply
Term _multiply
The of a slice .
Definition Slice.h:272
Slice::swap
void swap(Slice &slice)
Simultaneously set the value of this object to that of slice and vice versa.
Definition Slice.cpp:252
Slice::Slice
Slice(SliceStrategy &strategy)
Construct the slice in a ring of zero variables.
Definition Slice.cpp:26
Slice::getMultiply
Term & getMultiply()
Returns for a slice .
Definition Slice.h:113
Slice::pruneSubtract
bool pruneSubtract()
Removes those generators of subtract that do not strictly divide the lcm of getIdeal(),...
Definition Slice.cpp:281
Slice::run
virtual void run(TaskEngine &tasks)
Does whatever work this task represents.
Definition Slice.cpp:321
Slice::_lcm
Term _lcm
The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind.
Definition Slice.h:285
Slice::clearIdealAndSubtract
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition Slice.cpp:99
Slice::applyLowerBound
bool applyLowerBound()
Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with ...
Definition Slice.cpp:289
Slice::getLowerBound
virtual bool getLowerBound(Term &bound, size_t var) const =0
Calculates a lower bound that depends on var.
Slice::getIdeal
const Ideal & getIdeal() const
Returns for a slice .
Definition Slice.h:104
Slice::getLcm
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition Slice.cpp:52
Slice::_lcmUpdated
bool _lcmUpdated
Indicates whether _lcm is correct.
Definition Slice.h:293
Slice::_subtract
Ideal _subtract
The of a slice .
Definition Slice.h:269
Slice::getVarCount
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition Slice.h:96
Slice::~Slice
virtual ~Slice()
Definition Slice.cpp:47
Slice::dispose
virtual void dispose()
Called when the task is no longer used but run has not and will not be called.
Definition Slice.cpp:325
Slice::getSubtract
Ideal & getSubtract()
Returns for a slice .
Definition Slice.h:107
Slice::simplify
virtual bool simplify()
Simplifies this object such that it may become simpler without changing the content.
Definition Slice.cpp:204
StrictMultiplePredicate
Definition Slice.cpp:147
StrictMultiplePredicate::_varCount
size_t _varCount
Definition Slice.cpp:159
StrictMultiplePredicate::operator()
bool operator()(const Exponent *term)
Definition Slice.cpp:153
StrictMultiplePredicate::StrictMultiplePredicate
StrictMultiplePredicate(const Exponent *term, size_t varCount)
Definition Slice.cpp:149
StrictMultiplePredicate::_term
const Exponent * _term
Definition Slice.cpp:158
TaskEngine
TaskEngine handles a list of tasks that are to be carried out.
Definition TaskEngine.h:40
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::decrement
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition Term.h:532
Term::getSizeOfSupport
static size_t getSizeOfSupport(const Exponent *a, size_t varCount)
Returns the number of variables such that divides .
Definition Term.h:402
Term::strictlyDivides
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
Definition Term.h:196
Term::getVarCount
size_t getVarCount() const
Definition Term.h:85
Term::getFirstNonZeroExponent
static size_t getFirstNonZeroExponent(const Exponent *a, size_t varCount)
Returns least var such that a[var] is non-zero.
Definition Term.h:346
Term::isIdentity
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition Term.h:316
Term::getFirstNonZeroExponent
size_t getFirstNonZeroExponent() const
Definition Term.h:354
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