Changeset 8275a9 in git
- Timestamp:
- Nov 22, 2013, 5:41:38 PM (10 years ago)
- Branches:
- (u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
- Children:
- 9e8ae12733559521215c7641624da588f2d8cdf3
- Parents:
- 3c3e3de41fd6ba44babbfa0c6384b376182586ee
- git-author:
- Yue Ren <ren@mathematik.uni-kl.de>2013-11-22 17:41:38+01:00
- git-committer:
- Yue Ren <ren@mathematik.uni-kl.de>2013-12-11 17:46:46+01:00
- Files:
-
- 7 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/COPYING
r3c3e3d r8275a9 134 134 paramet.lib Thomas Keilen keilen@mathematik.uni-kl.de 135 135 perron.lib Oleksandr Motsak motsak at mathematik dot uni minus kl dot de 136 phindex.lib 136 phindex.lib 137 137 pointid.lib Stefan Steidel steidel@mathematik.uni-kl.de 138 138 poly.lib Olaf Bachmann obachman@mathematik.uni-kl.de 139 139 Gert-Martin Greuel greuel@mathematik.uni-kl.de 140 140 Anne Fruehbis-Krueger anne@mathematik.uni-kl.de 141 oldpolymake.libThomas Markwig keilen@mathematik.uni-kl.de141 polymake.lib Thomas Markwig keilen@mathematik.uni-kl.de 142 142 presolve.lib Gert-Martin Greuel greuel@mathematik.uni-kl.de 143 143 primdec.lib Gerhard Pfister pfister@mathematik.uni-kl.de -
Singular/LIB/polymake.lib
r3c3e3d r8275a9 2 2 category="Tropical Geometry"; 3 3 info=" 4 LIBRARY: oldpolymake.lib Computations with polytopes and fans,5 4 LIBRARY: polymake.lib Computations with polytopes and fans, 5 interface to polymake and TOPCOM 6 6 AUTHOR: Thomas Markwig, email: keilen@mathematik.uni-kl.de 7 7 … … 15 15 length and labeling of their vertices resp. rays, differs from the conventions 16 16 used in polymake and thus from the conventions used in the polymake 17 extension polymake.so of Singular. We recommend to use the newer polymake.so 17 extension polymake.so of Singular. We recommend to use the newer polymake.so 18 18 whenever possible. 19 19 20 20 IMPORTANT NOTE: 21 Even though this is a Singular library for computing polytopes and fans 22 such as the Newton polytope or the Groebner fan of a polynomial, most of 23 the hard computations are NOT done by Singular but by the program 21 Even though this is a Singular library for computing polytopes and fans 22 such as the Newton polytope or the Groebner fan of a polynomial, most of 23 the hard computations are NOT done by Singular but by the program 24 24 @* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt 25 @* (see http://www.math.tu-berlin.de/polymake/), 25 @* (see http://www.math.tu-berlin.de/polymake/), 26 26 @* respectively (only in the procedure triangulations) by the program 27 27 @* - topcom by Joerg Rambau, Universitaet Bayreuth (see 28 28 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM); 29 @* this library should rather be seen as an interface which allows to use a 30 (very limited) number of options which polymake respectively topcom offers 31 to compute with polytopes and fans and to make the results available in 32 Singular for further computations; 29 @* this library should rather be seen as an interface which allows to use a 30 (very limited) number of options which polymake respectively topcom offers 31 to compute with polytopes and fans and to make the results available in 32 Singular for further computations; 33 33 moreover, the user familiar with Singular does not have to learn the syntax 34 of polymake or topcom, if the options offered here are sufficient for his 34 of polymake or topcom, if the options offered here are sufficient for his 35 35 purposes. 36 @* Note, though, that the procedures concerned with planar polygons are 36 @* Note, though, that the procedures concerned with planar polygons are 37 37 independent of both, polymake and topcom. 38 38 39 39 PROCEDURES USING POLYMAKE: 40 40 polymakePolytope() computes the vertices of a polytope using polymake 41 newtonPolytope () computes the Newton polytope of a polynomial41 newtonPolytopeP() computes the Newton polytope of a polynomial 42 42 newtonPolytopeLP() computes the lattice points of the Newton polytope 43 normalFan () computes the normal fan of a polytope43 normalFanL() computes the normal fan of a polytope 44 44 groebnerFan() computes the Groebner fan of a polynomial 45 45 … … 52 52 53 53 PROCEDURES CONERNED WITH PLANAR POLYGONS: 54 cycleLength() computes the cycleLength of cycle 54 cycleLength() computes the cycleLength of cycle 55 55 splitPolygon() splits a marked polygon into vertices, facets, interior points 56 56 eta() computes the eta-vector of a triangulation 57 findOrientedBoundary() computes the boundary of a convex hull 57 findOrientedBoundary() computes the boundary of a convex hull 58 58 cyclePoints() computes lattice points connected to some lattice point 59 59 latticeArea() computes the lattice area of a polygon … … 63 63 64 64 KEYWORDS: polytope; fan; secondary fan; secondary polytope; polymake; 65 Newton polytope; Groebner fan 65 Newton polytope; Groebner fan 66 66 "; 67 67 … … 101 101 proc polymakePolytope (intmat points) 102 102 "USAGE: polymakePolytope(points); polytope intmat 103 ASSUME: each row of points gives the coordinates of a lattice point of a 104 polytope with their affine coordinates as given by the output of 103 ASSUME: each row of points gives the coordinates of a lattice point of a 104 polytope with their affine coordinates as given by the output of 105 105 secondaryPolytope 106 PURPOSE: the procedure calls polymake to compute the vertices of the polytope 106 PURPOSE: the procedure calls polymake to compute the vertices of the polytope 107 107 as well as its dimension and information on its facets 108 108 RETURN: list, L with four entries 109 109 @* L[1] : an integer matrix whose rows are the coordinates of vertices 110 of the polytope 110 of the polytope 111 111 @* L[2] : the dimension of the polytope 112 @* L[3] : a list whose ith entry explains to which vertices the 113 ith vertex of the Newton polytope is connected 114 -- i.e. L[3][i] is an integer vector and an entry k in 115 there means that the vertex L[1][i] is connected to the 112 @* L[3] : a list whose ith entry explains to which vertices the 113 ith vertex of the Newton polytope is connected 114 -- i.e. L[3][i] is an integer vector and an entry k in 115 there means that the vertex L[1][i] is connected to the 116 116 vertex L[1][k] 117 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 118 (1,var(1),...,var(nvar)) give a linear system of equations 117 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 118 (1,var(1),...,var(nvar)) give a linear system of equations 119 119 describing the affine hull of the polytope, 120 120 i.e. the smallest affine space containing the polytope 121 NOTE: - for its computations the procedure calls the program polymake by 122 Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; 123 it therefore is necessary that this program is installed in order 121 NOTE: - for its computations the procedure calls the program polymake by 122 Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; 123 it therefore is necessary that this program is installed in order 124 124 to use this procedure; 125 125 see http://www.math.tu-berlin.de/polymake/ 126 @* - note that in the vertex edge graph we have changed the polymake 127 convention which starts indexing its vertices by zero while we start 126 @* - note that in the vertex edge graph we have changed the polymake 127 convention which starts indexing its vertices by zero while we start 128 128 with one ! 129 129 EXAMPLE: example polymakePolytope; shows an example" … … 147 147 "EXAMPLE:"; 148 148 echo=2; 149 // the lattice points of the unit square in the plane 149 // the lattice points of the unit square in the plane 150 150 list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); 151 151 // the secondary polytope of this lattice point configuration is computed … … 167 167 ///////////////////////////////////////////////////////////////////////////// 168 168 169 proc newtonPolytope (poly f)170 "USAGE: newtonPolytope (f); f poly169 proc newtonPolytopeP (poly f) 170 "USAGE: newtonPolytopeP(f); f poly 171 171 RETURN: list, L with four entries 172 172 @* L[1] : an integer matrix whose rows are the coordinates of vertices 173 173 of the Newton polytope of f 174 174 @* L[2] : the dimension of the Newton polytope of f 175 @* L[3] : a list whose ith entry explains to which vertices the 176 ith vertex of the Newton polytope is connected 177 -- i.e. L[3][i] is an integer vector and an entry k in 175 @* L[3] : a list whose ith entry explains to which vertices the 176 ith vertex of the Newton polytope is connected 177 -- i.e. L[3][i] is an integer vector and an entry k in 178 178 there means that the vertex L[1][i] is 179 179 connected to the vertex L[1][k] 180 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 181 (1,var(1),...,var(nvar)) give a linear system of equations 180 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 181 (1,var(1),...,var(nvar)) give a linear system of equations 182 182 describing the affine hull of the Newton polytope, i.e. the 183 183 smallest affine space containing the Newton polytope 184 NOTE: - if we replace the first column of L[4] by zeros, i.e. if we move 185 the affine hull to the origin, then we get the equations for the 186 orthogonal complement of the linearity space of the normal fan dual 184 NOTE: - if we replace the first column of L[4] by zeros, i.e. if we move 185 the affine hull to the origin, then we get the equations for the 186 orthogonal complement of the linearity space of the normal fan dual 187 187 to the Newton polytope, i.e. we get the EQUATIONS that 188 188 we need as input for polymake when computing the normal fan … … 190 190 TU Berlin and Michael Joswig, so it only works if polymake is installed; 191 191 see http://www.math.tu-berlin.de/polymake/ 192 EXAMPLE: example newtonPolytope ; shows an example"192 EXAMPLE: example newtonPolytopeP; shows an example" 193 193 { 194 194 int i,j; 195 // compute the list of exponent vectors of the polynomial, 195 // compute the list of exponent vectors of the polynomial, 196 196 // which are the lattice points 197 197 // whose convex hull is the Newton polytope of f … … 214 214 poly f=y3+x2+xy+2xz+yz+z2+1; 215 215 // the Newton polytope of f is 216 list np=newtonPolytope (f);216 list np=newtonPolytopeP(f); 217 217 // the vertices of the Newton polytope are: 218 218 np[1]; … … 220 220 np[2]; 221 221 // np[3] contains information how the vertices are connected to each other, 222 // e.g. the first vertex (number 0) is connected to the second, third and 222 // e.g. the first vertex (number 0) is connected to the second, third and 223 223 // fourth vertex 224 224 np[3][1]; … … 226 226 f=x2-y3; 227 227 // the Newton polytope of f is 228 np=newtonPolytope (f);228 np=newtonPolytopeP(f); 229 229 // the vertices of the Newton polytope are: 230 230 np[1]; 231 231 // its dimension is 232 np[2]; 233 // the Newton polytope is contained in the affine space given 232 np[2]; 233 // the Newton polytope is contained in the affine space given 234 234 // by the equations 235 235 intmat(np[4])*M; … … 240 240 proc newtonPolytopeLP (poly f) 241 241 "USAGE: newtonPolytopeLP(f); f poly 242 RETURN: list, the exponent vectors of the monomials occuring in f, 242 RETURN: list, the exponent vectors of the monomials occuring in f, 243 243 i.e. the lattice points of the Newton polytope of f 244 EXAMPLE: example n ormalFan; shows an example"244 EXAMPLE: example newtonPolytopeLP; shows an example" 245 245 { 246 246 list np; … … 266 266 ///////////////////////////////////////////////////////////////////////////// 267 267 268 proc normalFan (def vertices, def affinehull,list graph,int er,list #)269 "USAGE: normalFan (vert,aff,graph,rays,[,#]); vert,aff intmat, graph list, rays int, # string270 ASSUME: - vert is an integer matrix whose rows are the coordinate of 271 the vertices of a convex lattice polytope; 268 proc normalFanL (def vertices, def affinehull,list graph,int er,list #) 269 "USAGE: normalFanL (vert,aff,graph,rays,[,#]); vert,aff intmat, graph list, rays int, # string 270 ASSUME: - vert is an integer matrix whose rows are the coordinate of 271 the vertices of a convex lattice polytope; 272 272 @* - aff describes the affine hull of this polytope, i.e. 273 the smallest affine space containing it, in the following sense: 274 denote by n the number of columns of vert, then multiply aff by 275 (1,x(1),...,x(n)) and set the resulting terms to zero in order to 273 the smallest affine space containing it, in the following sense: 274 denote by n the number of columns of vert, then multiply aff by 275 (1,x(1),...,x(n)) and set the resulting terms to zero in order to 276 276 get the equations for the affine hull; 277 @* - the ith entry of graph is an integer vector describing to which 278 vertices the ith vertex is connected, i.e. a k as entry means that 277 @* - the ith entry of graph is an integer vector describing to which 278 vertices the ith vertex is connected, i.e. a k as entry means that 279 279 the vertex vert[i] is connected to vert[k]; 280 @* - the integer rays is either one (if the extreme rays should be 280 @* - the integer rays is either one (if the extreme rays should be 281 281 computed) or zero (otherwise) 282 RETURN: list, the ith entry of L[1] contains information about the cone in the 283 normal fan dual to the ith vertex of the polytope 284 @* L[1][i][1] = integer matrix representing the inequalities which 282 RETURN: list, the ith entry of L[1] contains information about the cone in the 283 normal fan dual to the ith vertex of the polytope 284 @* L[1][i][1] = integer matrix representing the inequalities which 285 285 describe the cone dual to the ith vertex 286 @* L[1][i][2] = a list which contains the inequalities represented 287 by L[i][1] as a list of strings, where we use the 286 @* L[1][i][2] = a list which contains the inequalities represented 287 by L[i][1] as a list of strings, where we use the 288 288 variables x(1),...,x(n) 289 289 @* L[1][i][3] = only present if 'er' is set to 1; in that case it is 290 an interger matrix whose rows are the extreme rays 290 an interger matrix whose rows are the extreme rays 291 291 of the cone 292 @* L[2] = is an integer matrix whose rows span the linearity space 293 of the fan, i.e. the linear space which is contained in 292 @* L[2] = is an integer matrix whose rows span the linearity space 293 of the fan, i.e. the linear space which is contained in 294 294 each cone 295 295 NOTE: - the procedure calls for its computation polymake by Ewgenij Gawrilow, 296 TU Berlin and Michael Joswig, so it only works if polymake is 296 TU Berlin and Michael Joswig, so it only works if polymake is 297 297 installed; 298 298 see http://www.math.tu-berlin.de/polymake/ 299 @* - in the optional argument # it is possible to hand over other names 299 @* - in the optional argument # it is possible to hand over other names 300 300 for the variables to be used -- be careful, the format must be correct 301 and that is not tested, e.g. if you want the variable names to be 301 and that is not tested, e.g. if you want the variable names to be 302 302 u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11 303 EXAMPLE: example normalFan ; shows an example"303 EXAMPLE: example normalFanL; shows an example" 304 304 { 305 305 if (typeof(affinehull) != "intmat" && typeof (affinehull) != "bigintmat") 306 306 { 307 ERROR("normalFan : input affinehull has to be either intmat or bigintmat");307 ERROR("normalFanL: input affinehull has to be either intmat or bigintmat"); 308 308 list L; 309 309 return (L); … … 311 311 list ineq; // stores the inequalities of the cones 312 312 int i,j,k; 313 // we work over the following ring 313 // we work over the following ring 314 314 execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;"); 315 315 string greatersign=">"; … … 336 336 for (i=1;i<=nrows(vertices);i++) 337 337 { 338 // first we produce for each vertex in the polytope 338 // first we produce for each vertex in the polytope 339 339 // the inequalities describing the dual cone in the normal fan 340 list pp; // contain strings representing the inequalities 340 list pp; // contain strings representing the inequalities 341 341 // describing the normal cone 342 342 if (typeof (vertices) == "intmat") 343 343 { 344 intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 344 intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 345 345 } // as rows 346 346 if (typeof (vertices) == "bigintmat") 347 347 { 348 bigintmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 348 bigintmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 349 349 } // as rows 350 // consider all the vertices to which the ith vertex in the 350 // consider all the vertices to which the ith vertex in the 351 351 // polytope is connected by an edge 352 352 for (j=1;j<=size(graph[i]);j++) 353 353 { 354 354 // produce the vector ie_j pointing from the jth vertex to the ith vertex; 355 // this will be the jth inequality for the cone in the normal fan dual to 355 // this will be the jth inequality for the cone in the normal fan dual to 356 356 // the ith vertex 357 357 ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]-vertices[graph[i][j],1..ncols(vertices)]; … … 360 360 p=(VAR*EXP)[1,1]; 361 361 pl,pr=0,0; 362 // separate the terms with positive coefficients in p from 362 // separate the terms with positive coefficients in p from 363 363 // those with negative coefficients 364 364 for (k=1;k<=size(p);k++) … … 373 373 } 374 374 } 375 // build the string which represents the jth inequality 375 // build the string which represents the jth inequality 376 376 // for the cone dual to the ith vertex 377 // as polynomial inequality of type string, and store this 377 // as polynomial inequality of type string, and store this 378 378 // in the list pp as jth entry 379 379 pp[j]=string(pl)+" "+greatersign+" "+string(pr); … … 384 384 } 385 385 // remove the first column of affine hull to compute the linearity space 386 intmat linearity[1][ncols(vertices)];386 bigintmat linearity[1][ncols(vertices)]; 387 387 if (nrows(affinehull)>0) 388 388 { … … 396 396 list extremerays; // keeps the result 397 397 cone kegel; 398 intmat linearspan=intmatAddFirstColumn(linearity,"rays");398 bigintmat linearspan=intmatAddFirstColumn(linearity,"rays"); 399 399 intmat M; // the matrix keeping the inequalities 400 400 for (i=1;i<=size(ineq);i++) … … 409 409 } 410 410 // get the linearity space 411 return(list(ineq,linearity)); 411 return(list(ineq,linearity)); 412 412 } 413 413 example … … 419 419 poly f=y3+x2+xy+2xz+yz+z2+1; 420 420 // the Newton polytope of f is 421 list np=newtonPolytope (f);421 list np=newtonPolytopeP(f); 422 422 // the Groebner fan of f, i.e. the normal fan of the Newton polytope 423 list gf=normalFan (np[1],np[4],np[3],1,"x,y,z");423 list gf=normalFanL(np[1],np[4],np[3],1,"x,y,z"); 424 424 // the number of cones in the Groebner fan of f is: 425 425 size(gf[1]); … … 438 438 proc groebnerFan (poly f) 439 439 "USAGE: groebnerFan(f); f poly 440 RETURN: list, the ith entry of L[1] contains information about the ith cone 441 in the Groebner fan dual to the ith vertex in the Newton 440 RETURN: list, the ith entry of L[1] contains information about the ith cone 441 in the Groebner fan dual to the ith vertex in the Newton 442 442 polytope of the f 443 @* L[1][i][1] = integer matrix representing the inequalities 444 which describe the cone 445 @* L[1][i][2] = a list which contains the inequalities represented 443 @* L[1][i][1] = integer matrix representing the inequalities 444 which describe the cone 445 @* L[1][i][2] = a list which contains the inequalities represented 446 446 by L[1][i][1] as a list of strings 447 @* L[1][i][3] = an interger matrix whose rows are the extreme rays 447 @* L[1][i][3] = an interger matrix whose rows are the extreme rays 448 448 of the cone 449 @* L[2] = is an integer matrix whose rows span the linearity space 450 of the fan, i.e. the linear space which is contained 451 in each cone 452 @* L[3] = the Newton polytope of f in the format of the procedure 453 newtonPolytope 454 @* L[4] = integer matrix where each row represents the exponent 449 @* L[2] = is an integer matrix whose rows span the linearity space 450 of the fan, i.e. the linear space which is contained 451 in each cone 452 @* L[3] = the Newton polytope of f in the format of the procedure 453 newtonPolytopeP 454 @* L[4] = integer matrix where each row represents the exponent 455 455 vector of one monomial occuring in the input polynomial 456 456 NOTE: - if you have already computed the Newton polytope of f then you might want 457 to use the procedure normalFan instead in order to avoid doing costly457 to use the procedure normalFanL instead in order to avoid doing costly 458 458 computation twice 459 459 @* - the procedure calls for its computation polymake by Ewgenij Gawrilow, … … 463 463 { 464 464 int i,j; 465 // compute the list of exponent vectors of the polynomial, which are 465 // compute the list of exponent vectors of the polynomial, which are 466 466 // the lattice points whose convex hull is the Newton polytope of f 467 467 intmat exponents[size(f)][nvars(basering)]; … … 481 481 } 482 482 variablen=variablen[1,size(variablen)-1]; 483 // call normalFan in order to compute the Groebner fan484 list gf=normalFan (newtonp[1],newtonp[4],newtonp[3],1,variablen);483 // call normalFanL in order to compute the Groebner fan 484 list gf=normalFanL(newtonp[1],newtonp[4],newtonp[3],1,variablen); 485 485 // append newtonp to gf 486 486 gf[3]=newtonp; … … 525 525 proc triangulations (list polygon,list #) 526 526 "USAGE: triangulations(polygon[,#]); list polygon, list # 527 ASSUME: polygon is a list of integer vectors of the same size representing 528 the affine coordinates of the lattice points 527 ASSUME: polygon is a list of integer vectors of the same size representing 528 the affine coordinates of the lattice points 529 529 PURPOSE: the procedure considers the marked polytope given as the convex hull of 530 530 the lattice points and with these lattice points as markings; it then 531 computes all possible triangulations of this marked polytope 531 computes all possible triangulations of this marked polytope 532 532 RETURN: list, each entry corresponds to one triangulation and the ith entry is 533 533 itself a list of integer vectors of size three, where each integer … … 536 536 NOTE:- the procedure calls for its computations the program points2triangs 537 537 from the program topcom by Joerg Rambau, Universitaet Bayreuth; it 538 therefore is necessary that this program is installed in order to use 538 therefore is necessary that this program is installed in order to use 539 539 this procedure; see 540 540 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM 541 541 @* - if you only want to have the regular triangulations the procedure should 542 542 be called with the string 'regular' as optional argument 543 @* - the procedure creates the files /tmp/triangulationsinput and 543 @* - the procedure creates the files /tmp/triangulationsinput and 544 544 /tmp/triangulationsoutput; 545 the former is used as input for points2triangs and the latter is its 546 output containing the triangulations of corresponding to points in the 547 format of points2triangs; if you wish to use this for further 545 the former is used as input for points2triangs and the latter is its 546 output containing the triangulations of corresponding to points in the 547 format of points2triangs; if you wish to use this for further 548 548 computations with topcom, you have to call the procedure with the 549 string 'keepfiles' as optional argument 550 @* - note that an integer i in an integer vector representing a triangle 551 refers to the ith lattice point, i.e. polygon[i]; this convention is 552 different from TOPCOM's convention, where i would refer to the i-1st 549 string 'keepfiles' as optional argument 550 @* - note that an integer i in an integer vector representing a triangle 551 refers to the ith lattice point, i.e. polygon[i]; this convention is 552 different from TOPCOM's convention, where i would refer to the i-1st 553 553 lattice point 554 554 EXAMPLE: example triangulations; shows an example" … … 574 574 } 575 575 } 576 // prepare the input for points2triangs by writing the input polygon in the 576 // prepare the input for points2triangs by writing the input polygon in the 577 577 // necessary format 578 578 string spi="["; … … 598 598 } 599 599 string p2t=read("/tmp/triangulationsoutput"); // takes result of points2triangs 600 // delete the tmp-files, if no second argument is given 600 // delete the tmp-files, if no second argument is given 601 601 if (keepfiles==0) 602 602 { 603 603 system("sh","cd /tmp; rm -f triangulationsinput; rm -f triangulationsoutput"); 604 604 } 605 // preprocessing of p2t if points2triangs is version >= 0.15 605 // preprocessing of p2t if points2triangs is version >= 0.15 606 606 // brings p2t to the format of version 0.14 607 607 string np2t; // takes the triangulations in Singular format … … 625 625 } 626 626 else 627 { 627 { 628 628 np2t=np2t+p2t[i]; 629 629 } … … 637 637 { 638 638 if (np2t[size(np2t)]!=";") 639 { 639 { 640 640 np2t=np2t+p2t[size(p2t)-1]+p2t[size(p2t)]; 641 641 } … … 659 659 np2t=np2t+"))"; 660 660 i++; 661 } 661 } 662 662 else 663 663 { … … 713 713 "EXAMPLE:"; 714 714 echo=2; 715 // the lattice points of the unit square in the plane 715 // the lattice points of the unit square in the plane 716 716 list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); 717 717 // the triangulations of this lattice point configuration are computed … … 724 724 proc secondaryPolytope (list polygon,list #) 725 725 "USAGE: secondaryPolytope(polygon[,#]); list polygon, list # 726 ASSUME: - polygon is a list of integer vectors of the same size representing 726 ASSUME: - polygon is a list of integer vectors of the same size representing 727 727 the affine coordinates of lattice points 728 @* - if the triangulations of the corresponding polygon have already been 728 @* - if the triangulations of the corresponding polygon have already been 729 729 computed with the procedure triangulations then these can be given as 730 730 a second (optional) argument in order to avoid doing this computation … … 732 732 PURPOSE: the procedure considers the marked polytope given as the convex hull of 733 733 the lattice points and with these lattice points as markings; it then 734 computes the lattice points of the secondary polytope given by this 734 computes the lattice points of the secondary polytope given by this 735 735 marked polytope which correspond to the triangulations computed by 736 736 the procedure triangulations … … 740 740 polytope corresponding to polygon 741 741 @* L[2] = the list of corresponding triangulations 742 NOTE: if the triangluations are not handed over as optional argument the 742 NOTE: if the triangluations are not handed over as optional argument the 743 743 procedure calls for its computation of these triangulations the program 744 points2triangs from the program topcom by Joerg Rambau, Universitaet 745 Bayreuth; it therefore is necessary that this program is installed in 744 points2triangs from the program topcom by Joerg Rambau, Universitaet 745 Bayreuth; it therefore is necessary that this program is installed in 746 746 order to use this procedure; see 747 747 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM … … 759 759 int i,j,k,l; 760 760 intmat N[2][2]; // is used to compute areas of triangles 761 intvec vertex; // stores a point in the secondary polytope as 761 intvec vertex; // stores a point in the secondary polytope as 762 762 // intermediate result 763 763 int eintrag; 764 764 int halt; 765 intmat secpoly[size(triangs)][size(polygon)]; // stores all lattice points 765 intmat secpoly[size(triangs)][size(polygon)]; // stores all lattice points 766 766 // of the secondary polytope 767 // consider each triangulation and compute the corresponding point 767 // consider each triangulation and compute the corresponding point 768 768 // in the secondary polytope 769 769 for (i=1;i<=size(triangs);i++) 770 770 { 771 // for each triangulation we have to compute the coordinates 771 // for each triangulation we have to compute the coordinates 772 772 // corresponding to each marked point 773 773 for (j=1;j<=size(polygon);j++) 774 774 { 775 775 eintrag=0; 776 // for each marked point we have to consider all triangles in the 776 // for each marked point we have to consider all triangles in the 777 777 // triangulation which involve this particular point 778 778 for (k=1;k<=size(triangs[i]);k++) … … 796 796 secpoly[i,1..size(polygon)]=vertex; 797 797 } 798 return(list(secpoly,triangs)); 798 return(list(secpoly,triangs)); 799 799 } 800 800 example … … 818 818 proc secondaryFan (list polygon,list #) 819 819 "USAGE: secondaryFan(polygon[,#]); list polygon, list # 820 ASSUME: - polygon is a list of integer vectors of the same size representing 820 ASSUME: - polygon is a list of integer vectors of the same size representing 821 821 the affine coordinates of lattice points 822 @* - if the triangulations of the corresponding polygon have already been 823 computed with the procedure triangulations then these can be given 824 as a second (optional) argument in order to avoid doing this 822 @* - if the triangulations of the corresponding polygon have already been 823 computed with the procedure triangulations then these can be given 824 as a second (optional) argument in order to avoid doing this 825 825 computation again 826 826 PURPOSE: the procedure considers the marked polytope given as the convex hull of 827 827 the lattice points and with these lattice points as markings; it then 828 computes the lattice points of the secondary polytope given by this 828 computes the lattice points of the secondary polytope given by this 829 829 marked polytope which correspond to the triangulations computed by 830 830 the procedure triangulations 831 RETURN: list, the ith entry of L[1] contains information about the ith cone in 832 the secondary fan of the polygon, i.e. the cone dual to the 831 RETURN: list, the ith entry of L[1] contains information about the ith cone in 832 the secondary fan of the polygon, i.e. the cone dual to the 833 833 ith vertex of the secondary polytope 834 @* L[1][i][1] = integer matrix representing the inequalities which 834 @* L[1][i][1] = integer matrix representing the inequalities which 835 835 describe the cone dual to the ith vertex 836 @* L[1][i][2] = a list which contains the inequalities represented 836 @* L[1][i][2] = a list which contains the inequalities represented 837 837 by L[1][i][1] as a list of strings, where we use the 838 838 variables x(1),...,x(n) 839 839 @* L[1][i][3] = only present if 'er' is set to 1; in that case it is 840 an interger matrix whose rows are the extreme rays 840 an interger matrix whose rows are the extreme rays 841 841 of the cone 842 @* L[2] = is an integer matrix whose rows span the linearity space 843 of the fan, i.e. the linear space which is contained in 842 @* L[2] = is an integer matrix whose rows span the linearity space 843 of the fan, i.e. the linear space which is contained in 844 844 each cone 845 @* L[3] = the secondary polytope in the format of the procedure 845 @* L[3] = the secondary polytope in the format of the procedure 846 846 polymakePolytope 847 @* L[4] = the list of triangulations corresponding to the vertices 847 @* L[4] = the list of triangulations corresponding to the vertices 848 848 of the secondary polytope 849 849 NOTE:- the procedure calls for its computation polymake by Ewgenij Gawrilow, 850 850 TU Berlin and Michael Joswig, so it only works if polymake is installed; 851 851 see http://www.math.tu-berlin.de/polymake/ 852 @* - in the optional argument # it is possible to hand over other names for 853 the variables to be used -- be careful, the format must be correct and 854 that is not tested, e.g. if you want the variable names to be 852 @* - in the optional argument # it is possible to hand over other names for 853 the variables to be used -- be careful, the format must be correct and 854 that is not tested, e.g. if you want the variable names to be 855 855 u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11' 856 @* - if the triangluations are not handed over as optional argument the 857 procedure calls for its computation of these triangulations the program 858 points2triangs from the program topcom by Joerg Rambau, Universitaet 859 Bayreuth; it therefore is necessary that this program is installed in 856 @* - if the triangluations are not handed over as optional argument the 857 procedure calls for its computation of these triangulations the program 858 points2triangs from the program topcom by Joerg Rambau, Universitaet 859 Bayreuth; it therefore is necessary that this program is installed in 860 860 order to use this procedure; see 861 861 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM … … 869 869 { 870 870 list triang=#[1]; 871 } 871 } 872 872 list sp=secondaryPolytope(polygon,triang); 873 873 list spp=polymakePolytope(sp[1]); 874 list sf=normalFan (spp[1],spp[4],spp[3],1);874 list sf=normalFanL(spp[1],spp[4],spp[3],1); 875 875 return(list(sf[1],sf[2],spp,triang)); 876 876 } … … 906 906 proc cycleLength (list boundary,intvec interior) 907 907 "USAGE: cycleLength(boundary,interior); list boundary, intvec interior 908 ASSUME: boundary is a list of integer vectors describing a cycle in some 909 convex lattice polygon around the lattice point interior ordered 908 ASSUME: boundary is a list of integer vectors describing a cycle in some 909 convex lattice polygon around the lattice point interior ordered 910 910 clock wise 911 911 RETURN: string, the cycle length of the corresponding cycle in the dual … … 914 914 { 915 915 int j; 916 // create a ring whose variables are indexed by the points in 916 // create a ring whose variables are indexed by the points in 917 917 // boundary resp. by interior 918 918 string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]); … … 952 952 // interior is a lattice point in the interior of this lattice polygon 953 953 intvec interior=1,1; 954 // compute the general cycle length of a cycle of the corresponding cycle 954 // compute the general cycle length of a cycle of the corresponding cycle 955 955 // in the dual tropical curve, note that (0,1) and (2,1) do not contribute 956 956 cycleLength(boundary,interior); … … 961 961 proc splitPolygon (list markings) 962 962 "USAGE: splitPolygon (markings); markings list 963 ASSUME: markings is a list of integer vectors representing lattice points in 964 the plane which we consider as the marked points of the convex lattice 963 ASSUME: markings is a list of integer vectors representing lattice points in 964 the plane which we consider as the marked points of the convex lattice 965 965 polytope spanned by them 966 PURPOSE: split the marked points in the vertices, the points on the facets 966 PURPOSE: split the marked points in the vertices, the points on the facets 967 967 which are not vertices, and the interior points 968 968 RETURN: list, L consisting of three lists … … 970 970 @* L[1][i][1] = intvec, the coordinates of the ith vertex 971 971 @* L[1][i][2] = int, the position of L[1][i][1] in markings 972 @* L[2][i] : represents the lattice points on the facet of the 973 polygon with endpoints L[1][i] and L[1][i+1] 972 @* L[2][i] : represents the lattice points on the facet of the 973 polygon with endpoints L[1][i] and L[1][i+1] 974 974 (i considered modulo size(L[1])) 975 @* L[2][i][j][1] = intvec, the coordinates of the jth 975 @* L[2][i][j][1] = intvec, the coordinates of the jth 976 976 lattice point on that facet 977 @* L[2][i][j][2] = int, the position of L[2][i][j][1] 977 @* L[2][i][j][2] = int, the position of L[2][i][j][1] 978 978 in markings 979 @* L[3] : represents the interior lattice points of the polygon 979 @* L[3] : represents the interior lattice points of the polygon 980 980 @* L[3][i][1] = intvec, coordinates of ith interior point 981 981 @* L[3][i][2] = int, the position of L[3][i][1] in markings … … 988 988 vert[1]=pb[2]; 989 989 int i,j,k; // indices 990 list boundary; // stores the points on the facets of the 990 list boundary; // stores the points on the facets of the 991 991 // polygon which are not vertices 992 // append to the boundary points as well as to the vertices 992 // append to the boundary points as well as to the vertices 993 993 // the first vertex a second time 994 994 pb[1]=pb[1]+list(pb[1][1]); … … 1015 1015 // store the information on the boundary in vert[2] 1016 1016 vert[2]=boundary; 1017 // find the remaining points in the input which are not on 1017 // find the remaining points in the input which are not on 1018 1018 // the boundary by checking 1019 1019 // for each point in markings if it is contained in pb[1] … … 1032 1032 // store the interior points in vert[3] 1033 1033 vert[3]=interior; 1034 // add to each point in vert the index which it gets from 1034 // add to each point in vert the index which it gets from 1035 1035 // its position in the input markings; 1036 1036 // do so for ver[1] … … 1066 1066 } 1067 1067 vert[3][i]=list(vert[3][i],j); 1068 } 1068 } 1069 1069 return(vert); 1070 1070 } … … 1073 1073 "EXAMPLE:"; 1074 1074 echo=2; 1075 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1075 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1076 1076 // with all integer points as markings 1077 1077 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), … … 1093 1093 proc eta (list triang,list polygon) 1094 1094 "USAGE: eta(triang,polygon); triang, polygon list 1095 ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a 1096 list with three entries describing a convex lattice polygon in the 1095 ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a 1096 list with three entries describing a convex lattice polygon in the 1097 1097 following way: 1098 @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] 1099 is a lattice point which is a vertex of the lattice 1098 @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] 1099 is a lattice point which is a vertex of the lattice 1100 1100 polygon, and polygon[1][i][2] is an integer assigned to 1101 1101 this lattice point as identifying index 1102 @* polygon[2] : is a list of lists; for each vertex of the polygon, 1103 i.e. for each entry in polygon[1], it contains a list 1104 polygon[2][i], which contains the lattice points on the 1105 facet with endpoints polygon[1][i] and polygon[1][i+1] 1102 @* polygon[2] : is a list of lists; for each vertex of the polygon, 1103 i.e. for each entry in polygon[1], it contains a list 1104 polygon[2][i], which contains the lattice points on the 1105 facet with endpoints polygon[1][i] and polygon[1][i+1] 1106 1106 - i considered mod size(polygon[1]); 1107 each such lattice point contributes an entry 1107 each such lattice point contributes an entry 1108 1108 polygon[2][i][j][1] which is an integer 1109 vector giving the coordinate of the lattice point and an 1109 vector giving the coordinate of the lattice point and an 1110 1110 entry polygon[2][i][j][2] which is the identifying index 1111 @* polygon[3] : is a list of lists, where each entry corresponds to a 1112 lattice point in the interior of the polygon, with 1111 @* polygon[3] : is a list of lists, where each entry corresponds to a 1112 lattice point in the interior of the polygon, with 1113 1113 polygon[3][j][1] being the coordinates of the point 1114 1114 and polygon[3][j][2] being the identifying index; 1115 @* triang is a list of integer vectors all of size three describing a 1116 triangulation of the polygon described by polygon; if an entry of 1115 @* triang is a list of integer vectors all of size three describing a 1116 triangulation of the polygon described by polygon; if an entry of 1117 1117 triang is the vector (i,j,k) then the triangle is built by the vertices 1118 1118 with indices i, j and k 1119 RETURN: intvec, the integer vector eta describing that vertex of the Newton 1120 polytope discriminant of the polygone whose dual cone in the 1121 Groebner fan contains the cone of the secondary fan of the 1119 RETURN: intvec, the integer vector eta describing that vertex of the Newton 1120 polytope discriminant of the polygone whose dual cone in the 1121 Groebner fan contains the cone of the secondary fan of the 1122 1122 polygon corresponding to the given triangulation 1123 NOTE: for a better description of eta see Gelfand, Kapranov, 1123 NOTE: for a better description of eta see Gelfand, Kapranov, 1124 1124 Zelevinski: Discriminants, Resultants and multidimensional Determinants. 1125 1125 Chapter 10. … … 1127 1127 { 1128 1128 int i,j,k,l,m,n; // index variables 1129 list ordpolygon; // stores the lattice points in the order 1129 list ordpolygon; // stores the lattice points in the order 1130 1130 // used in the triangulation 1131 1131 list triangarea; // stores the areas of the triangulations … … 1153 1153 for (i=1;i<=size(triang);i++) 1154 1154 { 1155 // Note that the ith lattice point in orderedpolygon has the 1155 // Note that the ith lattice point in orderedpolygon has the 1156 1156 // number i-1 in the triangulation! 1157 1157 N=ordpolygon[triang[i][1]]-ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]-ordpolygon[triang[i][3]]; … … 1159 1159 } 1160 1160 intvec ETA; // stores the eta_ij 1161 int etaij; // stores the part of eta_ij during computations 1161 int etaij; // stores the part of eta_ij during computations 1162 1162 // which comes from triangle areas 1163 int seitenlaenge; // stores the part of eta_ij during computations 1163 int seitenlaenge; // stores the part of eta_ij during computations 1164 1164 // which comes from boundary facets 1165 1165 list seiten; // stores the lattice points on facets of the polygon 1166 1166 intvec v; // used to compute a facet length 1167 // 3) store first in seiten[i] all lattice points on the facet 1167 // 3) store first in seiten[i] all lattice points on the facet 1168 1168 // connecting the ith vertex, 1169 // i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], 1169 // i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], 1170 1170 // where we replace i+1 1171 1171 // 1 if i=size(polygon[1]); 1172 // then append the last entry of seiten once more at the very 1172 // then append the last entry of seiten once more at the very 1173 1173 // beginning of seiten, so 1174 1174 // that the index is shifted by one … … 1196 1196 if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3])) 1197 1197 { 1198 // ... if so, add the area of the triangle to etaij 1198 // ... if so, add the area of the triangle to etaij 1199 1199 etaij=etaij+triangarea[k]; 1200 // then check if that triangle has a facet which is contained 1201 // in one of the 1200 // then check if that triangle has a facet which is contained 1201 // in one of the 1202 1202 // two facets of the polygon which are adjecent to the given vertex ... 1203 1203 // these two facets are seiten[j] and seiten[j+1] … … 1213 1213 if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2])) 1214 1214 { 1215 // if so, then compute the vector pointing from this 1215 // if so, then compute the vector pointing from this 1216 1216 // lattice point to the vertex 1217 1217 v=polygon[1][j][1]-seiten[n][l][1]; 1218 // and the lattice length of this vector has to be 1218 // and the lattice length of this vector has to be 1219 1219 // subtracted from etaij 1220 1220 etaij=etaij-abs(gcd(v[1],v[2])); … … 1228 1228 ETA[polygon[1][j][2]]=etaij; 1229 1229 } 1230 // 5) compute the eta_ij for all lattice points on the facets 1230 // 5) compute the eta_ij for all lattice points on the facets 1231 1231 // of the polygon which are not vertices, these are the 1232 1232 // lattice points in polygon[2][1] to polygon[2][size(polygon[1])] … … 1234 1234 { 1235 1235 for (j=1;j<=size(polygon[2][i]);j++) 1236 { 1236 { 1237 1237 // initialise etaij 1238 1238 etaij=0; … … 1245 1245 if ((polygon[2][i][j][2]==triang[k][1]) or (polygon[2][i][j][2]==triang[k][2]) or (polygon[2][i][j][2]==triang[k][3])) 1246 1246 { 1247 // ... if so, add the area of the triangle to etaij 1247 // ... if so, add the area of the triangle to etaij 1248 1248 etaij=etaij+triangarea[k]; 1249 // then check if that triangle has a facet which is contained in the 1249 // then check if that triangle has a facet which is contained in the 1250 1250 // facet of the polygon which contains the lattice point in question, 1251 1251 // this is the facet seiten[i+1]; … … 1255 1255 // ... and for each lattice point in the triangle ... 1256 1256 for (m=1;m<=size(triang[k]);m++) 1257 { 1257 { 1258 1258 // ... if they coincide and are not the vertex itself ... 1259 1259 if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2])) 1260 1260 { 1261 // if so, then compute the vector pointing from 1261 // if so, then compute the vector pointing from 1262 1262 // this lattice point to the vertex 1263 1263 v=polygon[2][i][j][1]-seiten[i+1][l][1]; 1264 // and the lattice length of this vector contributes 1264 // and the lattice length of this vector contributes 1265 1265 // to seitenlaenge 1266 1266 seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2])); … … 1270 1270 } 1271 1271 } 1272 // if the lattice point was a vertex of any triangle 1272 // if the lattice point was a vertex of any triangle 1273 1273 // in the triangulation ... 1274 1274 if (etaij!=0) … … 1295 1295 if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3])) 1296 1296 { 1297 // ... if so, add the area of the triangle to etaij 1297 // ... if so, add the area of the triangle to etaij 1298 1298 etaij=etaij+triangarea[k]; 1299 1299 } … … 1308 1308 "EXAMPLE:"; 1309 1309 echo=2; 1310 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1310 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1311 1311 // with all integer points as markings 1312 1312 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), … … 1315 1315 // split the polygon in its vertices, its facets and its interior points 1316 1316 list sp=splitPolygon(polygon); 1317 // define a triangulation by connecting the only interior point 1317 // define a triangulation by connecting the only interior point 1318 1318 // with the vertices 1319 1319 list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10); … … 1321 1321 eta(triang,sp); 1322 1322 } 1323 1323 1324 1324 ///////////////////////////////////////////////////////////////////////////// 1325 1325 1326 1326 proc findOrientedBoundary (list polygon) 1327 1327 "USAGE: findOrientedBoundary(polygon); polygon list 1328 ASSUME: polygon is a list of integer vectors defining integer lattice points 1328 ASSUME: polygon is a list of integer vectors defining integer lattice points 1329 1329 in the plane 1330 1330 RETURN: list l with the following interpretation 1331 @* l[1] = list of integer vectors such that the polygonal path 1332 defined by these is the boundary of the convex hull of 1331 @* l[1] = list of integer vectors such that the polygonal path 1332 defined by these is the boundary of the convex hull of 1333 1333 the lattice points in polygon 1334 1334 @* l[2] = list, the redundant points in l[1] have been removed … … 1348 1348 } 1349 1349 // check is the polygon is only a line segment given by more than two points; 1350 // for this first compute sum of the absolute values of the determinants 1350 // for this first compute sum of the absolute values of the determinants 1351 1351 // of the matrices whose 1352 // rows are the vectors pointing from the first to the second point 1352 // rows are the vectors pointing from the first to the second point 1353 1353 // and from the 1354 // the first point to the ith point for i=3,...,size(polygon); 1354 // the first point to the ith point for i=3,...,size(polygon); 1355 1355 // if this sum is zero 1356 1356 // then the polygon is a line segment and we have to find its end points … … 1365 1365 intmat laenge[size(polygon)][size(polygon)]; 1366 1366 intvec mp; 1367 // for this collect first all vectors pointing from one lattice 1367 // for this collect first all vectors pointing from one lattice 1368 1368 // point to the next, 1369 1369 // compute their pairwise angles and their lengths 1370 1370 for (i=1;i<=size(polygon)-1;i++) 1371 { 1371 { 1372 1372 for (j=i+1;j<=size(polygon);j++) 1373 1373 { … … 1393 1393 polygon=sortlistbyintvec(polygon,abstand); 1394 1394 return(list(polygon,endpoints)); 1395 } 1395 } 1396 1396 /////////////////////////////////////////////////////////////// 1397 1397 list orderedvertices; // stores the vertices in an ordered way 1398 list minimisedorderedvertices; // stores the vertices in an ordered way; 1398 list minimisedorderedvertices; // stores the vertices in an ordered way; 1399 1399 // redundant ones removed 1400 list comparevertices; // stores vertices which should be compared to 1400 list comparevertices; // stores vertices which should be compared to 1401 1401 // the testvertex 1402 1402 orderedvertices[1]=polygon[1]; // set the starting vertex 1403 1403 minimisedorderedvertices[1]=polygon[1]; // set the starting vertex 1404 1404 intvec testvertex=polygon[1]; //vertex to which the others have to be compared 1405 intvec startvertex=polygon[1]; // keep the starting vertex to test, 1405 intvec startvertex=polygon[1]; // keep the starting vertex to test, 1406 1406 // when the end is reached 1407 1407 int endtest; // is set to one, when the end is reached 1408 int startvertexfound;// is 1, once for some testvertex a candidate 1409 // for the next vertex has been found 1408 int startvertexfound;// is 1, once for some testvertex a candidate 1409 // for the next vertex has been found 1410 1410 polygon=delete(polygon,1); // delete the testvertex 1411 1411 intvec v,w; 1412 1412 int l=1; // counts the vertices 1413 // the basic idea is that a vertex can be 1413 // the basic idea is that a vertex can be 1414 1414 // the next one on the boundary if all other vertices 1415 // lie to the right of the vector v pointing 1415 // lie to the right of the vector v pointing 1416 1416 // from the testvertex to this one; this can be tested 1417 // by checking if the determinant of the 2x2-matrix 1417 // by checking if the determinant of the 2x2-matrix 1418 1418 // with first column v and second column the vector w, 1419 // pointing from the testvertex to the new vertex, 1419 // pointing from the testvertex to the new vertex, 1420 1420 // is non-positive; if this is the case for all 1421 // new vertices, then the one in consideration is 1421 // new vertices, then the one in consideration is 1422 1422 // a possible choice for the next vertex on the boundary 1423 // and it is stored in naechste; we can then order 1423 // and it is stored in naechste; we can then order 1424 1424 // the candidates according to their distance from 1425 1425 // the testvertex; then they occur on the boundary in that order! … … 1433 1433 v=polygon[i]-testvertex; // points from the testvertex to the ith vertex 1434 1434 comparevertices=delete(polygon,i); // we needn't compare v to itself 1435 // we should compare v to the startvertex-testvertex; 1435 // we should compare v to the startvertex-testvertex; 1436 1436 // in the first calling of the loop 1437 // this is irrelevant since the difference will be zero; 1437 // this is irrelevant since the difference will be zero; 1438 1438 // however, later on it will 1439 // be vital, since we delete the vertices 1439 // be vital, since we delete the vertices 1440 1440 // which we have already tested from the list 1441 // of all vertices, and when all vertices 1441 // of all vertices, and when all vertices 1442 1442 // on the boundary have been found we would 1443 // therefore find a vertex in the interior 1443 // therefore find a vertex in the interior 1444 1444 // as candidate; but always testing against 1445 1445 // the starting vertex, this cannot happen 1446 comparevertices[size(comparevertices)+1]=startvertex; 1446 comparevertices[size(comparevertices)+1]=startvertex; 1447 1447 for (j=1;(j<=size(comparevertices)) and (d<=0);j++) 1448 1448 { … … 1452 1452 d=det(D); 1453 1453 } 1454 if (d<=0) // if all determinants are non-positive, 1454 if (d<=0) // if all determinants are non-positive, 1455 1455 { // then the ith vertex is a candidate 1456 1456 naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex, … … 1460 1460 } 1461 1461 if (size(naechste)>0) // then a candidate for the next vertex has been found 1462 { 1462 { 1463 1463 startvertexfound=1; // at least once a candidate has been found 1464 naechste=sortlist(naechste,3); // we order the candidates according 1464 naechste=sortlist(naechste,3); // we order the candidates according 1465 1465 // to their distance from testvertex; 1466 for (j=1;j<=size(naechste);j++) // then we store them in this 1466 for (j=1;j<=size(naechste);j++) // then we store them in this 1467 1467 { // order in orderedvertices 1468 1468 l++; 1469 1469 orderedvertices[l]=naechste[j][1]; 1470 1470 } 1471 testvertex=naechste[size(naechste)][1]; // we store the last one as 1471 testvertex=naechste[size(naechste)][1]; // we store the last one as 1472 1472 // next testvertex; 1473 1473 // store the next corner of NSD 1474 minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; 1475 naechste=sortlist(naechste,2); // then we reorder the vertices 1474 minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; 1475 naechste=sortlist(naechste,2); // then we reorder the vertices 1476 1476 // according to their position 1477 1477 for (j=size(naechste);j>=1;j--) // and we delete them from the vertices … … 1480 1480 } 1481 1481 } 1482 else // that means either that the vertex was inside the polygon, 1483 { // or that we have reached the last vertex on the boundary 1482 else // that means either that the vertex was inside the polygon, 1483 { // or that we have reached the last vertex on the boundary 1484 1484 // of the polytope 1485 if (startvertexfound==0) // the vertex was in the interior; 1485 if (startvertexfound==0) // the vertex was in the interior; 1486 1486 { // we delete it and start all over again 1487 orderedvertices[1]=polygon[1]; 1488 minimisedorderedvertices[1]=polygon[1]; 1487 orderedvertices[1]=polygon[1]; 1488 minimisedorderedvertices[1]=polygon[1]; 1489 1489 testvertex=polygon[1]; 1490 1490 startvertex=polygon[1]; 1491 1491 polygon=delete(polygon,1); 1492 1492 } 1493 else // we have reached the last vertex on the boundary of 1493 else // we have reached the last vertex on the boundary of 1494 1494 { // the polytope and can stop 1495 1495 endtest=1; … … 1498 1498 kill naechste; 1499 1499 } 1500 // test if the first vertex in minimisedorderedvertices 1500 // test if the first vertex in minimisedorderedvertices 1501 1501 // is on the same line with the second and 1502 // the last, i.e. if we started our search in the 1502 // the last, i.e. if we started our search in the 1503 1503 // middle of a face; if so, delete it 1504 1504 v=minimisedorderedvertices[2]-minimisedorderedvertices[1]; … … 1509 1509 minimisedorderedvertices=delete(minimisedorderedvertices,1); 1510 1510 } 1511 // test if the first vertex in minimisedorderedvertices 1511 // test if the first vertex in minimisedorderedvertices 1512 1512 // is on the same line with the two 1513 // last ones, i.e. if we started our search at the end of a face; 1513 // last ones, i.e. if we started our search at the end of a face; 1514 1514 // if so, delete it 1515 1515 v=minimisedorderedvertices[size(minimisedorderedvertices)-1]-minimisedorderedvertices[1]; … … 1543 1543 proc cyclePoints (list triang,list points,int pt) 1544 1544 "USAGE: cyclePoints(triang,points,pt) triang,points list, pt int 1545 ASSUME: - points is a list of integer vectors describing the lattice 1545 ASSUME: - points is a list of integer vectors describing the lattice 1546 1546 points of a marked polygon; 1547 @* - triang is a list of integer vectors describing a triangulation 1548 of the marked polygon in the sense that an integer vector of 1549 the form (i,j,k) describes the triangle formed by polygon[i], 1547 @* - triang is a list of integer vectors describing a triangulation 1548 of the marked polygon in the sense that an integer vector of 1549 the form (i,j,k) describes the triangle formed by polygon[i], 1550 1550 polygon[j] and polygon[k]; 1551 @* - pt is an integer between 1 and size(points), singling out a 1551 @* - pt is an integer between 1 and size(points), singling out a 1552 1552 lattice point among the marked points 1553 PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice 1554 points in points which in the triangulation triang are connected 1555 to the point points[pt]; the procedure computes all marked points 1553 PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice 1554 points in points which in the triangulation triang are connected 1555 to the point points[pt]; the procedure computes all marked points 1556 1556 in points which lie on the boundary of that polygon, ordered 1557 1557 clockwise 1558 RETURN: list, of integer vectors which are the coordinates of the lattice 1559 points on the boundary of the above mentioned polygon P, if 1560 this polygon is not the empty set (that would be the case if 1561 points[pt] is not a vertex of any triangle in the 1558 RETURN: list, of integer vectors which are the coordinates of the lattice 1559 points on the boundary of the above mentioned polygon P, if 1560 this polygon is not the empty set (that would be the case if 1561 points[pt] is not a vertex of any triangle in the 1562 1562 triangulation); otherwise return the empty list 1563 1563 EXAMPLE: example cyclePoints; shows an example" 1564 1564 { 1565 1565 int i,j; // indices 1566 list v; // saves the indices of lattice points connected to the 1566 list v; // saves the indices of lattice points connected to the 1567 1567 // interior point in the triangulation 1568 1568 // save all points in triangulations containing pt in v … … 1600 1600 pts[i]=points[v[i]]; 1601 1601 } 1602 // consider the convex polytope spanned by the points in pts, 1602 // consider the convex polytope spanned by the points in pts, 1603 1603 // find the points on the 1604 1604 // boundary and order them clockwise … … 1609 1609 "EXAMPLE:"; 1610 1610 echo=2; 1611 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1611 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1612 1612 // with all integer points as markings 1613 1613 list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), 1614 1614 intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), 1615 1615 intvec(0,2),intvec(0,3); 1616 // define a triangulation 1616 // define a triangulation 1617 1617 list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10), 1618 1618 intvec(1,8,9),intvec(1,2,8); … … 1626 1626 "USAGE: latticeArea(polygon); polygon list 1627 1627 ASSUME: polygon is a list of integer vectors in the plane 1628 RETURN: int, the lattice area of the convex hull of the lattice points in 1628 RETURN: int, the lattice area of the convex hull of the lattice points in 1629 1629 polygon, i.e. twice the Euclidean area 1630 1630 EXAMPLE: example polygonlatticeArea; shows an example" … … 1655 1655 proc picksFormula (list polygon) 1656 1656 "USAGE: picksFormula(polygon); polygon list 1657 ASSUME: polygon is a list of integer vectors in the plane and consider their 1658 convex hull C 1659 RETURN: list, L of three integersthe 1657 ASSUME: polygon is a list of integer vectors in the plane and consider their 1658 convex hull C 1659 RETURN: list, L of three integersthe 1660 1660 @* L[1] : the lattice area of C, i.e. twice the Euclidean area 1661 1661 @* L[2] : the number of lattice points on the boundary of C … … 1682 1682 bdpts=bdpts+abs(gcd(edge[1],edge[2])); 1683 1683 } 1684 // Pick's formula says that the lattice area A, the number g of interior 1684 // Pick's formula says that the lattice area A, the number g of interior 1685 1685 // points and 1686 1686 // the number b of boundary points are connected by the formula: A=b+2g-2 … … 1709 1709 proc ellipticNF (list polygon) 1710 1710 "USAGE: ellipticNF(polygon); polygon list 1711 ASSUME: polygon is a list of integer vectors in the plane such that their 1712 convex hull C has precisely one interior lattice point; i.e. C is the 1711 ASSUME: polygon is a list of integer vectors in the plane such that their 1712 convex hull C has precisely one interior lattice point; i.e. C is the 1713 1713 Newton polygon of an elliptic curve 1714 PURPOSE: compute the normal form of the polygon with respect to the unimodular 1714 PURPOSE: compute the normal form of the polygon with respect to the unimodular 1715 1715 affine transformations T=A*x+v; there are sixteen different normal forms 1716 (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 1717 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 1716 (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 1717 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 1718 1718 238--250.) 1719 1719 RETURN: list, L such that 1720 @* L[1] : list whose entries are the vertices of the normal form of 1720 @* L[1] : list whose entries are the vertices of the normal form of 1721 1721 the polygon 1722 1722 @* L[2] : the matrix A of the unimodular transformation 1723 1723 @* L[3] : the translation vector v of the unimodular transformation 1724 @* L[4] : list such that the ith entry is the image of polygon[i] 1724 @* L[4] : list such that the ith entry is the image of polygon[i] 1725 1725 under the unimodular transformation T 1726 1726 EXAMPLE: example ellipticNF; shows an example" … … 1754 1754 intvec trans; // stores the vector by which we have to translate the polygon 1755 1755 intmat A[2][2]; // stores the matrix by which we have to transform the polygon 1756 matrix M[3][3]; // stores the projective coordinates of the points 1756 matrix M[3][3]; // stores the projective coordinates of the points 1757 1757 // which are to be transformed 1758 matrix N[3][3]; // stores the projective coordinates of the points to 1758 matrix N[3][3]; // stores the projective coordinates of the points to 1759 1759 // which M is to be transformed 1760 intmat T[3][3]; // stores the unimodular affine transformation in 1760 intmat T[3][3]; // stores the unimodular affine transformation in 1761 1761 // projective form 1762 1762 // add the second point of pg once again at the end 1763 1763 pg=insert(pg,pg[2],size(pg)); 1764 // if there is only one edge which has the maximal number of lattice points, 1764 // if there is only one edge which has the maximal number of lattice points, 1765 1765 // then M should be: 1766 1766 M=pg[max],1,pg[max+1],1,pg[max+2],1; … … 1852 1852 M=pg[max],1,pg[max+1],1,pg[max+2],1; 1853 1853 // the orientation of the polygon matters 1854 A=pg[max-1]-pg[max],pg[max+1]-pg[max]; 1854 A=pg[max-1]-pg[max],pg[max+1]-pg[max]; 1855 1855 if (det(A)==4) 1856 1856 { … … 1901 1901 { 1902 1902 max++; 1903 } 1903 } 1904 1904 M=pg[max],1,pg[max+1],1,pg[max+2],1; 1905 1905 N=0,1,1,1,2,1,2,1,1; … … 1964 1964 // the vertices of the normal form are 1965 1965 nf[1]; 1966 // it has been transformed by the unimodular affine transformation A*x+v 1966 // it has been transformed by the unimodular affine transformation A*x+v 1967 1967 // with matrix A 1968 1968 nf[2]; … … 1981 1981 "USAGE: ellipticNFDB(n[,#]); n int, # list 1982 1982 ASSUME: n is an integer between 1 and 16 1983 PURPOSE: this is a database storing the 16 normal forms of planar polygons with 1983 PURPOSE: this is a database storing the 16 normal forms of planar polygons with 1984 1984 precisely one interior point up to unimodular affine transformations 1985 @* (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 1985 @* (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons 1986 1986 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 1987 1987 238--250.) 1988 1988 RETURN: list, L such that 1989 @* L[1] : list whose entries are the vertices of the nth normal form 1990 @* L[2] : list whose entries are all the lattice points of the 1991 nth normal form 1992 @* L[3] : only present if the optional parameter # is present, and 1993 then it is a polynomial in the variables (x,y) whose 1989 @* L[1] : list whose entries are the vertices of the nth normal form 1990 @* L[2] : list whose entries are all the lattice points of the 1991 nth normal form 1992 @* L[3] : only present if the optional parameter # is present, and 1993 then it is a polynomial in the variables (x,y) whose 1994 1994 Newton polygon is the nth normal form 1995 NOTE: the optional parameter is only allowed if the basering has the 1995 NOTE: the optional parameter is only allowed if the basering has the 1996 1996 variables x and y 1997 1997 EXAMPLE: example ellipticNFDB; shows an example" … … 2059 2059 static proc scalarproduct (intvec w,intvec v) 2060 2060 "USAGE: scalarproduct(w,v); w,v intvec 2061 ASSUME: w and v are integer vectors of the same length 2061 ASSUME: w and v are integer vectors of the same length 2062 2062 RETURN: int, the scalarproduct of v and w 2063 2063 NOTE: the procedure is called by findOrientedBoundary" … … 2074 2074 "USAGE: intmatcoldelete(w,i); w intmat, i int 2075 2075 RETURN: intmat, the integer matrix w with the ith comlumn deleted 2076 NOTE: the procedure is called by intmatsort and normalFan "2076 NOTE: the procedure is called by intmatsort and normalFanL" 2077 2077 { 2078 2078 if (typeof(w)=="intmat") … … 2137 2137 { 2138 2138 int m=nrows(M); 2139 2139 2140 2140 } 2141 2141 else … … 2195 2195 { 2196 2196 return(""); 2197 2197 2198 2198 } 2199 2199 if (i==1) … … 2305 2305 k++; 2306 2306 } 2307 else 2307 else 2308 2308 { 2309 2309 stop=1; … … 2348 2348 k++; 2349 2349 } 2350 else 2350 else 2351 2351 { 2352 2352 stop=1; … … 2397 2397 static proc polygonToCoordinates (list points) 2398 2398 "USAGE: polygonToCoordinates(points); points list 2399 ASSUME: points is a list of integer vectors each of size two describing the 2400 marked points of a convex lattice polygon like the output of 2399 ASSUME: points is a list of integer vectors each of size two describing the 2400 marked points of a convex lattice polygon like the output of 2401 2401 polygonDB 2402 RETURN: list, the first entry is a string representing the coordinates 2402 RETURN: list, the first entry is a string representing the coordinates 2403 2403 corresponding to the latticpoints seperated by commata 2404 the second entry is a list where the ith entry is a string 2405 representing the coordinate of corresponding to the ith 2406 lattice point the third entry is the latex format of the 2404 the second entry is a list where the ith entry is a string 2405 representing the coordinate of corresponding to the ith 2406 lattice point the third entry is the latex format of the 2407 2407 first entry 2408 2408 NOTE: the procedure is called by fan" … … 2426 2426 ASSUME: - M is an integer matrix where a first column of 0's or 1's should be added 2427 2427 @* - art is one of the following strings: 2428 @* + 'rays' : indicating that a first column of 0's should be added 2429 @* + 'points' : indicating that a first column of 1's should be added 2428 @* + 'rays' : indicating that a first column of 0's should be added 2429 @* + 'points' : indicating that a first column of 1's should be added 2430 2430 RETURN: intmat, a first column has been added to the matrix" 2431 2431 { -
Singular/LIB/tropical.lib
r3c3e3d r8275a9 204 204 LIB "elim.lib"; 205 205 LIB "linalg.lib"; 206 LIB " oldpolymake.lib";206 LIB "polymake.lib"; 207 207 LIB "primdec.lib"; 208 208 LIB "absfact.lib"; … … 6910 6910 "USAGE: intmatcoldelete(w,i); w intmat, i int 6911 6911 RETURN: intmat, the integer matrix w with the ith comlumn deleted 6912 NOTE: the procedure is called by intmatsort and normalFan "6912 NOTE: the procedure is called by intmatsort and normalFanL" 6913 6913 { 6914 6914 if ((i<1) or (i>ncols(w)) or (ncols(w)==1)) -
Singular/singular-libs
r3c3e3d r8275a9 23 23 paraplanecurves.lib phindex.lib \ 24 24 pointid.lib poly.lib \ 25 oldpolymake.lib presolve.lib primdec.lib primdecint.lib \25 polymake.lib presolve.lib primdec.lib primdecint.lib \ 26 26 primitiv.lib qhmoduli.lib random.lib realclassify.lib \ 27 27 realrad.lib reesclos.lib resbinomial.lib \ … … 53 53 ncfactor.lib nctools.lib perron.lib qmatrix.lib \ 54 54 ncall.lib 55 56 55 56 -
Tst/Short/polymake.tst
r3c3e3d r8275a9 3 3 LIB "tst.lib"; 4 4 tst_init(); 5 LIB " oldpolymake.lib";5 LIB "polymake.lib"; 6 6 /////////////////////////////////////////////////////////////////////////// 7 7 // A) Test for Procedures using Polymake 8 8 /////////////////////////////////////////////////////////////////////////// 9 9 example polymakePolytope; 10 example newtonPolytope ;10 example newtonPolytopeP; 11 11 example newtonPolytopeLP; 12 example normalFan ;12 example normalFanL; 13 13 example groebnerFan; 14 14 /////////////////////////////////////////////////////////////////////////// -
doc/COPYING.texi
r3c3e3d r8275a9 131 131 @copyright{} Winfried Bruns and Bogdan Ichim 132 132 @* @uref{http://www.mathematik.uni-osnabrueck.de/normaliz/} 133 @item polymake (used by oldpolymake.lib, @pxref{oldpolymake_lib})133 @item polymake (used by polymake.lib, @pxref{polymake_lib}) 134 134 @copyright{} Ewgenij Gawrilow and Michael Joswig 135 135 @* @uref{http://www.polymake.de/} … … 142 142 @copyright{} Oliver Labs (2001-2008), Stephan Holzer (2004-2005) 143 143 @* @uref{http://surfex.AlgebraicSurface.net} 144 @item TOPCOM (used by oldpolymake.lib, @pxref{oldpolymake_lib})144 @item TOPCOM (used by polymake.lib, @pxref{polymake_lib}) 145 145 @copyright{} J@"org Rambau 146 146 @* @uref{http://www.rambau.wm.uni-bayreuth.de/TOPCOM/} -
doc/Makefile.bsp
r3c3e3d r8275a9 63 63 CHKSUM_DB = ${DOC_SUBDIR}/chksum 64 64 # which tags to avoid: 65 DOC2TEX_EXAMPLE_EXCLUSIONS = -exclude oldpolymake65 DOC2TEX_EXAMPLE_EXCLUSIONS = -exclude polymake 66 66 # which tags to avoid: 67 TAG = oldpolymake67 TAG = polymake 68 68 DOC2TEX = ${PERL} ./doc2tex.pl -docdir ${DOC_SUBDIR} \ 69 69 -Singular ${SINGULAR} -verbose ${VERBOSE} -make ${MAKE} \
Note: See TracChangeset
for help on using the changeset viewer.