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