BigattiBaseCase.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 "BigattiBaseCase.h"
#include "BigattiState.h"
#include "TermTranslator.h"
#include <algorithm>
BigattiBaseCase::BigattiBaseCase(const TermTranslator& translator):
_maxCount(translator.getVarCount()),
_lcm(translator.getVarCount()),
_outputMultivariate(translator.getVarCount()),
_computeUnivariate(false),
_translator(translator),
_totalBaseCasesEver(0),
_totalTermsOutputEver(0),
_printDebug(false) {
}
bool BigattiBaseCase::genericBaseCase(const BigattiState& state) {
if (baseCase(state))
return true;
if (!state.getIdeal().isWeaklyGeneric())
return false;
enumerateScarfComplex(state, false);
++_totalBaseCasesEver;
return true;
}
bool BigattiBaseCase::baseCase(const BigattiState& state) {
ASSERT(_maxCount.size() == state.getVarCount());
if (simpleBaseCase(state))
return true;
if (state.getIdeal().getGeneratorCount() > state.getVarCount())
return false;
state.getIdeal().getLcm(_lcm);
if (state.getIdeal().getGeneratorCount() > _lcm.getSizeOfSupport())
return false;
fill(_maxCount.begin(), _maxCount.end(), 0);
Ideal::const_iterator end = state.getIdeal().end();
Ideal::const_iterator it = state.getIdeal().begin();
for (; it != end; ++it) {
bool hasMax = false;
for (size_t var = 0; var < state.getVarCount(); ++var) {
ASSERT((*it)[var] <= _lcm[var]);
if ((*it)[var] == _lcm[var] && _lcm[var] > 0) {
hasMax = true;
_maxCount[var] += 1;
if (_maxCount[var] > 1)
return false;
}
}
if (!hasMax)
return false;
}
enumerateScarfComplex(state, true);
++_totalBaseCasesEver;
return true;
}
void BigattiBaseCase::output(bool plus, const Term& term) {
if (_printDebug) {
fputs("Debug: Outputting term ", stderr);
fputc(plus ? '+' : '-', stderr);
term.print(stderr);
fputs(".\n", stderr);
}
++_totalTermsOutputEver;
if (_computeUnivariate) {
if (term.getVarCount() == 0)
_tmp = 0;
else
_tmp = _translator.getExponent(0, term);
for (size_t var = 1; var < term.getVarCount(); ++var)
_tmp += _translator.getExponent(var, term);
_outputUnivariate.add(plus, _tmp);
} else
_outputMultivariate.add(plus, term);
}
void BigattiBaseCase::feedOutputTo
(CoefBigTermConsumer& consumer,
bool inCanonicalOrder) {
if (_computeUnivariate)
_outputUnivariate.feedTo(consumer, inCanonicalOrder);
else
_outputMultivariate.feedTo(_translator, consumer, inCanonicalOrder);
}
void BigattiBaseCase::setPrintDebug(bool value) {
_printDebug = value;
}
void BigattiBaseCase::setComputeUnivariate(bool value) {
_computeUnivariate = value;
}
size_t BigattiBaseCase::getTotalBaseCasesEver() const {
return _totalBaseCasesEver;
}
size_t BigattiBaseCase::getTotalTermsOutputEver() const {
return _totalTermsOutputEver;
}
size_t BigattiBaseCase::getTotalTermsInOutput() const {
if (_computeUnivariate)
return _outputUnivariate.getTermCount();
else
return _outputMultivariate.getTermCount();
}
bool BigattiBaseCase::simpleBaseCase(const BigattiState& state) {
const Ideal& ideal = state.getIdeal();
size_t genCount = ideal.getGeneratorCount();
const Term& multiply = state.getMultiply();
if (genCount > 2)
return false;
output(true, multiply);
if (genCount == 0)
return true;
_lcm.product(multiply, ideal[0]);
output(false, _lcm);
if (genCount == 1)
return true;
ASSERT(genCount == 2);
_lcm.product(multiply, ideal[1]);
output(false, _lcm);
_lcm.lcm(ideal[0], ideal[1]);
_lcm.product(_lcm, multiply);
output(true, _lcm);
++_totalBaseCasesEver;
return true;
}
bool BigattiBaseCase::univariateAllFaces(const BigattiState& state) {
ASSERT(_computeUnivariate);
const Ideal& ideal = state.getIdeal();
const Term& multiply = state.getMultiply();
if (!ideal.disjointSupport())
return false;
if (ideal.getGeneratorCount() > 30)
return false; // Coefficients may not fit in 32 bits
Term max(ideal.getVarCount());
ideal.getLcm(max);
max.product(max, multiply);
_tmp = 0;
for (size_t var = 0; var < max.getVarCount(); ++var)
_tmp += _translator.getExponent(var, max);
if (_tmp > 1024*1024)
return false; // Too high memory requirement.
ASSERT(_tmp.fits_uint_p());
size_t maxDegree = _tmp.get_ui();
size_t approxWorkForScarfComplex = (1 << ideal.getGeneratorCount());
if (approxWorkForScarfComplex < maxDegree)
return false; // Scarf complex is on par or faster.
// At this point we have made sure that this instance makes sense to
// solve using this method. We have also determined that we can do
// everything in machine ints.
vector<int> poly;
poly.reserve(maxDegree);
poly.push_back(1);
// TODO: sort with smallest first to decrease work in early
// iterations.
for (size_t i = 0; i < ideal.getGeneratorCount(); ++i) {
ASSERT(poly.back() != 0);
const Exponent* gen = ideal[i];
// calculate degree
int degree = 0;
for (size_t var = 0; var < max.getVarCount(); ++var)
degree += _translator.getExponent(var, multiply[var] + gen[var]).get_ui()
- _translator.getExponent(var, multiply[var]).get_ui();
// replace poly P by (1-t^degree)*P = P-P*t^degree.
size_t oldSize = poly.size();
poly.resize(oldSize + degree);
for (size_t e = oldSize; e > 0;) {
--e;
poly[e+degree] -= poly[e];
}
}
int degree = 0;
for (size_t var = 0; var < max.getVarCount(); ++var)
degree += _translator.getExponent(var, multiply).get_ui();
for (size_t e = 0; e < poly.size(); ++e) {
if (_printDebug) {
fprintf(stderr, "Debug: Outputting term %i*t^%u.\n",
poly[e], (unsigned int)(e + degree));
}
++_totalTermsOutputEver;
_outputUnivariate.add(poly[e], e+degree);
}
return true;
}
void BigattiBaseCase::enumerateScarfComplex(const BigattiState& state,
bool allFaces) {
if (allFaces &&
_computeUnivariate &&
univariateAllFaces(state)) {
return;
}
const Ideal& ideal = state.getIdeal();
// Set up _states with enough entries of the right size.
size_t needed = ideal.getGeneratorCount() + 1;
if (_states.size() < needed)
_states.resize(needed);
for (size_t i = 0; i < _states.size(); ++i)
_states[i].term.reset(state.getVarCount());
// Set up the initial state
ASSERT(!ideal.isZeroIdeal());
_states[0].plus = true;
_states[0].pos = ideal.begin();
ASSERT(_states[0].term.isIdentity());
// Cache this to avoid repeated calls to end().
Ideal::const_iterator stop = ideal.end();
// Iterate until all states are done. The active entries of _states
// are those from index 0 up to and including _current.
size_t current = 0;
while (true) {
ASSERT(current < _states.size());
State& currentState = _states[current];
if (currentState.pos == stop) {
// This is a base case since we have considered all minimal
// generators.
_lcm.product(currentState.term, state.getMultiply());
output(currentState.plus, _lcm);
// We are done with this entry, so go back to the previous
// active entry.
if (current == 0)
break; // Nothing remains to be done.
--current;
} else {
// Split into two cases according to whether we put the minimal
// generator at pos into the face or not.
ASSERT(current + 1 < _states.size());
State& next = _states[current + 1];
next.term.lcm(currentState.term, *currentState.pos);
++currentState.pos;
if (allFaces || !ideal.strictlyContains(next.term)) {
// If allFaces is true we do not need to check the condition
// since we know it should always hold.
ASSERT(!ideal.strictlyContains(next.term));
next.plus = !currentState.plus;
next.pos = currentState.pos;
++current;
}
}
}
}
BigattiBaseCase.h
BigattiState.h
TermTranslator.h
BigattiBaseCase::BigattiBaseCase
BigattiBaseCase(const TermTranslator &translator)
Initialize this object to handle the computation of Hilbert-Poincare series numerator polynomials in ...
Definition BigattiBaseCase.cpp:25
BigattiBaseCase::_tmp
mpz_class _tmp
Definition BigattiBaseCase.h:98
BigattiBaseCase::_totalBaseCasesEver
size_t _totalBaseCasesEver
For statistics.
Definition BigattiBaseCase.h:128
BigattiBaseCase::getTotalTermsOutputEver
size_t getTotalTermsOutputEver() const
Returns the total number of terms this object has output.
Definition BigattiBaseCase.cpp:128
BigattiBaseCase::setPrintDebug
void setPrintDebug(bool value)
Starts to print debug output on what happens if value is true.
Definition BigattiBaseCase.cpp:116
BigattiBaseCase::_lcm
Term _lcm
Definition BigattiBaseCase.h:97
BigattiBaseCase::genericBaseCase
bool genericBaseCase(const BigattiState &state)
Returns ture if state is a base case slice while also considering genericity.
Definition BigattiBaseCase.cpp:36
BigattiBaseCase::_printDebug
bool _printDebug
Definition BigattiBaseCase.h:133
BigattiBaseCase::univariateAllFaces
bool univariateAllFaces(const BigattiState &state)
Definition BigattiBaseCase.cpp:168
BigattiBaseCase::getTotalBaseCasesEver
size_t getTotalBaseCasesEver() const
Returns the total number of base cases this object has seen.
Definition BigattiBaseCase.cpp:124
BigattiBaseCase::setComputeUnivariate
void setComputeUnivariate(bool value)
Use the fine grading if value is false, otherwise grade each variable by the same variable t.
Definition BigattiBaseCase.cpp:120
BigattiBaseCase::_maxCount
vector< size_t > _maxCount
Definition BigattiBaseCase.h:96
BigattiBaseCase::simpleBaseCase
bool simpleBaseCase(const BigattiState &state)
Computes the Hilbert-Poincare series of state and returns true if state is a particularly simple and ...
Definition BigattiBaseCase.cpp:139
BigattiBaseCase::_computeUnivariate
bool _computeUnivariate
Use the fine grading if false, otherwise grade each variable by the same variable t.
Definition BigattiBaseCase.h:122
BigattiBaseCase::baseCase
bool baseCase(const BigattiState &state)
Returns true if state is a base case slice without considering genericity.
Definition BigattiBaseCase.cpp:49
BigattiBaseCase::enumerateScarfComplex
void enumerateScarfComplex(const BigattiState &state, bool allFaces)
The ideal in state must be weakly generic.
Definition BigattiBaseCase.cpp:241
BigattiBaseCase::_outputMultivariate
HashPolynomial _outputMultivariate
The part of the finely graded Hilbert-Poincare numerator polynomial computed so far.
Definition BigattiBaseCase.h:102
BigattiBaseCase::_translator
const TermTranslator & _translator
Used to translate the output from ints.
Definition BigattiBaseCase.h:125
BigattiBaseCase::_totalTermsOutputEver
size_t _totalTermsOutputEver
For statistics.
Definition BigattiBaseCase.h:131
BigattiBaseCase::_states
vector< State > _states
Used in enumerateScarfCompex.
Definition BigattiBaseCase.h:118
BigattiBaseCase::output
void output(bool plus, const Term &term)
Add +term or -term to the output polynomial when plus is true or false respectively.
Definition BigattiBaseCase.cpp:86
BigattiBaseCase::_outputUnivariate
UniHashPolynomial _outputUnivariate
The part of the coarsely graded Hilbert-Poincare numerator polynomial computed so far.
Definition BigattiBaseCase.h:106
BigattiBaseCase::feedOutputTo
void feedOutputTo(CoefBigTermConsumer &consumer, bool inCanonicalOrder)
Feed the output Hilbert-Poincare numerator polynomial computed so far to the consumer.
Definition BigattiBaseCase.cpp:108
BigattiBaseCase::getTotalTermsInOutput
size_t getTotalTermsInOutput() const
Returns the number of terms in the output polynomial right now.
Definition BigattiBaseCase.cpp:132
BigattiState
Definition BigattiState.h:27
BigattiState::getMultiply
const Term & getMultiply() const
Definition BigattiState.cpp:37
BigattiState::getVarCount
size_t getVarCount() const
Definition BigattiState.cpp:49
BigattiState::getIdeal
const Ideal & getIdeal() const
Definition BigattiState.cpp:33
CoefBigTermConsumer
Definition CoefBigTermConsumer.h:29
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::isZeroIdeal
bool isZeroIdeal() const
Definition Ideal.cpp:86
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::strictlyContains
bool strictlyContains(const Exponent *term) const
Definition Ideal.cpp:73
Ideal::disjointSupport
bool disjointSupport() const
Returns true if all pairs of generators have disjoint support.
Definition Ideal.cpp:142
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
Ideal::isWeaklyGeneric
bool isWeaklyGeneric() const
Definition Ideal.cpp:121
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
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::product
static void product(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the product of a and b.
Definition Term.h:280
Term::getVarCount
size_t getVarCount() const
Definition Term.h:85
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::lcm
static void lcm(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the least commom multiple of a and b.
Definition Term.h:221
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
BigattiBaseCase::State
Used in enumerateScarfComplex and necessary to have here to define _states.
Definition BigattiBaseCase.h:110
BigattiBaseCase::State::pos
Ideal::const_iterator pos
Definition BigattiBaseCase.h:112
BigattiBaseCase::State::plus
bool plus
Definition BigattiBaseCase.h:113
BigattiBaseCase::State::term
Term term
Definition BigattiBaseCase.h:111