Frobby  0.9.0
MsmStrategy.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 "MsmStrategy.h"
19 
20 #include "MsmSlice.h"
21 #include "Term.h"
22 #include "Ideal.h"
23 #include "TermTranslator.h"
24 #include <vector>
25 #include "Projection.h"
26 #include "TermGrader.h"
27 
29  const SplitStrategy* splitStrategy):
30  SliceStrategyCommon(splitStrategy),
31  _consumer(consumer),
32  _initialSubtract(0) {
33  ASSERT(consumer != 0);
34 }
35 
37  const SplitStrategy* splitStrategy,
38  const Ideal& initialSubtract):
39  SliceStrategyCommon(splitStrategy),
40  _consumer(consumer),
41  _initialSubtract(new Ideal(initialSubtract)) {
42  ASSERT(consumer != 0);
43 }
44 
45 void MsmStrategy::run(const Ideal& ideal) {
46  ASSERT(_initialSubtract.get() == 0 ||
47  _initialSubtract->getVarCount() == ideal.getVarCount());
48 
50  size_t varCount = ideal.getVarCount();
51  if (_initialSubtract.get() == 0)
52  _initialSubtract = auto_ptr<Ideal>(new Ideal(varCount));
53 
54  Term sliceMultiply(varCount);
55  for (size_t var = 0; var < varCount; ++var)
56  sliceMultiply[var] = 1;
57 
58  auto_ptr<Slice> slice
59  (new MsmSlice(*this, ideal, *_initialSubtract, sliceMultiply, _consumer));
60  simplify(*slice);
61 
62  _initialSubtract.reset();
63  _tasks.addTask(slice.release());
64  _tasks.runTasks();
66 }
67 
68 bool MsmStrategy::processSlice(TaskEngine& tasks, auto_ptr<Slice> slice) {
69  ASSERT(slice.get() != 0);
70 
71  if (slice->baseCase(getUseSimplification())) {
72  freeSlice(slice);
73  return true;
74  }
75 
76  if (getUseIndependence() && _indep.analyze(*slice))
77  independenceSplit(slice);
78  else if (_split->isLabelSplit())
79  labelSplit(slice);
80  else {
82  pivotSplit(auto_ptr<Slice>(slice));
83  }
84 
85  return false;
86 }
87 
88 auto_ptr<MsmSlice> MsmStrategy::newMsmSlice() {
89  auto_ptr<Slice> slice(newSlice());
90  ASSERT(dynamic_cast<MsmSlice*>(slice.get()) != 0);
91  return auto_ptr<MsmSlice>(static_cast<MsmSlice*>(slice.release()));
92 }
93 
94 auto_ptr<Slice> MsmStrategy::allocateSlice() {
95  return auto_ptr<Slice>(new MsmSlice(*this));
96 }
97 
99  ASSERT(slice != 0);
100  ASSERT(dynamic_cast<MsmSlice*>(slice) != 0);
101  return true;
102 }
103 
104 void MsmStrategy::labelSplit(auto_ptr<Slice> sliceParam) {
105  ASSERT(sliceParam.get() != 0);
106  ASSERT(debugIsValidSlice(sliceParam.get()));
107  auto_ptr<MsmSlice> slice
108  (static_cast<MsmSlice*>(sliceParam.release()));
109 
110  ASSERT(!slice->adjustMultiply());
111  ASSERT(!slice->normalize());
112  ASSERT(_split != 0);
113  size_t var = _split->getLabelSplitVariable(*slice);
114 
115  Term term(slice->getVarCount());
116 
117  const Term& lcm = slice->getLcm();
118 
119  Ideal::const_iterator stop = slice->getIdeal().end();
120  Ideal::const_iterator label = stop;
121  bool hasTwoLabels = false;
122  for (Ideal::const_iterator it = slice->getIdeal().begin();
123  it != stop; ++it) {
124  if ((*it)[var] == 1) {
125  term = *it;
126  term[var] -= 1;
127 
128  bool couldBeLabel = !slice->getSubtract().contains(term);
129  if (couldBeLabel) {
130  for (size_t v = 0; v < slice->getVarCount(); ++v) {
131  if (term[v] == lcm[v]) {
132  couldBeLabel = false;
133  break;
134  }
135  }
136  }
137 
138  if (couldBeLabel) {
139  if (label == stop)
140  label = it;
141  else {
142  hasTwoLabels = true;
143  break;
144  }
145  }
146  }
147  }
148 
149  auto_ptr<Slice> hasLabelSlice;
150 
151  if (label != stop) {
152  term = *label;
153  term[var] -= 1;
154 
155  hasLabelSlice = newSlice();
156  *hasLabelSlice = *slice;
157  hasLabelSlice->innerSlice(term);
158 
159  if (hasTwoLabels)
160  slice->outerSlice(term);
161  }
162 
163  if (!hasTwoLabels) {
164  term.setToIdentity();
165  term[var] = 1;
166  slice->innerSlice(term);
167  }
168 
169  if (hasLabelSlice.get() != 0) {
170  simplify(*hasLabelSlice);
171  _tasks.addTask(hasLabelSlice.release());
172  }
173 
174  simplify(*slice);
175  _tasks.addTask(slice.release());
176 }
177 
178 class MsmIndependenceSplit : public TermConsumer, public Task {
179 public:
181  return this;
182  }
183 
185  return this;
186  }
187 
189  return &_rightConsumer;
190  }
191 
193  return _leftProjection;
194  }
195 
197  return _rightProjection;
198  }
199 
200  void reset(TermConsumer* consumer,
201  IndependenceSplitter& splitter) {
202  _consumer = consumer;
203  _tmpTerm.reset(splitter.getVarCount());
204 
207 
210  }
211 
212 private:
213  virtual void run(TaskEngine& engine) {
214  dispose();
215  }
216 
217  virtual void dispose() {
218  delete this;
219  }
220 
221  virtual void beginConsuming() {
222  }
223 
224  virtual void doneConsuming() {
225  }
226 
227  virtual void consume(const Term& term) {
231  it != stop; ++it) {
234  }
235  }
236 
237  struct RightConsumer : public TermConsumer {
238  virtual void beginConsuming() {
239  }
240 
241  virtual void doneConsuming() {
242  }
243 
244  virtual void consume(const Term& term) {
245  _decom.insert(term);
246  }
247 
249  } _rightConsumer;
250 
252 
255 
257 };
258 
259 void MsmStrategy::independenceSplit(auto_ptr<Slice> sliceParam) {
260  ASSERT(sliceParam.get() != 0);
261  ASSERT(debugIsValidSlice(sliceParam.get()));
262  auto_ptr<MsmSlice> slice
263  (static_cast<MsmSlice*>(sliceParam.release()));
264 
265  // Construct split object
266  auto_ptr<MsmIndependenceSplit> autoSplit(new MsmIndependenceSplit());
267  autoSplit->reset(slice->getConsumer(), _indep);
268  MsmIndependenceSplit* split = autoSplit.release();
269  _tasks.addTask(split); // Runs when we are done with all of this split.
270 
271  // Construct left slice.
272  auto_ptr<MsmSlice> leftSlice(new MsmSlice(*this));
273  leftSlice->setToProjOf(*slice, split->getLeftProjection(), split);
274  _tasks.addTask(leftSlice.release());
275 
276  // Construct right slice.
277  auto_ptr<MsmSlice> rightSlice(new MsmSlice(*this));
278  rightSlice->setToProjOf(*slice, split->getRightProjection(),
279  split->getRightConsumer());
280  _tasks.addTask(rightSlice.release());
281 
282  // Deal with slice.
283  freeSlice(auto_ptr<Slice>(slice));
284 }
285 
286 void MsmStrategy::getPivot(Term& pivot, Slice& slice) {
287  ASSERT(_split != 0);
289 
290  _split->getPivot(pivot, slice);
291 }
292 
293 void MsmStrategy::getPivot(Term& pivot, Slice& slice, const TermGrader& grader) {
294  ASSERT(_split != 0);
296 
297  _split->getPivot(pivot, slice, grader);
298 }
SliceStrategyCommon::_split
const SplitStrategy * _split
Definition: SliceStrategyCommon.h:80
Projection::inverseProject
void inverseProject(Term &to, const Exponent *from) const
Definition: Projection.cpp:78
MsmStrategy::_consumer
TermConsumer * _consumer
Definition: MsmStrategy.h:63
IndependenceSplitter::getBigProjection
void getBigProjection(Projection &projection) const
Definition: IndependenceSplitter.cpp:24
MsmIndependenceSplit::RightConsumer
Definition: MsmStrategy.cpp:237
stdinc.h
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition: Ideal.h:43
SliceStrategyCommon::newSlice
auto_ptr< Slice > newSlice()
Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice.
Definition: SliceStrategyCommon.cpp:65
Ideal::begin
const_iterator begin() const
Definition: Ideal.h:48
MsmIndependenceSplit::_tmpTerm
Term _tmpTerm
Definition: MsmStrategy.cpp:256
MsmStrategy::_initialSubtract
auto_ptr< Ideal > _initialSubtract
Definition: MsmStrategy.h:65
MsmStrategy::newMsmSlice
auto_ptr< MsmSlice > newMsmSlice()
Definition: MsmStrategy.cpp:88
MsmStrategy::allocateSlice
virtual auto_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
Definition: MsmStrategy.cpp:94
Term::reset
void reset(size_t newVarCount)
Definition: Term.h:543
Ideal::clearAndSetVarCount
void clearAndSetVarCount(size_t varCount)
Definition: Ideal.cpp:646
MsmIndependenceSplit::getLeftConsumer
TermConsumer * getLeftConsumer()
Definition: MsmStrategy.cpp:184
MsmStrategy::_indep
IndependenceSplitter _indep
Definition: MsmStrategy.h:62
MsmIndependenceSplit::run
virtual void run(TaskEngine &engine)
Does whatever work this task represents.
Definition: MsmStrategy.cpp:213
SliceStrategyCommon::_tasks
TaskEngine _tasks
This keeps track of pending tasks to process.
Definition: SliceStrategyCommon.h:84
MsmStrategy::independenceSplit
void independenceSplit(auto_ptr< Slice > slice)
Definition: MsmStrategy.cpp:259
MsmIndependenceSplit::getRightConsumer
TermConsumer * getRightConsumer()
Definition: MsmStrategy.cpp:188
IndependenceSplitter::analyze
bool analyze(const Slice &slice)
Definition: IndependenceSplitter.cpp:32
SplitStrategy
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
Term.h
IndependenceSplitter
Definition: IndependenceSplitter.h:29
SplitStrategy::getPivot
virtual void getPivot(Term &pivot, Slice &slice) const =0
Sets pivot to the pivot of a pivot split on slice.
MsmStrategy::debugIsValidSlice
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
Definition: MsmStrategy.cpp:98
IndependenceSplitter::getVarCount
size_t getVarCount() const
Definition: IndependenceSplitter.cpp:97
MsmStrategy::processSlice
virtual bool processSlice(TaskEngine &tasks, auto_ptr< Slice > slice)
Process the parameter slice.
Definition: MsmStrategy.cpp:68
SliceStrategyCommon::simplify
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
Definition: SliceStrategyCommon.cpp:55
TermConsumer::beginConsuming
virtual void beginConsuming()=0
Tell the consumer to begin consuming an ideal.
TaskEngine
TaskEngine handles a list of tasks that are to be carried out.
Definition: TaskEngine.h:40
MsmSlice
Invariant: either the slice is a trivial base case, or removeDoubleLcm returns false.
Definition: MsmSlice.h:33
Ideal::end
const_iterator end() const
Definition: Ideal.h:49
SplitStrategy::isPivotSplit
virtual bool isPivotSplit() const =0
If returns true, only call getPivot.
SliceStrategyCommon::pivotSplit
virtual void pivotSplit(auto_ptr< Slice > slice)
Takes over ownership of slice.
Definition: SliceStrategyCommon.cpp:77
MsmIndependenceSplit::_leftProjection
Projection _leftProjection
Definition: MsmStrategy.cpp:253
TaskEngine::addTask
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
Ideal.h
SliceStrategyCommon::getUseIndependence
bool getUseIndependence() const
Returns true if independence splits should be performed when possible.
Definition: SliceStrategyCommon.cpp:113
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
TermConsumer
This class is used to transfer terms one at a time from one part of the program to another,...
Definition: TermConsumer.h:36
Task
A Task object represents a unit of work that is performed when the method run() is called.
Definition: Task.h:27
Term
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
SliceStrategyCommon::getUseSimplification
bool getUseSimplification() const
Returns true if slices should be simplified.
Definition: SliceStrategyCommon.cpp:117
MsmIndependenceSplit::getLeftProjection
const Projection & getLeftProjection()
Definition: MsmStrategy.cpp:192
Ideal::getVarCount
size_t getVarCount() const
Definition: Ideal.h:56
MsmIndependenceSplit::RightConsumer::beginConsuming
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition: MsmStrategy.cpp:238
MsmStrategy.h
MsmIndependenceSplit::RightConsumer::doneConsuming
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition: MsmStrategy.cpp:241
IndependenceSplitter::getRestProjection
void getRestProjection(Projection &projection) const
Definition: IndependenceSplitter.cpp:28
MsmStrategy::run
virtual void run(const Ideal &ideal)
Run the Slice algorithm.
Definition: MsmStrategy.cpp:45
MsmIndependenceSplit
Definition: MsmStrategy.cpp:178
TermConsumer::doneConsuming
virtual void doneConsuming()=0
Must be called once after each time beginConsuming has been called.
MsmIndependenceSplit::getLeftEvent
Task * getLeftEvent()
Definition: MsmStrategy.cpp:180
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:251
MsmIndependenceSplit::consume
virtual void consume(const Term &term)
Consume a term.
Definition: MsmStrategy.cpp:227
SliceStrategyCommon
This class adds code to the SliceStrategy base class that is useful for derived classes.
Definition: SliceStrategyCommon.h:34
SplitStrategy::getLabelSplitVariable
virtual size_t getLabelSplitVariable(const Slice &slice) const =0
Returns the variable to perform a label split on.
MsmStrategy::getPivot
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
Definition: MsmStrategy.cpp:286
TaskEngine::runTasks
void runTasks()
Runs all pending tasks.
Definition: TaskEngine.cpp:61
MsmIndependenceSplit::doneConsuming
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
Definition: MsmStrategy.cpp:224
Projection::getRangeVarCount
size_t getRangeVarCount() const
Definition: Projection.cpp:24
TermTranslator.h
MsmSlice.h
SplitStrategy::isLabelSplit
virtual bool isLabelSplit() const =0
If returns true, only call getLabelSplitVariable.
Ideal
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
MsmIndependenceSplit::dispose
virtual void dispose()
Called when the task is no longer used but run has not and will not be called.
Definition: MsmStrategy.cpp:217
Term::setToIdentity
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition: Term.h:296
TermConsumer::consume
virtual void consume(const Term &term)=0
Consume a term.
MsmIndependenceSplit::_rightConsumer
MsmIndependenceSplit::RightConsumer _rightConsumer
Ideal::insert
void insert(const Exponent *term)
Definition: Ideal.cpp:455
Projection
Definition: Projection.h:29
MsmIndependenceSplit::_rightProjection
Projection _rightProjection
Definition: MsmStrategy.cpp:254
MsmIndependenceSplit::RightConsumer::_decom
Ideal _decom
Definition: MsmStrategy.cpp:248
MsmStrategy::MsmStrategy
MsmStrategy(TermConsumer *consumer, const SplitStrategy *splitStrategy)
Definition: MsmStrategy.cpp:28
ASSERT
#define ASSERT(X)
Definition: stdinc.h:85
MsmIndependenceSplit::beginConsuming
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Definition: MsmStrategy.cpp:221
SliceStrategyCommon::freeSlice
virtual void freeSlice(auto_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
Definition: SliceStrategyCommon.cpp:39
MsmIndependenceSplit::getRightProjection
const Projection & getRightProjection()
Definition: MsmStrategy.cpp:196
TermGrader
A TermGrader assigns a value, the degree, to each monomial.
Definition: TermGrader.h:27
Projection.h
MsmStrategy::labelSplit
void labelSplit(auto_ptr< Slice > slice)
Definition: MsmStrategy.cpp:104
MsmIndependenceSplit::RightConsumer::consume
virtual void consume(const Term &term)
Consume a term.
Definition: MsmStrategy.cpp:244
TermGrader.h
MsmIndependenceSplit::_consumer
TermConsumer * _consumer
Definition: MsmStrategy.cpp:251
MsmIndependenceSplit::reset
void reset(TermConsumer *consumer, IndependenceSplitter &splitter)
Definition: MsmStrategy.cpp:200