[6ba162] | 1 | // globals.h |
---|
| 2 | |
---|
| 3 | // In this file |
---|
| 4 | // - some facilities as the g++ input/output routines are included, |
---|
| 5 | // - the general data type can be chosen (the people of Singular do not like |
---|
| 6 | // templates), |
---|
| 7 | // - some makros are defined for an easier handling of the program, |
---|
| 8 | // - some flags and constants can be set to observe the behaviour of the |
---|
| 9 | // algorithms when using different strategies. |
---|
| 10 | |
---|
| 11 | #ifndef GLOBALS_H |
---|
| 12 | #define GLOBALS_H |
---|
| 13 | // Include facilities needed by several files: |
---|
| 14 | |
---|
[76f3a18] | 15 | // the following is not good! TODO: move to all including sources... |
---|
| 16 | #include "config.h" |
---|
[4b2690] | 17 | |
---|
[6ba162] | 18 | #include <stdio.h> |
---|
[10b7a4] | 19 | #ifndef HAVE_IOSTREAM_H |
---|
| 20 | #include <iostream> |
---|
| 21 | #include <fstream> |
---|
| 22 | #include <iomanip> |
---|
| 23 | #include <limits> |
---|
| 24 | #else |
---|
[6ba162] | 25 | #include <iostream.h> |
---|
| 26 | #include <fstream.h> |
---|
| 27 | #include <iomanip.h> |
---|
[10b7a4] | 28 | #include <limits.h> |
---|
| 29 | #endif |
---|
[6ba162] | 30 | #include <stddef.h> |
---|
| 31 | #include <stdlib.h> |
---|
| 32 | #include <math.h> |
---|
| 33 | #include <string.h> |
---|
| 34 | |
---|
[10b7a4] | 35 | using namespace std; |
---|
| 36 | |
---|
[6ba162] | 37 | // Include a BigInt class from a foreign library: |
---|
| 38 | // This is needed by the LLL algorithm. If no such class is included, |
---|
| 39 | // it computes with long ints; this results in overflows and unexpected |
---|
| 40 | // behaviour even when computing with relatively small instances. |
---|
| 41 | |
---|
| 42 | #define GMP |
---|
| 43 | |
---|
| 44 | #ifdef GMP |
---|
| 45 | |
---|
| 46 | #include "BigInt.h" |
---|
| 47 | |
---|
| 48 | #else // GMP |
---|
| 49 | |
---|
| 50 | typedef long BigInt; |
---|
| 51 | |
---|
| 52 | #endif // GMP |
---|
| 53 | |
---|
| 54 | // Define the general data type: |
---|
| 55 | // short seems to be sufficient for most practicable instances. |
---|
| 56 | |
---|
| 57 | typedef short Integer; |
---|
| 58 | // The general data type to deal with can be short, long or int... |
---|
| 59 | |
---|
[194c2e7] | 60 | //#define _SHORT_ |
---|
[6ba162] | 61 | // For an overflow control for thE result of the LLL algorithm, we have to |
---|
| 62 | // know the data type used. |
---|
| 63 | |
---|
| 64 | |
---|
| 65 | |
---|
| 66 | // Define a BOOLEAN data type etc. for an easy-to-read code: |
---|
| 67 | |
---|
| 68 | typedef char BOOLEAN; |
---|
| 69 | #define TRUE 1 |
---|
| 70 | #define FALSE 0 |
---|
| 71 | |
---|
| 72 | #define MAXIMUM(a,b) (a>b? a:b) |
---|
| 73 | |
---|
| 74 | #define INHOMOGENEOUS 0 |
---|
| 75 | #define HOMOGENEOUS 1 |
---|
| 76 | // For a more comfortable call of the term_ordering constructors. |
---|
| 77 | |
---|
| 78 | |
---|
| 79 | |
---|
| 80 | |
---|
| 81 | // Enumerate the algorithms: |
---|
| 82 | // The ideal constructor (builds an ideal from the input matrix) depends on |
---|
| 83 | // the algorithm. The constants are defined to make constructor calls easier |
---|
| 84 | // (you do not need to remember a number). |
---|
| 85 | |
---|
| 86 | #define CONTI_TRAVERSO 1 |
---|
| 87 | #define POSITIVE_CONTI_TRAVERSO 2 |
---|
| 88 | #define POTTIER 3 |
---|
| 89 | #define HOSTEN_STURMFELS 4 |
---|
| 90 | #define DIBIASE_URBANKE 5 |
---|
| 91 | #define BIGATTI_LASCALA_ROBBIANO 6 |
---|
| 92 | |
---|
| 93 | |
---|
| 94 | |
---|
| 95 | |
---|
| 96 | // Enumerate the criteria to discard unnecessary S-pairs: |
---|
| 97 | // The constants are defined to allow an easier call of BuchbergerŽs algorithm |
---|
| 98 | // with different criteria. This algorithm takes as an argument a short int |
---|
| 99 | // which represents the combination of criteria to be used (with a default |
---|
| 100 | // combination if no argument is given). |
---|
| 101 | // The method to compute the argument for a certain combination is simple: |
---|
| 102 | // Simply add the constants that belong to criteria you want to use. As the |
---|
| 103 | // constants are chosen to be different powers of 2, each short int (in the |
---|
| 104 | // range of 0 to 31) gives a unique combination (cf. the read-write-execute |
---|
| 105 | // rights for files in UNIX systems). |
---|
| 106 | // EXAMPLE: |
---|
| 107 | // If you want to call BuchbergerŽs algorithm with the criterion "relatively |
---|
| 108 | // prime leading terms" and the second criterion for the ideal I, write: |
---|
| 109 | // |
---|
| 110 | // I.reduced_Groebner_basis_1(REL_PRIMENESS + SECOND_CRITERION); |
---|
| 111 | // or |
---|
| 112 | // I.reduced_Groebner_basis_1(17); |
---|
| 113 | // |
---|
| 114 | // The argument 0 means that no criteria are used, the argument 31 leads to |
---|
| 115 | // the use of all criteria. |
---|
| 116 | |
---|
| 117 | #define REL_PRIMENESS 1 |
---|
| 118 | #define M_CRITERION 2 |
---|
| 119 | #define F_CRITERION 4 |
---|
| 120 | #define B_CRITERION 8 |
---|
| 121 | #define SECOND_CRITERION 16 |
---|
| 122 | |
---|
| 123 | // The names of tehse criteria are chosen according to the criteria |
---|
| 124 | // described in Gebauer/Moeller (except from the last). |
---|
| 125 | // The first one (relatively prime leading terms) is a local criterion |
---|
| 126 | // and the most effective. |
---|
| 127 | // The last four criteria are global ones involving searches over the |
---|
| 128 | // generator lists. But although the lcm-computations performed by these |
---|
| 129 | // checks are not much cheaper than a reduction, most of the criteria seem to |
---|
| 130 | // accelerate the computations. |
---|
| 131 | // REL_PRIMENESS should always be used. |
---|
| 132 | // The Gebauer/Moeller-criteria (M,F,B) seem to improve computation time in |
---|
| 133 | // the general case; Buchberger's second criterion seems to improve it in |
---|
| 134 | // more special cases (for example the transportation problem). They should |
---|
| 135 | // be switched on and off according to these results, but never be enabled |
---|
| 136 | // together; the overhead of too many criteria leads to a rather bad |
---|
| 137 | // performance in all cases. |
---|
| 138 | // The relatively primeness criterion is tested first because it |
---|
| 139 | // is very easy to check. The order of the Gebauer/Moeller-criteria does not |
---|
| 140 | // really affect computation. The relative order of the Gebauer/Moeller |
---|
| 141 | // criteria and the second criterion (if they are enabled together) has almost |
---|
| 142 | // the same effect as switching off the last criterion in this order. |
---|
| 143 | // There is no possibility to change the order in which the criteria are |
---|
| 144 | // tested without changing the program! |
---|
| 145 | |
---|
| 146 | |
---|
| 147 | |
---|
| 148 | |
---|
| 149 | // Enumerate the term orderings that can be used to refine the weight: |
---|
| 150 | // W_REV_LEX will give a term ordering in the classical sense if and only if |
---|
| 151 | // all weights are positive. It has been implemented because several |
---|
| 152 | // algorithms need a reverse lexicographical refinement. (Of course, these |
---|
| 153 | // algorithms control if they have a positive grading.) |
---|
| 154 | // A warning will be output when using W_REV_LEX in an insecure case. |
---|
| 155 | |
---|
| 156 | #define W_LEX 4 |
---|
| 157 | #define W_REV_LEX 5 |
---|
| 158 | #define W_DEG_LEX 6 |
---|
| 159 | #define W_DEG_REV_LEX 7 |
---|
| 160 | |
---|
| 161 | |
---|
| 162 | |
---|
| 163 | // Enumerate the term ordering used for the block of elimination variables: |
---|
| 164 | |
---|
| 165 | #define LEX 1 |
---|
| 166 | #define DEG_LEX 2 |
---|
| 167 | #define DEG_REV_LEX 3 |
---|
| 168 | |
---|
| 169 | ////////////////////////////////////////////////////////////////////////////// |
---|
| 170 | /////////////// TEST PARAMETER SECTION //////////////////////////////// |
---|
| 171 | ////////////////////////////////////////////////////////////////////////////// |
---|
| 172 | |
---|
| 173 | // Set flags concerning the basic operations and the course of Buchberger's |
---|
| 174 | // algorithm: |
---|
| 175 | |
---|
| 176 | #define SUPPORT_DRIVEN_METHODS |
---|
| 177 | // possibilities: |
---|
| 178 | // SUPPORT_DRIVEN_METHODS |
---|
| 179 | // NO_SUPPORT_DRIVEN_METHODS |
---|
| 180 | |
---|
| 181 | // This flag allows to switch of and on the use of the support vectors in |
---|
| 182 | // the binomial class; these are used to speed up tests for reducibility of |
---|
| 183 | // binomials, relative primeness etc. |
---|
| 184 | |
---|
| 185 | #define SUPPORT_DRIVEN_METHODS_EXTENDED |
---|
| 186 | // possibilities: |
---|
| 187 | // SUPPORT_DRIVEN_METHODS_EXTENDED |
---|
| 188 | // NO_SUPPORT_DRIVEN_METHODS_EXTENDED |
---|
| 189 | |
---|
| 190 | // This flag allows to switch of and on the extended use of the support |
---|
| 191 | // information. This includes the splitting of the ideal generators into |
---|
| 192 | // several lists according to their head support. This discards many |
---|
| 193 | // unnecessary tests for divisibility etc. |
---|
| 194 | // SUPPORT_DRIVEN_METHODS_EXTENDED should only be enabled when |
---|
| 195 | // SUPPORT_DRIVEN_METHODS is set, too! The combination |
---|
| 196 | // NO_SUPPORT_DRIVEN_METHODS and SUPPORT_DRIVEN_METHODS_EXTENDED is quite |
---|
| 197 | // senseless and will only work if your compiler automatically initializes |
---|
| 198 | // integers to zero. |
---|
| 199 | |
---|
| 200 | const unsigned short List_Support_Variables=8; |
---|
| 201 | |
---|
| 202 | // This is the number of variables considered to create and maintain the |
---|
| 203 | // generator lists of an ideal if SUPPORT_DRIVEN_METHODS_EXTENDED is |
---|
| 204 | // enabled. As there are 2^List_Support_Variables lists, this number |
---|
| 205 | // should not be too big (to avoid the overhead of many empty lists). |
---|
| 206 | // The best number may depend on the problem size and structure... |
---|
| 207 | |
---|
| 208 | #define SUPPORT_VARIABLES_LAST |
---|
| 209 | // possibilities: |
---|
| 210 | // SUPPORT_VARIABLES_LAST |
---|
| 211 | // SUPPORT_VARIABLES_FIRST |
---|
| 212 | |
---|
| 213 | // This flag determines whether the first or the last variables are considered |
---|
| 214 | // by the support methods. So this setting will only affect the computation if |
---|
| 215 | // such methods are enabled. |
---|
| 216 | // The reason for the introduction of this flag is the following: |
---|
| 217 | // The Conti-Traverso algorithm for solving an integer program works in two |
---|
| 218 | // phases: Given an artificial solution in auxiliary variables, these |
---|
| 219 | // variables are first eliminated to get a feasible solution. The elimination |
---|
| 220 | // variables are for technical reasons always the last. In a second phase, |
---|
| 221 | // this solution is reduced to a minimal solution with respect to a given |
---|
| 222 | // term ordering. |
---|
| 223 | // If SUPPORT_VARIABLES_LAST is set, the first phase will probably take |
---|
| 224 | // less time as if SUPPORT_VARIABLES_FIRST is set. If one is only interested |
---|
| 225 | // in finding a feasible solution (not necessary minimal), |
---|
| 226 | // SUPPORT_VARIABLES_LAST might be the better choice. |
---|
| 227 | |
---|
| 228 | #endif // GLOBALS_H |
---|
| 229 | |
---|