HilbertSlice.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 "HilbertSlice.h"
#include "CoefTermConsumer.h"
#include "HilbertBasecase.h"
#include "HilbertStrategy.h"
HilbertSlice::HilbertSlice(HilbertStrategy& strategy):
Slice(strategy),
_consumer(0) {
}
HilbertSlice::HilbertSlice(HilbertStrategy& strategy,
const Ideal& ideal, const Ideal& subtract,
const Term& multiply, CoefTermConsumer* consumer):
Slice(strategy, ideal, subtract, multiply),
_consumer(consumer) {
ASSERT(consumer != 0);
}
bool HilbertSlice::baseCase(bool simplified) {
ASSERT(_consumer != 0);
// Check that each variable appears in some minimal generator.
if (getLcm().getSizeOfSupport() < _varCount)
return true;
if (!getLcm().isSquareFree())
return false;
if (_varCount == 0)
return true;
// TODO: find a way other than static to use the same basecase
// object every time, instead of allocating a new one. This provides
// around a 4% speed-up, at least on Cygwin. We cannot use static
// since the base case has an mpz_class, and static mpz_class
// crashes on Mac OS X.
HilbertBasecase basecase;
basecase.computeCoefficient(_ideal);
const mpz_class& coef = basecase.getLastCoefficient();
if (coef != 0)
_consumer->consume(coef, getMultiply());
clearIdealAndSubtract();
return true;
}
Slice& HilbertSlice::operator=(const Slice& slice) {
ASSERT(dynamic_cast<const HilbertSlice*>(&slice) != 0);
Slice::operator=(slice);
_consumer = ((HilbertSlice&)slice)._consumer;
return *this;
}
bool HilbertSlice::simplifyStep() {
if (applyLowerBound())
return true;
pruneSubtract();
return false;
}
void HilbertSlice::setToProjOf(const Slice& slice,
const Projection& projection,
CoefTermConsumer* consumer) {
ASSERT(consumer != 0);
Slice::setToProjOf(slice, projection);
_consumer = consumer;
}
void HilbertSlice::swap(HilbertSlice& slice) {
Slice::swap(slice);
std::swap(_consumer, slice._consumer);
}
bool HilbertSlice::getLowerBound(Term& bound, size_t var) const {
bool seenAny = false;
Ideal::const_iterator stop = getIdeal().end();
for (Ideal::const_iterator it = getIdeal().begin(); it != stop; ++it) {
if ((*it)[var] == 0)
continue;
if (seenAny)
bound.gcd(bound, *it);
else {
bound = *it;
seenAny = true;
}
}
if (seenAny) {
ASSERT(bound[var] >= 1);
bound.decrement();
return true;
} else {
// In this case the content is empty.
return false;
}
}
CoefTermConsumer.h
HilbertBasecase.h
HilbertSlice.h
HilbertStrategy.h
CoefTermConsumer
Definition CoefTermConsumer.h:24
HilbertBasecase
Definition HilbertBasecase.h:27
HilbertBasecase::computeCoefficient
void computeCoefficient(Ideal &ideal)
Definition HilbertBasecase.cpp:131
HilbertBasecase::getLastCoefficient
const mpz_class & getLastCoefficient()
Definition HilbertBasecase.cpp:190
HilbertSlice::setToProjOf
void setToProjOf(const Slice &slice, const Projection &projection, CoefTermConsumer *consumer)
Definition HilbertSlice.cpp:81
HilbertSlice::getLowerBound
virtual bool getLowerBound(Term &bound, size_t var) const
Calculates a lower bound that depends on var.
Definition HilbertSlice.cpp:95
HilbertSlice::baseCase
virtual bool baseCase(bool simplified)
Returns true if this slice is a base case slice, and in that case produces output in a derivative-spe...
Definition HilbertSlice.cpp:37
HilbertSlice::operator=
virtual Slice & operator=(const Slice &slice)
Performs a deep copy of slice into this object.
Definition HilbertSlice.cpp:65
HilbertSlice::simplifyStep
virtual bool simplifyStep()
Like simplify(), except that only one simplification step is performed.
Definition HilbertSlice.cpp:73
HilbertSlice::HilbertSlice
HilbertSlice(HilbertStrategy &strategy)
Definition HilbertSlice.cpp:24
HilbertSlice::_consumer
CoefTermConsumer * _consumer
Definition HilbertSlice.h:59
HilbertSlice::swap
void swap(HilbertSlice &slice)
Definition HilbertSlice.cpp:90
HilbertStrategy
Definition HilbertStrategy.h:33
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::end
const_iterator end() const
Definition Ideal.h:49
Projection
Definition Projection.h:29
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::operator=
virtual Slice & operator=(const Slice &slice)=0
Performs a deep copy of slice into this object.
Definition Slice.cpp:77
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::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::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::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
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::gcd
static void gcd(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the greatest common divisor of a and b.
Definition Term.h:255
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