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 | |
---|
43 | class term_ordering; |
---|
44 | |
---|
45 | |
---|
46 | |
---|
47 | class binomial |
---|
48 | { |
---|
49 | |
---|
50 | |
---|
51 | |
---|
52 | private: |
---|
53 | |
---|
54 | Integer* exponent_vector; |
---|
55 | |
---|
56 | short _number_of_variables; |
---|
57 | |
---|
58 | |
---|
59 | #ifdef SUPPORT_DRIVEN_METHODS |
---|
60 | |
---|
61 | unsigned long head_support; |
---|
62 | unsigned long tail_support; |
---|
63 | |
---|
64 | #endif // SUPPORT_DRIVEN_METHODS |
---|
65 | |
---|
66 | |
---|
67 | |
---|
68 | public: |
---|
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); |
---|
193 | // Verifies if lcm(head(a),head(c)) divides properly lcm(head(b),head(c)). |
---|
194 | |
---|
195 | friend BOOLEAN F(const binomial& a, const binomial& b, const binomial& c); |
---|
196 | // Verifies if lcm(head(a),head(c))=lcm(head(b),head(c)). |
---|
197 | |
---|
198 | friend BOOLEAN B(const binomial& a, const binomial& b, const binomial& c); |
---|
199 | // Verifies if head(a) divides lcm(head(b),head(c)) and |
---|
200 | // lcm(head(a),head(b))!=lcm(head(b),head(c))!=lcm(head(a),head(c)). |
---|
201 | |
---|
202 | friend BOOLEAN second_crit(const binomial& a, const binomial& b, |
---|
203 | const binomial& c); |
---|
204 | // Verifies if head(a) divides lcm(head(b),head(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 | |
---|
237 | int adapt_to_term_ordering(const term_ordering&); |
---|
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 |
---|
246 | // head_support and tail_support. |
---|
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 | |
---|