Ideal.h
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/.
*/
#ifndef IDEAL_GUARD
#define IDEAL_GUARD
class Term;
#include <vector>
#include <algorithm>
#include <ostream>
class Ideal {
typedef vector<Exponent*> Cont;
public:
Ideal(size_t varCount = 0);
explicit Ideal(const Term& term);
Ideal(const Ideal& ideal);
~Ideal();
// *** Accessors
typedef Cont::const_iterator const_iterator;
typedef Cont::iterator iterator;
typedef Cont::const_reverse_iterator const_reverse_iterator;
typedef Cont::reverse_iterator reverse_iterator;
const_iterator begin() const {return _terms.begin();}
const_iterator end() const {return _terms.end();}
const Exponent* operator[](size_t index) const {return _terms[index];}
iterator begin() {return _terms.begin();}
iterator end() {return _terms.end();}
Exponent*& operator[](size_t index) {return _terms[index];}
size_t getVarCount() const {return _varCount;}
size_t getGeneratorCount() const {return _terms.size();}
bool isIncomparable(const Exponent* term) const;
// Returns true if any generator divides term.
bool contains(const Exponent* term) const;
// Returns true if the identity is one of the generators.
bool containsIdentity() const;
// Returns true if some minimal generator strictly divides term.
bool strictlyContains(const Exponent* term) const;
// Returns true if no generator divides another.
bool isMinimallyGenerated() const;
// Returns true if there are no generators.
bool isZeroIdeal() const;
// Returns true if all generators are pure powers. This only
// corresponds to the mathematical definition of an irreducible
// polynomial ideal if the ideal is minimally generated.
bool isIrreducible() const;
// Returns true if all generators are square free.
bool isSquareFree() const;
// Returns true if no non-zero exponent of the same variable appears
// in two distinct generators. This only corresponds to the
// mathematical definition of strongly generic if the ideal is
// minimally generated. This method is not const because it permutes
// the generators.
bool isStronglyGeneric();
// Returns true if for every pair of distinct generators a and b
// with a[i]=b[i]>0 there is some third generator that strictly
// divides lcm(a,b). This only corresponds to the mathematical
// definition of weak genericity if the ideal is minimally
// generated.
bool isWeaklyGeneric() const;
bool disjointSupport() const;
void getLcm(Exponent* lcm) const;
void getGcd(Exponent* gcd) const;
void getGcdAtExponent(Exponent* gcd, size_t var, Exponent exp);
void getGcdOfMultiplesOf(Exponent* gcd, const Exponent* divisor);
// least[var] will be the smallest non-zero exponent of var that
// appears among the generators.
void getLeastExponents(Exponent* least) const;
void getSupportCounts(Exponent* counts) const;
size_t getTypicalExponent(size_t& var, Exponent& exp);
size_t getMostNonGenericExponent(size_t& var, Exponent& exp);
size_t getTypicalNonGenericExponent(size_t& var, Exponent& exp);
bool getNonGenericExponent(size_t& var, Exponent& exp);
// returns the first generator that var divides or end() if no such
// generator exists.
const_iterator getMultiple(size_t var) const;
bool operator==(const Ideal& ideal) const;
void print(FILE* file) const;
void print(ostream& out) const;
// *** Mutators
// Insert generators into the ideal.
void insert(const Exponent* term);
void insert(const Ideal& ideal);
void insert(size_t var, Exponent e);
// This is equivalent to calling insert and then minimize.
void insertReminimize(const Exponent* term);
void insertReminimize(size_t var, Exponent e);
// Remove non-redundant generators.
void minimize();
// Sorts the generators in the specified order
void sortReverseLex(); // reverse lexicographic order
void sortLex(); // lexicographic order from left
// Sort the generators in ascending order according to the exponent of var.
void singleDegreeSort(size_t var);
// Replace each generator g by g * term.
void product(const Exponent* term);
// Replace each generator g by g : by. The second overload has by
// equal to var raised to e.
void colon(const Exponent* by);
void colon(size_t var, Exponent e);
// Equivalent to calling colon(by) and then minimize. The second
// overload has by equal to var raised to e. Returns true if the support
// of any generator was changed.
bool colonReminimize(const Exponent* colon);
bool colonReminimize(size_t var, Exponent e);
// Swaps it and the last element, and then removes the last element,
// which is the element originally pointed to by it.
void remove(const_iterator it);
// Removes those generators that are multiples of term. The second
// overload has term equal to var raised to e.
void removeMultiples(const Exponent* term);
void removeMultiples(size_t var, Exponent e);
// Insert those generators of ideal that are not multiples of
// term. The second overload has term equal to var raised to e.
void insertNonMultiples(const Exponent* term, const Ideal& ideal);
void insertNonMultiples(size_t var, Exponent e, const Ideal& ideal);
// Removes those generators that are strict multiples of term.
void removeStrictMultiples(const Exponent* term);
// Remove duplicate generators.
void removeDuplicates();
// Removes all generators, and optionally sets the number of variables.
void clear();
void clearAndSetVarCount(size_t varCount);
void mapExponentsToZeroNoMinimize(const Term& zeroExponents);
void takeRadicalNoMinimize();
Ideal& operator=(const Ideal& ideal);
void swap(Ideal& ideal);
template<class Predicate>
bool removeIf(Predicate pred);
static void clearStaticCache();
protected:
class ExponentAllocator {
public:
ExponentAllocator(size_t varCount);
~ExponentAllocator();
Exponent* allocate();
void reset(size_t newVarCount);
void swap(ExponentAllocator& allocator);
private:
ExponentAllocator(const ExponentAllocator&);
ExponentAllocator& operator=(const ExponentAllocator&);
bool useSingleChunking() const;
size_t _varCount;
Exponent* _chunk;
Exponent* _chunkIterator;
Exponent* _chunkEnd;
vector<Exponent*> _chunks;
};
size_t _varCount;
vector<Exponent*> _terms;
ExponentAllocator _allocator;
};
template<class Predicate>
inline bool Ideal::removeIf(Predicate pred) {
iterator newEnd = std::remove_if(_terms.begin(), _terms.end(), pred);
if (newEnd != _terms.end()) {
_terms.erase(newEnd, _terms.end());
return true;
} else
return false;
}
inline ostream& operator<<(ostream& out, const Ideal& ideal) {
ideal.print(out);
return out;
}
#endif
operator<<
ostream & operator<<(ostream &out, const Ideal &ideal)
Definition Ideal.h:331
Ideal::ExponentAllocator
Definition Ideal.h:290
Ideal::ExponentAllocator::_chunkIterator
Exponent * _chunkIterator
Definition Ideal.h:309
Ideal::ExponentAllocator::reset
void reset(size_t newVarCount)
Definition Ideal.cpp:781
Ideal::ExponentAllocator::swap
void swap(ExponentAllocator &allocator)
Definition Ideal.cpp:798
Ideal::ExponentAllocator::_chunkEnd
Exponent * _chunkEnd
Definition Ideal.h:310
Ideal::ExponentAllocator::_varCount
size_t _varCount
Definition Ideal.h:306
Ideal::ExponentAllocator::_chunk
Exponent * _chunk
Definition Ideal.h:308
Ideal::ExponentAllocator::_chunks
vector< Exponent * > _chunks
Definition Ideal.h:312
Ideal::ExponentAllocator::operator=
ExponentAllocator & operator=(const ExponentAllocator &)
Ideal::ExponentAllocator::useSingleChunking
bool useSingleChunking() const
Definition Ideal.cpp:806
Ideal::ExponentAllocator::allocate
Exponent * allocate()
Definition Ideal.cpp:750
Ideal::ExponentAllocator::ExponentAllocator
ExponentAllocator(const ExponentAllocator &)
Ideal::ExponentAllocator::~ExponentAllocator
~ExponentAllocator()
Definition Ideal.cpp:746
Ideal::ExponentAllocator::ExponentAllocator
ExponentAllocator(size_t varCount)
Definition Ideal.cpp:738
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::getGcdOfMultiplesOf
void getGcdOfMultiplesOf(Exponent *gcd, const Exponent *divisor)
Sets gcd to the greatest common divisor of those generators that are divisible by divisor.
Definition Ideal.cpp:197
Ideal::removeStrictMultiples
void removeStrictMultiples(const Exponent *term)
Definition Ideal.cpp:622
Ideal::removeDuplicates
void removeDuplicates()
Definition Ideal.cpp:634
Ideal::singleDegreeSort
void singleDegreeSort(size_t var)
Definition Ideal.cpp:518
Ideal::minimize
void minimize()
Definition Ideal.cpp:501
Ideal::operator[]
Exponent *& operator[](size_t index)
Definition Ideal.h:54
Ideal::isSquareFree
bool isSquareFree() const
Definition Ideal.cpp:98
Ideal::const_reverse_iterator
Cont::const_reverse_iterator const_reverse_iterator
Definition Ideal.h:45
Ideal::product
void product(const Exponent *term)
Definition Ideal.cpp:525
Ideal::isZeroIdeal
bool isZeroIdeal() const
Definition Ideal.cpp:86
Ideal::remove
void remove(const_iterator it)
Definition Ideal.cpp:576
Ideal::getGcd
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
Definition Ideal.cpp:164
Ideal::Cont
vector< Exponent * > Cont
Definition Ideal.h:28
Ideal::insertNonMultiples
void insertNonMultiples(const Exponent *term, const Ideal &ideal)
Definition Ideal.cpp:608
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition Ideal.h:57
Ideal::_allocator
ExponentAllocator _allocator
Definition Ideal.h:317
Ideal::getMostNonGenericExponent
size_t getMostNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the most non-generic degree.
Definition Ideal.cpp:272
Ideal::~Ideal
~Ideal()
Definition Ideal.cpp:28
Ideal::getMultiple
const_iterator getMultiple(size_t var) const
Definition Ideal.cpp:668
Ideal::containsIdentity
bool containsIdentity() const
Definition Ideal.cpp:65
Ideal::begin
iterator begin()
Definition Ideal.h:52
Ideal::colon
void colon(const Exponent *by)
Definition Ideal.cpp:531
Ideal::clearAndSetVarCount
void clearAndSetVarCount(size_t varCount)
Definition Ideal.cpp:646
Ideal::getLcm
void getLcm(Exponent *lcm) const
Sets lcm to the least common multiple of all generators.
Definition Ideal.cpp:157
Ideal::takeRadicalNoMinimize
void takeRadicalNoMinimize()
Replaces all generators with their support and does not remove any non-minimal generators this may pr...
Definition Ideal.cpp:660
Ideal::getNonGenericExponent
bool getNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is some non-generic degree.
Definition Ideal.cpp:379
Ideal::isIncomparable
bool isIncomparable(const Exponent *term) const
Definition Ideal.cpp:48
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::clearStaticCache
static void clearStaticCache()
Ideal caches memory allocated with new internally and reuses it to avoid calling new all the time.
Definition Ideal.cpp:810
Ideal::sortReverseLex
void sortReverseLex()
Definition Ideal.cpp:510
Ideal::_terms
vector< Exponent * > _terms
Definition Ideal.h:316
Ideal::clear
void clear()
Definition Ideal.cpp:641
Ideal::mapExponentsToZeroNoMinimize
void mapExponentsToZeroNoMinimize(const Term &zeroExponents)
Replaces the exponents from zeroExponents with zero and does not remove any non-minimal generators th...
Definition Ideal.cpp:652
Ideal::contains
bool contains(const Exponent *term) const
Definition Ideal.cpp:57
Ideal::sortLex
void sortLex()
Definition Ideal.cpp:514
Ideal::getTypicalExponent
size_t getTypicalExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-zero exponent.
Definition Ideal.cpp:237
Ideal::insert
void insert(const Exponent *term)
Definition Ideal.cpp:455
Ideal::strictlyContains
bool strictlyContains(const Exponent *term) const
Definition Ideal.cpp:73
Ideal::insertReminimize
void insertReminimize(const Exponent *term)
Definition Ideal.cpp:484
Ideal::getLeastExponents
void getLeastExponents(Exponent *least) const
Definition Ideal.cpp:217
Ideal::disjointSupport
bool disjointSupport() const
Returns true if all pairs of generators have disjoint support.
Definition Ideal.cpp:142
Ideal::end
iterator end()
Definition Ideal.h:53
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::operator=
Ideal & operator=(const Ideal &ideal)
Definition Ideal.cpp:676
Ideal::removeIf
bool removeIf(Predicate pred)
Removes those generators m such that pred(m) evaluates to true.
Definition Ideal.h:321
Ideal::print
void print(FILE *file) const
Definition Ideal.cpp:440
Ideal::swap
void swap(Ideal &ideal)
Definition Ideal.cpp:683
Ideal::operator[]
const Exponent * operator[](size_t index) const
Definition Ideal.h:50
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
Ideal::getSupportCounts
void getSupportCounts(Exponent *counts) const
counts[var] will be the number of generators divisible by var.
Definition Ideal.cpp:227
Ideal::Ideal
Ideal(size_t varCount=0)
Initialize this object to the zero ideal in varCount variables.
Definition Ideal.cpp:31
Ideal::isIrreducible
bool isIrreducible() const
Definition Ideal.cpp:90
Ideal::removeMultiples
void removeMultiples(const Exponent *term)
Definition Ideal.cpp:584
Ideal::reverse_iterator
Cont::reverse_iterator reverse_iterator
Definition Ideal.h:46
Ideal::isWeaklyGeneric
bool isWeaklyGeneric() const
Definition Ideal.cpp:121
Ideal::getTypicalNonGenericExponent
size_t getTypicalNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-generic degree.
Definition Ideal.cpp:326
Ideal::isStronglyGeneric
bool isStronglyGeneric()
Definition Ideal.cpp:106
Ideal::iterator
Cont::iterator iterator
Definition Ideal.h:44
Ideal::colonReminimize
bool colonReminimize(const Exponent *colon)
Definition Ideal.cpp:550
Ideal::isMinimallyGenerated
bool isMinimallyGenerated() const
Definition Ideal.cpp:81
Ideal::_varCount
size_t _varCount
Definition Ideal.h:315
Ideal::getGcdAtExponent
void getGcdAtExponent(Exponent *gcd, size_t var, Exponent exp)
Sets gcd to the greatest common divisor of those generators that raise the variable var to the power ...
Definition Ideal.cpp:177
Ideal::operator==
bool operator==(const Ideal &ideal) const
Rereturns true if *this equals ideal.
Definition Ideal.cpp:424
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Exponent
unsigned int Exponent
Definition stdinc.h:89