BigattiHilbertAlgorithm.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 "BigattiHilbertAlgorithm.h"
#include "Ideal.h"
#include "CoefBigTermConsumer.h"
#include "BigattiState.h"
BigattiHilbertAlgorithm::
BigattiHilbertAlgorithm
(unique_ptr<Ideal> ideal,
const TermTranslator& translator,
const BigattiParams& params,
unique_ptr<BigattiPivotStrategy> pivot,
CoefBigTermConsumer& consumer):
_translator(translator),
_consumer(&consumer),
_baseCase(translator),
_pivot(std::move(pivot)),
_computeUnivariate(false),
_params(params) {
ASSERT(ideal.get() != 0);
ASSERT(ideal->isMinimallyGenerated());
_varCount = ideal->getVarCount();
_tmp_simplify_gcd.reset(_varCount);
_baseCase.setPrintDebug(_params.getPrintDebug());
// TODO: use swap to avoid copy of ideal.
_tasks.addTask(new BigattiState(this, *ideal, Term(_varCount)));
}
void BigattiHilbertAlgorithm::setComputeUnivariate(bool value) {
_computeUnivariate = value;
}
void BigattiHilbertAlgorithm::run() {
if (_pivot.get() == 0)
_pivot = BigattiPivotStrategy::createStrategy("median", true);
_baseCase.setComputeUnivariate(_computeUnivariate);
_tasks.runTasks();
_baseCase.feedOutputTo(*_consumer, _params.getProduceCanonicalOutput());
if (_params.getPrintStatistics()) {
fputs("*** Statistics for run of Bigatti algorithm ***\n", stderr);
fprintf(stderr, " %u states processed.\n",
(unsigned int)_tasks.getTotalTasksEver());
fprintf(stderr, " %u base cases.\n",
(unsigned int)_baseCase.getTotalBaseCasesEver());
fprintf(stderr, " %u terms output.\n",
(unsigned int)_baseCase.getTotalTermsOutputEver());
fprintf(stderr, " %u terms in final output.\n",
(unsigned int)_baseCase.getTotalTermsInOutput());
}
}
void BigattiHilbertAlgorithm::processState(unique_ptr<BigattiState> state) {
if (_params.getUseSimplification())
simplify(*state);
if (_params.getPrintDebug()) {
fputs("Debug: Processing state.\n", stderr);
state->print(stderr);
}
bool isBaseCase = _params.getUseGenericBaseCase() ?
_baseCase.genericBaseCase(*state) :
_baseCase.baseCase(*state);
if (isBaseCase) {
freeState(std::move(state));
return;
}
const Term& pivot = _pivot->getPivot(*state);
if (_params.getPrintDebug()) {
fputs("Debug: Performing pivot split on ", stderr);
pivot.print(stderr);
fputs(".\n", stderr);
}
ASSERT(!pivot.isIdentity());
ASSERT(!state->getIdeal().contains(pivot));
unique_ptr<BigattiState> colonState(_stateCache.newObjectCopy(*state));
colonState->colonStep(pivot);
_tasks.addTask(colonState.release());
state->addStep(pivot);
_tasks.addTask(state.release());
}
void BigattiHilbertAlgorithm::simplify(BigattiState& state) {
Term& gcd = _tmp_simplify_gcd;
ASSERT(gcd.getVarCount() == _varCount);
state.getIdeal().getGcd(gcd);
if (!gcd.isIdentity()) {
// Do colon and output multiply-gcd*multiply.
_baseCase.output(true, state.getMultiply());
state.colonStep(gcd);
_baseCase.output(false, state.getMultiply());
}
IF_DEBUG(state.getIdeal().getGcd(gcd));
ASSERT(gcd.isIdentity());
}
void BigattiHilbertAlgorithm::freeState(unique_ptr<BigattiState> state) {
state->getIdeal().clear(); // To preserve memory
_stateCache.freeObject(std::move(state));
}
BigattiHilbertAlgorithm.h
BigattiState.h
CoefBigTermConsumer.h
Ideal.h
BigattiHilbertAlgorithm::freeState
void freeState(unique_ptr< BigattiState > state)
Definition BigattiHilbertAlgorithm.cpp:125
BigattiHilbertAlgorithm::_pivot
unique_ptr< BigattiPivotStrategy > _pivot
Definition BigattiHilbertAlgorithm.h:70
BigattiHilbertAlgorithm::_varCount
size_t _varCount
Definition BigattiHilbertAlgorithm.h:59
BigattiHilbertAlgorithm::BigattiHilbertAlgorithm
BigattiHilbertAlgorithm(unique_ptr< Ideal > ideal, const TermTranslator &translator, const BigattiParams &params, unique_ptr< BigattiPivotStrategy > pivot, CoefBigTermConsumer &consumer)
Construct an object for running the Bigatti et.al.
Definition BigattiHilbertAlgorithm.cpp:27
BigattiHilbertAlgorithm::_consumer
CoefBigTermConsumer * _consumer
Definition BigattiHilbertAlgorithm.h:61
BigattiHilbertAlgorithm::_params
BigattiParams _params
Definition BigattiHilbertAlgorithm.h:73
BigattiHilbertAlgorithm::_tasks
TaskEngine _tasks
Definition BigattiHilbertAlgorithm.h:62
BigattiHilbertAlgorithm::_baseCase
BigattiBaseCase _baseCase
Definition BigattiHilbertAlgorithm.h:68
BigattiHilbertAlgorithm::simplify
void simplify(BigattiState &state)
Definition BigattiHilbertAlgorithm.cpp:109
BigattiHilbertAlgorithm::_tmp_simplify_gcd
Term _tmp_simplify_gcd
Definition BigattiHilbertAlgorithm.h:66
BigattiHilbertAlgorithm::_computeUnivariate
bool _computeUnivariate
Definition BigattiHilbertAlgorithm.h:72
BigattiHilbertAlgorithm::setComputeUnivariate
void setComputeUnivariate(bool value)
Definition BigattiHilbertAlgorithm.cpp:50
BigattiHilbertAlgorithm::_stateCache
ObjectCache< BigattiState > _stateCache
Definition BigattiHilbertAlgorithm.h:63
BigattiHilbertAlgorithm::run
void run()
Definition BigattiHilbertAlgorithm.cpp:54
BigattiHilbertAlgorithm::processState
void processState(unique_ptr< BigattiState > state)
Definition BigattiHilbertAlgorithm.cpp:75
BigattiHilbertAlgorithm::BigattiState
friend class BigattiState
Definition BigattiHilbertAlgorithm.h:75
BigattiHilbertAlgorithm::_translator
const TermTranslator & _translator
Definition BigattiHilbertAlgorithm.h:60
BigattiParams
Definition BigattiParams.h:25
BigattiState::colonStep
void colonStep(const Term &term)
Definition BigattiState.cpp:79
BigattiState::getMultiply
const Term & getMultiply() const
Definition BigattiState.cpp:37
BigattiState::getIdeal
const Ideal & getIdeal() const
Definition BigattiState.cpp:33
CoefBigTermConsumer
Definition CoefBigTermConsumer.h:29
Ideal::getGcd
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
Definition Ideal.cpp:164
TermTranslator
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Definition TermTranslator.h:41
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::print
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
Definition Term.cpp:110
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
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
IF_DEBUG
#define IF_DEBUG(X)
Definition stdinc.h:85
ASSERT
#define ASSERT(X)
Definition stdinc.h:86