Home

manual

1. It is optional and the default is all The mat must be given with this file The homogeneous generators of the linear system A basis for the linear subspace of the cone If this file does not exist then the linear subspace is trivial Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed Use the Matrix algorithm default for 32 and 64 Use the Support algorithm default for arbitrary Set ORDERING as the ordering in which the columns are chosen The possible orderings are maxinter minindex maxcutoff default and mincutoff Set the frequency of output default is 1000 Do not output anything to the screen Display this help and exit Chapter 3 Command line reference 45 3 13 rays Usage rays options PROJECT Computes the extreme rays of a cone Input Files PROJECT mat PROJECT sign PROJECT rel Output Files PROJECT ray PROJECT qfree Options p precision PREC mat support order ORDERING output freg n quiet help A matrix compulsory The sign constraints of the variables 1 means non negative 0 means a free variable and 2 means both non negative and non positive It is optional and the default is all non negative The relations on the matrix rows lt gt It is optional and the d
2. version Display version information Output options q quiet Quiet mode u update 1 Updated output on console default uu update 2 More verbose updated output on console v verbose 1 Output once every variable computation vv verbose 2 Output once every norm sum computation vvv verbose 3 Output once every norm computation Logging options n log 0 Disable logging default 1 log 1 Log once every variable computation to PROJECT log 11 log 2 Log once every norm sum computation to PROJECT log 111 log 3 Log once every norm computation to PROJECT log Input files PROJECT mat Matrix PROJECT lat Lattice basis can be provided instead of matrix PROJECT sign Sign of columns optional PROJECT 1b Lower bounds of columns optional PROJECT ub Upper bounds of columns optional Backup files Chapter 3 Command line reference 31 PROJECT backup Backup file PROJECT backup Temporary backup file if it exists it may be newer than PROJECT backup Output files PROJECT gra Graver basis PROJECT zfree Free part of the solution PROJECT maxnorm Vectors with maximum norm if m maxnorm is in use 3 5 groebner 32 3 5 groebner Usage groebner options PROJECT Computes a Groebner basis of the toric ideal of a matrix or more general of the lattice ideal of a lattice Input Files PROJECT PROJECT PROJECT PROJECT PROJECT PROJECT PROJECT PRO
3. 2 1 Affine systems and their encodings 24 with A R and A ZZ respectively In order to solve this affine system using zsolve we create the following input files to encode the affine system affine lat affine sign 14 2 4 1220 1 1 1 0 2 3 0 1 and then call zsolve affine This creates the files affine zhom and affine zinhon Chapter 3 Command line reference 3 1 circuits Usage circuits options PROJECT Computes the circuits of a cone Input Files PROJECT mat A matrix compulsory PROJECT sign The sign constraints of the variables 1 means non negative 0 means a free variable and 2 means both non negative and non positive It is optional and the default is both PROJECT rel The relations on the matrix rows lt gt It is optional and the default is all The mat must be given with this file Output Files PROJECT cir The circuits of the cone PROJECT qfree A basis for the linear subspace of the cone If this file does not exist then the linear subspace is trivial Options p precision PREC Select PREC as the integer arithmetic precision 25 3 1 circuits 26 mat support order ORDERING output freg n quiet help PREC is one of the following 64 default 32 and arbitrary only arb is needed Use the Matrix algorithm default for 32 and 6
4. FILENAME EXT O 1 transpose Transpose matrix and write it FILENAME EXT tra in 4ti2 format degree Print 1 norms of all vectors degree N Extract all vectors of 1 norm FILENAME EXT deg N equal to N degree N1 N2 Extract all vectors of 1 norm FILENAME EXT deg N1 N2 between N1 and N2 inclusive support Print supports of all vectors support S Extract all vectors of support FILENAME EXT supp S Chapter 3 Command line reference Al size equal to S support S1 2 Extract all vectors of support FILENAME EXT supp S1 S2 size between 21 and S2 incl positive Extract positive parts of vectors FILENAME EXT pos Corresponds to leading terms of binomials 3way ABC Write vectors as 3 way tables FILENAME EXT 3way of size Ax Bx C nonzero at K Extract all vectors that have FILENAME EXT nonzero K nonzero K th coordinate Undocumented or obscure options for experts representatives dominated Extract all non dominated vectors FILENAME EXT nondom maximal non dominated FILENAME EXT maxnondom expand representatives to full orbits type T AxB Computes a matrix vector product macaulay2 mathematica cocoa sum Print the sum of the columns submatrix LISTFILENAME FILENAME EXT submat remove column I FILENAME EXT remcol remcol I FILENAME EXT remcol stabilizer SYMMFILENAME FILENAME EXT stab fill column FILENAME EXT fil add column FILENAME EXT addcol fix Ii IK Extract fixed vectors FILENAME E
5. 2 3 6 12 1 4 1 2 11 tig ty T 3 _4ti2_int64_t rel m 4 _4ti2_LB _4ti2_UB _4ti2_UB _4ti2_LB _4ti2_int64_t sign n _4ti2_LB _4ti2_LB _4ti2_LB Output data const int k 4 int64_t zhom k n 3 4 1 3 8 5 TL 9 2 4 19 18 5 T _4ti2_state zsolve_api _4ti2_zsolve_create_state _4ti2_PREC_INT_64 const int argc 2 char argv 2 char zsolve char q _4ti2_state_set_options zsolve_api argc argv _4ti2_matrix cons_matrix _4ti2_state_create_matrix zsolve_api m n mat amp cons_matrix for int i 0 i lt m i for int j 0 j lt n j L _4ti2_matrix_set_entry_int64_t cons_matrix i j mat i j T _4ti2_matrix_write_to_stdout cons_matrix _4ti2_matrix rel_matrix _4ti2_state_create_matrix zsolve_api 1 m rel amp rel_matrix for int i 0 i lt m i _4ti2_matrix_set_entry_int64_t rel_matrix 0 i relli Ati2 matrix write to stdout rel matrix _4ti2_matrix sign matrix _4ti2_state_create_matrix zsolve_api 1 n sign amp sign matrix for int i 0 i lt n i 4 3 Example program qsolve 56 _4ti2_matrix_set_entry_int64_t sign_matrix 0 i sign i _4ti2_matrix_write_to_stdout sign_matrix _4ti2_state_ compute zsolve_api _4ti2_matrix zhom_matrix _4ti2_state_ get_matrix zsolve_api zhom amp zhom_matri
6. 3 x 4x6 table with 2 marginals that is again only counts along coordinate axes corresponds to the complex 1 2 2 3 3 1 on 3 nodes with levels 3 4 and 6 respectively Thus its encoding is in 4ti2 would look like 3x4x6 mod 3 3 4 6 3 2 2 2 3 2 1 A binary model on the bipartite graph Ka then reads as k2_3 mod NN NN Ny N a N q N NN Ra on Pp wom Ee w Chapter 2 Advanced guide In this part we deal with several more advanced problem specifications in 4ti2 First we introduce affine systems and their encodings In fact affine systems are the basic objects used in 4ti2 since every linear system is transformed into an affine system However in the integer situation it is not always possible to trans form an affine system back into a linear system without adding variables or modulo constraints 2 1 Affine systems and their encodings Let a Lz be an integer linear affine space given by the vector a Z and by generators for the lattice Lz C Z We wish to find a finite sign compatible description for the set of all integer vectors x a Lz As an example let consider the linear space Cr and the lattice Lz both spanned by the two vectors 1 2 1 0 and 2 3 0 1 Moreover consider the sign constraints 1 2 2 0 Thus we are looking for a finite explicit sign compatible description for all x that can be written as 1 2 Be A 1 0 0 1
7. There is a new function minimize to solve integer linear programs 68 AUTHORS The 4ti2 team Ralf Hemmecke Raymond Hemmecke Matthias Koeppe Peter Malkin Matthias Walter 69 70 THANKS Many thanks to Kris Nairn for suggesting the name 4ti2 Cool Moreover lots of thanks to many 4ti2 users for suggesting many interesting and useful improvements 71 72 Bibliography 1 2 3 4 5 6 7 8 A M Bigatti R LaScala and L Robbiano Computing toric ideals Journal of Symbolic Computation 27 1999 351 365 J A De Loera R Hemmecke and M K ppe Algebraic and geometric ideas in the theory of discrete optimization MOS SIAM Series on Optimization Society for Industrial and Applied Mathematics Philadelphia PA 2013 doi 10 1137 ISBN 978 1 61197 243 6 R Gebauer and H M Moller On an installation of Buchberger s algorithm Journal of Symbolic Computation 6 1988 275 286 U U Haus M Koppe and R Weismantel A primal all integer algorithm based on irreducible solutions Math Programming Series B 96 2003 no 2 205 246 R Hemmecke Exploiting symmetries in the computation of Graver bases 2004 arXiv math C0 0410334 R Hemmecke On the computation of Hilbert bases of cones Mathematical Software ICMS 2002 A M Cohen X S Gao and N Takayama eds World Scientific 2002 On the positive sum property and the computation
8. gt 20 for all 2 7 1 2 3 Bringing all x to the left hand side of these equations the matrix A3x3 defining this linear system is 1 1 1 1 1 0 0 U 111 0 0 1 1 1 0 1 1 1 0 1 0 0 Aan 101 0 1 0 1 0 110 0 0 1 0 1 0 1 1 0 1 U 1 110 0 1 0 1 0 U Below we will deal with the more interesting case of integer magic squares For the moment however we wish to compute the extreme rays of the magic square cone z Asss2 0 2 gt 0 In order to call the function rays we only have to create one file say magic3x3 mat in which we specify the problem matrix A3 3 The remaining data is set by default to 1 2 Brief tutorial 12 equations only to homogeneous system and to all variables are non negative Note that we are allowed to change these defaults except homogeneity by specifying data in magic3x3 rel and magic3x3 sign magic3x3 mat 7 9 1 1 1 1 1 1 0 0 0 1 11 0 0 0 1 1 1 U 1 1 1 0 0 1 U 1 01 0 1 0 0 110 et U 1 0 1 1 0 1 0 U 1 1 1 0 0 1 1 0 Now we call rays magic3x3 which creates the single file magic3x3 ray 4 9 02 11210102 12001220 1 201012120 10221002 1 that corresponds to the four extremal rays of the 3 x 3 magic square cone Every magic 3 x 3 square is a non negative linear combination of these four magic squares If we turn now to integer magic squares we are looking
9. maxnorm Vectors with maximum norm if m maxnorm is in use 3 16 zsolve 50 Chapter 4 Ati2 as a callable library Some portions of 4ti2 can be used as a callable library to avoid I O and process overhead It has a simple C API that closely mirrors the commands qsolve rays circuits zsolve hilbert graver Depending on its configuration 4ti2 builds and installs several libraries either as static or shared libraries using libtool The functions equivalent to zsolve hilbert graver require the use of libzsolve The functions equivalent to qsolve rays circuits require the use of 1ib4ti2common and depending on the arithmetic precision requested the use of 1ib4ti2int32 11b4ti2int64 or 1ib4ti2gmp 4 1 C API header file 4ti2 4ti2 h A single header file lt 4ti2 4ti2 h gt provides the C API It is reproduced below for reference 4ti2 A software package for algebraic geometric and combinatorial problems on linear spaces Copyright C 2008 4ti2 team Main author s Peter Malkin This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License 51 4 1 C API header file 4ti2 4ti2 h 52 as published by the Free Software Foundation either version 2 of the License or at your option any later version This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHAN
10. of Graver test sets Math Programming Series B 96 2003 247 269 R Hemmecke and P N Malkin Computing generating sets of lattice ideals and Markov bases of lattices Journal of Symbolic Computation 44 2009 1463 1476 73 BIBLIOGRAPHY 74 9 S Hosten and B Sturmfels GRIN An implementation of Gr bner bases for integer programming Integer Programming and Combinatorial Optimization E Balas and J Clausen eds Lecture Notes in Computer Science vol 920 Springer Berlin Heidelberg 1995 pp 267 276 doi 10 1007 3 540 59408 6_ ISBN 978 3 540 59408 6 10 M K ppe Erzeugende Mengen f r gemischt ganzzahlige Programme Diploma thesis Otto von Guericke Universitat Magdeburg 1999 available from URL http www math ucdavis edu mkoeppe art mkoeppe diplom ps 11 P N Malkin Truncated Markov bases and Gr bner bases for integer program ming 2006 arXiv math 0612615 12 B Sturmfels Algebraic recipes for integer programming 2003 arXiv math 0C 0310194 13 R Urbaniak Decomposition of generating sets and of integer programs Disser tation Technische Universitat Berlin 1998 BIBLIOGRAPHY 75
11. that you enable c support enable cxx configure option If you have installed gmp but not in a location that 4ti2 finds by default then you Chapter 5 README Instructions on configuring and building 4ti2 61 will need to invoke configure with gmp ROOT OF GMP INSTALLATION HIERARCHY If you have gmp but not with c support then configure will fail with an error saying that the file gmpxx h cannot be found USING MACPORTS ON MAC OS X Use the following commands sudo port install gmp glpk configure with gmp opt local with glpk opt local make sudo make install INSTALLATION ON WINDOWS USING CYGWIN 1 Install Cygwin from https www cygwin com In the installer select the following packages Devel gcc core gcc g make Math glpk gmp libglpk devel libgmp devel 2 Make sure you unpack the 4ti2 sources into a C DIRECTORY WITHOUT SPACES IN IT for example C 4ti2 3 Open the Cygwin terminal 4 Type 62 cd cygdrive c DIRECTORY WITHOUT SPACES IN IT configure make make install 5 Now you can run 4ti2 s commands from the Cygwin terminal DOCUMENTATION See the manual or the website http www 4ti2 de for information on using 4ti2 Chapter 6 NEWS Changes to 4ti2 since version 1 2 News in 4ti2 version 1 6 6 compared to 1 6 5 Fix segfault in graver when a matrix with trivial kernel is input testcase graver trivial kernel Reported by Alfredo Sanchez News i
12. the normal form of a list of feasible points Input Files PROJECT mat A matrix optional if lattice basis is given PROJECT lat A lattice basis optional if matrix is given PROJECT gro The Groebner basis of the lattice needed PROJECT cost The cost matrix optional default is degrevlex Ties are broken with degrevlex PROJECT feas An list of integer feasible solutions needed PROJECT sign The sign constraints of the variables 1 means non negative and 70 means a free variable It is optional and the default is all non negative Output Files PROJECT nf The normal forms of the feasible solutions Options p precision PREC Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed q quiet Do not output anything to the screen h help Display this help and exit 3 10 output 40 3 10 output usage output options FILENAME EXT Transforms a 4ti2 matrix file to something else General options quiet No output is written to the screen Options that control what to output their output files binomials Write vectors as binomials FILENAME EXT bin Use an optional input file FILENAME EXT vars to specify variable names maple Write vectors as Maple list FILENAME EXT maple This format is suitable also for CoCoA Mathematica Macaulay2 0 1 Extract vectors with 0 1 components only
13. two files ppi17 mat so we do not really have to create this file our selves and the file ppi17 gra containing the desired identities Compare this run ning time with the time taken by 1 2 Brief tutorial 16 graver ppi17 Do you notice the speed up Let us now turn to the question of determining the support minimal partition iden tities This in fact is the question of computing the circuits of the matrix del TBS ee RT We use the same input file ppi3 mat 1 3 1 2 3 as above and call circuits ppi3 This call will create an output file ppi3 cir that looks like ppi3 cir 3 3 30 1 2 1 U 0 3 2 Thus there are 3 support minimal partition identities of order n 3 1 1 1 3 1 1 2 2 2 2 3 3 Note that support minimal partition identities are primitive since the circuits of a matrix are contained in the Graver basis of this matrix See the book 2 section 3 8 or Hemmecke 7 for details on the algorithm imple mented Chapter 1 Beginner s guide 17 1 2 5 Integer programming and toric Grobner bases In this example you learn about the functions minimize groebner and normalform The following neat example is based on the example presented in 12 Let us assume that we want to give change worth 99 cents using only pennies 1ct nickels 5ct dimes 10ct and quarters 25ct Clearly 4 14 4 5 0 10 3 25 99 would be one way to do it Is this there anot
14. 0000000000 0 000111100000000 0 000000011110000 0 00000000000 1 1 1 1 1 000100010001000 0 100010001000100 0 010001000100010 0 00100010001000 1 Chapter 1 Beginner s guide 21 Let us compute the Markov basis via the call markov 4x4 which creates a single output file 4x4 mar containing the 36 Markov basis elements Up to symmetry swapping rows or columns the Markov basis consists of the single move 1 1 0 0 1 100 0 000 0 000 In fact this elementary move is up to symmetry the only representative of the minimal Markov moves for arbitrary m x n tables using row and column counts Creating the matrices for statistical models may be pretty cumbersome 4ti2 pro vides a litte function genmodel that helps the user with creating matrices for hierarchical models defined by a complex The m x n tables problem above corresponds to the complex 1 2 on two nodes with levels m and n respectively Let us encode the complex for 3 x 6 tables with 1 marginals row and column sums in 3x6 mod 3x6 mod 3 3 2 1 1 and call genmodel 3x6 to produce the desired matrix file 3x6 mat The encoding of the complex should be obvious from the example first we state the number of nodes and their levels then we give the number of maximal faces Finally 1 2 Brief tutorial 22 we list each maximal face by first specifying the number of nodes on it and then by listing these nodes Thus a
15. 4 Use the Support algorithm default for arbitrary Set ORDERING as the ordering in which the columns are chosen The possible orderings are maxinter minindex maxcutoff default and mincutoff Set the frequency of output default is 1000 Do not output anything to the screen Display this help and exit Chapter 3 Command line reference 27 3 2 genmodel usage genmodel options FILENAME Computes the problem matrix corresponding to graphical statistical models given by a simplicial complex and levels on the nodes Options q quiet No output is written to the screen Input file FILENAME mod Simplicial complex and levels on the nodes Output file FILENAME mat Matrix file Example Consider the problem of 3x3x3 tables with 2 marginals These are given by K_3 as the simplicial complex on 3 nodes and with levels of 3 on each node In 333 mod write 33 12 23 31 Calling genmodel 333 produces the following file 333 mat 27 27 100000000100000000100000000 010000000010000000010000000 N N N U U W m 10010 000000 0100100000000 010010000000 o o o 00000000 00000000 00000000 oo oo oo 0000000000000 111000 000 Oo o 00000000 00000000 orRrnOoOoRr oo G w G a Oo o o o o o o 3 2 genmodel 28 Chapter 3 Command line reference 3 3 gensymm usage gensymm options A BC D FILENAME Computes the generators for
16. JECT mat lat cost sign mar weights weights max zsol Output Files PROJECT Options p precision PREC gro a algorithm ALG g generation ALG A matrix optional if lattice basis is given A lattice basis optional if matrix is given The cost matrix which determines the term ordering optional default is degrevlex Ties are broken with degrevlex The sign constraints of the variables 1 means non negative and 0 means a free variable It is optional and the default is all non negative The Markov basis generating set of the lattice optional The weight vectors used for truncation optional The maximum weights used for truncation This file is needed when PROJECT weights exists An integer solution to specify a fiber optional The integer solution is used for truncation The Groebner basis of the lattice Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed Select ALG as the completion procedure for computing Groebner bases ALG is one of fifo weighted or unbounded Select ALG as the procedure for computing a generating set or Markov basis ALG is one of hybrid default project and lift max min or saturation Chapter 3 Command line reference 33 t truncation TRUNC Set TRUNC as the truncation met
17. T e The matrix A has to be put into the file PROJECT mat 24 1111 1234 The relations then have to be specified in PROJECT rel 12 lt lt The right hand side vector goes into PROJECT rhs 12 6 10 And finally the sign constraints end up in PROJECT sign 14 1220 Chapter 1 Beginner s guide 7 Note e The input files all have the format of a matrix preceded by the matrix di mensions As the dimensions already specify how many symbols have to be read the matrix could also be given in only one line or even in many lines of different lengths e In 4ti2 version 1 3 1 and later all appearing numbers have to be integers e Consequently this implies that at the moment qsolve only supports homoge neous linear systems that is systems with b 0 since minimal inhomogeneous solutions could have rational components 1 1 3 What does an explicit solution to linear systems look like If the system is solved over R using qsolve 4ti2 returns two sets of integer vectors e aset H of support minimal homogeneous solutions and e a set F defining the linear vector space the solution set lives in As only homogeneous linear systems are supported in this version of 4ti2 no list of minimal inhomogeneous solutions is computed Any solution z of the linear system v X wh V Bef 1 1 with h H fk F and a gt 0 can now be written as If the system is solved over Z using zsol
18. TABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have received a copy of the GNU General Public License along with this program if not write to the Free Software Foundation Inc 51 Franklin Street Fifth Floor Boston MA 02110 1301 USA ifndef define _4ti2_H _4ti2_H include lt inttypes h gt include 4ti2 4ti2_config h ifdef _ 4ti2_HAVE_GMP include lt gmp h gt endif ifdef extern endif Enum typedef Enum typedef Enum typedef 4ti2 typedef typedef non cplusplus representing the possible arithmetic precision settings available enum _4ti2_PREC_INT_32 32 _4ti2_PREC_INT_64 64 _4ti2_PREC_INT_ARB 0 _4ti2_precision representing values describing the constraints on a variable or row of the constraint matrix enum _4ti2_FR 0 _4ti2_LB 1 _4ti2_UB 1 _4ti2_DB 2 _4ti2_FX 3 _4ti2_constraint representing the exit status of an API call to 4ti2 enum _4ti2_OK 0 _4ti2_ERROR 1 _4ti2_status data structures struct _4ti2_state _4ti2_state struct _4ti2_matrix _4ti2_matrix Create a QSolve 4ti2 state object _4ti2_state _4ti2_qsolve_create_state _4ti2_precision prec Create a QSolve 4ti2 rays object _4ti2_state _4ti2_rays_create_state _4ti2_precision prec Create a QSolve 4ti2 circuits object _4ti2_state _4ti2_circuits_create_state _4ti2_prec
19. User s Guide for 4ti2 version 1 6 6 svn A software package for algebraic geometric and combinatorial problems on linear spaces June 10 2015 Contents Tree ee eT eee Se Tee ST 1 1 1 Linear systems and integer linear systems 1 1 2 Specifying a linear system in 4ti2 1 1 3 What does an explicit solution to linear systems look like 1 2 Brief tutorial esco ee ee Re a 1 2 1 Solving linear systems over Z with zsolve ere el ade ae ee ee 1 2 5 Integer programming and toric Grobner bases 1 2 6 Markov Bases in Statistics 2 22 on on nn 2 Advanced guide 2 1 Affine systems and their encodings 2 222 nn nenn 3 Command line reference AA s dk 6 we be bee ACR Oe MALE Re A g a A OS a 3 2 genmouel lt 222 2 ds ey ee ee ah Hee abo trae BA CONTENTS 4 ELO TODE a poe oe eee BE ee ee Pee ee ne RE nee 32 36 II AI 34 AA ARA ae 36 A AAA E 38 39 lO sess e Aa AR 39 AI AE 40 A AE 43 A AI 44 AE EA 45 AM cara A A Se hee 46 MATT HT 47 SED ee ee ree A ae ee ee AE 48 4 Ati2 as a callable library 51 4 1 C API header file 4ti2 4ti2 h occ eee ee eee ee ee eas 51 4 2 Example program zsolve zu we oo ae a a OS 54 4 3 Example program qsolve es 4 aca oH eos a Da oa ea Bee ws 56 5 README Instructions on configuring and building 4ti2 59 6 NEWS Changes to 4ti2 since version 1 2 63 AUTHORS The 4ti2 team 68 THANKS 70 Bibliography 72 Chapter 1 Beginner s gu
20. XT fix that is those vectors that have x i i for the given i fox Ii IK Extract relaxed fixed vectors FILENAME EXT fox 3 10 output 42 initial forms Extract initial forns FILENAME ini Call with FILENAME rather FILENAME ini bin than FILENAME EXT Reads FILENAME gro and optionally FILENAME cost and FILENAME vars Examples output binomials file gra writes the Graver basis elements as binomials in file gra bin output 0 1 foo gra extracts the 0 1 elements from the Graver basis elements and writes them into foo gra 0 1 Chapter 3 Command line reference 43 3 11 ppi usage ppi binary output N Computes the primitive partition identities that is the Graver basis of 1 23 N Options b binary output Create a binary file ppiN dat instead of text file ppiN gra 3 12 qsolve 44 3 12 qsolve Usage qsolve options PROJECT Computes a generator description of a cone Input Files PROJECT mat PROJECT sign PROJECT rel Output Files PROJECT ah om PROJECT qfree Options p precision PREC mat support order ORDERING output freg n quiet help A matrix compulsory The sign constraints of the variables 1 means non negative 70 means a free variable and 2 means both non negative and non positive It is optional and the default is all free The relations on the matrix rows lt gt
21. bner basis of the toric ideal Ia x 2 Au Av u v ZA with respect to a term ordering lt compatible with c that is C v lt cTu implies x lt x This toric Gr bner basis is computed by groebner 4coins and gives the output file Acoins gro Remark Many algorithm options are available and can be selected by command line options of groebner see section As reference to the algorithms we recom mend the book 2 section 11 4 or Hemmecke and Malkin 8 as well as Bigatti LaScala and Robbiano 1 Gebauer and M ller 3 and Hosten and Sturmfels 9 Since runnning times of the various algorithms are hard to predict it may for some hard problems make sense to start several computations in parallel each with dif ferent algorithms Then we specify our feasible solution in Chapter 1 Beginner s guide 19 Acoins feas 1 4 440 3 and call normalform 4coins to produce the file Acoins nf 1 4 4142 that also contains the desired optimal solution Remark We could also specify a list of feasible solutions in 4coins feas Then the call normalform 4coins creates a file 4coins nf containing the minima to the corresponding integer pro grams If zo is a feasible solution the corresponding integer program is defined by putting the right hand side to Az 1 2 6 Markov Bases in Statistics In this example you learn about
22. e non pointed case Hilbert bases are not uniquely determined Let zfree_l zfree_k be the vectors in the zfree file and hil_1 hil_l be the vectors in the hil file Then a Hilbert basis of the non pointed cone is hil 1 hil 1 hil 1 hil 1 zfree 1 zfree_k Chapter 6 NEWS Changes to 4ti2 since version 1 2 65 In the 1 3 series hilbert silently appended the lattice generators to the hil file Thus the list of vectors in the hil file was not a Hilbert basis of the non pointed cone this was a bug Note that zsolve did work correctly in the 1 3 series Fix a bug of zsolve and hilbert on 64 bit platforms where sizeof unsigned long gt sizeof int which affected problems with more than 32 variables and could lead to wrong results Testcases al dutour testcase 2013 08 21 Accept longer filenames Enable shared library builds on the Cygwin platform using the libtool no undefined flag However this requires that shared libraries of GMP GLPK are available Use gnulib to provide getopt_long if not available in the system libraries If the C compiler does not have int32_t and int64_t use int and long int instead Fixed bug in lattice transformation with too few rows Reported by Jerry James for Fedora Fix a build failure with gcc 4 7 Patch by Jerry James for Fedora News in 4ti2 version 1 5 2 compared to 1 5 1 Build a GMP only 4ti2 if t
23. efault is all The mat must be given with this file The extreme rays of the cone A basis for the linear subspace of the cone If this file does not exist then the linear subspace is trivial Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed Use the Matrix algorithm default for 32 and 64 Use the Support algorithm default for arbitrary Set ORDERING as the ordering in which the columns are chosen The possible orderings are maxinter minindex maxcutoff default and mincutoff Set the frequency of output default is 1000 Do not output anything to the screen Display this help and exit 3 14 walk 46 3 14 walk Usage walk options PROJECT Computes the minimal solution of an integer linear program or more general a lattice program using a Groebner basis Input Files PROJECT mat PROJECT lat PROJECT gro start PROJECT gro cost PROJECT cost PROJECT zsol PROJECT sign Output Files PROJECT gro Options p La es precision PREC truncation TRU output freg n quiet help A matrix optional only if lattice basis is given A lattice basis optional only if matrix is given The starting Groebner basis needed The starting cost vector optional default is degrevlex Ties are broken with degrevlex The target cost vector optional d
24. efault is degrevlex Ties are broken with degrevlex An integer solution to specify a fiber needed The sign constraints of the variables 1 means non negative and 0 means a free variable It is optional and the default is all non negative The Groebner basis of the lattice Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed NC Set TRUNC as the truncation method TRUNC is of the following ip lp weight default or none Only relevant if zsol is given Set the frequency of output default is 1000 Do not output anything to the screen Display this help and exit Chapter 3 Command line reference 47 3 15 zbasis Usage zbasis options PROJECT Computes an integer lattice basis Input Files PROJECT A matrix needed Output Files PROJECT lat A lattice basis Options p precision PREC Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed q quiet Do not output anything to the screen h help Display this help and exit 3 16 zsolve 48 3 16 zsolve Usage zsolve options PROJECT Solves linear inequality and equation systems over the integers Basic options p PREC precision PREC Use precision 32 64 gmp Default is 32 bit m
25. for a Hilbert basis of the 3 x 3 magic square cone As the default settings for hilbert are the same as for rays we can use the same input file Chapter 1 Beginner s guide 13 magic3x3 mat 7 9 FOrRrF OF KA a FP OF FP A 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 for this computation However to compute the Hilbert basis we call which creates the single output file hilbert magic3x3 magic3x3 hil 5 KA a Mr oO 9 Rh O O V V Ka ve OF HD O O N Rh ip MO VN oO Horn r YY NND CO oO Fe OF N that corresponds to the five elements in the minimal Hilbert basis of the 3 x 3 magic square cone 1 2 Brief tutorial 14 Every integer magic 3 x 3 square is a non negative integer linear combination of these five integer magic squares Note that the all 1 square is in the interior of the magic square cone See 2 section 3 8 or 6 for details on the algorithm implemented 1 2 4 Computing circuits and Graver bases In this example you learn about the functions graver ppi and circuits As an example of a Graver basis computation let us compute the primitive partition identities of order n 4 Before we do the simple computation let us explain what a primitive partition identity is A partition identity is any identity of the form ai ak b b
26. g 11 log 2 Log once every norm sum computation to PROJECT log 111 log 3 Log once every norm computation to PROJECT log Input files PROJECT mat Matrix PROJECT lat Lattice basis can be provided instead of matrix PROJECT rel Relations lt gt PROJECT sign Sign of columns optional PROJECT ub Upper bounds of columns optional Backup files Chapter 3 Command line reference 35 PROJECT backup Backup file PROJECT backup Temporary backup file if it exists it may be newer than PROJECT backup Output files PROJECT hil Hilbert basis PROJECT zfree Free part of the solution PROJECT maxnorm Vectors with maximum norm if m maxnorm is in use 3 7 markov 36 3 7 markov Usage markov options PROJECT Computes a Markov basis generating set of the toric ideal of a matrix or more general of the lattice ideal of a lattice Input Files PROJECT PROJECT PROJECT PROJECT PROJECT PROJECT lat sign weights weights max zsol Output Files PROJECT Options p precision PREC mar a algorithm ALG g generation ALG A matrix optional only if lattice basis is given A lattice basis optional only if matrix is given The sign constraints of the variables 1 means non negative and 70 means a free variable It is optional and the default is all non negative The weight vectors used for truncation optional The maximum weight
27. he C compiler does not have int32_t and int64_t News in 4ti2 version 1 5 1 compared to 1 5 66 Fix a build problem with enable shared News in 4ti2 version 1 5 compared to 1 4 Latest version of new qsolve News in 4ti2 version 1 4 compared to 1 3 2 Portability fixes New abstract C and C API callable library header files in 4ti2 New implementation of zsolve in C News in 4ti2 version 1 3 2 compared to 1 3 1 New build system using GNU Autoconf Automake and Libtool This allows 4ti2 to be built using the standard configure amp amp make amp amp make install sequence Bug fixes Portability fixes for GCC versions 4 3 x and 4 4 x News in 4ti2 version 1 3 1 compared to 1 2 groebner and markov are again heavily improved groebner and markov allow non homogeneous lattice ideals Chapter 6 NEWS Changes to 4ti2 since version 1 2 67 groebner and markov allow truncation There is a new function walk performing a Grbner walk There are new functions qsolve and zsolve for solving linear systems over the reals or the integers respectively There are new functions rays and circuits to compute extreme rays and circuits The functions circuits and graver allow to fix certain orthants Une may compute with projections by specifying variables to be ignored
28. her choice of 11 coins that sums up to 99ct but uses fewer nickels and quarters in total In other words we would like to solve min 24 1 23 24 11 21 572 1073 2574 99 21 2 03 24 Zu Let us set up the problem in 4ti2 4coins mat Acoins zsol Acoins sign Acoins cost 2 4 1 4 1 4 1 4 11 1 1 4 4 0 3 1 1 1 1 0101 1 5 10 25 Note that we do not have to specify a relations file 4coins rel since already by default all relations are assumed to be equations Now we simply call minimize 4coins which creates the single output file Acoins min 1 4 414 2 From this we conclude that 4 14 1 5 4 10 2 25 99 is an optimal choice using only 3 instead of 7 nickels and quarters 1 2 Brief tutorial 18 Remark Earlier versions of 4ti2 allowed to specify the right hand side vector in a file called 4coins rhs instead of giving a solution in 4coins zsol This is no longer supported Since we already know a feasible solution there is another way we might attack this problem namely via toric Gr bner bases See 2 Chapter 11 for an introduction to toric ideals and their Gr bner bases and also their generalizations lattice ideals For this we first need to specify the matrix A and the cost vector c in the two files 4coins mat and 4coins cost 4coins mat Acoins cost 2 4 1 4 11 1 1 0101 1 5 10 25 Then we compute the Gr
29. hod TRUNC is of the following ip lp weight default or none Only relevant if zsol is given m minimal STATE If STATE is yes default then 4ti2 will compute a minimal Markov basis If STATE is no then the Markov basis will not necessarily be minimal r auto reduce freg n Set the frequency of auto reduction default is 2500 f output freq n Set the frequency of output default is 1000 q quiet Do not output anything to the screen h help Display this help and exit 3 6 hilbert 34 3 6 hilbert Usage hilbert options PROJECT Computes the Hilbert basis of a matrix or a given lattice Basic options p PREC precision PREC Use precision 32 64 gmp Default is 32 bit m maxnorm Write vectors with maximum norm to PROJECT maxnorm b FREQ backup FREQ Frequently backup status to PROJECT backup r resume Resume from backup file PROJECT backup h help Display this help version Display version information Output options q quiet Quiet mode u update 1 Updated output on console default uu update 2 More verbose updated output on console v verbose 1 Output once every variable computation vv verbose 2 Output once every norm sum computation vvv verbose 3 Output once every norm computation Logging options n log 0 Disable logging default 1 log 1 Log once every variable computation to PROJECT lo
30. ide In this part we use a few sample problems to introduce you to the basic functionality of 4ti2 After working through this part you should know about linear systems and their encodings in 4ti2 and should be able to do computations using the following functions e qsolve rays circuits e zsolve hilbert graver ppi e minimize groebner normalform e genmodel markov 1 1 Linear systems and their encodings In this section you learn about the data structure linear system and how it is specified in 4ti2 1 1 1 Linear systems and integer linear systems In 4ti2 a linear system is defined by d constraints Ax bin n unknowns x where each constraint is either lt or gt that is lt gt Moreover one may 5 1 1 Linear systems and their encodings 6 specify sign constraints on the variables that need to be respected in an explicit continuous integer representation of all solutions There is no particular difference in 4ti2 between a linear system and an integer linear system Currently the user chooses between one of the two by calling the appropriate functions on the linear system 1 1 2 Specifying a linear system in 4ti2 In order to use a linear system as input we need to specify its parts to 4ti2 As our 1 1 1 1 lt 6 T 1234 lt 10 with sign constraints 1 2 2 0 which we will explain below running example take First we have to give our problem a project name say PROJEC
31. ision prec Create a ZSolve 4ti2 state object Chapter 4 4ti2 as a callable library 53 _4ti2_state _4ti2_zsolve_create_state _4ti2_precision prec Create a ZSolve 4ti2 state object _4ti2_state _4ti2_hilbert_create_state _4ti2_precision prec Create a ZSolve 4ti2 state object _4ti2_state _4ti2_graver_create_state _4ti2_precision prec Read in options for the 4ti2 state object These options are exactly the same as the command line options without the project filename at the end Note that argv 0 is ignored _4ti2_status _4ti2_state_set_options _4ti2_state state int argc char argv if 0 Implementation does not exist mkoeppe Read in the state object from project _4ti2_status _4ti2_state_read _4ti2_state state const charr project Write out the state object to project _4ti2_status _4ti2_state_write _4ti2_state state const char project endif Deletes a 4ti2 state object void _4ti2_state_delete _4ti2_state state Runs the main algorithm of the 4ti2 state object _4ti2_status _4ti2_state_compute _4ti2_state state Create a 4ti2 matrix Previous matrix is deleted if it exists Pointer is 0 if name is not valid _4ti2_status _4ti2_state_create_matrix _4ti2_state state int num_rows int num_cols const char name _4ti2_matrix mat Read a 4ti2 matrix from a file Previous matrix is deleted if it exists Returns 0 if name is not valid _4ti2_
32. ix _4ti2_state_compute qsolve_api _4ti2_matrix qhom_matrix _4ti2_state_get_matrix qsolve_api qhom amp qhom_matrix _4ti2_matrix_write_to_stdout qhom_matrix Check the output if _4ti2_matrix_get_num_rows qhom_matrix k return 1 T if _4ti2_matrix_get_num_cols qhom_matrix n return 1 T for int i 0 i lt k i for int j 0 j lt n j _4ti2_int64_t value _4ti2_matrix_get_entry_int64_t qhom_matrix i j amp value if value ghom i j return 1 T _4ti2_state_delete qsolve_api return 0 Chapter 5 README Instructions on configuring and building 4ti2 4ti2 A software package for algebraic geometric and combinatorial problems on linear spaces Copyright C 2006 2015 4ti2 team This program is modify it under as published by of the License This program is but WITHOUT ANY MERCHANTABILITY free software you can redistribute it and or the terms of the GNU General Public License the Free Software Foundation either version 2 or at your option any later version distributed in the hope that it will be useful WARRANTY without even the implied warranty of or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have along with this Foundation Inc COMPILING 4ti2 received a copy of the GNU General Public License program if not write to the Free Software 51 Franklin Street Fifth F
33. linear program or more general a lattice program using a Groebner basis Input Files PROJECT mat A matrix optional only if lattice basis is given PROJECT lat A lattice basis optional only if matrix is given PROJECT cost The cost vector Exactly one vector allowed PROJECT zsol An integer solution to specify a fiber needed PROJECT sign The sign constraints of the variables 1 means non negative and 0 means a free variable It is optional and the default is all non negative Output Files PROJECT min Options p s precision PREC algorithm ALG truncation TRUNC auto reduce freg n output freg n quiet help The minimal solution for the given fiber Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed Select ALG as the completion procedure for computing Groebner bases ALG is one of fifo weighted or unbounded Set TRUNC as the truncation method TRUNC is of the following ip lp weight default or none Only relevant if zsol is given Set the frequency of auto reduction default is 2500 Set the frequency of output default is 1000 Do not output anything to the screen Display this help and exit Chapter 3 Command line reference 39 3 9 normalform Usage normalform options PROJECT Computes
34. loor Boston MA 02110 1301 USA 59 60 Run the following commands with the 4ti2 directory configure prefix INSTALLATION DIRECTORY make make check make install exec The final command will install 4ti2 in a directory tree below the INSTALLATION DIRECTORY that you gave with the first command If you omit the prefix option make install will install 4ti2 in the usr local hierarchy You will need glpk and gmp installed first see below The first command make compiles all the executables The second command make check runs a lot of automatic checks This will take a while If a check fails then please notify the 4ti2 team You will need gcc version 3 4 or higher You will need an installed version of glpk linear programming software See the website http www gnu org software glpk for more information The version 4 7 has been tested If you do not have glpk installed or 4ti2 cannot find glpk then the compilation will fail saying that it cannot find the file glpk h If you have installed glpk but not in a location that 4ti2 finds by default then you will need to invoke configure with glpk ROOT OF GLPK INSTALLATION HIERARCHY You will also need an installed version of gmp The GNU MP Bignum Library with c support enabled see http www swox com gmp for more details Versions 4 2 1 and 4 1 4 have been tested If you are compiling a version of gmp from the source make sure
35. lue _4ti2_status _4ti2_matrix_get_entry_mpz_ptr const _4ti2_matrix matrix int r int c mpz_ptr value endif ifdef cplusplus extern C endif endif 4 2 Example program zsolve Example programs using the C API can be found in the source tree of 4ti2 in the directories test qsolve api and test zsolve api Below we reproduce the example program test zsolve api test_zsolve_api cpp 4ti2 A software package for algebraic geometric and combinatorial problems on linear spaces Copyright C 2006 4ti2 team Main author s This program is modify it under as published by of the License This program is but WITHOUT ANY MERCHANTABILITY Peter Malkin free software you can redistribute it and or the terms of the GNU General Public License the Free Software Foundation either version 2 or at your option any later version distributed in the hope that it will be useful WARRANTY without even the implied warranty of or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have along with this Foundation Inc received a copy of the GNU General Public License program if not write to the Free Software 51 Franklin Street Fifth Floor Boston MA 02110 1301 USA Chapter 4 4ti2 as a callable library 55 include 4ti2 4ti2 h int main Input data const intm 4 const int n 3 _4ti2_int64_t mat m n
36. lve Let us have a look at the linear system E y lt 2 d y lt 1 r y gt I1 y gt 0 over Z We have to create the files encoding the linear system Let us call our project system Then the input files look as follows Chapter 1 Beginner s guide 9 system mat system rel system rhs system sign 3 2 1 3 1 3 1 2 1 1 lt lt gt 2 1 1 0 1 3 1 1 1 Then we call zsolve system This call creates two files system zinhom system zhom 4 2 3 2 0 1 1 1 2 0 1 2 1 0 1 3 1 1 which correspond to the explicit description of all integer solutions Feasible solutions Computed representation y 3x 1 y 3x 1 4 4 2 N o A A Q N lt II x 1 N N 0 A a y tlo Ca G 2 rma CC LL Note that in the pictures above we are only interested in the lattice points inside the colored regions The full regions are colored only for the purpose of visualizing the covering of all feasible integer solutions by finitely many shifted copies of the il monoid 1 2 Brief tutorial 10 1 2 2 Solving linear systems over Q with qsolve qsolve solves linear systems over Q however note that it only supports homoge neous linear systems that is systems with b 0 qsolve system This call creates files system qhom system qfree To solve an inhomogeneous system Ax b x gt 0 you still need to do so
37. maxnorm Write vectors with maximum norm to PROJECT maxnorm b FREQ backup FREQ Frequently backup status to PROJECT backup r resume Resume from backup file PROJECT backup h help Display this help version Display version information Output options q quiet Quiet mode u update 1 Updated output on console default uu update 2 More verbose updated output on console v verbose 1 Output once every variable computation vv verbose 2 Output once every norm sum computation vvv verbose 3 Output once every norm computation Logging options n log 0 Disable logging default 1 log 1 Log once every variable computation to PROJECT log 11 log 2 Log once every norm sum computation to PROJECT log 111 log 3 Log once every norm computation to PROJECT log Input files PROJECT mat Matrix PROJECT lat Lattice basis can be provided instead of matrix PROJECT rhs Right hand side PROJECT rel Relations lt gt PROJECT sign Sign of columns optional PROJECT 1b Lower bounds of columns optional PROJECT ub Upper bounds of columns optional Chapter 3 Command line reference 49 Backup files PROJECT backup Backup file PROJECT backup Temporary backup file if it exists it may be newer than PROJECT backup Output files PROJECT zinhom Inhomogeneous part of the solution PROJECT zhom Homogeneous part of the solution PROJECT zfree Free part of the solution PROJECT
38. me work yourself 1 Solve system Ar bu 0 x gt 0 u gt 0 using qsolve 2 Keep those solutions with u 0 These generate the recession cone of un bounded directions 3 Normalize those solutions with u gt 0 to have u 1 by dividing the vector by u Be aware that this could create rational numbers 4 Drop the u component Any solution to Ar b x gt 0 can then be obtained by adding one solution from 3 to a nonnegative linear combination of solutions from 2 1 2 3 Computing extreme rays and Hilbert bases In this example you learn about the functions rays and hilbert They are conve nient versions of qsolve and zsolve for particular cases Let us consider the set of magic 3 x 3 squares with non negative real entries that is the set of all 3 x 3 arrays with non negative real entries whose row sums column sums and main diagonal sums all add up to the same number the magic constant of the square Chapter 1 Beginner s guide 11 Clearly addition of two magic squares gives another magic square as well as does multiplication of a magic square by a non negative number Therefore we may talk about the cone of magic 3 x 3 squares In fact this cone is a pointed rational polyhedral cone described by the linear system T11 T12 X13 T21 T22 T23 Pai 132 X33 211 T21 T31 Tiz T22 T32 13 T23 T33 X11 T22 X33 731 T22 T13 Zi
39. n 4ti2 version 1 6 5 compared to 1 6 4 Fix build failure with gcc 4 9 2 News in 4ti2 version 1 6 4 compared to 1 6 3 Improved error checking while reading zsolve input files Reported by Sebastian Gutsche The PDF manual has been updated to include a reference to commands and their options and a reference to the API The command reference on www 4ti2 de has also been updated Better option handling Make long options available in non GNU platforms such as Mac OS X All commands now support the 63 64 standard help and version options Minor fix to the test suite Reported by Luis David Garcia Puente News in 4ti2 version 1 6 3 compared to 1 6 2 The manual has been updated Minor build fixes News in 4ti2 version 1 6 2 compared to 1 6 1 Use GLPK s new glp_ API instead of the old lpx_ API declared obsolete in glpk 4 47 and removed in 4 52 Patch by Jerry James for Fedora News in 4ti2 version 1 6 1 compared to 1 6 Compile fix for XCode 5 0 2 Apple LLVM version 5 0 clang 500 2 79 News in 4ti2 version 1 6 compared to 1 5 2 Restore the functionality of hilbert in versions up to 1 3 2 to accept rel files This signalled an error in the 1 4 and 1 5 series Note that zsolve did accept rel files in the 1 4 and 1 5 series When the cone is not pointed hilbert now outputs a zfree file containing a lattice basis in addition to the hil file Note that in th
40. r Boston MA 02110 1301 USA include 4ti2 4ti2 h int main Input data const int m 4 const int n 3 _4ti2_int64_t mat m n 2 3 6 2 1 4 Li 2 11 F 1i i 17 3 _4ti2_int64_t rel m _4ti2_LB _4ti2_UB _4ti2_UB _4ti2_LB _4ti2_int64_t sign n _4ti2_LB _4ti2_LB _4ti2_LB Output data const int k 4 _4ti2_int64_t ghom k In 3 4 1 3 8 5 9 2 4 19 18 5 _4ti2_state qsolve_api _4ti2_qsolve_create_state _4ti2_PREC_INT_64 const int argc 2 char argv 2 char qsolve char q _4ti2_state_set_options qsolve_api argc argv _4ti2_matrix cons_matrix _4ti2_state_create_matrix qsolve_api m n mat amp cons_matrix for int i 0 i lt m i for int j 0 j lt n j _4ti2_matrix_set_entry_int64_t cons_matrix i j mat i j _4ti2_matrix_write_to_stdout cons_matrix _4ti2_matrix rel_matrix _4ti2_state_create_matrix qsolve_api 1 m rel amp rel matrix for int i 0 i lt m i _4ti2_matrix_set_entry_int64_t rel_matrix 0 i rel i Ati2 matrix write to stdout rel matrix _4ti2_matrix sign matrix 4 3 Example program qsolve 58 4ti2 state create matrix qsolve api 1 n sign amp sign_matrix for int i 0 i lt n i _4ti2_matrix_set_entry_int64_t sign_matrix 0 i sign i _4ti2_matrix_write_to_stdout sign_matr
41. s used for truncation This file is needed when PROJECT weights exists An integer solution to specify a fiber optional The integer solution is used for truncation The Markov basis generating set of the lattice Select PREC as the integer arithmetic precision PREC is one of the following 64 default 32 and arbitrary only arb is needed Select ALG as the completion procedure for computing Groebner bases ALG is one of fifo weighted or unbounded Select ALG as the procedure for computing a generating set or Markov basis ALG is one of hybrid default project and lift max min or saturation t truncation TRUNC Set TRUNC as the truncation method TRUNC is m minimal STATE of the following ip lp weight default or none Only relevant if zsol is given If STATE is yes default then 4ti2 will compute a minimal Markov basis If STATE is Chapter 3 Command line reference 37 no then the Markov basis will not necessarily be minimal r auto reduce freg n Set the frequency of auto reduction default is 2500 f output freq n Set the frequency of output default is 1000 q quiet Do not output anything to the screen h help Display this help and exit 3 8 minimize 38 3 8 minimize Usage minimize options PROJECT Computes the minimal solution of an integer
42. status _4ti2_state_read_matrix _4ti2_state state const char filename const char name _4ti2_matrix matrix Get a 4ti2 matrix Returns 0 if name is not valid or if matrix has not been created _4ti2_status _4ti2_state_get_matrix _4ti2_state state const char name _4ti2_matrix matrix Returns the number of rows of the matrix int _4ti2_matrix_get_num_rows const _4ti2_matrix matrix Returns the number of columns of the matrix int _4ti2_matrix_get_num_cols const _4ti2_matrix matrix Write the 4ti2 matrix to stdout void _4ti2_matrix_write_to_stdout const _4ti2_matrix matrix Write the 4ti2 matrix to sterr void _4ti2_matrix_write_to_stderr const _4ti2_matrix matrix Write the 4ti2 matrix to the file called filename void _4ti2_matrix_write_to_file const _4ti2_matrix matrix const char filename 4 2 Example program zsolve 54 Operations on the matrix _4ti2_status _4ti2_matrix_set_entry_int32_t _4ti2_matrix matrix int r int c _4ti2_int32_t value _4ti2_status _4ti2_matrix_get_entry_int32_t const _4ti2_matrix matrix int r int c _4ti2_int32_t value _4ti2_status _4ti2_matrix_set_entry_int64_t _4ti2_matrix matrix int r int c _4ti2_int64_t value _4ti2_status _4ti2_matrix_get_entry_int64_t const _4ti2_matrix matrix int r int c _4ti2_int64_t value ifdef _4ti2_HAVE_GMP _4ti2_status _4ti2_matrix_set_entry_mpz_ptr _4ti2_matrix matrix int r int c mpz_ptr va
43. the functions markov and genmodel Let us consider the following 4 x 4 table of non negative integer numbers together with all row and column sums 11 23 4 15 17 2 16 12 48 52 34 12 3 22 71 3 11 25 7 46 1 2 Brief tutorial 20 In statistics one wishes to sample among arrays that have fixed counts say fixed row and column sums In order to sample one needs a set of moves that in particular do not change the counts when added to the current table Clearly these moves must have counts 0 and thus quite naturally lead us to the toric ideal Ila 1 x Au Av u v ZP where 1111000000000000 0000111100000000 0000000011110000 rn 000000000000 1 1 11 1000100010001000 0100010001000100 0010001000100010 0001000100010001 It turns out that for any set of fixed counts a minimal Markov basis is given by a minimal generating set of this toric ideal Note that a Markov basis connects all non negative tables with these counts in the sense that for any two non negative tables 7 and 73 with these counts there is a sequence of non negative tables 7 So Sy Ta with the same counts as T and To and such that Si S _ or S 1 5 is in the Markov basis for i 1 N For two way tables the situation is still very simple as our computations with 4 x 4 tables will now demonstrate Write the matrix that defines our toric ideal in the file 4x4 mat 4x4 mat 8 16 1 11100
44. the symmetry group acting on 4 way tables with 3 marginals By putting one side length to 1 this includes 3 way tables with 2 marginals Options q quiet No output is written to the screen Output file FILENAME sym generators for the symmetry group Example Consider the problem of 3x3x3 tables with 2 marginals Calling gensymm 3 3 3 1 333 produces the file 333 sym containing the following lines 9 27 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 1234567809 10 11 12 13 14 15 16 17 181234567809 19 20 21 22 23 24 25 26 27 56789123 13 14 15 16 17 18 10 11 12 22 23 24 25 26 27 19 20 21 561237809 13 14 15 10 11 12 16 17 18 22 23 24 19 20 21 25 26 27 3156489 7 11 12 10 14 15 13 17 18 16 20 21 19 23 24 22 26 27 25 13546879 11 10 12 14 13 15 17 16 18 20 19 21 23 22 24 26 25 27 2310 11 12 19 20 21 4 5 6 13 14 15 22 23 24 7 8 9 16 17 18 25 26 27 10 19 4 13 22 7 16 25 2 11 20 5 14 23 8 17 26 3 12 21 6 15 24 9 18 27 147258360910 13 16 11 14 17 12 15 18 19 22 25 20 23 26 21 24 27 e e N N FS sq 3 4 graver 30 3 4 graver Usage graver options PROJECT Computes the Graver basis of a matrix or a given lattice Basic options p PREC precision PREC Use precision 32 64 gmp Default is 32 bit m maxnorm Write vectors with maximum norm to PROJECT maxnorm b FREQ backup FREQ Frequently backup status to PROJECT backup r resume Resume from backup file PROJECT backup h help Display this help
45. ve 4ti2 returns three sets of integer vectors e aset H of minimal homogeneous integer solutions e aset J of minimal inhomogeneous integer solutions and e a set F defining the sublattice of Z the solution set lives in 1 2 Brief tutorial 8 Any solution z of the linear system can now be written as 2 i V ajh Y Bebe 1 2 for some 1 I and with h H f F and a Z4 Sign file Let us finally clarify what the sign file PROJECT sign is good for The sign file may declare a variable to be non negative 1 to be non positive 1 or to consider both cases independently and unite the answers 2 If a nonzero sign has been assigned to a variable the explicit representations and above of a solution z have to respect the sign on that variable The default setting for each variable is 0 when using qsolve and zsolve that is the sign need not be respected in the explicit representation In our example above the first variable is declared to be non negative the second and the third one expand to 2 2 4 orthant constraints and the fourth variable is unconstrained Note however that 4ti2 does not decompose the problem internally into the four problems with sign patterns 1 1 1 0 1 1 1 0 1 1 1 0 and 1 1 1 0 but deals with them more efficiently at the same time 1 2 Brief tutorial 1 2 1 Solving linear systems over Z with zsolve In this example you learn about the function zso
46. with generally not distinct integer numbers 0 lt a b lt n A partition identity is called primitive if no proper subidentity exists For example 1 2 3 2 2 2 is a partition identity which is not primitive since it contains the subidentity 143 2 2 which is in fact primitive The description of the primitive partition identities for fixed n however is exactly the description of the Graver basis of the matrix A 1 23 n Let us finally do the computation for n 3 We create an input file ppi3 for 4ti2 which looks as follows ppi3 mat 1 3 1 2 3 Chapter 1 Beginner s guide 15 and call graver ppi3 This call will create an output file ppi3 gra that looks like ppi3 gra 5 3 3 0 1 2 1 0 0 3 2 1 1 1 2 1 Thus there are 5 primitive partition identities of order n 3 1 14 1 3 1 1 2 2 2 2 3 3 1 2 3 1 3 2 2 You may try and compute the primitive partition identities for bigger n say n 17 20 or 23 Be aware especially the latter two problems take a long long time What is the biggest n for which you can compute the primitive partition identities of order n on your machine within one hour Due to the very special structure of the matrix there are algorithmic speed ups 4 10 13 The currently fastest algorithm to compute primitive partition identities is implemented in the function ppi of 4ti2 Try running ppi 17 which creates
47. x _4ti2_matrix_write_to_stdout zhom_matrix Check the output if _4ti2_matrix_get_num_rows zhom_matrix k return 1 T if _4ti2_matrix_get_num_cols zhom_matrix n return 1 T 11 for int i 0 i lt k i for int j 0 j lt n j i 11 int64_t value _4ti2_matrix_get_entry_int64_t zhom_matrix i j amp value if value zhom i j return 1 T I 777 T _4ti2_state_delete zsolve_api return 0 4 3 Example program qsolve Below we reproduce the example program test qsolve api qsolve_main cpp 4ti2 A software package for algebraic geometric and combinatorial problems on linear spaces Copyright C 2006 4ti2 team Main author s This program is modify it under as published by of the License This program is but WITHOUT ANY MERCHANTABILITY Peter Malkin free software you can redistribute it and or the terms of the GNU General Public License the Free Software Foundation either version 2 or at your option any later version distributed in the hope that it will be useful WARRANTY without even the implied warranty of or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have received a copy of the GNU General Public License Chapter 4 4ti2 as a callable library 57 along with this program if not write to the Free Software Foundation Inc 51 Franklin Street Fifth Floo

manual

Contents

Download Pdf Manuals

Related Search

Related Contents