Changeset 7e8485 in git
 Timestamp:
 Oct 21, 2013, 3:57:03 PM (9 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
 Children:
 48935b4077cd8f5a0f1e6050b74b4fbd0f364df1
 Parents:
 f1babfbabc0fc2906b36df32051eaaf09673dc6f
 gitauthor:
 Martin Lee <martinlee84@web.de>20131021 15:57:03+02:00
 gitcommitter:
 Yue Ren <ren@mathematik.unikl.de>20131211 17:46:45+01:00
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/oldpolymake.lib
rf1babf r7e8485 1 //// 2 version="version oldpolymake.lib 4.0.0.0 Jun_2013 "; // $Id$ 1 version="version oldpolymake.lib 4.0.0.0 Jun_2013 "; 3 2 category="Tropical Geometry"; 4 3 info=" 5 LIBRARY: oldpolymake.lib Computations with polytopes and fans,6 interface to polymake and TOPCOM4 LIBRARY: oldpolymake.lib Computations with polytopes and fans, 5 interface to polymake and TOPCOM 7 6 AUTHOR: Thomas Markwig, email: keilen@mathematik.unikl.de 8 7 … … 10 9 Most procedures will not work unless polymake or topcom is installed and 11 10 if so, they will only work with the operating system LINUX! 12 For more detailed information see the following note orconsult the11 For more detailed information see IMPORTANT NOTE respectively consult the 13 12 help string of the procedures. 14 13 15 NOTE: 16 Even though this is a Singular library for computing polytopes and fans 17 such as the Newton polytope or the Groebner fan of a polynomial, most of 18 the hard computations are NOT done by Singular but by the program 14 The conventions used in this library for polytopes and fans, e.g. the 15 length and labeling of their vertices resp. rays, differs from the conventions 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 18 whenever possible. 19 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 19 24 @*  polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt 20 @* (see http://www.math.tuberlin.de/polymake/), 21 @* respectively (only in the procedure triangula rions) by the program22 @*  topcom by Joerg Rambau, Universitaet Bayreuth (see http://www.unibayreuth.de/23 24 @* This library should rather be seen as an interface which allows to use a25 (very limited) number of options which polymake respectively topcom offers 26 to compute with polytopes and fans and to make the results available in 27 Singular for further computations; 25 @* (see http://www.math.tuberlin.de/polymake/), 26 @* respectively (only in the procedure triangulations) by the program 27 @*  topcom by Joerg Rambau, Universitaet Bayreuth (see 28 @* http://www.unibayreuth.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; 28 33 moreover, the user familiar with Singular does not have to learn the syntax 29 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 30 35 purposes. 31 @* Note, though, that the procedures concerned with planar polygons are 36 @* Note, though, that the procedures concerned with planar polygons are 32 37 independent of both, polymake and topcom. 33 38 34 PROCEDURES: 35 polymakePolytope() computes the vertices of a polytope using polymake 36 newtonPolytopeP() computes the Newton polytope of a polynomial 37 newtonPolytopeLP() computes the lattice points of the Newton polytope 38 normalFan() computes the normal fan of a polytope 39 groebnerFan() computes the Groebner fan of a polynomial 40 intmatToPolymake() transforms an integer matrix into polymake format 41 polymakeToIntmat() transforms polymake output into an integer matrix 42 43 triangulations() computes all triangulations of a marked polytope 44 secondaryPolytope() computes the secondary polytope of a marked polytope 45 46 secondaryFan() computes the secondary fan of a marked polytope 47 48 cycleLength() computes the cycleLength of cycle 49 splitPolygon() splits a marked polygon into vertices, facets, interior points 50 eta() computes the etavector of a triangulation 51 findOrientedBoundary() computes the boundary of a convex hull 52 cyclePoints() computes lattice points connected to some lattice point 53 latticeArea() computes the lattice area of a polygon 54 picksFormula() computes the ingrediants of Pick's formula for a polygon 55 ellipticNF() computes the normal form of an elliptic polygon 56 ellipticNFDB() displays the 16 normal forms of elliptic polygons 57 58 polymakeKeepTmpFiles() determines if the files created in /tmp should be kept 39 PROCEDURES USING POLYMAKE: 40 polymakePolytope() computes the vertices of a polytope using polymake 41 newtonPolytope() computes the Newton polytope of a polynomial 42 newtonPolytopeLP() computes the lattice points of the Newton polytope 43 normalFan() computes the normal fan of a polytope 44 groebnerFan() computes the Groebner fan of a polynomial 45 46 PROCEDURES USING TOPCOM: 47 triangulations() computes all triangulations of a marked polytope 48 secondaryPolytope() computes the secondary polytope of a marked polytope 49 50 PROCEDURES USING POLYMAKE AND TOPCOM: 51 secondaryFan() computes the secondary fan of a marked polytope 52 53 PROCEDURES CONERNED WITH PLANAR POLYGONS: 54 cycleLength() computes the cycleLength of cycle 55 splitPolygon() splits a marked polygon into vertices, facets, interior points 56 eta() computes the etavector of a triangulation 57 findOrientedBoundary() computes the boundary of a convex hull 58 cyclePoints() computes lattice points connected to some lattice point 59 latticeArea() computes the lattice area of a polygon 60 picksFormula() computes the ingrediants of Pick's formula for a polygon 61 ellipticNF() computes the normal form of an elliptic polygon 62 ellipticNFDB() displays the 16 normal forms of elliptic polygons 59 63 60 64 KEYWORDS: polytope; fan; secondary fan; secondary polytope; polymake; 61 Newton polytope; Groebner fan 65 Newton polytope; Groebner fan 62 66 "; 63 67 … … 83 87 LIB "linalg.lib"; 84 88 LIB "random.lib"; 89 LIB "polymake.so"; 85 90 //////////////////////////////////////////////////////////////////////////////// 86 91 … … 90 95 ///////////////////////////////////////////////////////////////////////////// 91 96 92 proc polymakePolytope (intmat po lytop,list #)93 "USAGE: polymakePolytope(po lytope[,#]); polytope list, # string94 ASSUME: each row of po lytope gives the coordinates of a lattice point of a95 polytope with their affine coordinates as given by the output of 97 proc polymakePolytope (intmat points) 98 "USAGE: polymakePolytope(points); polytope intmat 99 ASSUME: each row of points gives the coordinates of a lattice point of a 100 polytope with their affine coordinates as given by the output of 96 101 secondaryPolytope 97 PURPOSE: the procedure calls polymake to compute the vertices of the polytope 102 PURPOSE: the procedure calls polymake to compute the vertices of the polytope 98 103 as well as its dimension and information on its facets 99 RETURN: list L with four entries104 RETURN: list, L with four entries 100 105 @* L[1] : an integer matrix whose rows are the coordinates of vertices 101 of the polytope 106 of the polytope 102 107 @* L[2] : the dimension of the polytope 103 @* L[3] : a list whose i th entry explains to which vertices the104 ith vertex of the Newton polytope is connected 105  i.e. L[3][i] is an integer vector and an entry k in 106 there means that the vertex L[1][i] is connected to the 108 @* L[3] : a list whose ith entry explains to which vertices the 109 ith vertex of the Newton polytope is connected 110  i.e. L[3][i] is an integer vector and an entry k in 111 there means that the vertex L[1][i] is connected to the 107 112 vertex L[1][k] 108 @* L[4] : an integer matrix whose rows mulitplied by109 (1,var(1),...,var(nvar)) give a linear system of equations 113 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 114 (1,var(1),...,var(nvar)) give a linear system of equations 110 115 describing the affine hull of the polytope, 111 116 i.e. the smallest affine space containing the polytope 112 NOTE:  for its computations the procedure calls the program polymake by 113 Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; 114 it therefore is necessary that this program is installed in order 117 NOTE:  for its computations the procedure calls the program polymake by 118 Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; 119 it therefore is necessary that this program is installed in order 115 120 to use this procedure; 116 121 see http://www.math.tuberlin.de/polymake/ 117 @*  note that in the vertex edge graph we have changed the polymake 118 convention which starts indexing its vertices by zero while we start 122 @*  note that in the vertex edge graph we have changed the polymake 123 convention which starts indexing its vertices by zero while we start 119 124 with one ! 120 @*  the procedure creates the file /tmp/polytope.polymake which contains121 the polytope in polymake format; if you wish to use this for further122 computations with polymake, you have to use the procedure123 polymakeKeepTmpFiles in before124 @*  moreover, the procedure creates the file /tmp/polytope.output which125 it deletes again before ending126 @*  it is possible to provide an optional second argument a string127 which then will be used instead of 'polytope' in the name of the128 polymake output file129 125 EXAMPLE: example polymakePolytope; shows an example" 130 126 { 131 // the header for the file secendarypolytope.polymake 132 string sp="_application polytope 133 _version 2.2 134 _type RationalPolytope 135 136 POINTS 137 "; 127 // add a first column to polytope as homogenising coordinate 128 points=intmatAddFirstColumn(points,"points"); 129 polytope polytop=polytopeViaPoints(points); 130 list graph=vertexAdjacencyGraph(polytop)[2]; 138 131 int i,j; 139 // set the name for the polymake output file 140 if (size(#)>0) 141 { 142 if (typeof(#[1])=="string") 143 { 144 string dateiname=#[1]; 145 } 146 else 147 { 148 string dateiname="polytope"; 149 } 150 } 151 else 152 { 153 string dateiname="polytope"; 154 } 155 // create the lattice point list for polymake 156 sp=sp+intmatToPolymake(polytop,"points"); 157 // initialise dateiname.polymake and compute the vertices 158 write(":w /tmp/"+dateiname+".polymake",sp); 159 system("sh","cd /tmp; polymake "+dateiname+".polymake VERTICES > "+dateiname+".output"); 160 string vertices=read("/tmp/"+dateiname+".output"); 161 system("sh","/bin/rm /tmp/"+dateiname+".output"); 162 intmat np=polymakeToIntmat(vertices,"affine"); 163 // compute the dimension 164 system("sh","cd /tmp; polymake "+dateiname+".polymake DIM > "+dateiname+".output"); 165 string pdim=read("/tmp/"+dateiname+".output"); 166 system("sh","/bin/rm /tmp/"+dateiname+".output"); 167 pdim=pdim[5,size(pdim)6]; 168 execute("int nd="+pdim+";"); 169 // compute the vertexedge graph 170 system("sh","cd /tmp; polymake "+dateiname+".polymake GRAPH > "+dateiname+".output"); 171 string vertexedgegraph=read("/tmp/"+dateiname+".output"); 172 system("sh","/bin/rm /tmp/"+dateiname+".output"); 173 vertexedgegraph=vertexedgegraph[7,size(vertexedgegraph)8]; 174 string newveg; 175 for (i=1;i<=size(vertexedgegraph);i++) 176 { 177 if (vertexedgegraph[i]=="{") 178 { 179 newveg=newveg+"intvec("; 180 } 181 else 182 { 183 if (vertexedgegraph[i]=="}") 184 { 185 newveg=newveg+"),"; 186 } 187 else 188 { 189 if (vertexedgegraph[i]==" ") 190 { 191 newveg=newveg+","; 192 } 193 else 194 { 195 newveg=newveg+vertexedgegraph[i]; 196 } 197 } 198 } 199 } 200 newveg=newveg[1,size(newveg)1]; 201 execute("list nveg="+newveg+";"); 202 // raise each entry in nveg by one 203 for (i=1;i<=size(nveg);i++) 204 { 205 for (j=1;j<=size(nveg[i]);j++) 206 { 207 nveg[i][j]=nveg[i][j]+1; 208 } 209 } 210 // compute the affine hull 211 system("sh","cd /tmp; polymake "+dateiname+".polymake AFFINE_HULL > "+dateiname+".output"); 212 string equations=read("/tmp/"+dateiname+".output"); 213 system("sh","/bin/rm /tmp/"+dateiname+".output"); 214 if (size(equations)>14) 215 { 216 intmat neq=polymakeToIntmat(equations,"cleardenom"); 217 } 218 else 219 { 220 intmat neq[1][ncols(polytop)+1]; 221 } 222 // delete the tmpfiles, if polymakekeeptmpfiles is not set 223 if (defined(polymakekeeptmpfiles)==0) 224 { 225 system("sh","/bin/rm /tmp/"+dateiname+".polymake"); 226 } 227 // return the files 228 return(list(np,nd,nveg,neq)); 132 for (i=1;i<=size(graph);i++) 133 { 134 for (j=1;j<=size(graph[i]);j++) 135 { 136 graph[i][j]=graph[i][j]+1; 137 } 138 } 139 return(list(intmatcoldelete(vertices(polytop),1),dimension(polytop),graph,equations(polytop))); 229 140 } 230 141 example … … 232 143 "EXAMPLE:"; 233 144 echo=2; 234 // the lattice points of the unit square in the plane 145 // the lattice points of the unit square in the plane 235 146 list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); 236 147 // the secondary polytope of this lattice point configuration is computed … … 247 158 ring r=0,x(1..4),dp; 248 159 matrix M[5][1]=1,x(1),x(2),x(3),x(4); 249 np[4]*M;160 intmat(np[4])*M; 250 161 } 251 162 252 163 ///////////////////////////////////////////////////////////////////////////// 253 164 254 proc newtonPolytope P (poly f,list #)255 "USAGE: newtonPolytope P(f[,#]); f poly, # string256 RETURN: list L with four entries165 proc newtonPolytope (poly f) 166 "USAGE: newtonPolytope(f); f poly 167 RETURN: list, L with four entries 257 168 @* L[1] : an integer matrix whose rows are the coordinates of vertices 258 169 of the Newton polytope of f 259 170 @* L[2] : the dimension of the Newton polytope of f 260 @* L[3] : a list whose ith entry explains to which vertices the 261 ith vertex of the Newton polytope is connected 262  i.e. L[3][i] is an integer vector and an entry k in 171 @* L[3] : a list whose ith entry explains to which vertices the 172 ith vertex of the Newton polytope is connected 173  i.e. L[3][i] is an integer vector and an entry k in 263 174 there means that the vertex L[1][i] is 264 175 connected to the vertex L[1][k] 265 @* L[4] : an integer matrix whose rows mulitplied by266 (1,var(1),...,var(nvar)) give a linear system of equations 176 @* L[4] : an matrix of type bigintmat whose rows mulitplied by 177 (1,var(1),...,var(nvar)) give a linear system of equations 267 178 describing the affine hull of the Newton polytope, i.e. the 268 179 smallest affine space containing the Newton polytope 269 NOTE:  if we replace the first column of L[4] by zeros, i.e. if we move 270 the affine hull to the origin, then we get the equations for the 271 orthogonal compl oment of the linearity space of the normal fan dual180 NOTE:  if we replace the first column of L[4] by zeros, i.e. if we move 181 the affine hull to the origin, then we get the equations for the 182 orthogonal complement of the linearity space of the normal fan dual 272 183 to the Newton polytope, i.e. we get the EQUATIONS that 273 184 we need as input for polymake when computing the normal fan … … 275 186 TU Berlin and Michael Joswig, so it only works if polymake is installed; 276 187 see http://www.math.tuberlin.de/polymake/ 277 @*  the procedure creates the file /tmp/newtonPolytope.polymake which 278 contains the polytope in polymake format and which can be used for 279 further computations with polymake 280 @*  moreover, the procedure creates the file /tmp/newtonPolytope.output 281 and deletes it again before ending 282 @*  it is possible to give as an optional second argument a string 283 which then will be used instead of 'newtonPolytope' in the name of 284 the polymake output file 285 EXAMPLE: example newtonPolytopeP; shows an example" 188 EXAMPLE: example newtonPolytope; shows an example" 286 189 { 287 190 int i,j; 288 // compute the list of exponent vectors of the polynomial, 191 // compute the list of exponent vectors of the polynomial, 289 192 // which are the lattice points 290 193 // whose convex hull is the Newton polytope of f … … 296 199 f=flead(f); 297 200 } 298 if (size(#)==0)299 {300 #[1]="newtonPolytope";301 }302 201 // call polymakePolytope with exponents 303 return(polymakePolytope(exponents ,#));202 return(polymakePolytope(exponents)); 304 203 } 305 204 example … … 311 210 poly f=y3+x2+xy+2xz+yz+z2+1; 312 211 // the Newton polytope of f is 313 list np=newtonPolytope P(f);212 list np=newtonPolytope(f); 314 213 // the vertices of the Newton polytope are: 315 214 np[1]; … … 317 216 np[2]; 318 217 // np[3] contains information how the vertices are connected to each other, 319 // e.g. the first vertex (number 0) is connected to the second, third and 218 // e.g. the first vertex (number 0) is connected to the second, third and 320 219 // fourth vertex 321 220 np[3][1]; … … 323 222 f=x2y3; 324 223 // the Newton polytope of f is 325 np=newtonPolytope P(f);224 np=newtonPolytope(f); 326 225 // the vertices of the Newton polytope are: 327 226 np[1]; 328 227 // its dimension is 329 np[2]; 330 // the Newton polytope is contained in the affine space given 228 np[2]; 229 // the Newton polytope is contained in the affine space given 331 230 // by the equations 332 np[4]*M;231 intmat(np[4])*M; 333 232 } 334 233 … … 337 236 proc newtonPolytopeLP (poly f) 338 237 "USAGE: newtonPolytopeLP(f); f poly 339 RETURN: list, the exponent vectors of the monomials occuring in f, 238 RETURN: list, the exponent vectors of the monomials occuring in f, 340 239 i.e. the lattice points of the Newton polytope of f 341 240 EXAMPLE: example normalFan; shows an example" … … 365 264 proc normalFan (intmat vertices,intmat affinehull,list graph,int er,list #) 366 265 "USAGE: normalFan (vert,aff,graph,rays,[,#]); vert,aff intmat, graph list, rays int, # string 367 ASSUME:  vert is an integer matrix whose rows are the coordinate of 368 the vertices of a convex lattice polytope; 266 ASSUME:  vert is an integer matrix whose rows are the coordinate of 267 the vertices of a convex lattice polytope; 369 268 @*  aff describes the affine hull of this polytope, i.e. 370 the smallest affine space containing it, in the following sense: 371 denote by n the number of columns of vert, then multiply aff by 372 (1,x(1),...,x(n)) and set the resulting terms to zero in order to 269 the smallest affine space containing it, in the following sense: 270 denote by n the number of columns of vert, then multiply aff by 271 (1,x(1),...,x(n)) and set the resulting terms to zero in order to 373 272 get the equations for the affine hull; 374 @*  the ith entry of graph is an integer vector describing to which 375 vertices the ith vertex is connected, i.e. a k as entry means that 273 @*  the ith entry of graph is an integer vector describing to which 274 vertices the ith vertex is connected, i.e. a k as entry means that 376 275 the vertex vert[i] is connected to vert[k]; 377 @*  the integer rays is either one (if the extreme rays should be 276 @*  the integer rays is either one (if the extreme rays should be 378 277 computed) or zero (otherwise) 379 RETURN: list, the ith entry of L[1] contains information about the cone in the 380 normal fan dual to the ith vertex of the polytope 381 @* L[1][i][1] = integer matrix representing the inequalities which 278 RETURN: list, the ith entry of L[1] contains information about the cone in the 279 normal fan dual to the ith vertex of the polytope 280 @* L[1][i][1] = integer matrix representing the inequalities which 382 281 describe the cone dual to the ith vertex 383 @* L[1][i][2] = a list which contains the inequalities represented 384 by L[i][1] as a list of strings, where we use the 282 @* L[1][i][2] = a list which contains the inequalities represented 283 by L[i][1] as a list of strings, where we use the 385 284 variables x(1),...,x(n) 386 285 @* L[1][i][3] = only present if 'er' is set to 1; in that case it is 387 an interger matrix whose rows are the extreme rays 286 an interger matrix whose rows are the extreme rays 388 287 of the cone 389 @* L[2] = is an integer matrix whose rows span the linearity space 390 of the fan, i.e. the linear space which is contained in 288 @* L[2] = is an integer matrix whose rows span the linearity space 289 of the fan, i.e. the linear space which is contained in 391 290 each cone 392 291 NOTE:  the procedure calls for its computation polymake by Ewgenij Gawrilow, 393 TU Berlin and Michael Joswig, so it only works if polymake is 292 TU Berlin and Michael Joswig, so it only works if polymake is 394 293 installed; 395 294 see http://www.math.tuberlin.de/polymake/ 396 @*  in the optional argument # it is possible to hand over other names 295 @*  in the optional argument # it is possible to hand over other names 397 296 for the variables to be used  be careful, the format must be correct 398 which is not tested, e.g. if you want the variable names to be399 u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11'297 and that is not tested, e.g. if you want the variable names to be 298 u00,u10,u01,u11 then you must hand over the string u11,u10,u01,u11 400 299 EXAMPLE: example normalFan; shows an example" 401 300 { 402 301 list ineq; // stores the inequalities of the cones 403 302 int i,j,k; 404 // we work over the following ring 303 // we work over the following ring 405 304 execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;"); 406 305 string greatersign=">"; … … 427 326 for (i=1;i<=nrows(vertices);i++) 428 327 { 429 // first we produce for each vertex in the polytope 328 // first we produce for each vertex in the polytope 430 329 // the inequalities describing the dual cone in the normal fan 431 list pp; // contain strings representing the inequalities 330 list pp; // contain strings representing the inequalities 432 331 // describing the normal cone 433 intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 332 intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities 434 333 // as rows 435 // consider all the vertices to which the ith vertex in the 334 // consider all the vertices to which the ith vertex in the 436 335 // polytope is connected by an edge 437 336 for (j=1;j<=size(graph[i]);j++) 438 337 { 439 338 // produce the vector ie_j pointing from the jth vertex to the ith vertex; 440 // this will be the jth inequality for the cone in the normal fan dual to 339 // this will be the jth inequality for the cone in the normal fan dual to 441 340 // the ith vertex 442 341 ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]vertices[graph[i][j],1..ncols(vertices)]; … … 445 344 p=(VAR*EXP)[1,1]; 446 345 pl,pr=0,0; 447 // separate the terms with positive coefficients in p from 346 // separate the terms with positive coefficients in p from 448 347 // those with negative coefficients 449 348 for (k=1;k<=size(p);k++) … … 458 357 } 459 358 } 460 // build the string which represents the jth inequality 359 // build the string which represents the jth inequality 461 360 // for the cone dual to the ith vertex 462 // as polynomial inequality of type string, and store this 361 // as polynomial inequality of type string, and store this 463 362 // in the list pp as jth entry 464 363 pp[j]=string(pl)+" "+greatersign+" "+string(pr); … … 469 368 } 470 369 // remove the first column of affine hull to compute the linearity space 471 intmat linearity=intmatcoldelete(affinehull,1); 370 intmat linearity[1][ncols(vertices)]; 371 if (nrows(affinehull)>0) 372 { 373 linearity=intmatcoldelete(affinehull,1); 374 } 472 375 ////////////////////////////////////////////////////////////////// 473 376 // Compute next the extreme rays of the cones … … 476 379 { 477 380 list extremerays; // keeps the result 478 string polymake; // keeps polymake output 479 // the header for ineq.polymake 480 string head="_application polytope 481 _version 2.2 482 _type RationalPolytope 483 484 INEQUALITIES 485 "; 486 // the tail for both polymake files 487 string tail=" 488 EQUATIONS 489 "; 490 tail=tail+intmatToPolymake(linearity,"rays"); 491 string ungleichungen; // keeps the inequalities for the polymake code 381 cone kegel; 382 intmat linearspan=intmatAddFirstColumn(linearity,"rays"); 492 383 intmat M; // the matrix keeping the inequalities 493 // create the file ineq.output494 write(":w /tmp/ineq.output","");495 int dimension; // keeps the dimension of the intersection the496 // bad cones with the u11tobeseencone497 384 for (i=1;i<=size(ineq);i++) 498 385 { 499 i,". Cone of ",nrows(vertices); // indicate how many 500 // vertices have been dealt with 501 ungleichungen=intmatToPolymake(ineq[i][1],"rays"); 502 // write the inequalities to ineq.polymake and call polymake 503 write(":w /tmp/ineq.polymake",head+ungleichungen+tail); 504 ungleichungen=""; // clear ungleichungen 505 system("sh","cd /tmp; /bin/rm ineq.output; polymake ineq.polymake VERTICES > ineq.output"); 506 // read the result of polymake 507 polymake=read("/tmp/ineq.output"); 508 intmat VERT=polymakeToIntmat(polymake,"affine"); 509 extremerays[i]=VERT; 510 kill VERT; 386 kegel=coneViaInequalities(intmatAddFirstColumn(ineq[i][1],"rays"),linearspan); 387 extremerays[i]=intmatcoldelete(rays(kegel),1); 511 388 } 512 389 for (i=1;i<=size(ineq);i++) … … 515 392 } 516 393 } 517 // delete the tmpfiles, if polymakekeeptmpfiles is not set518 if (defined(polymakekeeptmpfiles)==0)519 {520 system("sh","/bin/rm /tmp/ineq.polymake");521 system("sh","/bin/rm /tmp/ineq.output");522 }523 394 // get the linearity space 524 return(list(ineq,linearity)); 395 return(list(ineq,linearity)); 525 396 } 526 397 example … … 532 403 poly f=y3+x2+xy+2xz+yz+z2+1; 533 404 // the Newton polytope of f is 534 list np=newtonPolytope P(f);405 list np=newtonPolytope(f); 535 406 // the Groebner fan of f, i.e. the normal fan of the Newton polytope 536 407 list gf=normalFan(np[1],np[4],np[3],1,"x,y,z"); … … 549 420 ///////////////////////////////////////////////////////////////////////////// 550 421 551 proc groebnerFan (poly f ,list #)552 "USAGE: groebnerFan(f [,#]); f poly, # string553 RETURN: list, the ith entry of L[1] contains information about the ith cone 554 in the Groebner fan dual to the ith vertex in the Newton 422 proc groebnerFan (poly f) 423 "USAGE: groebnerFan(f); f poly 424 RETURN: list, the ith entry of L[1] contains information about the ith cone 425 in the Groebner fan dual to the ith vertex in the Newton 555 426 polytope of the f 556 @* L[1][i][1] = integer matrix representing the inequalities 557 which describe the cone 558 @* L[1][i][2] = a list which contains the inequalities represented 427 @* L[1][i][1] = integer matrix representing the inequalities 428 which describe the cone 429 @* L[1][i][2] = a list which contains the inequalities represented 559 430 by L[1][i][1] as a list of strings 560 @* L[1][i][3] = an interger matrix whose rows are the extreme rays 431 @* L[1][i][3] = an interger matrix whose rows are the extreme rays 561 432 of the cone 562 @* L[2] = is an integer matrix whose rows span the linearity space 563 of the fan, i.e. the linear space which is contained 564 in each cone 565 @* L[3] = the Newton polytope of f in the format of the procedure 433 @* L[2] = is an integer matrix whose rows span the linearity space 434 of the fan, i.e. the linear space which is contained 435 in each cone 436 @* L[3] = the Newton polytope of f in the format of the procedure 566 437 newtonPolytope 567 @* L[4] = integer matrix where each row represents the expone t438 @* L[4] = integer matrix where each row represents the exponent 568 439 vector of one monomial occuring in the input polynomial 569 440 NOTE:  if you have already computed the Newton polytope of f then you might want 570 to use the procedure normalFan instead in order to avoid doing costly 441 to use the procedure normalFan instead in order to avoid doing costly 571 442 computation twice 572 443 @*  the procedure calls for its computation polymake by Ewgenij Gawrilow, 573 444 TU Berlin and Michael Joswig, so it only works if polymake is installed; 574 445 see http://www.math.tuberlin.de/polymake/ 575 @*  the procedure creates the file /tmp/newtonPolytope.polymake which576 contains the Newton polytope of f in polymake format and which can577 be used for further computations with polymake578 @*  it is possible to give as an optional second argument as string which579 then will be used instead of 'newtonPolytope' in the name of the580 polymake output file581 446 EXAMPLE: example groebnerFan; shows an example" 582 447 { 583 448 int i,j; 584 // compute the list of exponent vectors of the polynomial, which are 449 // compute the list of exponent vectors of the polynomial, which are 585 450 // the lattice points whose convex hull is the Newton polytope of f 586 451 intmat exponents[size(f)][nvars(basering)]; … … 591 456 f=flead(f); 592 457 } 593 if (size(#)==0)594 {595 #[1]="newtonPolytope";596 }597 458 // call polymakePolytope with exponents 598 list newtonp=polymakePolytope(exponents ,"newtonPolytope");459 list newtonp=polymakePolytope(exponents); 599 460 // get the variables as string 600 461 string variablen; … … 642 503 643 504 644 /////////////////////////////////////////////////////////////////////////////645 646 proc intmatToPolymake (intmat M,string art)647 "USAGE: intmatToPolymake(M,art); M intmat, art string648 ASSUME:  M is an integer matrix which should be transformed into polymake649 format;650 @*  art is one of the following strings:651 @* + 'rays' : indicating that a first column of 0's should be added652 @* + 'points' : indicating that a first column of 1's should be added653 RETURN: string, the matrix is transformed in a string and a first column has654 been added655 EXAMPLE: example intmatToPolymake; shows an example"656 {657 if (art=="rays")658 {659 string anf="0 ";660 }661 else662 {663 string anf="1 ";664 }665 string sp;666 int i,j;667 // create the lattice point list for polymake668 for (i=1;i<=nrows(M);i++)669 {670 sp=sp+anf;671 for (j=1;j<=ncols(M);j++)672 {673 sp=sp+string(M[i,j])+" ";674 if (j==ncols(M))675 {676 sp=sp+"677 ";678 }679 }680 }681 return(sp);682 }683 example684 {685 "EXAMPLE:";686 echo=2;687 intmat M[3][4]=1,2,3,4,5,6,7,8,9,10,11,12;688 intmatToPolymake(M,"rays");689 intmatToPolymake(M,"points");690 }691 692 /////////////////////////////////////////////////////////////////////////////693 694 proc polymakeToIntmat (string pm,string art)695 "USAGE: polymakeToIntmat(pm,art); pm, art string696 ASSUME: pm is the result of calling polymake with one 'argument' like697 VERTICES, AFFINE_HULL, etc., so that the first row of the string is698 the name of the corresponding 'argument' and the further rows contain699 the result which consists of vectors either over the integers700 or over the rationals701 RETURN: intmat, the rows of the matrix are basically the vectors in pm, starting702 from the second row, where each row has been multiplied with the703 lowest common multiple of the denominators of its entries as if704 it is an integer matrix; moreover, if art=='affine', then705 the first column is omitted since we only want affine706 coordinates707 EXAMPLE: example polymakeToIntmat; shows an example"708 {709 // we need a line break710 string zeilenumbruch="711 ";712 // remove the 'argment' name, i.e. the first row of pm713 while (pm[1]!=zeilenumbruch)714 {715 pm=stringdelete(pm,1);716 }717 pm=stringdelete(pm,1);718 // find out how many entries each vector has, namely one more719 // than 'spaces' in a row720 int i=1;721 int s=1;722 int z=1;723 while (pm[i]!=zeilenumbruch)724 {725 if (pm[i]==" ")726 {727 s++;728 }729 i++;730 }731 // if we want to have affine coordinates732 if (art=="affine")733 {734 s; // then there is one column less735 // and the entry of the first column (in the first row) has to be removed736 while (pm[1]!=" ")737 {738 pm=stringdelete(pm,1);739 }740 pm=stringdelete(pm,1);741 }742 // we add two line breaks at the end in order to have this as743 // a stopping criterion744 pm=pm+zeilenumbruch+zeilenumbruch;745 // we now have to work through each row746 for (i=1;i<=size(pm);i++)747 {748 // if there are two consecutive line breaks we are done749 if ((pm[i]==zeilenumbruch) and (pm[i+1]==zeilenumbruch))750 {751 i=size(pm)+1;752 }753 else754 {755 // a line break has to be replaced by a comma756 if (pm[i]==zeilenumbruch)757 {758 z++;759 pm[i]=",";760 // if we want to have affine coordinates,761 // then we have to delete the first entry in each row762 if (art=="affine")763 {764 while (pm[i+1]!=" ")765 {766 pm=stringdelete(pm,i+1);767 }768 pm=stringdelete(pm,i+1);769 }770 }771 // a space has to be replaced by a comma772 if (pm[i]==" ")773 {774 pm[i]=",";775 }776 }777 }778 // if we have introduced superflous commata at the end, they should be removed779 while (pm[size(pm)]==",")780 {781 pm=stringdelete(pm,size(pm));782 }783 // since the matrix could be over the rationals,784 // we need a ring with rational coefficients785 ring zwischering=0,x,lp;786 // create the matrix with the elements of pm as entries787 execute("matrix mm["+string(z)+"]["+string(s)+"]="+pm+";");788 // transform this into an integer matrix789 matrix M[1][ncols(mm)]; // takes a row of mm790 int cm; // takes a lowest common multiple791 // multiply each row by an integer such that its entries are integers792 for (int j=1;j<=nrows(mm);j++)793 {794 M=mm[j,1..ncols(mm)];795 cm=commondenominator(M);796 for (i=1;i<=ncols(mm);i++)797 {798 mm[j,i]=cm*mm[j,i];799 }800 }801 // transform the matrix mm into an integer matrix802 execute("intmat im["+string(z)+"]["+string(s)+"]="+string(mm)+";");803 return(im);804 }805 example806 {807 "EXAMPLE:";808 echo=2;809 // this is the usual output of some polymake computation810 string pm="VERTICES811 0 1 3 5/3 1/3 1 23/3 1/3 5/3 1/3 1812 0 1 3 23/3 5/3 1 5/3 1/3 1/3 1/3 1813 0 1 1 1/3 1/3 1 5/3 1/3 23/3 5/3 3814 0 1 1 5/3 23/3 3 1/3 5/3 1/3 1/3 1815 0 1 1 1/3 5/3 3 1/3 23/3 1/3 5/3 1816 0 1 1 1/3 1/3 1 1/3 5/3 5/3 23/3 3817 0 1 1 1 3 5 1 3 1 1 1818 0 1 1 1 1 1 1 1 3 3 5819 0 1 5 3 1 1 3 1 1 1 1820 821 ";822 intmat PM=polymakeToIntmat(pm,"affine");823 // note that the first column has been removed, since we asked for824 // affine coordinates, and the denominators have been cleared825 print(PM);826 }827 828 505 /////////////////////////////////////////////////////////////////////////////// 829 506 /// PROCEDURES USING TOPCOM 830 507 /////////////////////////////////////////////////////////////////////////////// 831 508 832 proc triangulations (list polygon )833 "USAGE: triangulations(polygon ); list polygon834 ASSUME: polygon is a list of integer vectors of the same size representing 835 the affine coordinates of the lattice points 509 proc triangulations (list polygon,list #) 510 "USAGE: triangulations(polygon[,#]); list polygon, list # 511 ASSUME: polygon is a list of integer vectors of the same size representing 512 the affine coordinates of the lattice points 836 513 PURPOSE: the procedure considers the marked polytope given as the convex hull of 837 514 the lattice points and with these lattice points as markings; it then 838 computes all possible triangulations of this marked polytope 515 computes all possible triangulations of this marked polytope 839 516 RETURN: list, each entry corresponds to one triangulation and the ith entry is 840 517 itself a list of integer vectors of size three, where each integer … … 843 520 NOTE: the procedure calls for its computations the program points2triangs 844 521 from the program topcom by Joerg Rambau, Universitaet Bayreuth; it 845 therefore is necessary that this program is installed in order to use 522 therefore is necessary that this program is installed in order to use 846 523 this procedure; see 847 524 @* http://www.unibayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM 848 @*  the procedure creates the files /tmp/triangulationsinput and 525 @*  if you only want to have the regular triangulations the procedure should 526 be called with the string 'regular' as optional argument 527 @*  the procedure creates the files /tmp/triangulationsinput and 849 528 /tmp/triangulationsoutput; 850 the former is used as input for points2triangs and the latter is its 851 output containing the triangulations of corresponding to points in the 852 format of points2triangs; if you wish to use this for further 853 computations with topcom, you have to use the procedure854 polymakeKeepTmpFiles in before855 @*  note that an integer i in an integer vector representing a triangle 856 refers to the ith lattice point, i.e. polygon[i]; this convention is 857 different from TOPCOM's convention, where i would refer to the i1st 529 the former is used as input for points2triangs and the latter is its 530 output containing the triangulations of corresponding to points in the 531 format of points2triangs; if you wish to use this for further 532 computations with topcom, you have to call the procedure with the 533 string 'keepfiles' as optional argument 534 @*  note that an integer i in an integer vector representing a triangle 535 refers to the ith lattice point, i.e. polygon[i]; this convention is 536 different from TOPCOM's convention, where i would refer to the i1st 858 537 lattice point 859 538 EXAMPLE: example triangulations; shows an example" 860 539 { 861 540 int i,j; 862 // prepare the input for points2triangs by writing the input polygon in the 541 // check for optional arguments 542 int regular,keepfiles; 543 if (size(#)>0) 544 { 545 for (i=1;i<=size(#);i++) 546 { 547 if (typeof(#[i])=="string") 548 { 549 if (#[i]=="keepfiles") 550 { 551 keepfiles=1; 552 } 553 if (#[i]=="regular") 554 { 555 regular=1; 556 } 557 } 558 } 559 } 560 // prepare the input for points2triangs by writing the input polygon in the 863 561 // necessary format 864 562 string spi="["; … … 875 573 write(":w /tmp/triangulationsinput",spi); 876 574 // call points2triangs 877 system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput"); 575 if (regular==1) // compute only regular triangulations 576 { 577 system("sh","cd /tmp; points2triangs regular < triangulationsinput > triangulationsoutput"); 578 } 579 else // compute all triangulations 580 { 581 system("sh","cd /tmp; points2triangs < triangulationsinput > triangulationsoutput"); 582 } 878 583 string p2t=read("/tmp/triangulationsoutput"); // takes result of points2triangs 879 // delete the tmpfiles, if polymakekeeptmpfiles is not set880 if ( defined(polymakekeeptmpfiles)==0)584 // delete the tmpfiles, if no second argument is given 585 if (keepfiles==0) 881 586 { 882 587 system("sh","cd /tmp; rm f triangulationsinput; rm f triangulationsoutput"); 883 588 } 884 // preprocessing of p2t if points2triangs is version >= 0.15 589 // preprocessing of p2t if points2triangs is version >= 0.15 885 590 // brings p2t to the format of version 0.14 886 591 string np2t; // takes the triangulations in Singular format … … 904 609 } 905 610 else 906 { 611 { 907 612 np2t=np2t+p2t[i]; 908 613 } … … 916 621 { 917 622 if (np2t[size(np2t)]!=";") 918 { 623 { 919 624 np2t=np2t+p2t[size(p2t)1]+p2t[size(p2t)]; 920 625 } … … 938 643 np2t=np2t+"))"; 939 644 i++; 940 } 645 } 941 646 else 942 647 { … … 953 658 else 954 659 { 955 np2t=np2t+p2t[i]; 660 if (p2t[i]=="[") 661 { 662 // in Topcom version 17.4 (and maybe also in earlier versions) the list 663 // of triangulations is indexed starting with index 0, in Singular 664 // we have to start with index 1 665 np2t=np2t+p2t[i]+"1+"; 666 } 667 else 668 { 669 np2t=np2t+p2t[i]; 670 } 956 671 } 957 672 } … … 962 677 list T; 963 678 execute(np2t); 679 // depending on the version of Topcom, the list T has or has not an entry T[1] 680 // if it has none, the entry should be removed 681 while (typeof(T[1])=="none") 682 { 683 T=delete(T,1); 684 } 964 685 // raise each index by one 965 686 for (i=1;i<=size(T);i++) … … 976 697 "EXAMPLE:"; 977 698 echo=2; 978 // the lattice points of the unit square in the plane 699 // the lattice points of the unit square in the plane 979 700 list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); 980 701 // the triangulations of this lattice point configuration are computed … … 987 708 proc secondaryPolytope (list polygon,list #) 988 709 "USAGE: secondaryPolytope(polygon[,#]); list polygon, list # 989 ASSUME:  polygon is a list of integer vectors of the same size representing 710 ASSUME:  polygon is a list of integer vectors of the same size representing 990 711 the affine coordinates of lattice points 991 @*  if the triangulations of the corresponding polygon have already been 712 @*  if the triangulations of the corresponding polygon have already been 992 713 computed with the procedure triangulations then these can be given as 993 714 a second (optional) argument in order to avoid doing this computation … … 995 716 PURPOSE: the procedure considers the marked polytope given as the convex hull of 996 717 the lattice points and with these lattice points as markings; it then 997 computes the lattice points of the secondary polytope given by this 718 computes the lattice points of the secondary polytope given by this 998 719 marked polytope which correspond to the triangulations computed by 999 720 the procedure triangulations 1000 721 RETURN: list, say L, such that: 1001 722 @* L[1] = intmat, each row gives the affine coordinates of a lattice 1002 point in the secondary polytope given by the marked polytope1003 corresponding to polygon723 point in the secondary polytope given by the marked 724 polytope corresponding to polygon 1004 725 @* L[2] = the list of corresponding triangulations 1005 NOTE: if the triangluations are not handed over as optional argument the 726 NOTE: if the triangluations are not handed over as optional argument the 1006 727 procedure calls for its computation of these triangulations the program 1007 points2triangs from the program topcom by Joerg Rambau, Universitaet 1008 Bayreuth; it therefore is necessary that this program is installed in 728 points2triangs from the program topcom by Joerg Rambau, Universitaet 729 Bayreuth; it therefore is necessary that this program is installed in 1009 730 order to use this procedure; see 1010 731 @* http://www.unibayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM … … 1022 743 int i,j,k,l; 1023 744 intmat N[2][2]; // is used to compute areas of triangles 1024 intvec vertex; // stores a point in the secondary polytope as 745 intvec vertex; // stores a point in the secondary polytope as 1025 746 // intermediate result 1026 747 int eintrag; 1027 748 int halt; 1028 intmat secpoly[size(triangs)][size(polygon)]; // stores all lattice points 749 intmat secpoly[size(triangs)][size(polygon)]; // stores all lattice points 1029 750 // of the secondary polytope 1030 // consider each triangulation and compute the corresponding point 751 // consider each triangulation and compute the corresponding point 1031 752 // in the secondary polytope 1032 753 for (i=1;i<=size(triangs);i++) 1033 754 { 1034 // for each triangulation we have to compute the coordinates 755 // for each triangulation we have to compute the coordinates 1035 756 // corresponding to each marked point 1036 757 for (j=1;j<=size(polygon);j++) 1037 758 { 1038 759 eintrag=0; 1039 // for each marked point we have to consider all triangles in the 760 // for each marked point we have to consider all triangles in the 1040 761 // triangulation which involve this particular point 1041 762 for (k=1;k<=size(triangs[i]);k++) … … 1059 780 secpoly[i,1..size(polygon)]=vertex; 1060 781 } 1061 return(list(secpoly,triangs)); 782 return(list(secpoly,triangs)); 1062 783 } 1063 784 example … … 1081 802 proc secondaryFan (list polygon,list #) 1082 803 "USAGE: secondaryFan(polygon[,#]); list polygon, list # 1083 ASSUME:  polygon is a list of integer vectors of the same size representing 804 ASSUME:  polygon is a list of integer vectors of the same size representing 1084 805 the affine coordinates of lattice points 1085 @*  if the triangulations of the corresponding polygon have already been 1086 computed with the procedure triangulations then these can be given 1087 as a second (optional) argument in order to avoid doing this 806 @*  if the triangulations of the corresponding polygon have already been 807 computed with the procedure triangulations then these can be given 808 as a second (optional) argument in order to avoid doing this 1088 809 computation again 1089 810 PURPOSE: the procedure considers the marked polytope given as the convex hull of 1090 811 the lattice points and with these lattice points as markings; it then 1091 computes the lattice points of the secondary polytope given by this 812 computes the lattice points of the secondary polytope given by this 1092 813 marked polytope which correspond to the triangulations computed by 1093 814 the procedure triangulations 1094 RETURN: list, the ith entry of L[1] contains information about the ith cone in 1095 the secondary fan of the polygon, i.e. the cone dual to the 815 RETURN: list, the ith entry of L[1] contains information about the ith cone in 816 the secondary fan of the polygon, i.e. the cone dual to the 1096 817 ith vertex of the secondary polytope 1097 @* L[1][i][1] = integer matrix representing the inequalities which 818 @* L[1][i][1] = integer matrix representing the inequalities which 1098 819 describe the cone dual to the ith vertex 1099 @* L[1][i][2] = a list which contains the inequalities represented 820 @* L[1][i][2] = a list which contains the inequalities represented 1100 821 by L[1][i][1] as a list of strings, where we use the 1101 822 variables x(1),...,x(n) 1102 823 @* L[1][i][3] = only present if 'er' is set to 1; in that case it is 1103 an interger matrix whose rows are the extreme rays 824 an interger matrix whose rows are the extreme rays 1104 825 of the cone 1105 @* L[2] = is an integer matrix whose rows span the linearity space 1106 of the fan, i.e. the linear space which is contained in 826 @* L[2] = is an integer matrix whose rows span the linearity space 827 of the fan, i.e. the linear space which is contained in 1107 828 each cone 1108 @* L[3] = the secondary polytope in the format of the procedure 829 @* L[3] = the secondary polytope in the format of the procedure 1109 830 polymakePolytope 1110 @* L[4] = the list of triangulations corresponding to the vertices 831 @* L[4] = the list of triangulations corresponding to the vertices 1111 832 of the secondary polytope 1112 833 NOTE: the procedure calls for its computation polymake by Ewgenij Gawrilow, 1113 834 TU Berlin and Michael Joswig, so it only works if polymake is installed; 1114 835 see http://www.math.tuberlin.de/polymake/ 1115 @*  in the optional argument # it is possible to hand over other names for 1116 the variables to be used  be careful, the format must be correct 1117 which is not tested, e.g. if you want the variable names to be836 @*  in the optional argument # it is possible to hand over other names for 837 the variables to be used  be careful, the format must be correct and 838 that is not tested, e.g. if you want the variable names to be 1118 839 u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11' 1119 @*  if the triangluations are not handed over as optional argument the 1120 procedure calls for its computation of these triangulations the program 1121 points2triangs from the program topcom by Joerg Rambau, Universitaet 1122 Bayreuth; it therefore is necessary that this program is installed in 840 @*  if the triangluations are not handed over as optional argument the 841 procedure calls for its computation of these triangulations the program 842 points2triangs from the program topcom by Joerg Rambau, Universitaet 843 Bayreuth; it therefore is necessary that this program is installed in 1123 844 order to use this procedure; see 1124 845 @* http://www.unibayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM … … 1132 853 { 1133 854 list triang=#[1]; 1134 } 855 } 1135 856 list sp=secondaryPolytope(polygon,triang); 1136 857 list spp=polymakePolytope(sp[1]); … … 1169 890 proc cycleLength (list boundary,intvec interior) 1170 891 "USAGE: cycleLength(boundary,interior); list boundary, intvec interior 1171 ASSUME: boundary is a list of integer vectors describing a cycle in some 1172 convex lattice polygon around the lattice point interior ordered 892 ASSUME: boundary is a list of integer vectors describing a cycle in some 893 convex lattice polygon around the lattice point interior ordered 1173 894 clock wise 1174 895 RETURN: string, the cycle length of the corresponding cycle in the dual … … 1177 898 { 1178 899 int j; 1179 // create a ring whose variables are indexed by the points in 900 // create a ring whose variables are indexed by the points in 1180 901 // boundary resp. by interior 1181 902 string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]); … … 1215 936 // interior is a lattice point in the interior of this lattice polygon 1216 937 intvec interior=1,1; 1217 // compute the general cycle length of a cycle of the corresponding cycle 938 // compute the general cycle length of a cycle of the corresponding cycle 1218 939 // in the dual tropical curve, note that (0,1) and (2,1) do not contribute 1219 940 cycleLength(boundary,interior); … … 1224 945 proc splitPolygon (list markings) 1225 946 "USAGE: splitPolygon (markings); markings list 1226 ASSUME: markings is a list of integer vectors representing lattice points in 1227 the plane which we consider as the marked points of the convex lattice 947 ASSUME: markings is a list of integer vectors representing lattice points in 948 the plane which we consider as the marked points of the convex lattice 1228 949 polytope spanned by them 1229 PURPOSE: split the marked points in the vertices, the points on the facets 950 PURPOSE: split the marked points in the vertices, the points on the facets 1230 951 which are not vertices, and the interior points 1231 952 RETURN: list, L consisting of three lists … … 1233 954 @* L[1][i][1] = intvec, the coordinates of the ith vertex 1234 955 @* L[1][i][2] = int, the position of L[1][i][1] in markings 1235 @* L[2][i] : represents the lattice points on the facet of the 1236 polygon with endpoints L[1][i] and L[1][i+1] 956 @* L[2][i] : represents the lattice points on the facet of the 957 polygon with endpoints L[1][i] and L[1][i+1] 1237 958 (i considered modulo size(L[1])) 1238 @* L[2][i][j][1] = intvec, the coordinates of the jth 959 @* L[2][i][j][1] = intvec, the coordinates of the jth 1239 960 lattice point on that facet 1240 @* L[2][i][j][2] = int, the position of L[2][i][j][1] 961 @* L[2][i][j][2] = int, the position of L[2][i][j][1] 1241 962 in markings 1242 @* L[3] : represents the interior lattice points of the polygon 963 @* L[3] : represents the interior lattice points of the polygon 1243 964 @* L[3][i][1] = intvec, coordinates of ith interior point 1244 965 @* L[3][i][2] = int, the position of L[3][i][1] in markings … … 1251 972 vert[1]=pb[2]; 1252 973 int i,j,k; // indices 1253 list boundary; // stores the points on the facets of the 974 list boundary; // stores the points on the facets of the 1254 975 // polygon which are not vertices 1255 // append to the boundary points as well as to the vertices 976 // append to the boundary points as well as to the vertices 1256 977 // the first vertex a second time 1257 978 pb[1]=pb[1]+list(pb[1][1]); … … 1278 999 // store the information on the boundary in vert[2] 1279 1000 vert[2]=boundary; 1280 // find the remaining points in the input which are not on 1001 // find the remaining points in the input which are not on 1281 1002 // the boundary by checking 1282 1003 // for each point in markings if it is contained in pb[1] … … 1295 1016 // store the interior points in vert[3] 1296 1017 vert[3]=interior; 1297 // add to each point in vert the index which it gets from 1018 // add to each point in vert the index which it gets from 1298 1019 // its position in the input markings; 1299 1020 // do so for ver[1] … … 1329 1050 } 1330 1051 vert[3][i]=list(vert[3][i],j); 1331 } 1052 } 1332 1053 return(vert); 1333 1054 } … … 1336 1057 "EXAMPLE:"; 1337 1058 echo=2; 1338 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1059 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1339 1060 // with all integer points as markings 1340 1061 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), … … 1356 1077 proc eta (list triang,list polygon) 1357 1078 "USAGE: eta(triang,polygon); triang, polygon list 1358 ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a 1359 list with three entries describing a convex lattice polygon in the 1079 ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a 1080 list with three entries describing a convex lattice polygon in the 1360 1081 following way: 1361 @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] 1362 is a lattice point which is a vertex of the lattice 1082 @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] 1083 is a lattice point which is a vertex of the lattice 1363 1084 polygon, and polygon[1][i][2] is an integer assigned to 1364 1085 this lattice point as identifying index 1365 @* polygon[2] : is a list of lists; for each vertex of the polygon, 1366 i.e. for each entry in polygon[1], it contains a list 1367 polygon[2][i], which contains the lattice points on the 1368 facet with endpoints polygon[1][i] and polygon[1][i+1] 1086 @* polygon[2] : is a list of lists; for each vertex of the polygon, 1087 i.e. for each entry in polygon[1], it contains a list 1088 polygon[2][i], which contains the lattice points on the 1089 facet with endpoints polygon[1][i] and polygon[1][i+1] 1369 1090  i considered mod size(polygon[1]); 1370 each such lattice point contributes an entry 1091 each such lattice point contributes an entry 1371 1092 polygon[2][i][j][1] which is an integer 1372 vector giving the coordinate of the lattice point and an 1093 vector giving the coordinate of the lattice point and an 1373 1094 entry polygon[2][i][j][2] which is the identifying index 1374 @* polygon[3] : is a list of lists, where each entry corresponds to a 1375 lattice point in the interior of the polygon, with 1095 @* polygon[3] : is a list of lists, where each entry corresponds to a 1096 lattice point in the interior of the polygon, with 1376 1097 polygon[3][j][1] being the coordinates of the point 1377 1098 and polygon[3][j][2] being the identifying index; 1378 @* triang is a list of integer vectors all of size three describing a 1379 triangulation of the polygon described by polygon; if an entry of 1380 triang is the vector (i,j,k) then the triangle is built fromthe vertices1099 @* triang is a list of integer vectors all of size three describing a 1100 triangulation of the polygon described by polygon; if an entry of 1101 triang is the vector (i,j,k) then the triangle is built by the vertices 1381 1102 with indices i, j and k 1382 RETURN: intvec, the integer vector eta describing that vertex of the Newton 1383 polytope discriminant of the polygone whose dual cone in the 1384 Groebner fan contains the cone of the secondary fan of the 1103 RETURN: intvec, the integer vector eta describing that vertex of the Newton 1104 polytope discriminant of the polygone whose dual cone in the 1105 Groebner fan contains the cone of the secondary fan of the 1385 1106 polygon corresponding to the given triangulation 1386 NOTE: for a better description of eta see Gelfand, Kapranov, 1107 NOTE: for a better description of eta see Gelfand, Kapranov, 1387 1108 Zelevinski: Discriminants, Resultants and multidimensional Determinants. 1388 1109 Chapter 10. … … 1390 1111 { 1391 1112 int i,j,k,l,m,n; // index variables 1392 list ordpolygon; // stores the lattice points in the order 1113 list ordpolygon; // stores the lattice points in the order 1393 1114 // used in the triangulation 1394 1115 list triangarea; // stores the areas of the triangulations … … 1416 1137 for (i=1;i<=size(triang);i++) 1417 1138 { 1418 // Note that the ith lattice point in orderedpolygon has the 1139 // Note that the ith lattice point in orderedpolygon has the 1419 1140 // number i1 in the triangulation! 1420 1141 N=ordpolygon[triang[i][1]]ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]ordpolygon[triang[i][3]]; … … 1422 1143 } 1423 1144 intvec ETA; // stores the eta_ij 1424 int etaij; // stores the part of eta_ij during computations 1145 int etaij; // stores the part of eta_ij during computations 1425 1146 // which comes from triangle areas 1426 int seitenlaenge; // stores the part of eta_ij during computations 1147 int seitenlaenge; // stores the part of eta_ij during computations 1427 1148 // which comes from boundary facets 1428 1149 list seiten; // stores the lattice points on facets of the polygon 1429 1150 intvec v; // used to compute a facet length 1430 // 3) store first in seiten[i] all lattice points on the facet 1151 // 3) store first in seiten[i] all lattice points on the facet 1431 1152 // connecting the ith vertex, 1432 // i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], 1153 // i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], 1433 1154 // where we replace i+1 1434 1155 // 1 if i=size(polygon[1]); 1435 // then append the last entry of seiten once more at the very 1156 // then append the last entry of seiten once more at the very 1436 1157 // beginning of seiten, so 1437 1158 // that the index is shifted by one … … 1459 1180 if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3])) 1460 1181 { 1461 // ... if so, add the area of the triangle to etaij 1182 // ... if so, add the area of the triangle to etaij 1462 1183 etaij=etaij+triangarea[k]; 1463 // then check if that triangle has a facet which is contained 1464 // in one of the 1184 // then check if that triangle has a facet which is contained 1185 // in one of the 1465 1186 // two facets of the polygon which are adjecent to the given vertex ... 1466 1187 // these two facets are seiten[j] and seiten[j+1] … … 1476 1197 if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2])) 1477 1198 { 1478 // if so, then compute the vector pointing from this 1199 // if so, then compute the vector pointing from this 1479 1200 // lattice point to the vertex 1480 1201 v=polygon[1][j][1]seiten[n][l][1]; 1481 // and the lattice length of this vector has to be 1202 // and the lattice length of this vector has to be 1482 1203 // subtracted from etaij 1483 1204 etaij=etaijabs(gcd(v[1],v[2])); … … 1491 1212 ETA[polygon[1][j][2]]=etaij; 1492 1213 } 1493 // 5) compute the eta_ij for all lattice points on the facets 1214 // 5) compute the eta_ij for all lattice points on the facets 1494 1215 // of the polygon which are not vertices, these are the 1495 1216 // lattice points in polygon[2][1] to polygon[2][size(polygon[1])] … … 1497 1218 { 1498 1219 for (j=1;j<=size(polygon[2][i]);j++) 1499 { 1220 { 1500 1221 // initialise etaij 1501 1222 etaij=0; … … 1508 1229 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])) 1509 1230 { 1510 // ... if so, add the area of the triangle to etaij 1231 // ... if so, add the area of the triangle to etaij 1511 1232 etaij=etaij+triangarea[k]; 1512 // then check if that triangle has a facet which is contained in the 1233 // then check if that triangle has a facet which is contained in the 1513 1234 // facet of the polygon which contains the lattice point in question, 1514 1235 // this is the facet seiten[i+1]; … … 1518 1239 // ... and for each lattice point in the triangle ... 1519 1240 for (m=1;m<=size(triang[k]);m++) 1520 { 1241 { 1521 1242 // ... if they coincide and are not the vertex itself ... 1522 1243 if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2])) 1523 1244 { 1524 // if so, then compute the vector pointing from 1245 // if so, then compute the vector pointing from 1525 1246 // this lattice point to the vertex 1526 1247 v=polygon[2][i][j][1]seiten[i+1][l][1]; 1527 // and the lattice length of this vector contributes 1248 // and the lattice length of this vector contributes 1528 1249 // to seitenlaenge 1529 1250 seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2])); … … 1533 1254 } 1534 1255 } 1535 // if the lattice point was a vertex of any triangle 1256 // if the lattice point was a vertex of any triangle 1536 1257 // in the triangulation ... 1537 1258 if (etaij!=0) … … 1558 1279 if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3])) 1559 1280 { 1560 // ... if so, add the area of the triangle to etaij 1281 // ... if so, add the area of the triangle to etaij 1561 1282 etaij=etaij+triangarea[k]; 1562 1283 } … … 1571 1292 "EXAMPLE:"; 1572 1293 echo=2; 1573 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1294 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1574 1295 // with all integer points as markings 1575 1296 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), … … 1578 1299 // split the polygon in its vertices, its facets and its interior points 1579 1300 list sp=splitPolygon(polygon); 1580 // define a triangulation by connecting the only interior point 1301 // define a triangulation by connecting the only interior point 1581 1302 // with the vertices 1582 1303 list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10); … … 1584 1305 eta(triang,sp); 1585 1306 } 1586 1307 1587 1308 ///////////////////////////////////////////////////////////////////////////// 1588 1309 1589 1310 proc findOrientedBoundary (list polygon) 1590 1311 "USAGE: findOrientedBoundary(polygon); polygon list 1591 ASSUME: polygon is a list of integer vectors defining integer lattice points 1312 ASSUME: polygon is a list of integer vectors defining integer lattice points 1592 1313 in the plane 1593 1314 RETURN: list l with the following interpretation 1594 @* l[1] = list of integer vectors such that the polygonal path 1595 defined by these is the boundary of the convex hull of 1315 @* l[1] = list of integer vectors such that the polygonal path 1316 defined by these is the boundary of the convex hull of 1596 1317 the lattice points in polygon 1597 1318 @* l[2] = list, the redundant points in l[1] have been removed … … 1611 1332 } 1612 1333 // check is the polygon is only a line segment given by more than two points; 1613 // for this first compute sum of the absolute values of the determinants 1334 // for this first compute sum of the absolute values of the determinants 1614 1335 // of the matrices whose 1615 // rows are the vectors pointing from the first to the second point 1336 // rows are the vectors pointing from the first to the second point 1616 1337 // and from the 1617 // the first point to the ith point for i=3,...,size(polygon); 1338 // the first point to the ith point for i=3,...,size(polygon); 1618 1339 // if this sum is zero 1619 1340 // then the polygon is a line segment and we have to find its end points … … 1628 1349 intmat laenge[size(polygon)][size(polygon)]; 1629 1350 intvec mp; 1630 // for this collect first all vectors pointing from one lattice 1351 // for this collect first all vectors pointing from one lattice 1631 1352 // point to the next, 1632 1353 // compute their pairwise angles and their lengths 1633 1354 for (i=1;i<=size(polygon)1;i++) 1634 { 1355 { 1635 1356 for (j=i+1;j<=size(polygon);j++) 1636 1357 { … … 1656 1377 polygon=sortlistbyintvec(polygon,abstand); 1657 1378 return(list(polygon,endpoints)); 1658 } 1379 } 1659 1380 /////////////////////////////////////////////////////////////// 1660 1381 list orderedvertices; // stores the vertices in an ordered way 1661 list minimisedorderedvertices; // stores the vertices in an ordered way; 1382 list minimisedorderedvertices; // stores the vertices in an ordered way; 1662 1383 // redundant ones removed 1663 list comparevertices; // stores vertices which should be compared to 1384 list comparevertices; // stores vertices which should be compared to 1664 1385 // the testvertex 1665 1386 orderedvertices[1]=polygon[1]; // set the starting vertex 1666 1387 minimisedorderedvertices[1]=polygon[1]; // set the starting vertex 1667 1388 intvec testvertex=polygon[1]; //vertex to which the others have to be compared 1668 intvec startvertex=polygon[1]; // keep the starting vertex to test, 1389 intvec startvertex=polygon[1]; // keep the starting vertex to test, 1669 1390 // when the end is reached 1670 1391 int endtest; // is set to one, when the end is reached 1671 int startvertexfound;// is 1, once for some testvertex a candidate 1672 // for the next vertex has been found 1392 int startvertexfound;// is 1, once for some testvertex a candidate 1393 // for the next vertex has been found 1673 1394 polygon=delete(polygon,1); // delete the testvertex 1674 1395 intvec v,w; 1675 1396 int l=1; // counts the vertices 1676 // the basic idea is that a vertex can be 1397 // the basic idea is that a vertex can be 1677 1398 // the next one on the boundary if all other vertices 1678 // lie to the right of the vector v pointing 1399 // lie to the right of the vector v pointing 1679 1400 // from the testvertex to this one; this can be tested 1680 // by checking if the determinant of the 2x2matrix 1401 // by checking if the determinant of the 2x2matrix 1681 1402 // with first column v and second column the vector w, 1682 // pointing from the testvertex to the new vertex, 1403 // pointing from the testvertex to the new vertex, 1683 1404 // is nonpositive; if this is the case for all 1684 // new vertices, then the one in consideration is 1405 // new vertices, then the one in consideration is 1685 1406 // a possible choice for the next vertex on the boundary 1686 // and it is stored in naechste; we can then order 1407 // and it is stored in naechste; we can then order 1687 1408 // the candidates according to their distance from 1688 1409 // the testvertex; then they occur on the boundary in that order! … … 1696 1417 v=polygon[i]testvertex; // points from the testvertex to the ith vertex 1697 1418 comparevertices=delete(polygon,i); // we needn't compare v to itself 1698 // we should compare v to the startvertextestvertex; 1419 // we should compare v to the startvertextestvertex; 1699 1420 // in the first calling of the loop 1700 // this is irrelevant since the difference will be zero; 1421 // this is irrelevant since the difference will be zero; 1701 1422 // however, later on it will 1702 // be vital, since we delete the vertices 1423 // be vital, since we delete the vertices 1703 1424 // which we have already tested from the list 1704 // of all vertices, and when all vertices 1425 // of all vertices, and when all vertices 1705 1426 // on the boundary have been found we would 1706 // therefore find a vertex in the interior 1427 // therefore find a vertex in the interior 1707 1428 // as candidate; but always testing against 1708 1429 // the starting vertex, this cannot happen 1709 comparevertices[size(comparevertices)+1]=startvertex; 1430 comparevertices[size(comparevertices)+1]=startvertex; 1710 1431 for (j=1;(j<=size(comparevertices)) and (d<=0);j++) 1711 1432 { … … 1715 1436 d=det(D); 1716 1437 } 1717 if (d<=0) // if all determinants are nonpositive, 1438 if (d<=0) // if all determinants are nonpositive, 1718 1439 { // then the ith vertex is a candidate 1719 1440 naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex, … … 1723 1444 } 1724 1445 if (size(naechste)>0) // then a candidate for the next vertex has been found 1725 { 1446 { 1726 1447 startvertexfound=1; // at least once a candidate has been found 1727 naechste=sortlist(naechste,3); // we order the candidates according 1448 naechste=sortlist(naechste,3); // we order the candidates according 1728 1449 // to their distance from testvertex; 1729 for (j=1;j<=size(naechste);j++) // then we store them in this 1450 for (j=1;j<=size(naechste);j++) // then we store them in this 1730 1451 { // order in orderedvertices 1731 1452 l++; 1732 1453 orderedvertices[l]=naechste[j][1]; 1733 1454 } 1734 testvertex=naechste[size(naechste)][1]; // we store the last one as 1455 testvertex=naechste[size(naechste)][1]; // we store the last one as 1735 1456 // next testvertex; 1736 1457 // store the next corner of NSD 1737 minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; 1738 naechste=sortlist(naechste,2); // then we reorder the vertices 1458 minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; 1459 naechste=sortlist(naechste,2); // then we reorder the vertices 1739 1460 // according to their position 1740 1461 for (j=size(naechste);j>=1;j) // and we delete them from the vertices … … 1743 1464 } 1744 1465 } 1745 else // that means either that the vertex was inside the polygon, 1746 { // or that we have reached the last vertex on the boundary 1466 else // that means either that the vertex was inside the polygon, 1467 { // or that we have reached the last vertex on the boundary 1747 1468 // of the polytope 1748 if (startvertexfound==0) // the vertex was in the interior; 1469 if (startvertexfound==0) // the vertex was in the interior; 1749 1470 { // we delete it and start all over again 1750 orderedvertices[1]=polygon[1]; 1751 minimisedorderedvertices[1]=polygon[1]; 1471 orderedvertices[1]=polygon[1]; 1472 minimisedorderedvertices[1]=polygon[1]; 1752 1473 testvertex=polygon[1]; 1753 1474 startvertex=polygon[1]; 1754 1475 polygon=delete(polygon,1); 1755 1476 } 1756 else // we have reached the last vertex on the boundary of 1477 else // we have reached the last vertex on the boundary of 1757 1478 { // the polytope and can stop 1758 1479 endtest=1; … … 1761 1482 kill naechste; 1762 1483 } 1763 // test if the first vertex in minimisedorderedvertices 1484 // test if the first vertex in minimisedorderedvertices 1764 1485 // is on the same line with the second and 1765 // the last, i.e. if we started our search in the 1486 // the last, i.e. if we started our search in the 1766 1487 // middle of a face; if so, delete it 1767 1488 v=minimisedorderedvertices[2]minimisedorderedvertices[1]; … … 1772 1493 minimisedorderedvertices=delete(minimisedorderedvertices,1); 1773 1494 } 1774 // test if the first vertex in minimisedorderedvertices 1495 // test if the first vertex in minimisedorderedvertices 1775 1496 // is on the same line with the two 1776 // last ones, i.e. if we started our search at the end of a face; 1497 // last ones, i.e. if we started our search at the end of a face; 1777 1498 // if so, delete it 1778 1499 v=minimisedorderedvertices[size(minimisedorderedvertices)1]minimisedorderedvertices[1]; … … 1806 1527 proc cyclePoints (list triang,list points,int pt) 1807 1528 "USAGE: cyclePoints(triang,points,pt) triang,points list, pt int 1808 ASSUME:  points is a list of integer vectors describing the lattice 1529 ASSUME:  points is a list of integer vectors describing the lattice 1809 1530 points of a marked polygon; 1810 @*  triang is a list of integer vectors describing a triangulation 1811 of the marked polygon in the sense that an integer vector of 1812 the form (i,j,k) describes the triangle formed by polygon[i], 1531 @*  triang is a list of integer vectors describing a triangulation 1532 of the marked polygon in the sense that an integer vector of 1533 the form (i,j,k) describes the triangle formed by polygon[i], 1813 1534 polygon[j] and polygon[k]; 1814 @*  pt is an integer between 1 and size(points), singling out a 1535 @*  pt is an integer between 1 and size(points), singling out a 1815 1536 lattice point among the marked points 1816 PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice 1817 points in points which in the triangulation triang are connected 1818 to the point points[pt]; the procedure computes all marked points 1537 PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice 1538 points in points which in the triangulation triang are connected 1539 to the point points[pt]; the procedure computes all marked points 1819 1540 in points which lie on the boundary of that polygon, ordered 1820 1541 clockwise 1821 RETURN: list, of integer vectors which are the coordinates of the lattice 1822 points on the boundary of the above mentioned polygon P, if 1823 this polygon is not the empty set (that would be the case if 1824 points[pt] is not a vertex of any triangle in the 1542 RETURN: list, of integer vectors which are the coordinates of the lattice 1543 points on the boundary of the above mentioned polygon P, if 1544 this polygon is not the empty set (that would be the case if 1545 points[pt] is not a vertex of any triangle in the 1825 1546 triangulation); otherwise return the empty list 1826 1547 EXAMPLE: example cyclePoints; shows an example" 1827 1548 { 1828 1549 int i,j; // indices 1829 list v; // saves the indices of lattice points connected to the 1550 list v; // saves the indices of lattice points connected to the 1830 1551 // interior point in the triangulation 1831 1552 // save all points in triangulations containing pt in v … … 1863 1584 pts[i]=points[v[i]]; 1864 1585 } 1865 // consider the convex polytope spanned by the points in pts, 1586 // consider the convex polytope spanned by the points in pts, 1866 1587 // find the points on the 1867 1588 // boundary and order them clockwise … … 1872 1593 "EXAMPLE:"; 1873 1594 echo=2; 1874 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1595 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1875 1596 // with all integer points as markings 1876 1597 list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), 1877 1598 intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), 1878 1599 intvec(0,2),intvec(0,3); 1879 // define a triangulation 1600 // define a triangulation 1880 1601 list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10), 1881 1602 intvec(1,8,9),intvec(1,2,8); … … 1889 1610 "USAGE: latticeArea(polygon); polygon list 1890 1611 ASSUME: polygon is a list of integer vectors in the plane 1891 RETURN: int, the lattice area of the convex hull of the lattice points in 1612 RETURN: int, the lattice area of the convex hull of the lattice points in 1892 1613 polygon, i.e. twice the Euclidean area 1893 1614 EXAMPLE: example polygonlatticeArea; shows an example" … … 1918 1639 proc picksFormula (list polygon) 1919 1640 "USAGE: picksFormula(polygon); polygon list 1920 ASSUME: polygon is a list of integer vectors in the plane and consider their 1921 convex hull C 1922 RETURN: list, L of three integersthe 1641 ASSUME: polygon is a list of integer vectors in the plane and consider their 1642 convex hull C 1643 RETURN: list, L of three integersthe 1923 1644 @* L[1] : the lattice area of C, i.e. twice the Euclidean area 1924 1645 @* L[2] : the number of lattice points on the boundary of C … … 1945 1666 bdpts=bdpts+abs(gcd(edge[1],edge[2])); 1946 1667 } 1947 // Pick's formula says that the lattice area A, the number g of interior 1668 // Pick's formula says that the lattice area A, the number g of interior 1948 1669 // points and 1949 1670 // the number b of boundary points are connected by the formula: A=b+2g2 … … 1972 1693 proc ellipticNF (list polygon) 1973 1694 "USAGE: ellipticNF(polygon); polygon list 1974 ASSUME: polygon is a list of integer vectors in the plane such that their 1975 convex hull C has precisely one interior lattice point , i.e. C is the1695 ASSUME: polygon is a list of integer vectors in the plane such that their 1696 convex hull C has precisely one interior lattice point; i.e. C is the 1976 1697 Newton polygon of an elliptic curve 1977 PURPOSE: compute the normal form of the polygon with respect to the unimodular 1698 PURPOSE: compute the normal form of the polygon with respect to the unimodular 1978 1699 affine transformations T=A*x+v; there are sixteen different normal forms 1979 (see e.g. Bjorn Poonen, Fernando RodriguezVillegas: Lattice Polygons 1980 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 1700 (see e.g. Bjorn Poonen, Fernando RodriguezVillegas: Lattice Polygons 1701 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 1981 1702 238250.) 1982 1703 RETURN: list, L such that 1983 @* L[1] : list whose entries are the vertices of the normal form of 1704 @* L[1] : list whose entries are the vertices of the normal form of 1984 1705 the polygon 1985 1706 @* L[2] : the matrix A of the unimodular transformation 1986 1707 @* L[3] : the translation vector v of the unimodular transformation 1987 @* L[4] : list such that the ith entry is the image of polygon[i] 1708 @* L[4] : list such that the ith entry is the image of polygon[i] 1988 1709 under the unimodular transformation T 1989 1710 EXAMPLE: example ellipticNF; shows an example" … … 1991 1712 int i; // index 1992 1713 intvec edge; // stores the vector of an edge 1993 intvec boundary; // stores lattice lengths of the edges of the Newton cy lce1714 intvec boundary; // stores lattice lengths of the edges of the Newton cycle 1994 1715 // find the vertices of the Newton cycle and order it clockwise 1995 1716 list pg=findOrientedBoundary(polygon)[2]; … … 2017 1738 intvec trans; // stores the vector by which we have to translate the polygon 2018 1739 intmat A[2][2]; // stores the matrix by which we have to transform the polygon 2019 matrix M[3][3]; // stores the projective coordinates of the points 1740 matrix M[3][3]; // stores the projective coordinates of the points 2020 1741 // which are to be transformed 2021 matrix N[3][3]; // stores the projective coordinates of the points to 1742 matrix N[3][3]; // stores the projective coordinates of the points to 2022 1743 // which M is to be transformed 2023 intmat T[3][3]; // stores the unimodular affine transformation in 1744 intmat T[3][3]; // stores the unimodular affine transformation in 2024 1745 // projective form 2025 1746 // add the second point of pg once again at the end 2026 1747 pg=insert(pg,pg[2],size(pg)); 2027 // if there is only one edge which has the maximal number of lattice points, 1748 // if there is only one edge which has the maximal number of lattice points, 2028 1749 // then M should be: 2029 1750 M=pg[max],1,pg[max+1],1,pg[max+2],1; … … 2115 1836 M=pg[max],1,pg[max+1],1,pg[max+2],1; 2116 1837 // the orientation of the polygon matters 2117 A=pg[max1]pg[max],pg[max+1]pg[max]; 1838 A=pg[max1]pg[max],pg[max+1]pg[max]; 2118 1839 if (det(A)==4) 2119 1840 { … … 2164 1885 { 2165 1886 max++; 2166 } 1887 } 2167 1888 M=pg[max],1,pg[max+1],1,pg[max+2],1; 2168 1889 N=0,1,1,1,2,1,2,1,1; … … 2227 1948 // the vertices of the normal form are 2228 1949 nf[1]; 2229 // it has been transformed by the unimodular affine transformation A*x+v 1950 // it has been transformed by the unimodular affine transformation A*x+v 2230 1951 // with matrix A 2231 1952 nf[2]; … … 2244 1965 "USAGE: ellipticNFDB(n[,#]); n int, # list 2245 1966 ASSUME: n is an integer between 1 and 16 2246 PURPOSE: this is a database storing the 16 normal forms of planar polygons with 1967 PURPOSE: this is a database storing the 16 normal forms of planar polygons with 2247 1968 precisely one interior point up to unimodular affine transformations 2248 @* (see e.g. Bjorn Poonen, Fernando RodriguezVillegas: Lattice Polygons 1969 @* (see e.g. Bjorn Poonen, Fernando RodriguezVillegas: Lattice Polygons 2249 1970 and the number 12. Amer. Math. Monthly 107 (2000), no. 3, 2250 1971 238250.) 2251 1972 RETURN: list, L such that 2252 @* L[1] : list whose entries are the vertices of the nth normal form 2253 @* L[2] : list whose entries are all the lattice points of the 2254 nth normal form 2255 @* L[3] : only present if the optional parameter # is present, and 2256 then it is a polynomial in the variables (x,y) whose 1973 @* L[1] : list whose entries are the vertices of the nth normal form 1974 @* L[2] : list whose entries are all the lattice points of the 1975 nth normal form 1976 @* L[3] : only present if the optional parameter # is present, and 1977 then it is a polynomial in the variables (x,y) whose 2257 1978 Newton polygon is the nth normal form 2258 NOTE: the optional parameter is only allowed if the basering has the 1979 NOTE: the optional parameter is only allowed if the basering has the 2259 1980 variables x and y 2260 1981 EXAMPLE: example ellipticNFDB; shows an example" … … 2298 2019 // its lattice points are 2299 2020 nf[2]; 2300 }2301 2302 2303 /////////////////////////////////////////////////////////////////////////////////2304 /// AUXILARY PROCEDURES2305 /////////////////////////////////////////////////////////////////////////////////2306 2307 proc polymakeKeepTmpFiles (int i)2308 "USAGE: polymakeKeepTmpFiles(int i); i int2309 PURPOSE: some procedures create files in the directory /tmp which are used for2310 computations with polymake respectively topcom; these will be removed2311 when the corresponding procedure is left; however, it might be2312 desireable to keep them for further computations with either polymake or2313 topcom; this can be achieved by this procedure; call the procedure as:2314 @*  polymakeKeepTmpFiles(1);  then the files will be kept2315 @*  polymakeKeepTmpFiles(0);  then files will be removed in the future2316 RETURN: none"2317 {2318 if ((i==1) and (defined(polymakekeeptmpfiles)==0))2319 {2320 int polymakekeeptmpfiles;2321 export(polymakekeeptmpfiles);2322 }2323 if (i!=1)2324 {2325 if (defined(polymakekeeptmpfiles))2326 {2327 kill polymakekeeptmpfiles;2328 }2329 }2330 2021 } 2331 2022 … … 2352 2043 static proc scalarproduct (intvec w,intvec v) 2353 2044 "USAGE: scalarproduct(w,v); w,v intvec 2354 ASSUME: w and v are integer vectors of the same length 2045 ASSUME: w and v are integer vectors of the same length 2355 2046 RETURN: int, the scalarproduct of v and w 2356 2047 NOTE: the procedure is called by findOrientedBoundary" … … 2399 2090 { 2400 2091 int m=nrows(M); 2401 2092 2402 2093 } 2403 2094 else … … 2457 2148 { 2458 2149 return(""); 2459 2150 2460 2151 } 2461 2152 if (i==1) … … 2567 2258 k++; 2568 2259 } 2569 else 2260 else 2570 2261 { 2571 2262 stop=1; … … 2610 2301 k++; 2611 2302 } 2612 else 2303 else 2613 2304 { 2614 2305 stop=1; … … 2659 2350 static proc polygonToCoordinates (list points) 2660 2351 "USAGE: polygonToCoordinates(points); points list 2661 ASSUME: points is a list of integer vectors each of size two describing the 2662 marked points of a convex lattice polygon like the output of 2352 ASSUME: points is a list of integer vectors each of size two describing the 2353 marked points of a convex lattice polygon like the output of 2663 2354 polygonDB 2664 RETURN: list, the first entry is a string representing the coordinates 2355 RETURN: list, the first entry is a string representing the coordinates 2665 2356 corresponding to the latticpoints seperated by commata 2666 the second entry is a list where the ith entry is a string 2667 representing the coordinate of corresponding to the ith 2668 lattice point the third entry is the latex format of the 2357 the second entry is a list where the ith entry is a string 2358 representing the coordinate of corresponding to the ith 2359 lattice point the third entry is the latex format of the 2669 2360 first entry 2670 2361 NOTE: the procedure is called by fan" … … 2683 2374 return(list(coord,coords,latex)); 2684 2375 } 2376 2377 static proc intmatAddFirstColumn (intmat M,string art) 2378 "USAGE: intmatAddFirstColumn(M,art); M intmat, art string 2379 ASSUME:  M is an integer matrix where a first column of 0's or 1's should be added 2380 @*  art is one of the following strings: 2381 @* + 'rays' : indicating that a first column of 0's should be added 2382 @* + 'points' : indicating that a first column of 1's should be added 2383 RETURN: intmat, a first column has been added to the matrix" 2384 { 2385 intmat N[nrows(M)][ncols(M)+1]; 2386 int i,j; 2387 for (i=1;i<=nrows(M);i++) 2388 { 2389 if (art=="rays") 2390 { 2391 N[i,1]=0; 2392 } 2393 else 2394 { 2395 N[i,1]=1; 2396 } 2397 for (j=1;j<=ncols(M);j++) 2398 { 2399 N[i,j+1]=M[i,j]; 2400 } 2401 } 2402 return(N); 2403 } 2404 2405 2406
Note: See TracChangeset
for help on using the changeset viewer.