SliceFacade.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 "SliceFacade.h"
#include "BigTermConsumer.h"
#include "CoefBigTermConsumer.h"
#include "TermTranslator.h"
#include "BigIdeal.h"
#include "Ideal.h"
#include "Term.h"
#include "MsmStrategy.h"
#include "TranslatingTermConsumer.h"
#include "TranslatingCoefTermConsumer.h"
#include "DebugStrategy.h"
#include "DecomRecorder.h"
#include "TermGrader.h"
#include "OptimizeStrategy.h"
#include "CanonicalCoefTermConsumer.h"
#include "HilbertStrategy.h"
#include "IOHandler.h"
#include "BigPolynomial.h"
#include "TotalDegreeCoefTermConsumer.h"
#include "CoefBigTermRecorder.h"
#include "CanonicalTermConsumer.h"
#include "VarSorter.h"
#include "StatisticsStrategy.h"
#include "IrreducibleIdealSplitter.h"
#include "SizeMaxIndepSetAlg.h"
#include "SliceParams.h"
#include "error.h"
#include "display.h"
#include <iterator>
SliceFacade::SliceFacade(const SliceParams& params, const DataType& output):
Facade(params.getPrintActions()),
_params(params) {
_split = SplitStrategy::createStrategy(params.getSplit().c_str());
_common.readIdealAndSetOutput(params, output);
}
SliceFacade::SliceFacade(const SliceParams& params,
const BigIdeal& ideal,
BigTermConsumer& consumer):
Facade(params.getPrintActions()),
_params(params) {
_split = SplitStrategy::createStrategy(params.getSplit().c_str());
_common.setIdealAndIdealOutput(params, ideal, consumer);
}
SliceFacade::SliceFacade(const SliceParams& params,
const BigIdeal& ideal,
CoefBigTermConsumer& consumer):
Facade(params.getPrintActions()),
_params(params) {
_split = SplitStrategy::createStrategy(params.getSplit().c_str());
_common.setIdealAndPolyOutput(params, ideal, consumer);
}
SliceFacade::~SliceFacade() {
}
void SliceFacade::computeMultigradedHilbertSeries() {
ASSERT(isFirstComputation());
beginAction("Computing multigraded Hilbert-Poincare series.");
unique_ptr<CoefTermConsumer> consumer = _common.makeTranslatedPolyConsumer();
consumer->consumeRing(_common.getNames());
consumer->beginConsuming();
HilbertStrategy strategy(consumer.get(), _split.get());
runSliceAlgorithmWithOptions(strategy);
consumer->doneConsuming();
endAction();
}
void SliceFacade::computeUnivariateHilbertSeries() {
ASSERT(isFirstComputation());
beginAction("Computing univariate Hilbert-Poincare series.");
unique_ptr<CoefTermConsumer> consumer =
_common.makeToUnivariatePolyConsumer();
consumer->consumeRing(_common.getNames());
consumer->beginConsuming();
HilbertStrategy strategy(consumer.get(), _split.get());
runSliceAlgorithmWithOptions(strategy);
consumer->doneConsuming();
endAction();
}
void SliceFacade::computeIrreducibleDecomposition(bool encode) {
ASSERT(isFirstComputation());
produceEncodedIrrDecom(*_common.makeTranslatedIdealConsumer(!encode));
}
mpz_class SliceFacade::computeDimension(bool codimension) {
ASSERT(isFirstComputation());
if (_common.getIdeal().containsIdentity()) {
if (codimension) {
// convert to mpz_class before increment to ensure no overflow.
return mpz_class(_common.getIdeal().getVarCount()) + 1;
} else
return -1;
}
// todo: inline?
takeRadical();
beginAction("Preparing to compute dimension.");
vector<mpz_class> v;
fill_n(back_inserter(v), _common.getIdeal().getVarCount(), -1);
endAction();
mpz_class minusCodimension;
#ifdef DEBUG
// Only define hasComponents when DEBUG is defined since otherwise
// GCC will warn about hasComponents not being used.
bool hasComponents =
#endif
solveIrreducibleDecompositionProgram(v, minusCodimension, false);
ASSERT(hasComponents);
if (codimension)
return -minusCodimension;
else
return v.size() + minusCodimension;
}
void SliceFacade::computePrimaryDecomposition() {
ASSERT(isFirstComputation());
size_t varCount = _common.getIdeal().getVarCount();
Ideal irreducibleDecom(varCount);
{
DecomRecorder recorder(&irreducibleDecom);
produceEncodedIrrDecom(recorder);
}
beginAction
("Computing primary decomposition from irreducible decomposition.");
// Do intersection of each component also using irreducible
// decomposition of the dual. We can't use the Alexander dual
// methods, since those switch around the translator to emit altered
// big integers, while keeping the small integers the same, but we
// want to keep this in small integers. So we have to do the dual
// thing here.
// To get actual supports.
_common.getTranslator().setInfinityPowersToZero(irreducibleDecom);
// To collect same-support vectors together.
irreducibleDecom.sortReverseLex();
Term lcm(varCount);
irreducibleDecom.getLcm(lcm);
Term tmp(varCount);
Term support(varCount);
_common.getIdeal().clear();
Ideal& primaryComponentDual = _common.getIdeal();
Ideal primaryComponent(varCount);
DecomRecorder recorder(&primaryComponent);
unique_ptr<TermConsumer> consumer = _common.makeTranslatedIdealConsumer();
consumer->consumeRing(_common.getNames());
consumer->beginConsumingList();
Ideal::const_iterator stop = irreducibleDecom.end();
Ideal::const_iterator it = irreducibleDecom.begin();
while (it != stop) {
// Get all vectors with same support.
support = *it;
do {
tmp.encodedDual(*it, lcm);
primaryComponentDual.insert(tmp);
++it;
} while (it != stop && support.hasSameSupport(*it));
ASSERT(!primaryComponentDual.isZeroIdeal());
_common.getTranslator().addPurePowersAtInfinity(primaryComponentDual);
{
MsmStrategy strategy(&recorder, _split.get());
runSliceAlgorithmWithOptions(strategy);
}
_common.getTranslator().setInfinityPowersToZero(primaryComponent);
consumer->beginConsuming();
for (Ideal::const_iterator dualTerm = primaryComponent.begin();
dualTerm != primaryComponent.end(); ++dualTerm) {
tmp.encodedDual(*dualTerm, lcm);
consumer->consume(tmp);
}
consumer->doneConsuming();
primaryComponent.clear();
primaryComponentDual.clear();
}
consumer->doneConsumingList();
endAction();
}
void SliceFacade::computeMaximalStaircaseMonomials() {
ASSERT(isFirstComputation());
beginAction("Computing maximal staircase monomials.");
unique_ptr<TermConsumer> consumer = _common.makeTranslatedIdealConsumer();
consumer->consumeRing(_common.getNames());
MsmStrategy strategy(consumer.get(), _split.get());
runSliceAlgorithmWithOptions(strategy);
endAction();
}
void SliceFacade::computeMaximalStandardMonomials() {
ASSERT(isFirstComputation());
beginAction("Preparing to compute maximal standard monomials.");
_common.getTranslator().decrement();
endAction();
computeMaximalStaircaseMonomials();
}
void SliceFacade::computeAlexanderDual(const vector<mpz_class>& point) {
ASSERT(isFirstComputation());
ASSERT(point.size() == _common.getIdeal().getVarCount());
beginAction("Ensuring specified point is divisible by lcm.");
vector<mpz_class> lcm;
getLcmOfIdeal(lcm);
for (size_t var = 0; var < lcm.size(); ++var) {
if (lcm[var] > point[var]) {
endAction();
reportError
("The specified point to dualize on is not divisible by the "
"least common multiple of the minimal generators of the ideal.");
}
}
endAction();
beginAction("Preparing to compute Alexander dual.");
_common.getTranslator().dualize(point);
endAction();
produceEncodedIrrDecom(*_common.makeTranslatedIdealConsumer());
}
void SliceFacade::computeAlexanderDual() {
ASSERT(isFirstComputation());
beginAction("Computing lcm for Alexander dual.");
vector<mpz_class> lcm;
getLcmOfIdeal(lcm);
endAction();
computeAlexanderDual(lcm);
}
void SliceFacade::computeAssociatedPrimes() {
ASSERT(isFirstComputation());
size_t varCount = _common.getIdeal().getVarCount();
// Obtain generators of radical from irreducible decomposition.
Ideal radical(varCount);
{
Ideal decom(varCount);
DecomRecorder recorder(&decom);
produceEncodedIrrDecom(recorder);
beginAction("Computing associated primes from irreducible decomposition.");
Term tmp(varCount);
Ideal::const_iterator stop = decom.end();
for (Ideal::const_iterator it = decom.begin(); it != stop; ++it) {
for (size_t var = 0; var < varCount; ++var) {
// We cannot just check whether (*it)[var] == 0, since the
// added fake pure powers map to zero but are not themselves
// zero.
if (_common.getTranslator().getExponent(var, (*it)[var]) == 0)
tmp[var] = 0;
else
tmp[var] = 1;
}
radical.insert(tmp);
}
}
radical.removeDuplicates();
// Output associated primes.
setToZeroOne(_common.getTranslator());
unique_ptr<TermConsumer> consumer = _common.makeTranslatedIdealConsumer();
consumer->consumeRing(_common.getNames());
consumer->beginConsuming();
Term tmp(varCount);
Ideal::const_iterator stop = radical.end();
for (Ideal::const_iterator it = radical.begin(); it != stop; ++it) {
tmp = *it;
consumer->consume(tmp);
}
consumer->doneConsuming();
endAction();
}
bool SliceFacade::solveIrreducibleDecompositionProgram
(const vector<mpz_class>& grading,
mpz_class& optimalValue,
bool reportAllSolutions) {
ASSERT(isFirstComputation());
ASSERT(grading.size() == _common.getIdeal().getVarCount());
beginAction("Preparing to solve optimization program.");
if (!_common.getIdeal().containsIdentity())
_common.addPurePowersAtInfinity();
endAction();
return solveProgram(grading, optimalValue, reportAllSolutions);
}
bool SliceFacade::solveStandardProgram
(const vector<mpz_class>& grading,
mpz_class& optimalValue,
bool reportAllSolutions) {
ASSERT(isFirstComputation());
ASSERT(grading.size() == _common.getIdeal().getVarCount());
_common.getTranslator().decrement();
return solveProgram(grading, optimalValue, reportAllSolutions);
}
void SliceFacade::produceEncodedIrrDecom(TermConsumer& consumer) {
ASSERT(isFirstComputation());
beginAction("Computing irreducible decomposition.");
_common.addPurePowersAtInfinity();
MsmStrategy strategy(&consumer, _split.get());
consumer.consumeRing(_common.getNames());
runSliceAlgorithmWithOptions(strategy);
endAction();
}
bool SliceFacade::solveProgram(const vector<mpz_class>& grading,
mpz_class& optimalValue,
bool reportAllSolutions) {
ASSERT(isFirstComputation());
ASSERT(grading.size() == _common.getIdeal().getVarCount());
if (_params.getUseIndependenceSplits()) {
displayNote
("Turning off Independence splits as they are not supported\n"
"for optimization.");
_params.useIndependenceSplits(false);
}
if (_params.getUseBoundSimplification() &&
!_params.getUseBoundElimination()) {
displayNote
("Bound simplification requires using the bound to eliminate\n"
"non-improving slices, which has been turned off. Am now turning\n"
"this on.");
_params.useBoundElimination(true);
}
beginAction("Solving optimization program.");
OptimizeStrategy::BoundSetting boundSetting;
if (_params.getUseBoundSimplification()) {
ASSERT(_params.getUseBoundElimination());
boundSetting = OptimizeStrategy::UseBoundToEliminateAndSimplify;
} else if (_params.getUseBoundElimination())
boundSetting = OptimizeStrategy::UseBoundToEliminate;
else
boundSetting = OptimizeStrategy::DoNotUseBound;
TermGrader grader(grading, _common.getTranslator());
OptimizeStrategy strategy
(grader, _split.get(), reportAllSolutions, boundSetting);
runSliceAlgorithmWithOptions(strategy);
endAction();
const Ideal& solution = strategy.getMaximalSolutions();
unique_ptr<TermConsumer> consumer = _common.makeTranslatedIdealConsumer();
consumer->consumeRing(_common.getNames());
consumer->consume(solution);
if (solution.isZeroIdeal())
return false;
else {
optimalValue = strategy.getMaximalValue();
return true;
}
}
bool SliceFacade::isFirstComputation() const {
return _common.hasIdeal();
}
void SliceFacade::takeRadical() {
ASSERT(isFirstComputation());
beginAction("Taking radical of ideal.");
bool skip = false;
Term lcm(_common.getIdeal().getVarCount());
_common.getIdeal().getLcm(lcm);
if (lcm.isSquareFree())
skip = true;
if (!skip) {
_common.getTranslator().setInfinityPowersToZero(_common.getIdeal());
_common.getIdeal().takeRadicalNoMinimize();
_common.getIdeal().minimize();
}
setToZeroOne(_common.getTranslator());
endAction();
}
void SliceFacade::getLcmOfIdeal(vector<mpz_class>& bigLcm) {
ASSERT(isFirstComputation());
Term lcm(_common.getIdeal().getVarCount());
_common.getIdeal().getLcm(lcm);
bigLcm.clear();
bigLcm.reserve(_common.getIdeal().getVarCount());
for (size_t var = 0; var < _common.getIdeal().getVarCount(); ++var)
bigLcm.push_back(_common.getTranslator().getExponent(var, lcm));
}
void SliceFacade::runSliceAlgorithmWithOptions(SliceStrategy& strategy) {
ASSERT(isFirstComputation());
strategy.setUseIndependence(_params.getUseIndependenceSplits());
strategy.setUseSimplification(_params.getUseSimplification());
SliceStrategy* strategyWithOptions = &strategy;
unique_ptr<SliceStrategy> debugStrategy;
if (_params.getPrintDebug()) {
debugStrategy.reset
(new DebugStrategy(strategyWithOptions, stderr));
strategyWithOptions = debugStrategy.get();
}
unique_ptr<SliceStrategy> statisticsStrategy;
if (_params.getPrintStatistics()) {
statisticsStrategy.reset
(new StatisticsStrategy(strategyWithOptions, stderr));
strategyWithOptions = statisticsStrategy.get();
}
ASSERT(strategyWithOptions != 0);
strategyWithOptions->run(_common.getIdeal());
}
BigIdeal.h
BigPolynomial.h
BigTermConsumer.h
CanonicalCoefTermConsumer.h
CanonicalTermConsumer.h
CoefBigTermConsumer.h
CoefBigTermRecorder.h
DebugStrategy.h
DecomRecorder.h
HilbertStrategy.h
IOHandler.h
Ideal.h
IrreducibleIdealSplitter.h
MsmStrategy.h
OptimizeStrategy.h
SizeMaxIndepSetAlg.h
SliceFacade.h
SliceParams.h
StatisticsStrategy.h
TermGrader.h
setToZeroOne
void setToZeroOne(TermTranslator &translator)
Definition TermTranslator.cpp:481
TermTranslator.h
Term.h
TotalDegreeCoefTermConsumer.h
TranslatingCoefTermConsumer.h
TranslatingTermConsumer.h
VarSorter.h
BigIdeal
Definition BigIdeal.h:27
BigTermConsumer
Definition BigTermConsumer.h:29
CoefBigTermConsumer
Definition CoefBigTermConsumer.h:29
DataType
The intention of this class is to describe the different kinds of mathematical structures that Frobby...
Definition DataType.h:29
DecomRecorder
Definition DecomRecorder.h:25
Facade::beginAction
void beginAction(const char *message)
Prints message to standard error if printing is turned on, and records the time when the action start...
Definition Facade.cpp:38
Facade::endAction
void endAction()
Prints to standard error the time since the last call to beginAction.
Definition Facade.cpp:51
Facade::Facade
Facade(bool printActions)
Constructs a facade that prints out what it is doing if printActions is true.
Definition Facade.cpp:20
HilbertStrategy
Definition HilbertStrategy.h:33
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::removeDuplicates
void removeDuplicates()
Definition Ideal.cpp:634
Ideal::isZeroIdeal
bool isZeroIdeal() const
Definition Ideal.cpp:86
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::sortReverseLex
void sortReverseLex()
Definition Ideal.cpp:510
Ideal::clear
void clear()
Definition Ideal.cpp:641
Ideal::insert
void insert(const Exponent *term)
Definition Ideal.cpp:455
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
MsmStrategy
Definition MsmStrategy.h:37
OptimizeStrategy
OptimizeStrategy optimizes a function on the maximal standard monomials of a monomial ideal using bra...
Definition OptimizeStrategy.h:43
OptimizeStrategy::BoundSetting
BoundSetting
The values of BoundSetting indicate how to use the bound.
Definition OptimizeStrategy.h:46
OptimizeStrategy::DoNotUseBound
@ DoNotUseBound
Make no use of the bound.
Definition OptimizeStrategy.h:48
OptimizeStrategy::UseBoundToEliminateAndSimplify
@ UseBoundToEliminateAndSimplify
Eliminate non-improving slices and simplify slices by trying to generate non-improving slices that ar...
Definition OptimizeStrategy.h:57
OptimizeStrategy::UseBoundToEliminate
@ UseBoundToEliminate
Eliminate non-improving slices, achieving a branch-and-bound algorithm in place of the usual backtrac...
Definition OptimizeStrategy.h:52
OptimizeStrategy::getMaximalSolutions
const Ideal & getMaximalSolutions()
Returns one of or all of the msm's with optimal value found so far, depending on the value of reportA...
Definition OptimizeStrategy.cpp:41
OptimizeStrategy::getMaximalValue
const mpz_class & getMaximalValue()
The optimal value associated to all entries from getMaximalSolutions().
Definition OptimizeStrategy.cpp:45
SliceFacade::_split
unique_ptr< SplitStrategy > _split
Definition SliceFacade.h:225
SliceFacade::~SliceFacade
~SliceFacade()
Definition SliceFacade.cpp:75
SliceFacade::takeRadical
void takeRadical()
Definition SliceFacade.cpp:433
SliceFacade::computeAssociatedPrimes
void computeAssociatedPrimes()
Compute the associated primes of the ideal.
Definition SliceFacade.cpp:286
SliceFacade::runSliceAlgorithmWithOptions
void runSliceAlgorithmWithOptions(SliceStrategy &strategy)
Definition SliceFacade.cpp:467
SliceFacade::computeMultigradedHilbertSeries
void computeMultigradedHilbertSeries()
Compute the numerator of the multigraded Hilbert-Poincare series.
Definition SliceFacade.cpp:78
SliceFacade::solveStandardProgram
bool solveStandardProgram(const vector< mpz_class > &grading, mpz_class &value, bool reportAllSolutions)
Solve an optimization program over maximal standard monomials.
Definition SliceFacade.cpp:352
SliceFacade::solveIrreducibleDecompositionProgram
bool solveIrreducibleDecompositionProgram(const vector< mpz_class > &grading, mpz_class &optimalValue, bool reportAllSolutions)
Solve an optimization program over irreducible components.
Definition SliceFacade.cpp:337
SliceFacade::isFirstComputation
bool isFirstComputation() const
Definition SliceFacade.cpp:429
SliceFacade::_common
CommonParamsHelper _common
Definition SliceFacade.h:224
SliceFacade::getLcmOfIdeal
void getLcmOfIdeal(vector< mpz_class > &lcm)
Definition SliceFacade.cpp:455
SliceFacade::computeDimension
mpz_class computeDimension(bool codimension=false)
Compute the Krull dimension of ideal.
Definition SliceFacade.cpp:114
SliceFacade::SliceFacade
SliceFacade(const SliceParams &params, const DataType &output)
Definition SliceFacade.cpp:50
SliceFacade::computeUnivariateHilbertSeries
void computeUnivariateHilbertSeries()
Compute the numerator of the univariate Hilbert-Poincare series.
Definition SliceFacade.cpp:93
SliceFacade::_params
SliceParams _params
Definition SliceFacade.h:223
SliceFacade::computePrimaryDecomposition
void computePrimaryDecomposition()
Compute the unique "nicest" primary decomposition of the ideal.
Definition SliceFacade.cpp:150
SliceFacade::solveProgram
bool solveProgram(const vector< mpz_class > &grading, mpz_class &optimalValue, bool reportAllSolutions)
Definition SliceFacade.cpp:375
SliceFacade::computeIrreducibleDecomposition
void computeIrreducibleDecomposition(bool encode)
Compute the unique irredundant set of irreducible ideals whose intersection equals ideal.
Definition SliceFacade.cpp:109
SliceFacade::computeMaximalStaircaseMonomials
void computeMaximalStaircaseMonomials()
Compute the maximal staircase monomials of the ideal.
Definition SliceFacade.cpp:229
SliceFacade::computeMaximalStandardMonomials
void computeMaximalStandardMonomials()
Compute the maximal standard monomials of the ideal.
Definition SliceFacade.cpp:241
SliceFacade::produceEncodedIrrDecom
void produceEncodedIrrDecom(TermConsumer &consumer)
Definition SliceFacade.cpp:362
SliceFacade::computeAlexanderDual
void computeAlexanderDual()
Compute the Alexander dual of the ideal.
Definition SliceFacade.cpp:275
SliceParams
Definition SliceParams.h:25
SliceParams::getSplit
const string & getSplit() const
Definition SliceParams.h:30
SliceStrategy
This class describes the interface of a strategy object for the Slice Algorithm.
Definition SliceStrategy.h:33
SliceStrategy::setUseSimplification
virtual void setUseSimplification(bool use)=0
This method should only be called before calling run().
SliceStrategy::setUseIndependence
virtual void setUseIndependence(bool use)=0
This method should only be called before calling run().
SliceStrategy::run
virtual void run(const Ideal &ideal)=0
Run the Slice algorithm.
SplitStrategy::createStrategy
static unique_ptr< SplitStrategy > createStrategy(const string &prefix)
Returns the strategy whose name has the given prefix.
Definition SplitStrategy.cpp:497
StatisticsStrategy
A wrapper for a SliceStrategy that collects statistics on what is going on, while delegating everythi...
Definition StatisticsStrategy.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
TermConsumer::consumeRing
virtual void consumeRing(const VarNames &names)
Tell the consumer which ring is being used.
Definition TermConsumer.cpp:26
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::hasSameSupport
static bool hasSameSupport(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether for every variable .
Definition Term.h:446
Term::encodedDual
static void encodedDual(Exponent *res, const Exponent *dualOf, const Exponent *point, size_t varCount)
The parameter dualOf is interpreted to encode an irreducible ideal, and the dual of that reflected in...
Definition Term.h:505
displayNote
void displayNote(const string &msg)
Display msg to standard error in a way that indicates that this is something that the user should tak...
Definition display.cpp:135
display.h
This file contains functions for printing strings to standard error.
reportError
void reportError(const string &errorMsg)
Definition error.cpp:23
error.h
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