Frobby  0.9.5
HilbertSlice.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 "HilbertSlice.h"
19 
20 #include "CoefTermConsumer.h"
21 #include "HilbertBasecase.h"
22 #include "HilbertStrategy.h"
23 
25  Slice(strategy),
26  _consumer(0) {
27 }
28 
30  const Ideal& ideal, const Ideal& subtract,
31  const Term& multiply, CoefTermConsumer* consumer):
32  Slice(strategy, ideal, subtract, multiply),
33  _consumer(consumer) {
34  ASSERT(consumer != 0);
35 }
36 
37 bool HilbertSlice::baseCase(bool simplified) {
38  ASSERT(_consumer != 0);
39 
40  // Check that each variable appears in some minimal generator.
42  return true;
43 
44  if (!getLcm().isSquareFree())
45  return false;
46 
47  if (_varCount == 0)
48  return true;
49 
50  // TODO: find a way other than static to use the same basecase
51  // object every time, instead of allocating a new one. This provides
52  // around a 4% speed-up, at least on Cygwin. We cannot use static
53  // since the base case has an mpz_class, and static mpz_class
54  // crashes on Mac OS X.
55  HilbertBasecase basecase;
56  basecase.computeCoefficient(_ideal);
57  const mpz_class& coef = basecase.getLastCoefficient();
58 
59  if (coef != 0)
60  _consumer->consume(coef, getMultiply());
62  return true;
63 }
64 
66  ASSERT(dynamic_cast<const HilbertSlice*>(&slice) != 0);
67 
68  Slice::operator=(slice);
69  _consumer = ((HilbertSlice&)slice)._consumer;
70  return *this;
71 }
72 
74  if (applyLowerBound())
75  return true;
76 
77  pruneSubtract();
78  return false;
79 }
80 
81 void HilbertSlice::setToProjOf(const Slice& slice,
82  const Projection& projection,
83  CoefTermConsumer* consumer) {
84  ASSERT(consumer != 0);
85 
86  Slice::setToProjOf(slice, projection);
87  _consumer = consumer;
88 }
89 
91  Slice::swap(slice);
93 }
94 
95 bool HilbertSlice::getLowerBound(Term& bound, size_t var) const {
96  bool seenAny = false;
97 
99  for (Ideal::const_iterator it = getIdeal().begin(); it != stop; ++it) {
100  if ((*it)[var] == 0)
101  continue;
102 
103  if (seenAny)
104  bound.gcd(bound, *it);
105  else {
106  bound = *it;
107  seenAny = true;
108  }
109  }
110 
111  if (seenAny) {
112  ASSERT(bound[var] >= 1);
113  bound.decrement();
114  return true;
115  } else {
116  // In this case the content is empty.
117  return false;
118  }
119 }
virtual void consume(const Polynomial &poly)
void computeCoefficient(Ideal &ideal)
const mpz_class & getLastCoefficient()
void setToProjOf(const Slice &slice, const Projection &projection, CoefTermConsumer *consumer)
virtual bool getLowerBound(Term &bound, size_t var) const
Calculates a lower bound that depends on var.
virtual bool baseCase(bool simplified)
Returns true if this slice is a base case slice, and in that case produces output in a derivative-spe...
virtual Slice & operator=(const Slice &slice)
Performs a deep copy of slice into this object.
virtual bool simplifyStep()
Like simplify(), except that only one simplification step is performed.
HilbertSlice(HilbertStrategy &strategy)
CoefTermConsumer * _consumer
Definition: HilbertSlice.h:59
void swap(HilbertSlice &slice)
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
Cont::const_iterator const_iterator
Definition: Ideal.h:43
const_iterator end() const
Definition: Ideal.h:49
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
size_t _varCount
The number of variables in the ambient polynomial ring.
Definition: Slice.h:275
Ideal _ideal
The of a slice .
Definition: Slice.h:266
virtual Slice & operator=(const Slice &slice)=0
Performs a deep copy of slice into this object.
Definition: Slice.cpp:77
const Ideal & getIdeal() const
Returns for a slice .
Definition: Slice.h:104
void setToProjOf(const Slice &slice, const Projection &projection)
Set this object to be the projection of slice according to projection.
Definition: Slice.cpp:218
void swap(Slice &slice)
Simultaneously set the value of this object to that of slice and vice versa.
Definition: Slice.cpp:252
bool pruneSubtract()
Removes those generators of subtract that do not strictly divide the lcm of getIdeal(),...
Definition: Slice.cpp:281
void clearIdealAndSubtract()
Clears getIdeal() and getSubtract() and does not change getMultiply().
Definition: Slice.cpp:99
bool applyLowerBound()
Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with ...
Definition: Slice.cpp:289
Term & getMultiply()
Returns for a slice .
Definition: Slice.h:113
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Definition: Slice.cpp:52
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition: Term.h:532
static void gcd(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the greatest common divisor of a and b.
Definition: Term.h:255
size_t getSizeOfSupport(const Word *a, size_t varCount)
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
#define ASSERT(X)
Definition: stdinc.h:86