Frobby  0.9.1
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();
42  _tmp_simplify_gcd.reset(_varCount);
43 
44  _baseCase.setPrintDebug(_params.getPrintDebug());
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 
59  _tasks.runTasks();
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 
75 void 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() ?
85  _baseCase.genericBaseCase(*state) :
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 
125 void BigattiHilbertAlgorithm::freeState(auto_ptr<BigattiState> state) {
126  state->getIdeal().clear(); // To preserve memory
127  _stateCache.freeObject(state);
128 }
BigattiBaseCase::baseCase
bool baseCase(const BigattiState &state)
Returns true if state is a base case slice without considering genericity.
Definition: BigattiBaseCase.cpp:49
BigattiState.h
Term::isIdentity
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
CoefBigTermConsumer
Definition: CoefBigTermConsumer.h:29
stdinc.h
SliceLikeParams::getUseSimplification
bool getUseSimplification() const
Apply simplification to the state of the algorithm when possible.
Definition: SliceLikeParams.h:32
BigattiHilbertAlgorithm::_computeUnivariate
bool _computeUnivariate
Definition: BigattiHilbertAlgorithm.h:72
BigattiHilbertAlgorithm::_pivot
auto_ptr< BigattiPivotStrategy > _pivot
Definition: BigattiHilbertAlgorithm.h:70
ObjectCache::freeObject
void freeObject(auto_ptr< S > object)
Insert an object into the cache.
Definition: ObjectCache.h:90
BigattiHilbertAlgorithm::_baseCase
BigattiBaseCase _baseCase
Definition: BigattiHilbertAlgorithm.h:68
BigattiHilbertAlgorithm::processState
void processState(auto_ptr< BigattiState > state)
Definition: BigattiHilbertAlgorithm.cpp:75
BigattiParams::getUseGenericBaseCase
bool getUseGenericBaseCase() const
Returns whether to detect generic monomial ideals as a base case.
Definition: BigattiParams.h:31
BigattiState
Definition: BigattiState.h:27
BigattiBaseCase::getTotalBaseCasesEver
size_t getTotalBaseCasesEver() const
Returns the total number of base cases this object has seen.
Definition: BigattiBaseCase.cpp:124
ObjectCache::newObjectCopy
auto_ptr< T > newObjectCopy(const S &copyOf)
Returns a copy of copyOf.
Definition: ObjectCache.h:79
TermTranslator
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Definition: TermTranslator.h:41
BigattiBaseCase::setComputeUnivariate
void setComputeUnivariate(bool value)
Use the fine grading if value is false, otherwise grade each variable by the same variable t.
Definition: BigattiBaseCase.cpp:120
BigattiHilbertAlgorithm::run
void run()
Definition: BigattiHilbertAlgorithm.cpp:54
Term::print
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
BigattiHilbertAlgorithm::_tasks
TaskEngine _tasks
Definition: BigattiHilbertAlgorithm.h:62
TaskEngine::addTask
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
Ideal.h
Ideal::getGcd
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
Definition: Ideal.cpp:164
BigattiState::colonStep
void colonStep(const Term &term)
Definition: BigattiState.cpp:79
BigattiBaseCase::feedOutputTo
void feedOutputTo(CoefBigTermConsumer &consumer, bool inCanonicalOrder)
Feed the output Hilbert-Poincare numerator polynomial computed so far to the consumer.
Definition: BigattiBaseCase.cpp:108
Term
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
IF_DEBUG
#define IF_DEBUG(X)
Definition: stdinc.h:85
BigattiState::getMultiply
const Term & getMultiply() const
Definition: BigattiState.cpp:37
CommonParams::getPrintDebug
bool getPrintDebug() const
Returns whether to print information about what the algorithm is doing to standard error as it runs.
Definition: CommonParams.h:61
BigattiState::getIdeal
const Ideal & getIdeal() const
Definition: BigattiState.cpp:33
BigattiHilbertAlgorithm::_params
BigattiParams _params
Definition: BigattiHilbertAlgorithm.h:73
TaskEngine::getTotalTasksEver
size_t getTotalTasksEver()
Returns the number of times addTask has been successfully called.
Definition: TaskEngine.cpp:66
BigattiHilbertAlgorithm::setComputeUnivariate
void setComputeUnivariate(bool value)
Definition: BigattiHilbertAlgorithm.cpp:50
BigattiHilbertAlgorithm::_consumer
CoefBigTermConsumer * _consumer
Definition: BigattiHilbertAlgorithm.h:61
CommonParams::getProduceCanonicalOutput
bool getProduceCanonicalOutput() const
Returns whether to produce output in a canonical representation.
Definition: CommonParams.h:56
BigattiBaseCase::output
void output(bool plus, const Term &term)
Add +term or -term to the output polynomial when plus is true or false respectively.
Definition: BigattiBaseCase.cpp:86
BigattiParams
Definition: BigattiParams.h:25
TaskEngine::runTasks
void runTasks()
Runs all pending tasks.
Definition: TaskEngine.cpp:61
CoefBigTermConsumer.h
BigattiHilbertAlgorithm::BigattiHilbertAlgorithm
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.
Definition: BigattiHilbertAlgorithm.cpp:27
CommonParams::getPrintStatistics
bool getPrintStatistics() const
Returns whether to print statistics on what the algorithm did to standard error after it has run.
Definition: CommonParams.h:66
BigattiHilbertAlgorithm::freeState
void freeState(auto_ptr< BigattiState > state)
Definition: BigattiHilbertAlgorithm.cpp:125
BigattiBaseCase::getTotalTermsInOutput
size_t getTotalTermsInOutput() const
Returns the number of terms in the output polynomial right now.
Definition: BigattiBaseCase.cpp:132
ASSERT
#define ASSERT(X)
Definition: stdinc.h:86
BigattiHilbertAlgorithm::_tmp_simplify_gcd
Term _tmp_simplify_gcd
Definition: BigattiHilbertAlgorithm.h:66
BigattiHilbertAlgorithm.h
BigattiBaseCase::getTotalTermsOutputEver
size_t getTotalTermsOutputEver() const
Returns the total number of terms this object has output.
Definition: BigattiBaseCase.cpp:128
BigattiHilbertAlgorithm::_stateCache
ObjectCache< BigattiState > _stateCache
Definition: BigattiHilbertAlgorithm.h:63
BigattiBaseCase::genericBaseCase
bool genericBaseCase(const BigattiState &state)
Returns ture if state is a base case slice while also considering genericity.
Definition: BigattiBaseCase.cpp:36
SquareFreeTermOps::gcd
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:276
BigattiHilbertAlgorithm::simplify
void simplify(BigattiState &state)
Definition: BigattiHilbertAlgorithm.cpp:109
BigattiHilbertAlgorithm::_varCount
size_t _varCount
Definition: BigattiHilbertAlgorithm.h:59