source: git/IntegerProgramming/toric_ideal.hlp @ 194c2e7

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