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,
29 const BigattiParams& params,
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
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
78
79 if (_params.getPrintDebug()) {
80 fputs("Debug: Processing state.\n", stderr);
81 state->print(stderr);
82 }
83
87 if (isBaseCase) {
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
102 colonState->colonStep(pivot);
103 _tasks.addTask(colonState.release());
104
105 state->addStep(pivot);
106 _tasks.addTask(state.release());
107}
108
110 Term& gcd = _tmp_simplify_gcd;
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
126 state->getIdeal().clear(); // To preserve memory
128}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
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.
bool getPrintStatistics() const
Returns whether to print statistics on what the algorithm did to standard error after it has run.
bool getPrintDebug() const
Returns whether to print information about what the algorithm is doing to standard error as it runs.
bool getProduceCanonicalOutput() const
Returns whether to produce output in a canonical representation.
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.
size_t getTotalTasksEver()
Returns the number of times addTask has been successfully called.
void runTasks()
Runs all pending tasks.
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
#define IF_DEBUG(X)
Definition stdinc.h:85
#define ASSERT(X)
Definition stdinc.h:86