[6ba162] | 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 | |
---|