# source:git/IntegerProgramming/binomial.h@6ba162

spielwiese
Last change on this file since 6ba162 was 6ba162, checked in by Hans Schönemann <hannes@…>, 23 years ago
This commit was generated by cvs2svn to compensate for changes in r4282, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@4283 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 10.6 KB
Line
1// binomial.h
2
3// The binomials considered here are differences of power-products of a
4// special kind. The initial monomial or head (with respect to a given
5// term ordering as described in term_ordering.h) has coefficient 1, the other
6// monomial (the tail) has coefficient -1. The head and the tail of a
7// binomial are always relatively prime, i.e., they do not involve common
8// variables.
9
10// Such a binomial in n variables is represented as an Integer vector of
11// size n: If the i-th variable is involved in the head with exponent k,
12// the i-th component of the vector is set to k. If the i-th variable is
13// involved in the tail with exponent k, the i-th component of the vector
14// is set to -k.
15
16// The members head_support and tail_support of type unsigned long have to be
17// understood as bit-vectors with m components, where m is the number of
18// bits in a long integer. The i-th bit of head_support tells us if the i-th
19// variable is involved in the head of the binomial (for i<=m): it is 1
20// iff this variable appears in the head. Analogously for tail_support.
21// Using these vectors, the question if a binomial can be reduced by another
22// can often be answered by performing a simple bitwise operation.
23
24// To avoid global variables, the number of variables is taken by the
25// constructors. But as it is the same for all appearing binomials during
26// the run of our algorithms (unless some elimination is done), the member
27// functions do not perform any range checks. This makes the algorithms
28// more efficient.
29
30// Most of the constructors do not perform sign checks on their arguments.
31// The reason is simple: Unlike the matrix or term ordering constructors, some
32// binomial constructors are frequently called during computation. As the
33// new binomials are build from the input binomials, it is sufficient to do
34// these checks on the input.
35
36
37
38#ifndef BINOMIAL_H
39#define BINOMIAL_H
40
41
42
43class term_ordering;
44
45
46
47class binomial
48{
49
50
51
52private:
53
54  Integer* exponent_vector;
55
56  short _number_of_variables;
57
58
59#ifdef SUPPORT_DRIVEN_METHODS
60
62  unsigned long tail_support;
63
64#endif  // SUPPORT_DRIVEN_METHODS
65
66
67
68public:
69
70
71
72// constructors and destructor
73
74  binomial(const short& number_of_variables);
75  // Allocates memory for a binomial of size number_of_variables
76  // without initialization.
77  // No range check on the argument!
78
79  binomial(const short& number_of_variables, const Integer* exponents);
80  binomial(const short& number_of_variables, const Integer* exponents,
81           const term_ordering&);
82  // These constructors build a binomial from its exponent vector/array.
83  // The first one takes the positive components as its head, the negative
84  // ones as its tail; the second one determines its head and tail with
85  // respect to the given term ordering.
86  // The array "exponents" is always copied. It would be faster to set
87  // only pointers on it. However, this is very dangerous, and as these
88  // constructors are only used at the beginning of the algorithm, it would
89  // not really improve performance.
90  // The Integer pointer exponents is declared as "const" to suggest that
91  // the referenced array is not changed (although the "const"-declaration
92  // does not assert this).
93  // These constructor check the range (sign) of their argument
94  // number_of_variables because it is not frequently called, but at a
95  // critical point (ideal constructors).
96
97  binomial(const binomial&);
98  // copy-constructor
99  // No check if the copied binomial is corrupt!
100
101  ~binomial();
102  // destructor
103
104
105
106// object information
107
108  short number_of_variables() const;
109  // Returns the number of variables.
110
111  short error_status() const;
112  // Returns _number_of_variables iff _number_of_variables<0
113  // (this is the "errror flag").
114
115
116
117// assigment and access operators
118
119  binomial& operator=(const binomial&);
120  // assignment operator with memory control
121
122  Integer operator[](const short& i) const;
123  // Access operator for reading exponent_vector[i]
124  // (cannot be used to overwrite exponent_vector[i]);
125  // no range chack on i!
126
127
128
129// comparison operators
130
131  BOOLEAN operator==(const binomial& v) const;
132  BOOLEAN operator!=(const binomial& v) const;
133  // comparison of binomials
134
135  BOOLEAN operator==(const Integer comp_value) const;
136  BOOLEAN operator!=(const Integer comp_value) const;
137  BOOLEAN operator<=(const Integer comp_value) const;
138  BOOLEAN operator>=(const Integer comp_value) const;
139  // operators for an efficient comparison with the zero binomial
140  // (comp_value=0)
141
142
143
144// basic routines for Buchbergers's algorithm
145
146  Integer head_reductions_by(const binomial& b) const;
147  // Returns the number of possible reductions of the actual binomial's head
148  // by the binomial b.
149  // The return value -1 means that b==0 or head(b)==1; one should not try
150  // reduce by such a binomial (reduction is undefined or does not terminate).
151  // The procedure reduce_tail_by(...) returns the unchanged binomial in such
152  // a case without a warning. This is done in view of the application:
153  // If a generator of an ideal is reduced to zero during a Groebner basis
154  // calculation and one forgets to delete it, this generator is ignored
155  // (else it would probably cause a fatal error).
156
157  Integer tail_reductions_by(const binomial& b) const;
158  // Returns the number of possible reductions of the actual binomial's tail
159  // by the binomial b.
160  // For the return value -1 see above.
161
162  int reduce_head_by(const binomial& b, const term_ordering& w);
163  // Performs a multiple reduction of the actual binomial's head by the
164  // binomial b and computes the new head and tail with respect to the term
165  // ordering w.
166  // The return value is 1 if the binomial has really been reduced, 2 if
167  // the binomial has been reduced to zero, 0 if the binomial has not been
168  // changed.
169
170  int reduce_tail_by(const binomial& b, const term_ordering& w);
171  // Performs a multiple reduction of the actual binomial's tail by the
172  // binomial b and computes the new head and tail with respect to the term
173  // ordering w.
174  // The return value is 1 if the binomial has really been reduced, else 0.
175  // (By a tail reduction, the binomial cannot be reduced to zero if the
176  // binomial itself and b are consistent with w, i.e. if head and tail are
177  // correct.)
178
179  friend binomial& S_binomial(const binomial& a, const binomial& b,
180                              const term_ordering& w);
181  // Computes the S-binomial of a and b with respect to the term ordering w
182  // and returns a reference on it (the necessary memory is allocated during
183  // the computation).
184
185
186
187// criteria for unnecessary S-Pairs
188
189  friend BOOLEAN relatively_prime(const binomial& a, const binomial& b);
190  // Returns TRUE iff the leading terms of a and b are relatively prime.
191
192  friend BOOLEAN M(const binomial& a,const binomial& b,const binomial& c);
194
195  friend BOOLEAN F(const binomial& a, const binomial& b, const binomial& c);
197
198  friend BOOLEAN B(const binomial& a, const binomial& b, const binomial& c);
201
202  friend BOOLEAN second_crit(const binomial& a, const binomial& b,
203                             const binomial& c);
205
206
207
208// special routines needed by the IP-algorithms
209
210// All this routines are not very frequently used (especially not in
211// Buchberger's algorithm), so I haven't spent much time in optimization.
212// None of them performs range checks on their arguments.
213
214  BOOLEAN involves_elimination_variables(const term_ordering& w);
215  // Verifies if the binomial involves elimination variables with respect
216  // to w.
217  // UNCHECKED PRECONDITION: w and the binomial are compatible, i.e.
218  // involve the same number of variables.
219
220  BOOLEAN drop_elimination_variables(const term_ordering& w);
221  // Cuts the elimination variables (with respect to w) from the binomial
222  // and adapts the member _number_of_variables as well as the head and the
223  // tail.
224  // UNCHECKED PRECONDITION: w and the binomial are compatible.
225  // The interesting part of the binomial (ot its additive inverse) is copied
226  // hereby to be able to free the memory needed by the dropped components.
227
228  BOOLEAN drop_last_weighted_variable(const term_ordering& w);
229  // Cuts the last variable from the binomial and adapts the member
230  // _number_of_variables as well as head and tail (the last two to the given
231  // term_ordering)
232  // UNCHECKED PRECONDITION: w is a weighted termordering (without elimination
233  // variables) that is compatible to the actual binomial.
234  // The interesting part of the binomial (ot its additive inverse) is copied
235  // hereby to be able to free the memory needed by the dropped components.
236
238  // Determines head and tail of the binomial with respect to the given term
239  // ordering; i.e. multiplies the exponent vector with -1 and exchanges
240  // head_support and tail_support, if necessary.
241  // Returns -1 if head and tail were exchanged, 1 else.
242  // UNCHECKED PRECONDITION: w and the binomial are compatible.
243
244  binomial& swap_variables(const short& i,const short& j);
245  // Swaps the components i and j of the exponent vector and actualizes
247  // No range check on the arguments!
248
249  binomial& flip_variable(const short& i);
250  // Inverts component i of the exponent vector and actualizes head_support
251  // and tail_support.
252  // No range check on i!
253
254
255
256// output
257
258  void print() const;
259  void print_all() const;
260  // Writes the actual binomial to the standard output medium.
261  // The first routine only prints the exponent vector, the second prints
262  // the head and tail support, too (if SUPPORT_DRIVEN_METHODS are used).
263
264  void print(FILE* output) const;
265  void print_all(FILE* output) const;
266  // Writes the actual binomial to the referenced file which must have
267  // been opened for writing before.
268
269  void print(ofstream&) const;
270  void print_all(ofstream&) const;
271  // Writes the actual binomial to the given ofstream.
272
273  void format_print(ofstream&) const;
274  // Writes the given binomial to the actual ofstream in the format needed
275  // by the IP-algorithms.
276
277  friend class ideal;
278  // The class ideal is declared as a friend for efficiency reasons:
279  // This avoids many unnecessary function calls for inspecting members
280  // like head_support and tail_support.
281  // The class ideal does not change any members of the binomial class.
282
283  friend short term_ordering::compare(const binomial&, const binomial&) const;
284
285
286};
287
288
289#endif  // BINOMIAL_H
290
291
292
293
294
295
296
297
298
299
300
301
302
Note: See TracBrowser for help on using the repository browser.