Changeset 35ee9b7 in git
- Timestamp:
- Aug 7, 2008, 6:04:01 PM (16 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- dabe36544e87bab0e6bdb9b9936f225a7f67cdcd
- Parents:
- 1747d96b7453246c6adbfeaa049fcdc86ce6baeb
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/polymake.lib
r1747d96 r35ee9b7 1 version="$Id: polymake.lib,v 1. 6 2008-08-07 15:05:35keilen Exp $";1 version="$Id: polymake.lib,v 1.7 2008-08-07 16:04:01 keilen Exp $"; 2 2 category="Tropical Geometry"; 3 3 info=" 4 LIBRARY: polymake.lib Interface to polymake and TOPCOM4 LIBRARY: polymake.lib Computations with polytopes and fans, interface to polymake and TOPCOM 5 5 AUTHOR: Thomas Markwig, email: keilen@mathematik.uni-kl.de 6 6 … … 15 15 as the Newton polytope or the Groebner fan of a polynomial, most of the hard 16 16 computations are NOT done by Singular but by the program 17 18 19 20 21 22 17 @* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt 18 @* (see http://www.math.tu-berlin.de/polymake/), 19 @* respectively (only in the procedure triangularions) by the program 20 @* - topcom by Joerg Rambau, Universitaet Bayreuth 21 @* (see http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM); 22 @* this library should rather be seen as an interface which allows to use a (very limited) 23 23 number of options which polymake respectively topcom offers to compute with polytopes 24 24 and fans and to make the results available in Singular for further computations; 25 25 moreover, the user familiar with Singular does not have to learn the syntax of polymake 26 26 or topcom, if the options offered here are sufficient for his purposes. 27 27 @* Note, though, that the procedures concerned with planar polygons are independent of 28 28 both, polymake and topcom. 29 29 … … 91 91 as its dimension and information on its facets 92 92 RETURN: list, L with four entries 93 93 @* L[1] : an integer matrix whose rows are the coordinates of vertices 94 94 of the polytope 95 96 95 @* L[2] : the dimension of the polytope 96 @* L[3] : a list whose ith entry explains to which vertices the ith vertex 97 97 of the Newton polytope is connected -- i.e. L[3][i] is an integer 98 98 vector and an entry k in there means that the vertex L[1][i] is 99 99 connected to the vertex L[1][k] 100 100 @* L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give 101 101 a linear system of equations describing the affine hull of the polytope, 102 102 i.e. the smallest affine space containing the polytope … … 105 105 this program is installed in order to use this procedure; 106 106 see http://www.math.tu-berlin.de/polymake/ 107 107 @* - note that in the vertex edge graph we have changed the polymake convention which 108 108 starts indexing its vertices by zero while we start with one ! 109 109 @* - the procedure creates the file /tmp/polytope.polymake which contains the polytope 110 110 in polymake format and which can be used for further computations with polymake 111 111 @* - moreover, the procedure creates the file /tmp/polytope.output which it deletes 112 112 again before ending 113 113 @* - it is possible to give as an optional second argument as string which then will be 114 114 used instead of 'polytope' in the name of the polymake output file 115 115 EXAMPLE: example polymakePolytope; shows an example" … … 233 233 "USAGE: newtonPolytope(f[,#]); f poly, # string 234 234 RETURN: list, L with four entries 235 235 @* L[1] : an integer matrix whose rows are the coordinates of vertices 236 236 of the Newton polytope of f 237 238 237 @* L[2] : the dimension of the Newton polytope of f 238 @* L[3] : a list whose ith entry explains to which vertices the ith vertex 239 239 of the Newton polytope is connected -- i.e. L[3][i] is an integer 240 240 vector and an entry k in there means that the vertex L[1][i] is 241 241 connected to the vertex L[1][k] 242 242 @* L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give 243 243 a linear system of equations describing the affine hull of the Newton 244 244 polytope, i.e. the smallest affine space containing the Newton polytope … … 247 247 space of the normal fan dual to the Newton polytope, i.e. we get the EQUATIONS that 248 248 we need as input for polymake when computing the normal fan 249 249 @* - the procedure calls for its computation polymake by Ewgenij Gawrilow, 250 250 TU Berlin and Michael Joswig, so it only works if polymake is installed; 251 251 see http://www.math.tu-berlin.de/polymake/ 252 252 @* - the procedure creates the file /tmp/newtonPolytope.polymake which contains the polytope 253 253 in polymake format and which can be used for further computations with polymake 254 254 @* - moreover, the procedure creates the file /tmp/newtonPolytope.output which it deletes 255 255 again before ending 256 256 @* - it is possible to give as an optional second argument as string which then will be 257 257 used instead of 'newtonPolytope' in the name of the polymake output file 258 258 EXAMPLE: example newtonPolytope; shows an example" … … 300 300 // its dimension is 301 301 np[2]; 302 // the Newton polytope is contained in the affine space given by the equations 302 // the Newton polytope is contained in the affine space given 303 // by the equations 303 304 np[4]*M; 304 305 } … … 334 335 ASSUME: - vert is an integer matrix whose rows are the coordinate of the vertices of 335 336 a convex lattice polygon; 336 337 @* - aff describes the affine hull of this polytope, i.e. 337 338 the smallest affine space containing it, in the following sense: 338 339 denote by n the number of columns of vert, then multiply aff by (1,x(1),...,x(n)) 339 340 and set the resulting terms to zero in order to get the equations for the affine hull; 340 341 @* - the ith entry of graph is an integer vector describing to which vertices 341 342 the ith vertex is connected, i.e. a k as entry means that the vertex vert[i] is 342 343 connected to vert[k]; 343 344 @* - the integer rays is either one (if the extreme rays should be computed) or zero (otherwise) 344 345 RETURN: list, the ith entry of L[1] contains information about the cone in the normal fan 345 346 dual to the ith vertex of the polytope 346 347 @* L[1][i][1] = integer matrix representing the inequalities which describe the 347 348 cone dual to the ith vertex 348 349 @* L[1][i][2] = a list which contains the inequalities represented by L[i][1] 349 350 as a list of strings, where we use the variables x(1),...,x(n) 350 351 @* L[1][i][3] = only present if 'er' is set to 1; in that case it is an interger matrix 351 352 whose rows are the extreme rays of the cone 352 353 @* L[2] = is an integer matrix whose rows span the linearity space of the fan, 353 354 i.e. the linear space which is contained in each cone 354 355 NOTE: - the procedure calls for its computation polymake by Ewgenij Gawrilow, 355 356 TU Berlin and Michael Joswig, so it only works if polymake is installed; 356 357 see http://www.math.tu-berlin.de/polymake/ 357 358 @* - in the optional argument # it is possible to hand over other names for the 358 359 variables to be used -- be carful, the format must be correct and that is 359 360 not tested, e.g. if you want the variable names to be u00,u10,u01,u11 … … 497 498 RETURN: list, the ith entry of L[1] contains information about the ith cone in the Groebner fan 498 499 dual to the ith vertex in the Newton polytope of the f 499 500 L[1][i][2] = a list which contains the inequalities represented by L[i][1]500 @* L[1][i][1] = integer matrix representing the inequalities which describe the cone 501 @* L[1][i][2] = a list which contains the inequalities represented by L[1][i][1] 501 502 as a list of strings 502 503 503 @* L[1][i][3] = an interger matrix whose rows are the extreme rays of the cone 504 @* L[2] = is an integer matrix whose rows span the linearity space of the fan, 504 505 i.e. the linear space which is contained in each cone 505 L[3] = the Newton polytope of f in the format of the procedure newtonPolytope 506 @* L[3] = the Newton polytope of f in the format of the procedure newtonPolytope 507 @* L[4] = integer matrix where each row represents the exponet vector of one monomial 508 occuring in the input polynomial 506 509 NOTE: - if you have alread computed the Newton polytope of f then you might want 507 510 to use the procedure normalFan instead in order to avoid doing costly computation 508 511 twice 509 512 @* - the procedure calls for its computation polymake by Ewgenij Gawrilow, 510 513 TU Berlin and Michael Joswig, so it only works if polymake is installed; 511 514 see http://www.math.tu-berlin.de/polymake/ 512 515 @* - the procedure creates the file /tmp/newtonPolytope.polymake which contains the 513 516 Newton polytope of f in polymake format and which can be used for further 514 517 computations with polymake 515 518 @* - it is possible to give as an optional second argument as string which then will be 516 519 used instead of 'newtonPolytope' in the name of the polymake output file 517 520 EXAMPLE: example groebnerFan; shows an example" … … 544 547 // append newtonp to gf 545 548 gf[3]=newtonp; 546 // append newtonp the exponent vectors to gt549 // append the exponent vectors to gf 547 550 gf[4]=exponents; 548 551 return(gf); … … 572 575 gf[3][2]; 573 576 // np[3] contains information how the vertices are connected to each other, 574 // e.g. the first vertex is connected to the second, third and fourth vertex577 // e.g. the 1st vertex is connected to the 2nd, 3rd and 4th vertex 575 578 gf[3][3][1]; 576 579 } … … 581 584 "USAGE: intmatToPolymake(M,art); M intmat, art string 582 585 ASSUME: - M is an integer matrix which should be transformed into polymake format; 583 - art is one of the following strings 584 -'rays' : indicating that a first column of 0's should be added585 -'points' : indicating that a first column of 1's should be added586 @* - art is one of the following strings: 587 @* + 'rays' : indicating that a first column of 0's should be added 588 @* + 'points' : indicating that a first column of 1's should be added 586 589 RETURN: string, the matrix is transformed in a string and a first column has been added 587 590 EXAMPLE: example intmatToPolymake; shows an example" … … 768 771 from the program topcom by Joerg Rambau, Universitaet Bayreuth; it 769 772 therefore is necessary that this program is installed in order to use this 770 procedure; 771 seehttp://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM772 773 procedure; see 774 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM 775 @* - the procedure creates the files /tmp/triangulationsinput and /tmp/triangulationsoutput; 773 776 the former is used as input for points2triangs and the latter is its output 774 777 containing the triangulations of corresponding to points in the format … … 776 779 you have to hand an optional parameter (e.g. the number 1) to the procedure, 777 780 since otherwise the files will be destroyed before leaving the procedure 778 781 @* - note that an integer i in an integer vector representing a triangle refers to 779 782 the ith lattice point, i.e. polygon[i]; this convention is different from 780 783 TOPCOM's convention, where i would refer to the i-1st lattice point … … 907 910 ASSUME: - polygon is a list of integer vectors of the same size representing the affine 908 911 coordinates of lattice points 909 912 @* - if the triangulations of the corresponding polygon have already been computed 910 913 with the procedure triangulations then these can be given as a second (optional) 911 914 argument in order to avoid doing this computation again … … 916 919 the procedure triangulations 917 920 RETURN: list, say L, such that: 918 921 @* L[1] = intmat, each row gives the affine coordinates of a lattice point 919 922 in the secondary polytope given by the marked 920 923 polytope corresponding to polygon 921 924 @* L[2] = the list of corresponding triangulations 922 925 NOTE: if the triangluations are not handed over as optional argument the procedure calls 923 926 for its computation of these triangulations the program points2triangs 924 927 from the program topcom by Joerg Rambau, Universitaet Bayreuth; it 925 928 therefore is necessary that this program is installed in order to use this 926 procedure; 927 seehttp://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM929 procedure; see 930 @* http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM 928 931 EXAMPLE: example secondaryPolytope; shows an example" 929 932 { … … 1033 1036 // the integer vectors in boundary are lattice points on the boundary 1034 1037 // of a convex lattice polygon in the plane 1035 list boundary=intvec(0,0),intvec(0,1),intvec(0,2),intvec(2,2),intvec(2,1),intvec(2,0); 1038 list boundary=intvec(0,0),intvec(0,1),intvec(0,2),intvec(2,2), 1039 intvec(2,1),intvec(2,0); 1036 1040 // interior is a lattice point in the interior of this lattice polygon 1037 1041 intvec interior=1,1; 1038 1042 // compute the general cycle length of a cycle of the corresponding cycle 1039 // in the dual tropical curve --note that (0,1) and (2,1) do not contribute1043 // in the dual tropical curve, note that (0,1) and (2,1) do not contribute 1040 1044 cycleLength(boundary,interior); 1041 1045 } … … 1048 1052 and the interior points 1049 1053 RETURN: list, L consisting of three lists 1050 1051 1052 1053 1054 @* L[1] : represents the vertices the polygon ordered clockwise 1055 @* L[1][i][1] = intvec, the coordinates of the ith vertex 1056 @* L[1][i][2] = int, the position of L[1][i][1] in markings 1057 @* L[2][i] : represents the lattice points on the facet of the polygon with 1054 1058 endpoints L[1][i] and L[1][i+1] (i considered modulo size(L[1])) 1055 1056 1057 1058 1059 1059 @* L[2][i][j][1] = intvec, the coordinates of the jth lattice point on that facet 1060 @* L[2][i][j][2] = int, the position of L[2][i][j][1] in markings 1061 @* L[3] : represents the interior lattice points of the polygon 1062 @* L[3][i][1] = intvec, the coordinates of the ith interior point 1063 @* L[3][i][2] = int, the position of L[3][i][1] in markings 1060 1064 EXAMPLE: example splitPolygon; shows an example" 1061 1065 { … … 1149 1153 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1150 1154 // with all integer points as markings 1151 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2),intvec(0,2),intvec(0,3); 1155 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), 1156 intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), 1157 intvec(0,2),intvec(0,3); 1152 1158 // split the polygon in its vertices, its facets and its interior points 1153 1159 list sp=splitPolygon(polygon); … … 1165 1171 ASSUME: polygon has the format of the output of splitPolygon, i.e. it is a list with three 1166 1172 entries describing a convex lattice polygon in the following way: 1167 1173 @* polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] is a lattice point which is 1168 1174 a vertex of the lattice polygon, and polygon[1][i][2] is an integer assigned to 1169 1175 this lattice point as identifying index 1170 1176 @* polygon[2] : is a list of lists; for each vertex of the polygon, i.e. for each entry in polygon[1], 1171 1177 it contains a list polygon[2][i], which contains the lattice points on the facet 1172 1178 with endpoints polygon[1][i] and polygon[1][i+1] - i considered mod size(polygon[1]); … … 1174 1180 vector giving the coordinate of the lattice point and an entry polygon[2][i][j][2] 1175 1181 which is the identifying index 1176 1182 @* polygon[3] : is a list of lists, where each entry corresponds to a lattice point in the 1177 1183 interior of the polygon, with polygon[3][j][1] being the coordinates of the point 1178 1184 and polygon[3][j][2] being the identifying index; 1179 1185 @* triang is a list of integer vectors all of size three describing a triangulation of the 1180 1186 polygon described by polygon; if an entry of triang is the vector (i,j,k) then the triangle 1181 1187 is build by the vertices with indices i, j and k … … 1357 1363 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1358 1364 // with all integer points as markings 1359 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2),intvec(0,2),intvec(0,3); 1365 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), 1366 intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), 1367 intvec(0,2),intvec(0,3); 1360 1368 // split the polygon in its vertices, its facets and its interior points 1361 1369 list sp=splitPolygon(polygon); 1362 // define a triangulation by connecting the only interior point with the vertices 1370 // define a triangulation by connecting the only interior point 1371 // with the vertices 1363 1372 list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10); 1364 1373 // compute the eta-vector of this triangulation … … 1369 1378 "USAGE: findOrientedBoundary(polygon); polygon list 1370 1379 ASSUME: polygon is a list of integer vectors defining integer lattice points in the plane 1371 RETURN: list, l[1] = list of integer vectors such that the polygonal path defined by 1380 RETURN: list, l with the followin interpretation 1381 @* l[1] = list of integer vectors such that the polygonal path defined by 1372 1382 these is the boundary of the convex hull of the lattice points in polygon 1373 1383 @* l[2] = list, the redundant points in l[1] have been removed 1374 1384 EXAMPLE: example findOrientedBoundary; shows an example" 1375 1385 { … … 1536 1546 echo=2; 1537 1547 // the following lattice points in the plane define a polygon 1538 list polygon=intvec(0,0),intvec(3,1),intvec(1,0),intvec(2,0),intvec(1,1),intvec(3,2),intvec(1,2),intvec(2,3),intvec(2,4); 1548 list polygon=intvec(0,0),intvec(3,1),intvec(1,0),intvec(2,0), 1549 intvec(1,1),intvec(3,2),intvec(1,2),intvec(2,3), 1550 intvec(2,4); 1539 1551 // we compute its boundary 1540 1552 list boundarypolygon=findOrientedBoundary(polygon); … … 1548 1560 proc cyclePoints (list triang,list points,int pt) 1549 1561 "USAGE: cyclePoints(triang,points,pt) triang,points list, pt int 1550 ASSUME: points is a list of integer vectors describing the lattice points of a marked polygon;1551 1552 in the sense that an integer vector of the form (i,j,k) describes the triangle formed1553 by polygon[i], polygon[j] and polygon[k];1554 1555 the marked points1562 ASSUME: - points is a list of integer vectors describing the lattice points of a marked polygon; 1563 @* - triang is a list of integer vectors describing a triangulation of the marked polygon 1564 in the sense that an integer vector of the form (i,j,k) describes the triangle formed 1565 by polygon[i], polygon[j] and polygon[k]; 1566 @* - pt is an integer between 1 and size(points), singling out a lattice point among 1567 the marked points 1556 1568 PURPOSE: consider the convex lattice polygon, say P, spanned by all lattice points in points which 1557 1569 in the triangulation triang are connected to the point points[pt]; the procedure … … 1610 1622 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 1611 1623 // with all integer points as markings 1612 list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2),intvec(0,2),intvec(0,3); 1624 list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), 1625 intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), 1626 intvec(0,2),intvec(0,3); 1613 1627 // define a triangulation 1614 list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10),intvec(1,8,9),intvec(1,2,8); 1628 list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10), 1629 intvec(1,8,9),intvec(1,2,8); 1615 1630 // compute the points connected to (1,1) in triang 1616 1631 cyclePoints(triang,points,1); … … 1640 1655 echo=2; 1641 1656 // define a polygon with lattice area 5 1642 list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1),intvec(2,1),intvec(0,0); 1657 list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1), 1658 intvec(2,1),intvec(0,0); 1643 1659 latticeArea(polygon); 1644 1660 } … … 1648 1664 ASSUME: polygon is a list of integer vectors in the plane and consider their convex hull C 1649 1665 RETURN: list, L of three integersthe 1650 1651 1652 1666 @* L[1] : the lattice area of C, i.e. twice the Euclidean area 1667 @* L[2] : the number of lattice points on the boundary of C 1668 @* L[3] : the number of interior lattice points of C 1653 1669 NOTE: the integers in L are related by Pick's formula, namely: L[1]=L[2]+2*L[3]-2 1654 1670 EXAMPLE: example picksFormula; shows an example" … … 1681 1697 echo=2; 1682 1698 // define a polygon with lattice area 5 1683 list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1),intvec(2,1),intvec(0,0); 1699 list polygon=intvec(1,2),intvec(1,0),intvec(2,0),intvec(1,1), 1700 intvec(2,1),intvec(0,0); 1684 1701 list pick=picksFormula(polygon); 1685 1702 // the lattice area of the polygon is: … … 1703 1720 the number 12. Amer. Math. Monthly 107 (2000), no. 3, 238--250.) 1704 1721 RETURN: list, L such that 1705 1706 1707 1708 1722 @* L[1] : list whose entries are the vertices of the normal form of the polygon 1723 @* L[2] : the matrix A of the unimodular transformation 1724 @* L[3] : the translation vector v of the unimodular transformation 1725 @* L[4] : list such that the ith entry is the image of polygon[i] under the 1709 1726 unimodular transformation T 1710 1727 EXAMPLE: example ellipticNF; shows an example" … … 1934 1951 echo=2; 1935 1952 ring r=0,(x,y),dp; 1936 // the Newton polygon of the following polynomial has precisely one interior point 1953 // the Newton polygon of the following polynomial 1954 // has precisely one interior point 1937 1955 poly f=x22y11+x19y10+x17y9+x16y9+x12y7+x9y6+x7y5+x2y3; 1938 1956 list polygon=newtonPolytopeLP(f); … … 1960 1978 PURPOSE: this is a database storing the 16 normal forms of planar polygons with 1961 1979 precisely one interior point up to unimodular affine transformations 1962 1980 @* (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and 1963 1981 the number 12. Amer. Math. Monthly 107 (2000), no. 3, 238--250.) 1964 1982 RETURN: list, L such that 1965 1966 1967 1983 @* L[1] : list whose entries are the vertices of the nth normal form 1984 @* L[2] : list whose entries are all the lattice points of the nth normal form 1985 @* L[3] : only present if the optional parameter # is present, and then 1968 1986 it is a polynomial in the variables (x,y) whose Newton polygon 1969 1987 is the nth normal form
Note: See TracChangeset
for help on using the changeset viewer.