1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
USAGE: toric_ideal [options] matrix_file
DESCRIPTION:
toric_ideal is a program for computing the toric ideal of a matrix A.
This ideal is always given by the reduced Groebner basis with respect
to a given term ordering which is computed via Buchbergers
algorithm.
For this purpose, we can use six different algorithms:
The algorithm of Conti/Traverso (ct) computes the toric ideal of an
extended matrix. This ideal can be used later for solving integer
programming problems for given right hand vectors. By eliminating
auxiliary variables, we can get the toric ideal of the original matrix
from it. The same is true for the "positive" variant of the
Conti-Traverso-algorithm (pct) which can only be applied if A has
nonnegative entries, but should be faster in that case (it computes
the toric ideal of a smaller extended matrix).
All other algorithms compute the toric ideal of A itself. Except from
the elimination version of the Conti-Traverso algorithm (ect), they
should be more efficient than the algorithm mentionned before. These
are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano (blr),
Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two seem to
be the fastest in the actual implementation.
FILE FORMAT:
The input file has to be a MATRIX file. toric_ideal produces a
GROEBNER file named like the MATRIX file with extensions replaced by
.GB.<alg>
where GB stands for GROEBNER and <alg> is the abbreviation for the
used algorithm as above.
A MATRIX file should look as follows:
MATRIX
columns:
<number of columns>
cost vector:
<coefficients of the cost vector>
rows:
<number of rows>
matrix:
<matrix coefficients>
positive row space vector:
<coefficients of row space vector>
The last two lines are only needed when toric_ideal is called with the
algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
options
-alg hs
or
-alg blr
The other algorithms ignore these lines.
Example:
MATRIX
columns:
3
cost vector:
1 1 1
rows:
2
matrix:
1 2 3
4 5 6
positive row space vector:
1 2 3
A GROEBNER file looks as follows:
GROEBNER
computed with algorithm:
<algorithm name abbreviation> (* abbreviations as above *)
from file(s): (* the following four lines are
<name of respective MATRIX file> optional *)
computation time:
<computation time in seconds>
term ordering:
elimination block
<number of elimination variables>
<LEX / DEG_LEX (* only if number of elimination
/ DEG_REV_LEX> variables >0 *)
weighted block
<number of weighted variables>
<W_LEX / W_REV_LEX (* number of weighted variables
/ W_DEG_LEX / W_DEG_REV_LEX> should always be >0 *)
<weight_vector>
size:
<number of elements>
Groebner basis:
<basis elements>
<settings for the Buchberger
algorithm and compiler settings> (* optional *)
The Groebner basis consists always of binomials of the form x^a - x^b
where x^a and x^b are relatively prime. Such a binomial can be
represented by the vector a-b. The basis elements in the GROEBNER file
are given by the coefficients of this vector representation.
The settings for Buchbergers algorithm and the compiler flags are
produced when the GROEBNER file is generated by a call of toric_ideal
with the verbose output option
-v, --verbose
Example (not belonging to the example above):
GROEBNER
computed with algorithm:
du
term ordering:
elimination block:
0
weighted block:
3
W_LEX
1 2 3
size:
1
Groebner basis:
2 3 -2 (* x^2 * y^3 - z^2 *)
OPTIONS:
-alg <alg>,
--algorithm <alg> algorithm to use for computing the toric
ideal; <alg> may be
ct for Conti/Traverso,
pct for the positive Conti/Traverso,
ect for Conti/Traverso with elimination,
pt for Pottier,
hs for Hosten/Sturmfels,
du for Di Biase/Urbanke,
blr for Bigatti-LaScal-Robbiano.
-p <number> percentage of new generators to cause an
autoreduction during Buchbergers algorithm;
<number> may be an arbitrary float, a
negative value allows no intermediate
autoreductions
default is
-p 12.0
-S [RP] [M] [B] [M] [2] criteria to use in Buchbergers algorithm
for discarding unneccessary S-pairs
RP relatively prime leading terms
M Gebauer-Moeller criterion M
F Gebauer-Moeller criterion F
B Gebauer-Moeller criterion B
2 Buchbergers second criterion
default is
-S RP M B
-v,
--verbose verbose output mode; writes the settings for
Buchbergers algorithm and the compiler
flags into the output GROEBNER file
-V <number>,
--version <number> version of Buchbergers algorithm to use;
<number> may be 1, 1a, 2 or 3
default is
-V 1
|
