Frobby 0.9.5
BigattiHilbertAlgorithm.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2009 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
20
21#include "Ideal.h"
22#include "CoefBigTermConsumer.h"
23#include "BigattiState.h"
24
27(auto_ptr<Ideal> ideal,
28 const TermTranslator& translator,
29 const BigattiParams& params,
30 auto_ptr<BigattiPivotStrategy> pivot,
31 CoefBigTermConsumer& consumer):
32 _translator(translator),
33 _consumer(&consumer),
34 _baseCase(translator),
35 _pivot(pivot),
36 _computeUnivariate(false),
37 _params(params) {
38
39 ASSERT(ideal.get() != 0);
40 ASSERT(ideal->isMinimallyGenerated());
41 _varCount = ideal->getVarCount();
43
45
46 // TODO: use swap to avoid copy of ideal.
47 _tasks.addTask(new BigattiState(this, *ideal, Term(_varCount)));
48}
49
51 _computeUnivariate = value;
52}
53
55 if (_pivot.get() == 0)
56 _pivot = BigattiPivotStrategy::createStrategy("median", true);
57
61
63 fputs("*** Statistics for run of Bigatti algorithm ***\n", stderr);
64 fprintf(stderr, " %u states processed.\n",
65 (unsigned int)_tasks.getTotalTasksEver());
66 fprintf(stderr, " %u base cases.\n",
67 (unsigned int)_baseCase.getTotalBaseCasesEver());
68 fprintf(stderr, " %u terms output.\n",
69 (unsigned int)_baseCase.getTotalTermsOutputEver());
70 fprintf(stderr, " %u terms in final output.\n",
71 (unsigned int)_baseCase.getTotalTermsInOutput());
72 }
73}
74
75void BigattiHilbertAlgorithm::processState(auto_ptr<BigattiState> state) {
77 simplify(*state);
78
79 if (_params.getPrintDebug()) {
80 fputs("Debug: Processing state.\n", stderr);
81 state->print(stderr);
82 }
83
84 bool isBaseCase = _params.getUseGenericBaseCase() ?
86 _baseCase.baseCase(*state);
87 if (isBaseCase) {
88 freeState(state);
89 return;
90 }
91
92 const Term& pivot = _pivot->getPivot(*state);
93 if (_params.getPrintDebug()) {
94 fputs("Debug: Performing pivot split on ", stderr);
95 pivot.print(stderr);
96 fputs(".\n", stderr);
97 }
98 ASSERT(!pivot.isIdentity());
99 ASSERT(!state->getIdeal().contains(pivot));
100
101 auto_ptr<BigattiState> colonState(_stateCache.newObjectCopy(*state));
102 colonState->colonStep(pivot);
103 _tasks.addTask(colonState.release());
104
105 state->addStep(pivot);
106 _tasks.addTask(state.release());
107}
108
111 ASSERT(gcd.getVarCount() == _varCount);
112
113 state.getIdeal().getGcd(gcd);
114 if (!gcd.isIdentity()) {
115 // Do colon and output multiply-gcd*multiply.
116 _baseCase.output(true, state.getMultiply());
117 state.colonStep(gcd);
118 _baseCase.output(false, state.getMultiply());
119 }
120
121 IF_DEBUG(state.getIdeal().getGcd(gcd));
122 ASSERT(gcd.isIdentity());
123}
124
125void BigattiHilbertAlgorithm::freeState(auto_ptr<BigattiState> state) {
126 state->getIdeal().clear(); // To preserve memory
127 _stateCache.freeObject(state);
128}
size_t getTotalTermsOutputEver() const
Returns the total number of terms this object has output.
void setPrintDebug(bool value)
Starts to print debug output on what happens if value is true.
bool genericBaseCase(const BigattiState &state)
Returns ture if state is a base case slice while also considering genericity.
size_t getTotalBaseCasesEver() const
Returns the total number of base cases this object has seen.
void setComputeUnivariate(bool value)
Use the fine grading if value is false, otherwise grade each variable by the same variable t.
bool baseCase(const BigattiState &state)
Returns true if state is a base case slice without considering genericity.
void output(bool plus, const Term &term)
Add +term or -term to the output polynomial when plus is true or false respectively.
void feedOutputTo(CoefBigTermConsumer &consumer, bool inCanonicalOrder)
Feed the output Hilbert-Poincare numerator polynomial computed so far to the consumer.
size_t getTotalTermsInOutput() const
Returns the number of terms in the output polynomial right now.
BigattiHilbertAlgorithm(auto_ptr< Ideal > ideal, const TermTranslator &translator, const BigattiParams &params, auto_ptr< BigattiPivotStrategy > pivot, CoefBigTermConsumer &consumer)
Construct an object for running the Bigatti et.al.
void freeState(auto_ptr< BigattiState > state)
auto_ptr< BigattiPivotStrategy > _pivot
CoefBigTermConsumer * _consumer
void simplify(BigattiState &state)
void processState(auto_ptr< BigattiState > state)
ObjectCache< BigattiState > _stateCache
bool getUseGenericBaseCase() const
Returns whether to detect generic monomial ideals as a base case.
Definition: BigattiParams.h:31
void colonStep(const Term &term)
const Term & getMultiply() const
const Ideal & getIdeal() const
bool getPrintStatistics() const
Returns whether to print statistics on what the algorithm did to standard error after it has run.
Definition: CommonParams.h:66
bool getPrintDebug() const
Returns whether to print information about what the algorithm is doing to standard error as it runs.
Definition: CommonParams.h:61
bool getProduceCanonicalOutput() const
Returns whether to produce output in a canonical representation.
Definition: CommonParams.h:56
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
Definition: Ideal.cpp:164
auto_ptr< T > newObjectCopy(const S &copyOf)
Returns a copy of copyOf.
Definition: ObjectCache.h:79
void freeObject(auto_ptr< S > object)
Insert an object into the cache.
Definition: ObjectCache.h:90
bool getUseSimplification() const
Apply simplification to the state of the algorithm when possible.
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
size_t getTotalTasksEver()
Returns the number of times addTask has been successfully called.
Definition: TaskEngine.cpp:66
void runTasks()
Runs all pending tasks.
Definition: TaskEngine.cpp:61
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
void reset(size_t newVarCount)
Definition: Term.h:551
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
Definition: Term.cpp:110
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition: Term.h:316
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
#define IF_DEBUG(X)
Definition: stdinc.h:85
#define ASSERT(X)
Definition: stdinc.h:86