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:
36 ConsumerWrapper(size_t varCount):
37 _varCount(varCount),
38 _term(new mpz_ptr[varCount]) {
39 }
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;
62 mpz_ptr* _term;
63};
64
66 public ConsumerWrapper {
67public:
69 size_t varCount):
70 ConsumerWrapper(varCount),
71 _consumer(consumer) {
72 ASSERT(_consumer != 0);
73 }
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:
110 size_t varCount):
111 ConsumerWrapper(varCount),
112 _consumer(consumer),
113 _varCount(varCount) {
114 ASSERT(consumer != 0);
115 }
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
161}
162
165
168
171
174
175namespace FrobbyImpl {
176 using ::BigIdeal;
177
179 public:
180 FrobbyIdealHelper(size_t variableCount):
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
197Frobby::Ideal::Ideal(size_t variableCount) {
198 _data = new FrobbyImpl::FrobbyIdealHelper(variableCount);
199}
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
221void Frobby::Ideal::addExponent(const mpz_t exponent) {
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
236void Frobby::Ideal::addExponent(int exponent) {
237 mpz_class tmp(exponent);
238 addExponent(tmp.get_mpz_t());
239}
240
241void Frobby::Ideal::addExponent(unsigned int exponent) {
242 mpz_class tmp(exponent);
243 addExponent(tmp.get_mpz_t());
244}
245
246bool Frobby::alexanderDual(const Ideal& ideal,
247 const mpz_t* reflectionMonomial,
248 IdealConsumer& consumer) {
249 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
250
251 ExternalIdealConsumerWrapper wrappedConsumer
252 (&consumer, bigIdeal.getVarCount());
253
254 SliceParams params;
255 SliceFacade facade(params, bigIdeal, wrappedConsumer);
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)
263 mpz_set(point[var].get_mpz_t(), reflectionMonomial[var]);
264
265 // We guarantee not to retain a reference to reflectionMonomial
266 // when providing terms to the consumer.
267 reflectionMonomial = 0;
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,
280 const Ideal& reflectionMonomial,
281 IdealConsumer& consumer) {
282 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
283 const BigIdeal& reflectionIdeal =
284 FrobbyImpl::FrobbyIdealHelper::getIdeal(reflectionMonomial);
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
300 PolynomialConsumer& consumer) {
301 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
302
304 (&consumer, bigIdeal.getVarCount());
305 SliceParams params;
306 SliceFacade facade(params, bigIdeal, wrappedConsumer);
307
309}
310
312 PolynomialConsumer& consumer) {
313 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
314
315 ExternalPolynomialConsumerWrapper wrappedConsumer(&consumer, 1);
316 SliceParams params;
317 SliceFacade facade(params, bigIdeal, wrappedConsumer);
318
320}
321
326public:
327 IrreducibleIdealDecoder(IdealConsumer* consumer):
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
348 virtual void consume(mpz_ptr* exponentVector) {
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;
368 mpz_class _zero;
369};
370
372 IdealConsumer& consumer) {
373 IrreducibleIdealDecoder wrappedConsumer(&consumer);
374 if (!irreducibleDecompositionAsMonomials(ideal, wrappedConsumer)) {
375 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
376 consumer.idealBegin(bigIdeal.getVarCount());
377 consumer.idealEnd();
378 }
379}
380
382 IdealConsumer& consumer) {
383 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
384 if (bigIdeal.getGeneratorCount() == 0)
385 return false;
386
387 ExternalIdealConsumerWrapper wrappedConsumer
388 (&consumer, bigIdeal.getVarCount());
389 SliceParams params;
390 SliceFacade facade(params, bigIdeal, wrappedConsumer);
391
393 return true;
394}
395
397 IdealConsumer& consumer) {
398 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
399
400 ExternalIdealConsumerWrapper wrappedConsumer
401 (&consumer, bigIdeal.getVarCount());
402 SliceParams params;
403 SliceFacade facade(params, bigIdeal, wrappedConsumer);
404
406}
407
409 IdealConsumer& consumer) {
410 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
411
412 ExternalIdealConsumerWrapper wrappedConsumer
413 (&consumer, bigIdeal.getVarCount());
414 SliceParams params;
415 SliceFacade facade(params, bigIdeal, wrappedConsumer);
416
418}
419
421 const mpz_t* l,
422 IdealConsumer& consumer) {
423 ASSERT(l != 0);
424
425 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
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
431 ExternalIdealConsumerWrapper wrappedConsumer
432 (&consumer, bigIdeal.getVarCount());
433 SliceParams params;
434 params.useIndependenceSplits(false); // not supported
435 SliceFacade facade(params, bigIdeal, wrappedConsumer);
436
437 mpz_class dummy;
438 return facade.solveStandardProgram(grading, dummy, false);
439}
440
441void Frobby::codimension(const Ideal& ideal, mpz_t codim) {
442 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
443 dimension(ideal, codim);
444 mpz_ui_sub(codim, bigIdeal.getVarCount(), codim);
445}
446
447void Frobby::dimension(const Ideal& ideal, mpz_t dim) {
448 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
449
450 IdealFacade facade(false);
451 mpz_class dimen = facade.computeDimension(bigIdeal, false);
452 mpz_set(dim, dimen.get_mpz_t());
453}
454
455void Frobby::associatedPrimes(const Ideal& ideal, IdealConsumer& consumer) {
456 const BigIdeal& bigIdeal = FrobbyImpl::FrobbyIdealHelper::getIdeal(ideal);
457 IrreducibleIdealDecoder decodingConsumer(&consumer);
458
459 ExternalIdealConsumerWrapper wrappedConsumer
460 (&decodingConsumer, bigIdeal.getVarCount());
461 SliceParams params;
462 SliceFacade facade(params, bigIdeal, wrappedConsumer);
463
465}
const vector< mpz_class > & getTerm(size_t term) const
Definition BigIdeal.h:139
size_t getVarCount() const
Definition BigIdeal.h:148
size_t getGeneratorCount() const
Definition BigIdeal.h:144
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
mpz_class computeDimension(const BigIdeal &ideal, bool codimension=false, bool squareFreeAndMinimal=false)
Compute the Krull dimension of ideal.
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 computeAlexanderDual(const vector< mpz_class > &point)
Compute the Alexander dual of the ideal.
void computeAssociatedPrimes()
Compute the associated primes of the ideal.
void computeMultigradedHilbertSeries()
Compute the numerator of the multigraded Hilbert-Poincare series.
bool solveStandardProgram(const vector< mpz_class > &grading, mpz_class &value, bool reportAllSolutions)
Solve an optimization program over maximal standard monomials.
void computeUnivariateHilbertSeries()
Compute the numerator of the univariate Hilbert-Poincare series.
void computePrimaryDecomposition()
Compute the unique "nicest" primary decomposition of the ideal.
void computeIrreducibleDecomposition(bool encode)
Compute the unique irredundant set of irreducible ideals whose intersection equals ideal.
void computeMaximalStandardMonomials()
Compute the maximal standard monomials of the ideal.
void useIndependenceSplits(bool value)
Definition SliceParams.h:34
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
const mpz_class & getExponent(size_t variable, Exponent exponent) const
This method translates from IDs to arbitrary precision integers.
size_t getVarCount() const
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
size_t getVarCount() const
Returns the current number of variables.
Definition VarNames.h:113
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
This header file includes common definitions and is included as the first line of code in every imple...
#define ASSERT(X)
Definition stdinc.h:86