Frobby 0.9.5
frobby.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "frobby.h"
19
20#include "BigIdeal.h"
21#include "SliceFacade.h"
22#include "BigTermConsumer.h"
23#include "TermTranslator.h"
24#include "Term.h"
25#include "error.h"
26#include "CoefBigTermConsumer.h"
27#include "IdealFacade.h"
28#include "SliceParams.h"
29
30namespace constants {
31 const char * const version = "0.9.5";
32}
33
35protected:
40
41 virtual ~ConsumerWrapper() {
42 delete[] _term;
43 }
44
45 void setTerm(const Term& term, const TermTranslator& translator) {
46 ASSERT(term.getVarCount() == _varCount);
47 ASSERT(translator.getVarCount() == _varCount);
48
49 for (size_t var = 0; var < _varCount; ++var)
50 _term[var] = const_cast<mpz_ptr>
51 (translator.getExponent(var, term).get_mpz_t());
52 }
53
54 void setTerm(const vector<mpz_class>& term) {
55 ASSERT(term.size() == _varCount);
56
57 for (size_t var = 0; var < _varCount; ++var)
58 _term[var] = const_cast<mpz_ptr>(term[var].get_mpz_t());
59 }
60
61 size_t _varCount;
63};
64
66 public ConsumerWrapper {
67public:
74
75 virtual void consumeRing(const VarNames& names) {
76 ASSERT(names.getVarCount() == _varCount);
77 }
78
79 virtual void beginConsuming() {
81 }
82
83 virtual void consume(const Term& term, const TermTranslator& translator) {
84 ASSERT(term.getVarCount() == _varCount);
85 ASSERT(translator.getVarCount() == _varCount);
86
87 setTerm(term, translator);
89 }
90
91 virtual void consume(const vector<mpz_class>& term) {
92 ASSERT(term.size() == _varCount);
93
94 setTerm(term);
96 }
97
98 virtual void doneConsuming() {
100 }
101
102private:
104};
105
107 public ConsumerWrapper {
108public:
116
117 virtual void consumeRing(const VarNames& names) {
118 ASSERT(names.getVarCount() == _varCount);
119 }
120
121 virtual void beginConsuming() {
123 }
124
125 virtual void consume(const mpz_class& coef,
126 const Term& term,
127 const TermTranslator& translator) {
128 ASSERT(term.getVarCount() == _varCount);
129 ASSERT(translator.getVarCount() == _varCount);
130
131 setTerm(term, translator);
132 _consumer->consume(coef.get_mpz_t(), _term);
133 }
134
135 virtual void consume(const mpz_class& coef,
136 const vector<mpz_class>& term) {
137 ASSERT(term.size() == _varCount);
138
139 for (size_t var = 0; var < _varCount; ++var)
140 _term[var] = const_cast<mpz_ptr>(term[var].get_mpz_t());
141 _consumer->consume(coef.get_mpz_t(), _term);
142 }
143
144 // TODO: make a note somewhere that in case of an exception,
145 // polynomialEnd might not get called, this being because it is too
146 // much of a burden to require it not to throw any
147 // exceptions. Hmm... maybe there is an alternative solution.
148 virtual void doneConsuming() {
150 }
151
152private:
154 size_t _varCount;
155};
156
159
162
165
168
171
174
175namespace FrobbyImpl {
176 using ::BigIdeal;
177
179 public:
181 _ideal(VarNames(variableCount)),
182 _atVariable(variableCount) {
183 }
184
185 static const BigIdeal& getIdeal(const Frobby::Ideal& ideal) {
186 return ideal._data->_ideal;
187 }
188
189 private:
190 friend class Frobby::Ideal;
191
194 };
195}
196
200
202 _data = new FrobbyImpl::FrobbyIdealHelper(*ideal._data);
203}
204
206 delete _data;
207}
208
210 // Allocate new object before deleting old object to leave *this
211 // in a valid state in case of new throwing an exception.
214
215 delete _data;
216 _data = newValue;
217
218 return *this;
219}
220
222 ASSERT(_data->_atVariable <= _data->_ideal.getVarCount());
223
224 if (_data->_atVariable == _data->_ideal.getVarCount()) {
225 _data->_ideal.newLastTerm();
226 _data->_atVariable = 0;
227 if (_data->_ideal.getVarCount() == 0)
228 return;
229 }
230
231 mpz_class& ref = _data->_ideal.getLastTermExponentRef(_data->_atVariable);
232 mpz_set(ref.get_mpz_t(), exponent);
233 ++_data->_atVariable;
234}
235
238 addExponent(tmp.get_mpz_t());
239}
240
243 addExponent(tmp.get_mpz_t());
244}
245
246bool Frobby::alexanderDual(const Ideal& ideal,
250
252 (&consumer, bigIdeal.getVarCount());
253
256
257 if (reflectionMonomial == 0)
258 facade.computeAlexanderDual();
259 else {
260 vector<mpz_class> point;
261 point.resize(bigIdeal.getVarCount());
262 for (size_t var = 0; var < bigIdeal.getVarCount(); ++var)
264
265 // We guarantee not to retain a reference to reflectionMonomial
266 // when providing terms to the consumer.
268
269 try {
270 facade.computeAlexanderDual(point);
271 } catch (const FrobbyException&) {
272 return false;
273 }
274 }
275
276 return true;
277}
278
279bool Frobby::alexanderDual(const Ideal& ideal,
285
286 if (reflectionIdeal.getGeneratorCount() != 1)
287 return false;
288 if (reflectionIdeal.getVarCount() != bigIdeal.getVarCount())
289 return false;
290
291 const vector<mpz_class>& monomial = reflectionIdeal.getTerm(0);
292 const mpz_t* monomialPtr = 0;
293 if (reflectionIdeal.getVarCount() > 0)
294 monomialPtr = (const mpz_t*)&(monomial[0]);
295
296 return alexanderDual(ideal, monomialPtr, consumer);
297}
298
310
321
326public:
328 _varCount(0),
329 _consumer(consumer),
330 _term(0) {
331 ASSERT(_consumer != 0);
332 }
333
336
337 virtual void idealBegin(size_t varCount) {
338 _varCount = varCount;
339 _term.resize(varCount);
340 for (size_t var = 0; var < _varCount; ++var)
341 _term[var] = _zero.get_mpz_t();
342 }
343
344 virtual void idealEnd() {
345 _term.clear();
346 }
347
349 _consumer->idealBegin(_varCount);
350
351 bool isIdentity = true;
352 for (size_t var = 0; var < _varCount; ++var) {
353 if (mpz_cmp_ui(exponentVector[var], 0) != 0) {
354 isIdentity = false;
355 _term[var] = exponentVector[var];
356 _consumer->consume(&*(_term.begin()));
357 _term[var] = _zero.get_mpz_t();
358 }
359 }
360
361 _consumer->idealEnd();
362 }
363
364private:
365 size_t _varCount;
366 IdealConsumer* _consumer;
367 vector<mpz_ptr> _term;
369};
370
380
384 if (bigIdeal.getGeneratorCount() == 0)
385 return false;
386
388 (&consumer, bigIdeal.getVarCount());
391
392 facade.computeIrreducibleDecomposition(true);
393 return true;
394}
395
407
419
421 const mpz_t* l,
423 ASSERT(l != 0);
424
426
427 vector<mpz_class> grading;
428 for (size_t var = 0; var < bigIdeal.getVarCount(); ++var)
429 grading.push_back(mpz_class(l[var]));
430
432 (&consumer, bigIdeal.getVarCount());
434 params.useIndependenceSplits(false); // not supported
436
438 return facade.solveStandardProgram(grading, dummy, false);
439}
440
443 dimension(ideal, codim);
444 mpz_ui_sub(codim, bigIdeal.getVarCount(), codim);
445}
446
447void Frobby::dimension(const Ideal& ideal, mpz_t dim) {
449
450 IdealFacade facade(false);
451 mpz_class dimen = facade.computeDimension(bigIdeal, false);
452 mpz_set(dim, dimen.get_mpz_t());
453}
454
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
ConsumerWrapper(size_t varCount)
Definition frobby.cpp:36
void setTerm(const vector< mpz_class > &term)
Definition frobby.cpp:54
size_t _varCount
Definition frobby.cpp:61
void setTerm(const Term &term, const TermTranslator &translator)
Definition frobby.cpp:45
virtual ~ConsumerWrapper()
Definition frobby.cpp:41
mpz_ptr * _term
Definition frobby.cpp:62
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition frobby.cpp:98
ExternalIdealConsumerWrapper(Frobby::IdealConsumer *consumer, size_t varCount)
Definition frobby.cpp:68
Frobby::IdealConsumer * _consumer
Definition frobby.cpp:103
virtual void consumeRing(const VarNames &names)
Tell the consumer which ring is being used.
Definition frobby.cpp:75
virtual void consume(const Term &term, const TermTranslator &translator)
Definition frobby.cpp:83
virtual void consume(const vector< mpz_class > &term)
Definition frobby.cpp:91
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition frobby.cpp:79
virtual void consume(const mpz_class &coef, const Term &term, const TermTranslator &translator)
Definition frobby.cpp:125
virtual void consumeRing(const VarNames &names)
Definition frobby.cpp:117
ExternalPolynomialConsumerWrapper(Frobby::PolynomialConsumer *consumer, size_t varCount)
Definition frobby.cpp:109
Frobby::PolynomialConsumer * _consumer
Definition frobby.cpp:153
virtual void consume(const mpz_class &coef, const vector< mpz_class > &term)
Definition frobby.cpp:135
This is the base of the Frobby exception hierarchy for exceptions that can occur due to expected erro...
Definition error.h:27
FrobbyIdealHelper(size_t variableCount)
Definition frobby.cpp:180
static const BigIdeal & getIdeal(const Frobby::Ideal &ideal)
Definition frobby.cpp:185
This class provides a way to get monomial ideals as output from Frobby one generator at a time.
Definition frobby.h:77
virtual void idealBegin(size_t varCount)
Called before output of a monomial ideal.
Definition frobby.cpp:160
virtual ~IdealConsumer()
The provided implementation does nothing.
Definition frobby.cpp:157
virtual void idealEnd()
Called after output of a monomial ideal.
Definition frobby.cpp:163
virtual void consume(mpz_ptr *exponentVector)=0
For output of a generator of the ideal.
Ideal & operator=(const Ideal &ideal)
Definition frobby.cpp:209
Ideal(size_t variableCount)
Definition frobby.cpp:197
FrobbyImpl::FrobbyIdealHelper * _data
Definition frobby.h:64
void addExponent(const mpz_t exponent)
Call addExponent once for each variable to add a term one exponent at a time.
Definition frobby.cpp:221
This class provides a way to get polynomials as output from Frobby one term at a time.
Definition frobby.h:114
virtual void polynomialBegin(size_t varCount)
Called before output of a polynomial.
Definition frobby.cpp:169
virtual ~PolynomialConsumer()
The provided implementation does nothing.
Definition frobby.cpp:166
virtual void polynomialEnd()
Called after output of a polynomial.
Definition frobby.cpp:172
virtual void consume(const mpz_t coefficient, mpz_ptr *exponentVector)=0
For output of a term of the polynomial.
A facade for performing operations on BigIdeal.
Definition IdealFacade.h:34
IdealConsumer * _consumer
Definition frobby.cpp:366
virtual void idealBegin(size_t varCount)
Called before output of a monomial ideal.
Definition frobby.cpp:337
virtual void idealEnd()
Called after output of a monomial ideal.
Definition frobby.cpp:344
vector< mpz_ptr > _term
Definition frobby.cpp:367
IrreducibleIdealDecoder(IdealConsumer *consumer)
Definition frobby.cpp:327
virtual void consume(mpz_ptr *exponentVector)
For output of a generator of the ideal.
Definition frobby.cpp:348
A facade for operations on monomial ideals using the Slice Algorithm.
Definition SliceFacade.h:44
void useIndependenceSplits(bool value)
Definition SliceParams.h:34
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
size_t getVarCount() const
Definition Term.h:85
Defines the variables of a polynomial ring and facilities IO involving them.
Definition VarNames.h:40
The namespace FrobbyImpl is for internal use inside Frobby only.
Definition frobby.cpp:175
void dimension(const Ideal &ideal, mpz_t dim)
Compute the Krull dimension of a monomial ideal.
Definition frobby.cpp:447
bool alexanderDual(const Ideal &ideal, const mpz_t *reflectionMonomial, IdealConsumer &consumer)
Compute the Alexander dual of ideal using the point reflectionMonomial.
Definition frobby.cpp:246
void irreducibleDecompositionAsIdeals(const Ideal &ideal, IdealConsumer &consumer)
Compute the irreducible decomposition of ideal.
Definition frobby.cpp:371
void codimension(const Ideal &ideal, mpz_t codim)
Compute the codimension of a monomial ideal.
Definition frobby.cpp:441
void associatedPrimes(const Ideal &ideal, IdealConsumer &consumer)
Compute the associated primes of the ideal.
Definition frobby.cpp:455
void univariateHilbertPoincareSeries(const Ideal &ideal, PolynomialConsumer &consumer)
Compute the univariate Hilbert-Poincare series of ideal.
Definition frobby.cpp:311
bool solveStandardMonomialProgram(const Ideal &ideal, const mpz_t *l, IdealConsumer &consumer)
Solve the optimization program.
Definition frobby.cpp:420
bool irreducibleDecompositionAsMonomials(const Ideal &ideal, IdealConsumer &consumer)
Compute the irreducible decomposition of ideal, and encode each irreducible component as a monomial.
Definition frobby.cpp:381
void maximalStandardMonomials(const Ideal &ideal, IdealConsumer &consumer)
Compute the maximal standard monomials of ideal.
Definition frobby.cpp:408
void primaryDecomposition(const Ideal &ideal, IdealConsumer &consumer)
Compute the canonical primary decomposition of a monomial ideal.
Definition frobby.cpp:396
void multigradedHilbertPoincareSeries(const Ideal &ideal, PolynomialConsumer &consumer)
Compute the multigraded Hilbert-Poincare series of ideal.
Definition frobby.cpp:299
const char *const version
Definition frobby.cpp:31
#define ASSERT(X)
Definition stdinc.h:86