1 // ideal.h 2 3 // This class implements a saturated binomial ideal. Such an ideal is 4 // given by its generators. 5 // If SUPPORT_DRIVEN_METHODS_EXTENDED are enabled, the generators are not 6 // stored in a single list, but classified according to their support. This 7 // representation, together with the subset_tree data structure, allows a 8 // faster search for reducers. 9 10 // The entries of the two-dimensional array "subsets_of_support" are to be 11 // read as bit vectors with List_Support_Variables components (the constant 12 // List_Support_Variables is defined in globals.h). So all entries 13 // are in the range between 0 and 2^List_Support_Variables -1. 14 // subsets_of_support[i] is an array that contains all binary vectors whose 15 // support is a subset of that of i, i read as a binary vector. 16 // number_of_subsets[i] is the number of these subsets, i.e. the length of 17 // the array subsets_of_support[i]. 18 19 // If, for example, List_Support_Variables=8, the datastructure subset_tree 20 // has 6561=8^3 entries. 21 22 23 24 #ifndef IDEAL_H 25 #define IDEAL_H 26 27 28 29 #include "list.h" 30 #include "matrix.h" 31 32 33 34 35 const int Number_of_Lists=1<<List_Support_Variables; 36 37 38 39 40 ////////////////////// struct subset_tree //////////////////////////////////// 41 42 typedef struct 43 { 44 int* subsets_of_support[Number_of_Lists]; 45 int number_of_subsets[Number_of_Lists]; 46 } subset_tree; 47 48 //////////////////////// class ideal ///////////////////////////////////////// 49 50 class ideal 51 { 52 53 private: 54 55 // generator lists 56 57 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED 58 59 subset_tree S; 60 61 list generators[Number_of_Lists]; 62 63 list new_generators[Number_of_Lists]; 64 // Only needed in some special versions of Buchberger�s algorithm to 65 // store newly found generators. 66 67 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED 68 69 70 #ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED 71 72 list generators; 73 74 list new_generators; 75 // Only needed in some special versions of Buchberger�s algorithm to 76 // store newly found generators. 77 78 #endif // NO_SUPPORT_DRIVEN_METHODS_EXTENDED 79 80 // flags for the use of the S-pair criteria and the autoreduction 81 82 int rel_primeness; 83 int M_criterion; 84 int F_criterion; 85 int B_criterion; 86 int second_criterion; 87 // When Buchberger�s algorithm is called, we only use one argument which 88 // describes the combination of the criteria to be used (see in globals.h). 89 // But we use five flags instead of one here because this is a little more 90 // efficient. 91 // The standard setting enables the relative primeness criterion, the M- and 92 // the B-criterion. 93 94 float interreduction_percentage; 95 // To determine the autoreduction frequency, i.e. the percentage of new 96 // generators (i.e. generators found since the last autoreduction) with 97 // respect to the total size of an ideal that must be reached to cause an 98 // interreduction. 99 // If Interreduction_Percentage==0, interreduction is done after each 100 // S-Pair computation. If Interreduction_Percentage<0, interreduction is 101 // only done once at the end of the algorithm. 102 // The standard setting is 12 (=12%). 103 104 // further members 105 106 term_ordering w; 107 // For technical reasons, the term ordering is taken as a member. 108 // So we do not need to pass it as an argument to each ideal function, 109 // and the management of the generator lists is easier and safer when 110 // using SUPPORT_DRIVEN_METHODS_EXTENDED. 111 112 list aux_list; 113 // an auxiliary list for keeping (for example) S-pairs 114 115 long size; 116 // the actual number of generators of the ideal 117 // Also used as an "error flag"; a negative size means that an error has 118 // occurred: 119 // -1 indicates a "semantic" error (which occurs e.g. if some constructor 120 // argument is out of range) 121 // -2 indicates an error occurred when reading from a file 122 // -3 indicates an overflow of an integer type variable 123 124 125 long number_of_new_binomials; 126 // the number of newly found generators 127 128 // private member functions 129 130 // subroutines for building and deleting the subset_tree data structure 131 // (implemented in ideal.cc) 132 133 #ifdef SUPPORT_DRIVEN_METHODS_EXTENDED 134 135 void create_subset_tree(); 136 void destroy_subset_tree(); 137 138 #endif // SUPPORT_DRIVEN_METHODS_EXTENDED 139 140 // subroutines for Buchberger�s algorithm (implemented in Buchberger.cc except 141 // from the first two implemeted in ideal.cc) 142 143 // Some of these procedures do not interact with all versions of Buchberger�s 144 // algorithm. Generally, they cannot be combined as one likes. This header 145 // file only gives a brief overview of their features. For more detailed 146 // comments see the implementation. 147 148 ideal& add_new_generator(binomial& bin); 149 ideal& add_generator(binomial& bin); 150 // Inserts a (new) generator in the appropriate list. 151 152 int add_new_generators(); 153 // Moves the new generators to the generator lists. 154 155 // S-pair computation 156 157 BOOLEAN unnecessary_S_pair(list_iterator&, list_iterator&) const; 158 // Checks if the S_Pair of the binomials referenced by the iterators can be 159 // discarded (by the criteria chosen in globals.h). 160 161 ideal& compute_actual_S_pairs_1(); 162 ideal& compute_actual_S_pairs_1a(); 163 ideal& compute_actual_S_pairs_2(); 164 ideal& compute_actual_S_pairs_3(); 165 // different versions for computing the S-binomials of the actual generators 166 // They differ for example in the following points: 167 // - They insert the S-binomials in the order in which they are computed, in 168 // the order given by the term ordering w or according to their support. 169 // - Some reduce an S-binomial directly after its computation by the ideal 170 // generators, others reduce it later (after having computed more 171 // S-binomials, hence more possible reducers). 172 // - Some reduce the ideal generators immediately by a newly computed 173 // S-binomial, others don�t. 174 // In each case, the use of the list flag "done" guarantees that we perform 175 // the S-pair computation only once for each binomial pair. 176 177 // minimalization / autoreduction 178 179 ideal& reduce_by(const binomial&, list_iterator&, list_iterator&); 180 // Reduces the heads of the ideal generators by the given binomial 181 // (used by some versions of the S-pair computation). 182 183 ideal& minimalize_S_pairs(); 184 ideal& minimalize_new_generators(); 185 ideal& minimalize(); 186 // Performs an autoreduction of the binomials stored in aux_list 187 // respectively in the list(s) new_generators respectively in the 188 // generators. 189 // The respective list(s) is (are) reduced to a minimal set (not 190 // necessarily to a reduced set); this means that only the heads of the 191 // binomials are reduced, not their tails. This strategy showed to be 192 // a little more efficient than a complete autoreduction. 193 // The last two procedures use the "head_reduced" flag of the list class 194 // to avoid unnecessary tests for interreduction. 195 196 ideal& final_reduce(); 197 // final interreduction of the ideal generators 198 // It seems to be slightly more efficient to perform a complete 199 // interreduction only at the end of Buchberger's algorithm and 200 // to replace the intermediate interreductions by minimalizations. 201 // For efficiency reasons, this routine is designed for reducing a 202 // Groebner basis of an saturated ideal. Reducing another generating 203 // set with it may cause inconsistencies (cf. comment in the implementation). 204 205 // constructor subroutines for the handling of the different algorithms 206 // (implemented in ideal.cc) 207 // The "Conti-Traverso constructors" create a toric ideal directly from the 208 // input matrix and the term ordering given by the input weight vector. 209 // The other constructors create a toric ideal from a lattice basis of 210 // the kernel of the input matrix. 211 212 ideal& Conti_Traverso_ideal(matrix&, const term_ordering&); 213 ideal& Positive_Conti_Traverso_ideal(matrix&, const term_ordering&); 214 ideal& Pottier_ideal(matrix&, const term_ordering&); 215 ideal& Hosten_Sturmfels_ideal(matrix&, const term_ordering&); 216 ideal& DiBiase_Urbanke_ideal(matrix&, const term_ordering&); 217 ideal& Bigatti_LaScala_Robbiano_ideal(matrix&, const term_ordering&); 218 219 public: 220 221 // constructors and destructor (implemented in ideal.cc) 222 223 ideal(matrix&, const term_ordering&, const int& algorithm); 224 // Creates a binomial ideal from the given matrix using the given algorithm 225 // (see in globals.h). 226 // The arguments are checked for consistency as far as possible. 227 // The term ordering is needed to determine the leading terms of the 228 // binomials in the resulting generating set. Neither is the generated ideal 229 // saturated nor is it given in form of a Groebner basis. 230 // Such computations must be explicitely demanded. 231 // The argument matrix cannot be declared as const because the constructor 232 // may call the LLL-algorithm to compute the matrix kernel (if this hasn�t 233 // been done yet). This algorithm changes some matrix members. But the 234 // real matrix remains, of course, unchanged. 235 236 ideal(const ideal&); 237 // copy-constructor 238 // It might be useful to keep several Groebner bases of the same ideal 239 // (or of an ideal and its elimination ideal). 240 241 ideal(ifstream&, const term_ordering&, const int& number_of_generators); 242 // Reads an ideal from a given ifstream in the following way: 243 // A block of integers is converted into a binomial 244 // that is stored in the generator list(s) with respect to the given 245 // term ordering. The size of such a block is the size of the given 246 // term_ordering, i.e. the number of variables for which it was constructed. 247 // This is done number_of_generators times. 248 249 ~ideal(); 250 // destructor 251 252 // object information (implemented in ideal.cc) 253 254 long number_of_generators() const; 255 // Returns the actual number of generators. 256 257 int error_status() const; 258 // Returns -1 if an error has occurred (i.e. size<0), else 0. 259 260 // Buchberger stuff (implemented in Buchberger.cc) 261 262 ideal& reduced_Groebner_basis_1(const int& S_pair_criteria=11, 263 const float& interred_percentage=12.0); 264 ideal& reduced_Groebner_basis_1a(const int& S_pair_criteria=11, 265 const float& interred_percentage=12.0); 266 ideal& reduced_Groebner_basis_2(const int& S_pair_criteria=11, 267 const float& interred_percentage=12.0); 268 ideal& reduced_Groebner_basis_3(const int& S_pair_criteria=11, 269 const float& interred_percentage=12.0); 270 // Several different versions of Buchberger�s algorithm for computing 271 // the reduced Groebner basis of the actual ideal. They differ in the 272 // steering of the algorithm (i.e. in the way in which the S-pair 273 // computation and reduction is organized). Further variants can be 274 // obtained by setting the flags in globals.h (autoreduction frequency, 275 // use of the S-pair criteria and the support information). 276 // Except from the variant 1a (which orders the S-pairs with respect to w 277 // and which showed to be quite slow), the efficiency of these algorithms 278 // does not differ too much. 279 // The first argument indicates which criteria will be used to discard 280 // unnecessary S-pairs. For an explaination of how this works, see in 281 // globals.h. The default value 11 means that we use the criterion of 282 // relatively prime leading terms as well as the M- and the B-criterion. 283 // The second argument specifies the interreduction frequency; see the 284 // comment for the member interreduction_percentage above. The standard 285 // value is 12%. 286 // ATTENTION: In spite of the different argument type you should never 287 // try to use these functions with one default argument (either two or 288 // none). When writing 289 // reduced_Groebner_basis_1(10.5), 290 // the GNU C++ compiler casts 10.5 into an integer and takes it as the 291 // argument S_pair_criteria! 292 // ATTENTION: If the input ideal is not saturated, the computed reduced 293 // Groebner basis is not that of the input ideal, but that of an ideal 294 // "between" the input ideal and its saturation. 295 296 ideal& reduced_Groebner_basis(const int& version=1, 297 const int& S_pair_criteria=11, 298 const float& interred_percentage=12.0); 299 // Takes the version of Buchberger�s algorithm as above as an argument 300 // (to allow a call of different versions of our IP-algorithms from the 301 // command line). To call version 1a, the first argument has to be zero. 302 303 binomial& reduce(binomial& bin, BOOLEAN complete=TRUE) const; 304 // Reduces a binomial by the actual generators. 305 // To reduce a binomial by the ideal (outside of Buchberger�s algorithm), 306 // be sure to have computed the reduced Groebner basis before. 307 // The flag "complete" indicates if the binomial is reduced completely 308 // (head and tail); if it is set to FALSE, only the tail will be reduced. 309 // Using this flag in a clever manner allows to improve the performance 310 // of Buchberger's algorithm by up to three percent. 311 312 // special features needed by our IP-algorithms 313 // (implemented in ideal_stuff.cc) 314 315 ideal& eliminate(); 316 // Eliminates the generators involving elimination variables 317 // (with respect to the term ordering w). 318 // The reduced Groebner basis with respect to w should have been computed 319 // before calling this routine. 320 321 ideal& pseudo_eliminate(); 322 // Eliminates the generators involving the last weighted variable - 323 // a special routine needed by the algorithm of Bigatti, La Scala and 324 // Robbiano. 325 326 ideal& change_term_ordering_to(const term_ordering& _w); 327 // Replaces the actual term ordering by the argument ordering. 328 // Their "compatibility" (number of variables) is checked, head and tail 329 // of the generators are adapted to the new ordering. 330 // This may especially involve a rebuilding of the list structure if 331 // SUPPORT_DRIVEN_METHODS_EXTENDED are enabled. 332 333 ideal& swap_variables(const int& i, const int& j); 334 // Swaps the i-th and the j-th variable in all generators as well as the 335 // corresponding components of the term ordering's weight vector. 336 // If SUPPORT_DRIVEN_METHODS are enabled, the list structure is rebuilt 337 // according to the new order on the variables. 338 339 ideal& swap_variables_unsafe(const int& i, const int& j); 340 // Swaps the i-th and the j-th variable in all generators as well as the 341 // corresponding components of the term ordering's weight vector. 342 // DANGER: The head/tail structure is not rebuilt! 343 344 ideal& flip_variable_unsafe(const int& i); 345 // Inverts the sign of the i-th variable in all generators. 346 // DANGER: The list structure is not rebuilt! 347 348 // output (implemented in ideal.cc) 349 350 void print() const; 351 void print_all() const; 352 // Writes the ideal to the standard output medium. 353 // The second routine also prints the S-pair flags. 354 355 void print(FILE*) const; 356 void print_all(FILE*) const; 357 // Writes the ideal to the referenced file which has to be opened 358 // for writing before. 359 360 void print(ofstream&) const; 361 void print_all(ofstream &) const; 362 // Writes the ideal to the given ofstream. 363 364 void format_print(ofstream&) const; 365 // Writes the ideal generators to the given ofstream in a format 366 // that allows them to be reread by the ideal constructor from an ifstream. 367 368 }; 369 370 #endif // IDEAL_H 371