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
158}
159
161}
162
164}
165
167}
168
170}
171
173}
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
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) {
223
226 _data->_atVariable = 0;
227 if (_data->_ideal.getVarCount() == 0)
228 return;
229 }
230
232 mpz_set(ref.get_mpz_t(), exponent);
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
335 }
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}
void newLastTerm()
Definition: BigIdeal.cpp:104
const vector< mpz_class > & getTerm(size_t term) const
Definition: BigIdeal.h:139
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
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.
Definition: IdealFacade.cpp:82
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.
Definition: SliceFacade.cpp:78
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.
Definition: SliceFacade.cpp:93
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
bool isIdentity(const Word *a, Word *aEnd)
const char *const version
Definition: frobby.cpp:31
#define ASSERT(X)
Definition: stdinc.h:86