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 // assignment 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 303