IdealFacade.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 "IdealFacade.h"
#include "BigIdeal.h"
#include "Ideal.h"
#include "TermTranslator.h"
#include "IOHandler.h"
#include "IOFacade.h"
#include "Macaulay2IOHandler.h"
#include "CanonicalCoefTermConsumer.h"
#include "error.h"
#include "FrobbyStringStream.h"
#include "SizeMaxIndepSetAlg.h"
#include "HilbertBasecase.h"
#include "PivotEulerAlg.h"
IdealFacade::IdealFacade(bool printActions):
Facade(printActions) {
}
void IdealFacade::deform(BigIdeal& bigIdeal) {
beginAction("Applying generic deformation to ideal.");
bigIdeal.deform();
// Reduce range of exponents
Ideal ideal(bigIdeal.getVarCount());
TermTranslator translator(bigIdeal, ideal, false);
bigIdeal.clear();
bigIdeal.insert(ideal);
endAction();
}
void IdealFacade::takeRadical(BigIdeal& bigIdeal) {
beginAction("Taking radical of ideal.");
bigIdeal.takeRadical();
Ideal ideal(bigIdeal.getVarCount());
TermTranslator translator(bigIdeal, ideal, false);
bigIdeal.clear();
bigIdeal.insert(ideal, translator);
endAction();
}
void IdealFacade::swap01(BigIdeal& bigIdeal) {
beginAction("Swapping 0 and 1 exponents.");
const size_t genCount = bigIdeal.getGeneratorCount();
const size_t varCount = bigIdeal.getVarCount();
for (size_t gen = 0; gen < genCount; ++gen) {
for (size_t var = 0; var < varCount; ++var) {
if (bigIdeal[gen][var] == 1)
bigIdeal[gen][var] = 0;
else if (bigIdeal[gen][var] == 0)
bigIdeal[gen][var] = 1;
}
}
endAction();
}
mpz_class IdealFacade::computeDimension(const BigIdeal& bigIdeal,
bool codimension,
bool squareFreeAndMinimal) {
beginAction("Computing dimension of ideal.");
size_t varCount = bigIdeal.getVarCount();
size_t genCount = bigIdeal.getGeneratorCount();
Ideal radical(varCount);
Term tmp(varCount);
for (size_t term = 0; term < genCount; ++term) {
for (size_t var = 0; var < varCount; ++var) {
ASSERT(!squareFreeAndMinimal || bigIdeal[term][var] <= 1);
if (bigIdeal[term][var] == 0)
tmp[var] = 0;
else
tmp[var] = 1;
}
radical.insert(tmp);
}
ASSERT(!squareFreeAndMinimal || radical.isMinimallyGenerated());
if (!squareFreeAndMinimal)
radical.minimize();
SizeMaxIndepSetAlg alg;
alg.run(radical);
mpz_class result = alg.getMaxIndepSetSize();
endAction();
if (codimension)
return varCount - result;
else
return result;
}
void IdealFacade::takeProducts(const vector<BigIdeal*>& ideals,
BigIdeal& ideal) {
beginAction("Taking products.");
size_t idealCount = ideals.size();
for (size_t i = 0; i < idealCount; ++i) {
ASSERT(ideals[i] != 0);
if (!(ideal.getNames() == ideals[i]->getNames())) {
FrobbyStringStream errorMsg;
errorMsg <<
"Taking products of ideals in rings with different variable lists.\n";
string list;
ideal.getNames().toString(list);
errorMsg << "One ring has variables\n " << list << ",\n";
ideals[i]->getNames().toString(list);
errorMsg << "while another has variables\n " << list <<
".\nContact the Frobby developers if you need this functionality.";
reportError(errorMsg);
}
size_t genCount = ideals[i]->getGeneratorCount();
size_t varCount = ideals[i]->getVarCount();
ideal.newLastTerm();
for (size_t t = 0; t < genCount; ++t)
for (size_t var = 0; var < varCount; ++var)
ideal.getLastTermExponentRef(var) += (*ideals[i])[t][var];
}
endAction();
}
void IdealFacade::sortAllAndMinimize(BigIdeal& bigIdeal) {
beginAction("Minimizing ideal.");
Ideal ideal(bigIdeal.getVarCount());
TermTranslator translator(bigIdeal, ideal, false);
bigIdeal.clear();
ideal.minimize();
ideal.sortReverseLex();
bigIdeal.insert(ideal, translator);
endAction();
}
void IdealFacade::projectVar(BigIdeal& bigIdeal, size_t var) {
beginAction("Projecting a variable away.");
ASSERT(var < bigIdeal.getVarCount());
bigIdeal.projectVar(var);
endAction();
}
#include <iostream>
void IdealFacade::trimVariables(const vector<BigIdeal*>& ideals,
VarNames& names) {
beginAction("Removing unused variables.");
vector<char> used(names.getVarCount());
for (size_t i = 0; i < ideals.size(); ++i) {
BigIdeal& ideal = *(ideals[i]);
ASSERT(ideal.getNames() == names);
for (size_t gen = 0; gen < ideal.getGeneratorCount(); ++gen)
for (size_t var = 0; var < ideal.getVarCount(); ++var)
if (ideal[gen][var] != 0)
used[var] = true;
}
// Go from high to low to avoid removing variable i interfering with
// the offset of variable j, as it would when i < j.
for (size_t var = names.getVarCount(); var > 0;) {
--var;
if (!used[var]) {
names.projectVar(var);
for (size_t i = 0; i < ideals.size(); ++i)
ideals[i]->projectVar(var);
}
}
endAction();
}
void IdealFacade::addPurePowers(BigIdeal& bigIdeal) {
beginAction("Adding pure powers.");
vector<mpz_class> lcm;
bigIdeal.getLcm(lcm);
vector<mpz_class> purePower(bigIdeal.getVarCount());
for (size_t var = 0; var < bigIdeal.getVarCount(); ++var) {
purePower[var] = lcm[var] + 1;
if (!bigIdeal.contains(purePower))
bigIdeal.insert(purePower);
ASSERT(bigIdeal.contains(purePower));
purePower[var] = 0;
}
endAction();
}
void IdealFacade::sortGeneratorsUnique(BigIdeal& ideal) {
beginAction("Sorting generators and removing duplicates.");
ideal.sortGeneratorsUnique();
endAction();
}
void IdealFacade::sortGenerators(BigIdeal& ideal) {
beginAction("Sorting generators.");
ideal.sortGenerators();
endAction();
}
void IdealFacade::sortVariables(BigIdeal& ideal) {
beginAction("Sorting variables.");
ideal.sortVariables();
endAction();
}
void IdealFacade::printAnalysis(FILE* out, BigIdeal& bigIdeal) {
beginAction("Computing and printing analysis.");
Ideal ideal(bigIdeal.getVarCount());
TermTranslator translator(bigIdeal, ideal, false);
fprintf(stdout, "generators: %lu\n",
(unsigned long)ideal.getGeneratorCount());
fprintf(stdout, "variables: %lu\n",
(unsigned long)ideal.getVarCount());
size_t sizeBeforeMinimize = ideal.getGeneratorCount();
ideal.minimize();
fprintf(stdout, "minimally generated: %s\n",
ideal.getGeneratorCount() == sizeBeforeMinimize ? "yes" : "no");
fprintf(out, "strongly generic: %s\n",
ideal.isStronglyGeneric() ? "yes" : "no");
fprintf(out, "weakly generic: %s\n",
ideal.isWeaklyGeneric() ? "yes" : "no");
endAction();
}
void IdealFacade::printLcm(BigIdeal& ideal,
IOHandler* handler,
FILE* out) {
beginAction("Computing lcm");
vector<mpz_class> lcm;
ideal.getLcm(lcm);
IOFacade ioFacade(isPrintingActions());
ioFacade.writeTerm(lcm, ideal.getNames(), handler, out);
fputc('\n', out);
endAction();
}
BigIdeal.h
CanonicalCoefTermConsumer.h
FrobbyStringStream.h
HilbertBasecase.h
IOFacade.h
IOHandler.h
IdealFacade.h
Ideal.h
Macaulay2IOHandler.h
PivotEulerAlg.h
SizeMaxIndepSetAlg.h
TermTranslator.h
BigIdeal
Definition BigIdeal.h:27
BigIdeal::sortGenerators
void sortGenerators()
Definition BigIdeal.cpp:280
BigIdeal::newLastTerm
void newLastTerm()
Definition BigIdeal.cpp:104
BigIdeal::sortGeneratorsUnique
void sortGeneratorsUnique()
Definition BigIdeal.cpp:273
BigIdeal::getLastTermExponentRef
mpz_class & getLastTermExponentRef(size_t var)
Definition BigIdeal.h:126
BigIdeal::getLcm
void getLcm(vector< mpz_class > &lcm) const
Definition BigIdeal.cpp:143
BigIdeal::contains
bool contains(const vector< mpz_class > &term) const
Definition BigIdeal.cpp:207
BigIdeal::deform
void deform()
Definition BigIdeal.cpp:257
BigIdeal::getVarCount
size_t getVarCount() const
Definition BigIdeal.h:148
BigIdeal::clear
void clear()
Definition BigIdeal.cpp:218
BigIdeal::insert
void insert(const Ideal &ideal)
Definition BigIdeal.cpp:60
BigIdeal::getNames
const VarNames & getNames() const
Definition BigIdeal.cpp:253
BigIdeal::getGeneratorCount
size_t getGeneratorCount() const
Definition BigIdeal.h:144
BigIdeal::projectVar
void projectVar(size_t var)
Definition BigIdeal.cpp:158
BigIdeal::sortVariables
void sortVariables()
Definition BigIdeal.cpp:298
BigIdeal::takeRadical
void takeRadical()
Definition BigIdeal.cpp:264
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
Facade::isPrintingActions
bool isPrintingActions() const
Returns true if printing actions.
Definition Facade.cpp:66
FrobbyStringStream
A replacement for stringstream.
Definition FrobbyStringStream.h:26
IOFacade
A facade for input and output of mathematical objects.
Definition IOFacade.h:39
IOFacade::writeTerm
void writeTerm(const vector< mpz_class > &term, const VarNames &names, IOHandler *handler, FILE *out)
Definition IOFacade.cpp:218
IOHandler
An IOHandler implements input and output for some format in such a way that client code does not need...
Definition IOHandler.h:41
IdealFacade::sortAllAndMinimize
void sortAllAndMinimize(BigIdeal &bigIdeal)
Remove redundant generators from ideal.
Definition IdealFacade.cpp:156
IdealFacade::trimVariables
void trimVariables(const vector< BigIdeal * > &ideals, VarNames &names)
Remove those variables that do not appear in any generator.
Definition IdealFacade.cpp:181
IdealFacade::addPurePowers
void addPurePowers(BigIdeal &bigIdeal)
Adds x_i^(l_i+1) to the ideal for each i where that will be a minimal generator, where x^l is the lcm...
Definition IdealFacade.cpp:209
IdealFacade::swap01
void swap01(BigIdeal &ideal)
Change all 0 exponents to 1 and vice versa.
Definition IdealFacade.cpp:65
IdealFacade::sortGenerators
void sortGenerators(BigIdeal &ideal)
Sorts the generators of ideal.
Definition IdealFacade.cpp:237
IdealFacade::computeDimension
mpz_class computeDimension(const BigIdeal &ideal, bool codimension=false, bool squareFreeAndMinimal=false)
Compute the Krull dimension of ideal.
Definition IdealFacade.cpp:82
IdealFacade::deform
void deform(BigIdeal &ideal)
Applies some generic deformation to the ideal.
Definition IdealFacade.cpp:37
IdealFacade::takeRadical
void takeRadical(BigIdeal &ideal)
Takes the radical of the generators of ideal.
Definition IdealFacade.cpp:51
IdealFacade::printAnalysis
void printAnalysis(FILE *out, BigIdeal &ideal)
Definition IdealFacade.cpp:253
IdealFacade::IdealFacade
IdealFacade(bool printActions)
Definition IdealFacade.cpp:33
IdealFacade::sortVariables
void sortVariables(BigIdeal &ideal)
Sorts the variables of ideal.
Definition IdealFacade.cpp:245
IdealFacade::projectVar
void projectVar(BigIdeal &bigIdeal, size_t var)
Remove the variable var from the ideal and ring by substituting it by 1.
Definition IdealFacade.cpp:171
IdealFacade::sortGeneratorsUnique
void sortGeneratorsUnique(BigIdeal &ideal)
Sorts the generators of ideal and removes duplicates.
Definition IdealFacade.cpp:229
IdealFacade::takeProducts
void takeProducts(const vector< BigIdeal * > &ideals, BigIdeal &ideal)
Take the product of the minimal generators of each ideal, and add the resulting monomials as generato...
Definition IdealFacade.cpp:120
IdealFacade::printLcm
void printLcm(BigIdeal &ideal, IOHandler *handler, FILE *out)
Definition IdealFacade.cpp:277
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::minimize
void minimize()
Definition Ideal.cpp:501
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition Ideal.h:57
Ideal::sortReverseLex
void sortReverseLex()
Definition Ideal.cpp:510
Ideal::insert
void insert(const Exponent *term)
Definition Ideal.cpp:455
Ideal::isWeaklyGeneric
bool isWeaklyGeneric() const
Definition Ideal.cpp:121
Ideal::isStronglyGeneric
bool isStronglyGeneric()
Definition Ideal.cpp:106
Ideal::isMinimallyGenerated
bool isMinimallyGenerated() const
Definition Ideal.cpp:81
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
SizeMaxIndepSetAlg
Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.
Definition SizeMaxIndepSetAlg.h:61
SizeMaxIndepSetAlg::run
void run(Ideal &ideal)
Run the algorithm on ideal.
Definition SizeMaxIndepSetAlg.cpp:23
SizeMaxIndepSetAlg::getMaxIndepSetSize
mpz_class getMaxIndepSetSize()
Returns the largest size over all independent sets of the hypergraph passed to run.
Definition SizeMaxIndepSetAlg.cpp:67
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
VarNames
Defines the variables of a polynomial ring and facilities IO involving them.
Definition VarNames.h:40
VarNames::getVarCount
size_t getVarCount() const
Returns the current number of variables.
Definition VarNames.h:113
VarNames::projectVar
void projectVar(size_t index)
Definition VarNames.cpp:161
VarNames::toString
void toString(string &str) const
Definition VarNames.cpp:171
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