Changeset edef30 in git
 Timestamp:
 Dec 15, 2000, 1:22:56 PM (22 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '00e2e9c41af3fde1273eb3633f4c0c7c3db2579d')
 Children:
 02a0976e1a19dd9ef9d5b81bcd719b66669ea356
 Parents:
 c948324910a5e06db374ebc5119a410797010e26
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/brnoeth.lib
rc948324 redef30 1 version="$Id: brnoeth.lib,v 1. 3 20001215 11:51:55 SingularExp $";1 version="$Id: brnoeth.lib,v 1.4 20001215 12:22:56 obachman Exp $"; 2 2 info=" 3 LIBRARY: brnoeth.lib 4 3 LIBRARY: brnoeth.lib PROCEDURES FOR THE BRILLNOETHER ALGORITHM 4 5 5 AUTHORS: Jose Ignacio Farran Martin, ignfar@eis.uva.es 6 6 Christoph Lossen, lossen@mathematik.unikl.de 7 7 8 PURPOSE: BrillNoether algorithm, Weierstrass semigroups and AG codes9 10 8 SEE ALSO: hnoether_lib, triang_lib 11 9 12 KEYWORDS: Weierstrass semigroup; Algebraic Geometry codes; BrillNoether algorithm 10 KEYWORDS: Weierstrass semigroup; Algebraic Geometry codes; 11 BrillNoether algorithm 13 12 14 13 OVERVIEW: Implementation of the BrillNoether algorithm for solving the … … 20 19 by reading the end of the file brnoeth.lib. 21 20 22 PROCEDURES:21 MAIN PROCEDURES: 23 22 Adj_div(f); computes the conductor of a curve 24 23 NSplaces(h,A); computes nonsingular places up to given degree … … 26 25 Weierstrass(P,m,C); computes the Weierstrass semigroup of C at P up to m 27 26 extcurve(d,C); extends the curve C to an extension of degree d 28 AGcode_L(G,D,E); computes the evaluation AG code with given divisors G and D 29 AGcode_Omega(G,D,E); computes the residual AG code with given divisors G and D 27 AGcode_L(G,D,E); computes the evaluation AG code with given divisors 28 G and D 29 AGcode_Omega(G,D,E); computes the residual AG code with given divisors 30 G and D 30 31 prepSV(G,D,F,E); preprocessing for the basic decoding algorithm 31 32 decodeSV(y,K); decoding of a word with the basic decoding algorithm … … 36 37 sys_code(C); computes an equivalent systematic code 37 38 permute_L(L,P); applies a permutation to a list 38 39 39 "; 40 40 41 // ============================================================================= 41 42 // =========================================================================== 43 42 44 43 45 LIB "matrix.lib"; … … 47 49 // maybe useful : LIB "linalg.lib","primdec.lib","normal.lib"; 48 50 49 // ============================================================================= 51 52 // =========================================================================== 50 53 51 54 … … 56 59 57 60 proc closed_points (ideal I) 58 "USAGE: closed_points( ideal_expression ) 59 60 TYPE: list 61 62 PURPOSE: compute the affine closed points in the zeroset of an ideal 63 64 CREATE: list of prime ideals (std), corresponding to the (distinct affine 61 "USAGE: closed_points(I), where I is an ideal 62 63 RETURN: list of prime ideals (std), corresponding to the (distinct affine 65 64 closed) points of V(I). 66 65 67 NOTE: The ideal must have dimension 0, the basering must have 2 variables, 68 the ordering must be lp, and the base field must be finite and prime.@* 66 NOTE: The ideal must have dimension 0, the basering must have 2 67 variables, the ordering must be lp, and the base field must 68 be finite and prime.@* 69 69 The option(redSB) is convenient to be set in advance. 70 70 … … 214 214 { 215 215 // dimension check (has to be 0) 216 print("? something was wrong; possibly nonreduced curve"); 217 return(); 216 ERROR("something was wrong; possibly nonreduced curve"); 218 217 } 219 218 else … … 227 226 "USAGE: curve(f), where f is a polynomial (affine of projective) 228 227 CREATE: poly CHI in both ring aff_r=p,(x,y),lp and ring Proj_R=p,(x,y,z),lp 229 also ideal (std) Aff_SLocus of affine singular locus in the ring aff_r 228 also ideal (std) Aff_SLocus of affine singular locus in the ring 229 aff_r 230 230 RETURN: list (size 3) with aff_r,Proj_R and deg(f) 231 231 NOTE: f must be absolutely irreducible, but this is not checked … … 279 279 return(L); 280 280 } 281 print("? error : basering must have 2 or 3 variables"); 282 return(); 281 ERROR("basering must have 2 or 3 variables"); 283 282 } 284 283 … … 290 289 // the ideal ISL=s_locus(CHI) is assumed to be computed in advance for 291 290 // a plane curve CHI, and it must be given by a standard basis 292 // for our purpose the function must called with the "global" ideal "Aff_SLocus" 291 // for our purpose the function must called with the "global" ideal 292 // "Aff_SLocus" 293 293 list SL=list(); 294 294 ideal I=ISL; … … 323 323 setring base_r; 324 324 poly f_inf=imap(r_auxz,f_inf); 325 ideal I=factorize(f_inf,1); // points at infinity as homogeneous polynomials 325 ideal I=factorize(f_inf,1); // points at infinity as homogeneous 326 // polynomials 326 327 int s=size(I); 327 328 int i; … … 339 340 setring r_auxz; 340 341 poly f_yz=subst(F,x,1); 341 if ( subst(subst(diff(f_yz,y),y,0),z,0)==0 && subst(subst(diff(f_yz,z),y,0),z,0)==0 ) 342 if ( subst(subst(diff(f_yz,y),y,0),z,0)==0 && 343 subst(subst(diff(f_yz,z),y,0),z,0)==0 ) 342 344 { 343 345 // the point is singular … … 368 370 map phi=r_auxz,x+A,0,z; 369 371 poly f_origin=phi(f_xz); 370 if ( subst(subst(diff(f_origin,x),x,0),z,0)==0 && subst(subst(diff(f_origin,z),x,0),z,0)==0 ) 372 if ( subst(subst(diff(f_origin,x),x,0),z,0)==0 && 373 subst(subst(diff(f_origin,z),x,0),z,0)==0 ) 371 374 { 372 375 // the point is singular … … 387 390 else 388 391 { 389 // the point is nonrational and a field extension with minpoly=aux is needed 392 // the point is nonrational and a field extension with minpoly=aux 393 // is needed 390 394 ring r_ext=(char(basering),a),(x,y,z),lp; 391 395 poly F=imap(r_auxz,F); … … 395 399 map phi=r_ext,x+a,0,z; 396 400 poly f_origin=phi(f_xz); 397 if ( subst(subst(diff(f_origin,x),x,0),z,0)==0 && subst(subst(diff(f_origin,z),x,0),z,0)==0 ) 401 if ( subst(subst(diff(f_origin,x),x,0),z,0)==0 && 402 subst(subst(diff(f_origin,z),x,0),z,0)==0 ) 398 403 { 399 404 // the point is singular … … 420 425 static proc closed_points_ext (poly f,int d,ideal SL) 421 426 { 422 // computes : (closed affine nonsingular) points over an extension of degree d 427 // computes : (closed affine nonsingular) points over an extension of 428 // degree d 423 429 // remark(1) : singular points are supposed to be listed appart 424 430 // remark(2) : std SL=s_locus(f) is supposed to be computed in advance 425 431 // remark(3) : ideal SL is used to remove those points which are singular 426 // output : list of list of prime ideals with an intvec for storing the places 432 // output : list of list of prime ideals with an intvec for storing the 433 // places 427 434 int Q=char(basering)^d; // cardinality of the extension field 428 435 ideal I=f,x^Qx,y^Qy; // ideal of the searched points … … 462 469 RETURN: integer with the degree of the closed point given by P 463 470 SEE ALSO: closed_points 464 NOTE: If P is a (homogeneous irreducible) polynomial the point is at infinity,465 and if P is a (prime) ideal the points is affine, and the ideal must be given466 by 2 generators: the first one irreducible and depending only on y, and the467 second one irreducible over the extension given by y with the first generator468 as minimal polynomial471 NOTE: If P is a (homogeneous irreducible) polynomial the point is at 472 infinity, and if P is a (prime) ideal the points is affine, and 473 the ideal must be given by 2 generators: the first one irreducible 474 and depending only on y, and the second one irreducible over the 475 extension given by y with the first generator as minimal polynomial 469 476 " 470 477 { 471 478 // computes : the degree of a given point 472 // remark(1) : if the input is (irreducible homogeneous) poly => the point is at infinity 473 // remark(2) : it the input is (std. resp. lp. prime) ideal => the point is affine 479 // remark(1) : if the input is (irreducible homogeneous) poly => the point 480 // is at infinity 481 // remark(2) : it the input is (std. resp. lp. prime) ideal => the point is 482 // affine 474 483 if (typeof(P[1])=="ideal") 475 484 { … … 484 493 { 485 494 // this should not happen in principle 486 print("? error : nonvalid parameter"); 487 return(); 495 ERROR("nonvalid parameter"); 488 496 } 489 497 } … … 496 504 else 497 505 { 498 print("? error : parameter must have a poly or ideal in the first component"); 499 return(); 506 ERROR("parameter must have a poly or ideal in the first component"); 500 507 } 501 508 } … … 551 558 else 552 559 { 553 print("? error : first argument must be an affine point"); 554 return(); 560 ERROR("first argument must be an affine point"); 555 561 } 556 562 } … … 575 581 static proc isInLP (ideal P,list LP) 576 582 { 577 // checks if affine point P is a list LP and returns either its position or zero 578 // remark : all points in LP and P itself are assumed to be given by a standard basis 579 // warning : the procedure does not check whether the points are affine or not 583 // checks if affine point P is a list LP and returns either its position or 584 // zero 585 // remark : all points in LP and P itself are assumed to be given by a 586 // standard basis 587 // warning : the procedure does not check whether the points are affine or 588 // not 580 589 int s=size(LP); 581 590 if (s==0) … … 597 606 static proc res_deg () 598 607 { 599 // computes the residual degree of the basering with respect to its prime field 608 // computes the residual degree of the basering with respect to its prime 609 // field 600 610 // warning : minpoly must depend on a parameter called "a" 601 611 int ext; … … 617 627 static proc Frobenius (etwas,int r) 618 628 { 619 // applies the Frobenius map over F_{p^r} to an object defined over an extension of such field 620 // usually it is called with r=1, i.e. the Frobenius map over the prime field F_p 629 // applies the Frobenius map over F_{p^r} to an object defined over an 630 // extension of such field 631 // usually it is called with r=1, i.e. the Frobenius map over the prime 632 // field F_p 621 633 // returns always an object of the same type, and works correctly on 622 634 // numbers, polynomials, ideals, matrices or lists of the above types 623 // maybe : types vector and module should be added in the future, but they are not needed now 635 // maybe : types vector and module should be added in the future, but they 636 // are not needed now 624 637 int q=char(basering)^r; 625 638 if (typeof(etwas)=="number") … … 684 697 static proc conj_b (list L,int r) 685 698 { 686 // applies the Frobenius map over F_{p^r} to a list of type HNE defined over a larger extension 699 // applies the Frobenius map over F_{p^r} to a list of type HNE defined over 700 // a larger extension 687 701 // when r=1 it turns to be the Frobenius map over the prime field F_{p} 688 // returns : a list of type HNE which is either conjugate of the input or the same list 689 // in case of L being actually defined over the base field F_{p^r} 702 // returns : a list of type HNE which is either conjugate of the input or 703 // the same list in case of L being actually defined over the base field 704 // F_{p^r} 690 705 int p=char(basering); 691 706 int Q=p^r; … … 728 743 static proc grad_b (list L,int r) 729 744 { 730 // computes the degree of a list of type HNE which is actually defined over F_{p^r}731 // eventhough it is given in an extension of such field745 // computes the degree of a list of type HNE which is actually defined over 746 // F_{p^r} eventhough it is given in an extension of such field 732 747 int gr=1; 733 748 int rd=res_deg() div r; … … 752 767 static proc conj_bs (list L,int r) 753 768 { 754 // computes all the conjugates over F_{p^r} of a list of type HNE defined over an extension 755 // returns : a list of lists of type HNE, where the first one is the input list 756 // remark : notice that the degree of the branch is then the size of the output 769 // computes all the conjugates over F_{p^r} of a list of type HNE defined 770 // over an extension 771 // returns : a list of lists of type HNE, where the first one is the input 772 // list 773 // remark : notice that the degree of the branch is then the size of the 774 // output 757 775 list branches=list(); 758 776 int gr=1; … … 780 798 static proc subfield (sf) 781 799 { 782 // writes the generator "a" of a subfield of the coefficients field of basering 783 // in terms of the the current generator (also called "a") as a string 784 // sf is an existing ring whose coefficient field is such a subfield 785 // warning : in basering there must be a variable called "x" and subfield must not be prime 800 // writes the generator "a" of a subfield of the coefficients field of 801 // basering in terms of the the current generator (also called "a") as a 802 // string sf is an existing ring whose coefficient field is such a subfield 803 // warning : in basering there must be a variable called "x" and subfield 804 // must not be prime 786 805 def base_r=basering; 787 806 string new_m=string(minpoly); … … 842 861 else 843 862 { 844 print("warning : minpoly=0 in the subfield; you should check that nothing is wrong"); 863 dbprint(printlevel+1,"warning : minpoly=0 in the subfield; 864 you should check that nothing is wrong"); 845 865 return(string(1)); 846 866 } … … 853 873 // fetchs a poly with name "datum" to the current basering from the ring sf 854 874 // such that the generator is given by string "rel" 855 // warning : ring sf must have only variables (x,y) and basering must have at least (x,y) 856 // warning : the case of minpoly=0 is not regarded; there you can use "imap" instead 875 // warning : ring sf must have only variables (x,y) and basering must have 876 // at least (x,y) 877 // warning : the case of minpoly=0 is not regarded; there you can use "imap" 878 // instead 857 879 def base_r=basering; 858 880 if (rel=="a") … … 883 905 { 884 906 // fetchs a poly with name "datum" to the current basering from the ring lf 885 // and larger coefficients field, where the generator of current ring is given 886 // by string "rel" and "datum" is actually defined over the small field 887 // warning : "ring lf must have only variables (x,y) and basering must have at least (x,y) 888 // warning : the case of minpoly=0 is supposed unnecessary, since then "datum" should be 907 // and larger coefficients field, where the generator of current ring is 908 // given by string "rel" and "datum" is actually defined over the small 909 // field 910 // warning : "ring lf must have only variables (x,y) and basering must have 911 // at least (x,y) 912 // warning : the case of minpoly=0 is supposed unnecessary, since then 913 // "datum" should be 889 914 // already written only int the right way, i.e. in terms of the prime field 890 915 def base_r=basering; … … 906 931 ideal I=pdatum,prel; 907 932 I=eliminate(I,a); 908 poly newdatum=I[1]; 933 poly newdatum=I[1]; // hopefully it was done correctly and size(I)=1 !!!! 909 934 newdatum=subst(newdatum,b,a); 910 935 string snewdatum=string(newdatum); … … 920 945 // computes the "rational" places which are defined over a (closed) point 921 946 // Pp points to an appropriate point of the given curve 922 // creates : local rings (if they do not exist yet) and then add the places to a list 923 // each place is given basically by the coordinates of the point and a list HNdevelop 947 // creates : local rings (if they do not exist yet) and then add the 948 // places to a list 949 // each place is given basically by the coordinates of the point and a 950 // list HNdevelop 924 951 // returns : list with all updated data of the curve 925 952 // if the places already exist they are not computed again 926 // if sing==1 the point is assumed singular and computes the local conductor for all places 927 // using the local invariants of the branches 928 // if sing==2 the point is assumed singular and computes the local conductor for all places 929 // using the Dedekind formula and local parametrizations of the branches 930 // if sing<>1&2 the point is assumed nonsingular and the local conductor should be zero 953 // if sing==1 the point is assumed singular and computes the local conductor 954 // for all places using the local invariants of the branches 955 // if sing==2 the point is assumed singular and computes the local conductor 956 // for all places using the Dedekind formula and local parametrizations 957 // of the branches 958 // if sing<>1&2 the point is assumed nonsingular and the local conductor 959 // should be zero 931 960 list PP=list(); 932 961 if (Pp[1]==0) … … 969 998 ext1=d; 970 999 // the point is (A:B:1) but one must distinguish several cases 971 // P is assumed to be a std. resp. "(x,y),lp" and thus P[1] depends only on "y" 1000 // P is assumed to be a std. resp. "(x,y),lp" and thus P[1] depends 1001 // only on "y" 972 1002 if (d==1) 973 1003 { … … 988 1018 if (deg(P[1])==1) 989 1019 { 990 // the point is nonrational but the second component needs no field extension 1020 // the point is nonrational but the second component needs no 1021 // field extension 991 1022 number B=number(subst(P[1],y,0)); 992 1023 poly aux2=subst(P[2],y,B); … … 1027 1058 { 1028 1059 // this is the most complicated case of nonrational point 1029 // firstly : construct an extension of degree d and guess the minpoly 1060 // firstly : construct an extension of degree d and guess the 1061 // minpoly 1030 1062 poly P1=P[1]; 1031 1063 poly P2=P[2]; … … 1039 1071 poly P_1=imap(base_r,P1); 1040 1072 poly P_2=imap(base_r,P2); 1041 ideal factors1=factorize(P_1,1); 1073 ideal factors1=factorize(P_1,1); // hopefully this works !!!! 1042 1074 number coord@2=number(subst(factors1[1],y,0)); 1043 1075 // thirdly : compute one of the first components for the above root 1044 1076 poly P_0=subst(P_2,y,coord@2); 1045 ideal factors2=factorize(P_0,1); 1077 ideal factors2=factorize(P_0,1); // hopefully this works !!!! 1046 1078 number coord@1=number(subst(factors2[1],x,0)); 1047 1079 number coord@3=number(1); … … 1056 1088 { 1057 1089 // this should not happen in principle 1058 print("? error : nonvalid parameter"); 1059 return(); 1090 ERROR("nonvalid parameter"); 1060 1091 } 1061 1092 } … … 1115 1146 else 1116 1147 { 1117 print("? error : a point must have a poly or ideal in the first component"); 1118 return(); 1148 ERROR("a point must have a poly or ideal in the first component"); 1119 1149 } 1120 1150 } … … 1234 1264 { 1235 1265 // we start with a rational point but we get nonrational branches 1236 // they may have different degrees and then we may need reduce the field extensions 1237 // for each one, and finally check if the minpoly fetchs with S(i) or not 1238 // if one of the branches is rational, we may trust that is is written correctly 1266 // they may have different degrees and then we may need reduce the 1267 // field extensions for each one, and finally check if the minpoly 1268 // fetchs with S(i) or not 1269 // if one of the branches is rational, we may trust that is is written 1270 // correctly 1239 1271 if (sing==1) 1240 1272 { … … 1272 1304 } 1273 1305 } 1274 // the actual degree of each branch is computed and now check if the local ring exists 1306 // the actual degree of each branch is computed and now check if the 1307 // local ring exists 1275 1308 for (i=1;i<=n_branches;i=i+1) 1276 1309 { … … 1352 1385 for (k=1;k<=n;k=k+1) 1353 1386 { 1354 Maux[j,k]=rationalize(HNEring,"L@HNE["+string(i)+"][1]["+string(j)+","+string(k)+"]",newa); 1387 Maux[j,k]=rationalize(HNEring,"L@HNE["+string(i)+"][1]["+ 1388 string(j)+","+string(k)+"]",newa); 1355 1389 } 1356 1390 } … … 1471 1505 for (k=1;k<=n;k=k+1) 1472 1506 { 1473 Maux[j,k]=importdatum(HNEring,"L@HNE["+string(i)+"][1]["+string(j)+","+string(k)+"]",newa); 1507 Maux[j,k]=importdatum(HNEring,"L@HNE["+string(i)+"][1]["+ 1508 string(j)+","+string(k)+"]",newa); 1474 1509 } 1475 1510 } … … 1549 1584 for (i=1;i<=n_branches;i=i+1) 1550 1585 { 1551 // first compute the actual degree of each branch and check if the local ring exists 1586 // first compute the actual degree of each branch and check if the 1587 // local ring exists 1552 1588 ext_0=ext1*dgs[i]; 1553 1589 if (size(update_CURVE[5])>=ext_0) … … 1619 1655 for (k=1;k<=n;k=k+1) 1620 1656 { 1621 Maux[j,k]=rationalize(HNEring,"L@HNE["+string(i)+"][1]["+string(j)+","+string(k)+"]",newa); 1657 Maux[j,k]=rationalize(HNEring,"L@HNE["+string(i)+"][1]["+ 1658 string(j)+","+string(k)+"]",newa); 1622 1659 } 1623 1660 } … … 1696 1733 // computes the degree of the local conductor at a place of a plane curve 1697 1734 // if the point is nonsingular the result will be zero 1698 // the computation is carried out with the "Dedekind formula" via parametrizations 1735 // the computation is carried out with the "Dedekind formula" via 1736 // parametrizations 1699 1737 int a,b,Cq; 1700 1738 def b_ring=basering; … … 1876 1914 1877 1915 1878 // ============================================================================ =1879 // ******* *MAIN PROCEDURES for the "preprocessing" of BrillNoether ********1880 // ============================================================================ =1916 // ============================================================================ 1917 // ******* MAIN PROCEDURES for the "preprocessing" of BrillNoether ******** 1918 // ============================================================================ 1881 1919 1882 1920 1883 1921 proc Adj_div (poly f,list #) 1884 "USAGE: Adj_div( poly_expression [, list_expression] ) 1885 1886 TYPE: list 1887 1888 CREATE: list L with the computed data: 1889 @format 1890 L[1] is a list of rings: L[1][1]=aff_r (affine), L[1][2]=Proj_R (projective), 1891 L[2] is an intvec with 2 entries (degree, genus), 1892 L[3] is a list of intvec (closed places), 1893 L[4] is an intvec (conductor), 1894 L[5] is a list of lists: 1895 L[5][d][1] is a (local) ring over an extension of degree d, 1896 L[5][d][2] is an intvec (degrees of base points of places of degree d) 1897 @end format 1898 1899 PURPOSE: computes and stores the fundamental data of a plane curve 1900 as needed for AG codes. 1922 "USAGE: Adj_div( f [,#] ), where f is a poly, [ # a list ] 1923 1924 RETURN: list L with the computed data: 1925 @format 1926 L[1] is a list of rings: L[1][1]=aff_r (affine), L[1][2]=Proj_R (projective), 1927 L[2] is an intvec with 2 entries (degree, genus), 1928 L[3] is a list of intvec (closed places), 1929 L[4] is an intvec (conductor), 1930 L[5] is a list of lists: 1931 L[5][d][1] is a (local) ring over an extension of degree d, 1932 L[5][d][2] is an intvec (degrees of base points of places of degree d) 1933 @end format 1934 1935 NOTE: @code{Adj_div(f);} computes and stores the fundamental data of the 1936 plane curve defined by f as needed for AG codes. 1901 1937 In the affine ring you can find the following data: 1902 1938 @format … … 1920 1956 a place and all its conjugates) which is represented by an intvec 1921 1957 of size two, the first entry is the degree of the place (in 1922 particular, it tells the local ring where to find the data describing1923 one representative of the closed place), and the second one1924 is the position of those data in the lists POINTS, etc., inside1925 this local ring.@*1958 particular, it tells the local ring where to find the data 1959 describing one representative of the closed place), and the 1960 second one is the position of those data in the lists POINTS, etc., 1961 inside this local ring.@* 1926 1962 In the intvec L[4] (conductor) the ith entry corresponds to the 1927 ith entry in the list of places L[3]. 1928 1929 NOTE:With no optional arguments, the conductor is computed by1963 ith entry in the list of places L[3].@* 1964 1965 With no optional arguments, the conductor is computed by 1930 1966 local invariants of the singularities; otherwise it is computed 1931 1967 by the Dedekind formula. @* … … 1937 1973 1938 1974 KEYWORDS: HamburgerNoether expansions; adjunction divisor 1975 1939 1976 SEE ALSO: closed_points, NSplaces 1977 1940 1978 EXAMPLE: example Adj_div; shows an example 1941 1979 " … … 1949 1987 if (char(basering)==0) 1950 1988 { 1951 print("? error : base field not implemented"); 1952 return(); 1989 ERROR("Base field not implemented"); 1953 1990 } 1954 1991 if (npars(basering)>0) 1955 1992 { 1956 print("? error : base field not implemented"); 1957 return(); 1993 ERROR("Base field not implemented"); 1958 1994 } 1959 1995 intvec opgt=option(get); … … 2103 2139 2104 2140 2105 // ============================================================================ =2141 // ============================================================================ 2106 2142 2107 2143 2108 2144 proc NSplaces (int h,list CURVE) 2109 "USAGE: NSplaces( int_expression, list_expression ) 2110 2111 TYPE: list 2112 2113 PURPOSE: @code{NSplaces(h,CURVE);} returns a list L with updated data of 2114 @code{CURVE} after computing all points up to degree H+@code{h} 2115 (H the maximum degree of the 2116 previously computed places: @* 2145 "USAGE: NSplaces( h, CURVE ), where h is an integer and CURVE is a list 2146 2147 RETURN: list L with updated data of CURVE after computing all 2148 points up to degree H+h (H the maximum degree of the previously 2149 computed places: @* 2117 2150 @format 2118 2151 in affine ring L[1][1]: 2119 lists Aff_Points(d) with affine nonsingular points of degree d (if nonempty) 2152 lists Aff_Points(d) with affine nonsingular points of degree d 2153 (if nonempty) 2120 2154 in L[3]: the newly computed closed places are added, 2121 in L[5]: local rings created/updated to store (represent ativesof) new places.2155 in L[5]: local rings created/updated to store (represent. of) new places. 2122 2156 @end format 2123 2124 2125 NOTE: 2126 2127 SEE ALSO: 2128 EXAMPLE: 2157 See @ref{Adj_div} for a description of the entries in L. 2158 2159 NOTE: The list_expression should be the output of the procedure Adj_div.@* 2160 2161 SEE ALSO: closed_points, Adj_div 2162 EXAMPLE: example NSplaces; shows an example 2129 2163 " 2130 2164 { 2131 // computes all the nonsingular closed places with degree up to a certain bound; 2132 // this bound is the maximum degree of an existing singular place or nonsingular 2133 // place at infinity plus an increment h>=0 which is given as input 2165 // computes all the nonsingular closed places with degree up to a certain 2166 // bound; this bound is the maximum degree of an existing singular place or 2167 // nonsingular place at infinity plus an increment h>=0 which is given as 2168 // input 2134 2169 // creates lists of points and the corresponding places 2135 2170 // list CURVE must be the output of the procedure "Adj_div" … … 2150 2185 for (i=1;i<=M;i=i+1) 2151 2186 { 2152 dbprint(printlevel+1,"Computing nonsingular affine places of degree "+string(i)+" ... "); 2187 dbprint(printlevel+1,"Computing nonsingular affine places of degree " 2188 +string(i)+" ... "); 2153 2189 list Aff_Points(i)=closed_points_deg(CHI,i,Aff_SLocus); 2154 2190 s=size(Aff_Points(i)); … … 2214 2250 2215 2251 static proc supplement (matrix W,matrix V) 2216 "USAGE: supplement(W,V), where W,V are matrices of numbers such that the vector space 2217 generated by the rows of W is contained in that generated by the rows of V 2252 "USAGE: supplement(W,V), where W,V are matrices of numbers such that the 2253 vector space generated by the rows of W is contained in that 2254 generated by the rows of V 2218 2255 RETURN: matrix whose rows generate a supplementary vector space of W in V, 2219 2256 or a zero rowmatrix if <W>==<V> … … 2221 2258 " 2222 2259 { 2223 // W and V represent independent sets of vectors and <W> is assumed to be contained in <V> 2224 // computes matrix S whose rows are l.i. vectors s.t. <W> union <S> is a basis of <V> 2225 // careful : the size of all vectors is assumed to be the same but it is not checked 2226 // and neither the linear independence of the vectors is checked 2260 // W and V represent independent sets of vectors and <W> is assumed to be 2261 // contained in <V> 2262 // computes matrix S whose rows are l.i. vectors s.t. <W> union <S> is a 2263 // basis of <V> 2264 // careful : the size of all vectors is assumed to be the same but it is 2265 // not checked and neither the linear independence of the vectors is checked 2227 2266 // the trivial case W=0 is not covered by this procedure (and thus V<>0) 2228 2267 // if <W>=<V> then a zero rowmatrix is returned … … 2245 2284 static proc supplem (matrix M) 2246 2285 "USAGE: suplement(M), where M is a matrix of numbers with maximal rank 2247 RETURN: matrix whose rows generate a supplementary vector space of <M> in k^n,2248 where k is the base field and n is the number of columns2286 RETURN: matrix whose rows generate a supplementary vector space of <M> in 2287 k^n, where k is the base field and n is the number of columns 2249 2288 SEE ALSO: supplement 2250 2289 NOTE: The rank r is assumed to be 1<r<n. … … 2350 2389 static proc nmultiples (int n,int dgX,poly f) 2351 2390 { 2352 // computes a basis of the space of forms of degree n which are multiple of CHI 2353 // returns a matrix whose rows are the coordinates (related to nFORMS(n)) of such a basis 2391 // computes a basis of the space of forms of degree n which are multiple of 2392 // CHI 2393 // returns a matrix whose rows are the coordinates (related to nFORMS(n)) 2394 // of such a basis 2354 2395 // warning : it is supposed to be called inside Proj_R 2355 2396 // warning : nFORMS(n) is created in the way, together with nFORMS(ndegX) … … 2384 2425 // the procedure is supposed to be called inside the ring Proj_R and 2385 2426 // assumes that the forms nFORMS(n) are previously computed 2386 // the output is a matrix whose rows are the coordinates in nFORMS(n) of such a basis 2427 // the output is a matrix whose rows are the coordinates in nFORMS(n) of 2428 // such a basis 2387 2429 // remark : the support of D may contain "extra" places 2388 2430 def BR=basering; … … 2596 2638 for (i=1;i<=k;i=i+1) 2597 2639 { 2598 // in this case D[NPls+i]>0 is assumed to be true during the BrillNoether algorithm 2640 // in this case D[NPls+i]>0 is assumed to be true during the 2641 // BrillNoether algorithm 2599 2642 RR=D[NPls+i]; 2600 2643 setring aff_r; … … 2682 2725 // computes the intersection number of h and the curve CHI at a certain place 2683 2726 // returns a list with the intersection number and the "leading coefficient" 2684 // the procedure must be called inside a local ring, h must be a local equation 2685 // with respect to the desired place, and m indicates the number of place 2686 // inside that local ring, containing lists POINT(S)/BRANCH(ES)/PARAMETRIZATION(S) 2687 // when m=0 an "extra place" is considered 2727 // the procedure must be called inside a local ring, h must be a local 2728 // equation with respect to the desired place, and m indicates the 2729 // number of place inside that local ring, containing lists 2730 // POINT(S)/BRANCH(ES)/PARAMETRIZATION(S) when m=0 an "extra place" is 2731 // considered 2688 2732 def BR=basering; 2689 2733 if (m>0) … … 2749 2793 static proc extra_place (ideal P) 2750 2794 { 2751 // computes the "rational" place which is defined over a (closed) "extra" point 2795 // computes the "rational" place which is defined over a (closed) "extra" 2796 // point 2752 2797 // an "extra" point will be necessarily affine, nonsingular and nonrational 2753 2798 // creates : a specific local ring to deal with the (unique) place above it … … 2758 2803 poly aux=subst(P[2],y,1); 2759 2804 ext=ext*deg(aux); 2760 // P is assumed to be a std. resp. "(x,y),lp" and thus P[1] depends only on "y" 2805 // P is assumed to be a std. resp. "(x,y),lp" and thus P[1] depends only 2806 // on "y" 2761 2807 if (deg(P[1])==1) 2762 2808 { 2763 // the point is nonrational but the second component needs no field extension 2809 // the point is nonrational but the second component needs no field 2810 // extension 2764 2811 number B=number(subst(P[1],y,0)); 2765 2812 poly aux2=subst(P[2],y,B); … … 2832 2879 for (j=1;j<=n;j=j+1) 2833 2880 { 2834 Maux[i,j]=importdatum(HNEring,"L@HNE[1]["+string(i)+","+string(j)+"]",newa); 2881 Maux[i,j]=importdatum(HNEring,"L@HNE[1]["+string(i)+","+ 2882 string(j)+"]",newa); 2835 2883 } 2836 2884 } … … 2853 2901 2854 2902 static proc intersection_div (poly H,list CURVE) 2855 "USAGE: intersection_div(H,CURVE), where H is a homogeneous polynomial in ring 2856 Proj_R=p,(x,y,z),lp and CURVE is the list of data for the given curve 2903 "USAGE: intersection_div(H,CURVE), where H is a homogeneous polynomial 2904 in ring Proj_R=p,(x,y,z),lp and CURVE is the list of data for 2905 the given curve 2857 2906 CREATE: new places which had not been computed in advance if necessary 2858 those places are stored each one in a local ring where you find lists2859 POINT,BRANCH,PARAMETRIZATION for the place living in that ring;2860 the degree of the point/place in such a ring is stored in an intvec,2861 an d the base points in the remaining list2862 Everything is exported in a list @EXTRA@ inside the ring aff_r=CURVE[1][1]2863 a nd returned with the updated CURVE2864 RETURN: list with the intersection divisor (intvec) between the underlying curve2865 and H=0, and the list CURVE updated2907 those places are stored each one in a local ring where you find 2908 lists POINT,BRANCH,PARAMETRIZATION for the place living in that 2909 ring; the degree of the point/place in such a ring is stored in 2910 an intvec, and the base points in the remaining list 2911 Everything is exported in a list @EXTRA@ inside the ring 2912 aff_r=CURVE[1][1] and returned with the updated CURVE 2913 RETURN: list with the intersection divisor (intvec) between the underlying 2914 curve and H=0, and the list CURVE updated 2866 2915 SEE ALSO: Adj_div, NSplaces, closed_points 2867 NOTE: The procedure must be called from the ring Proj_R=CURVE[1][2] (projective) 2868 If @EXTRA@ already exists, the new places are added to the previous data 2916 NOTE: The procedure must be called from the ring Proj_R=CURVE[1][2] 2917 (projective). 2918 If @EXTRA@ already exists, the new places are added to the 2919 previous data. 2869 2920 " 2870 2921 { 2871 2922 // computes the intersection divisor of H and the curve CHI 2872 // returns a list with (possibly) "extra places" and it must be called inside Proj_R 2873 // in case of extra places, some local rings ES(1) ... ES(m) are created together 2874 // with an integer list "extra_dgs" containing the degrees of those places 2923 // returns a list with (possibly) "extra places" and it must be called 2924 // inside Proj_R 2925 // in case of extra places, some local rings ES(1) ... ES(m) are created 2926 // together with an integer list "extra_dgs" containing the degrees of 2927 // those places 2875 2928 intvec opgt=option(get); 2876 2929 option(redSB); … … 2904 2957 if (Tz3==0) 2905 2958 { 2906 // if this still does not work > try always with ALL points in Inf_Points !!!! 2959 // if this still does not work > try always with ALL points in 2960 // Inf_Points !!!! 2907 2961 poly Hinf=subst(H,z,0); 2908 2962 setring aff_r; 2909 // compute the points at infinity of H and see which of them are in Inf_Points 2963 // compute the points at infinity of H and see which of them are in 2964 // Inf_Points 2910 2965 poly h=imap(BRing,h); 2911 2966 poly hinf=imap(BRing,Hinf); … … 2954 3009 else 2955 3010 { 2956 // H is a multiple of z and hence all the points in Inf_Points intersect with H 3011 // H is a multiple of z and hence all the points in Inf_Points intersect 3012 // with H 2957 3013 setring aff_r; 2958 3014 poly h=imap(BRing,h); … … 3123 3179 static proc local_eq (poly H,SS,int m) 3124 3180 { 3125 // computes a local equation of poly H in the ring SS related to the place "m" 3181 // computes a local equation of poly H in the ring SS related to the place 3182 // "m" 3126 3183 // list POINT/POINTS is searched depending on wether m=0 or m>0 respectively 3127 // warning : the procedure must be called from ring "Proj_R" and returns a string 3184 // warning : the procedure must be called from ring "Proj_R" and returns a 3185 // string 3128 3186 def BRing=basering; 3129 3187 setring SS; … … 3164 3222 static proc min_wt_rmat (matrix M) 3165 3223 { 3166 // finds the row of M with minimum nonzero entries, i.e. minimum "Hammingweight" 3224 // finds the row of M with minimum nonzero entries, i.e. minimum 3225 // "Hammingweight" 3167 3226 int m=nrows(M); 3168 3227 int n=ncols(M); … … 3198 3257 3199 3258 3200 // ============================================================================ =3201 // ******* *MAIN PROCEDURE : the BrillNoether algorithm ********3202 // ============================================================================ =3259 // ============================================================================ 3260 // ******* MAIN PROCEDURE : the BrillNoether algorithm ******** 3261 // ============================================================================ 3203 3262 3204 3263 3205 3264 proc BrillNoether (intvec G,list CURVE) 3206 "USAGE: BrillNoether( intvec_expression, list_expression ) 3207 3208 TYPE: list 3209 3210 PURPOSE: @code{BrillNoether(G,CURVE);} computes a vector basis of the linear 3211 system L(G), where G is a given rational divisor over a nonsingular 3212 curve. 3213 3214 CREATE: list of ideals (each of them with two homogeneous generators, which 3215 represent the nominator, resp. denominator, of a rational function). 3216 3217 NOTE: The procedure must be called from the ring CURVE[1][2], where CURVE is 3218 the output of the procedure @code{NSplaces}. @* 3265 "USAGE: BrillNoether(G,CURVE), where G is an intvec and CURVE is a list 3266 3267 RETURN: list of ideals (each of them with two homogeneous generators, 3268 which represent the nominator, resp. denominator, of a rational 3269 function).@* 3270 The corresponding rational functions form a vector basis of the 3271 linear system L(G), G a rational divisor over a nonsingular curve. 3272 3273 NOTE: The procedure must be called from the ring CURVE[1][2], where 3274 CURVE is the output of the procedure @code{NSplaces}. @* 3219 3275 The intvec G represents a rational divisor supported on the closed 3220 3276 places of CURVE[3] (e.g. @code{G=2,0,1;} means 2 times the closed … … 3331 3387 3332 3388 3333 // ******** procedures for dealing with "RATIONAL FUNCTIONS" over a plane curve ******** 3334 // a rational function F may be given by (homogeneous) ideal or (affine) poly (or number) 3389 // *** procedures for dealing with "RATIONAL FUNCTIONS" over a plane curve *** 3390 // a rational function F may be given by (homogeneous) ideal or (affine) poly 3391 // (or number) 3335 3392 3336 3393 … … 3349 3406 { 3350 3407 // simplifies a rational function f/g extracting the gcd(f,g) 3351 // maybe add a "restriction" to the curve "CHI" but it is not easy to programm 3408 // maybe add a "restriction" to the curve "CHI" but it is not easy to 3409 // programm 3352 3410 poly auxp=gcd(F[1],F[2]); 3353 3411 return(ideal(division(auxp,F)[1])); … … 3357 3415 static proc sumRF (F,G) 3358 3416 { 3359 // sum of two "rational functions" F,G given by either a pair numerator/denominator or a poly 3417 // sum of two "rational functions" F,G given by either a pair 3418 // nominator/denominator or a poly 3360 3419 if ( typeof(F)=="ideal" && typeof(G)=="ideal" ) 3361 3420 { … … 3431 3490 3432 3491 static proc orderRF (ideal F,SS,int m) 3433 "USAGE: orderRF(F,SS,m), where F is an ideal, SS is a ring and m is an integer 3492 "USAGE: orderRF(F,SS,m), where F is an ideal, SS is a ring and m is an 3493 integer 3434 3494 RETURN: list with the order (int) and the leading coefficient (number) 3435 NOTE: F represents a rational function, thus the procedure must be called from R or R(d) 3436 SS contains the name of a local ring where rational places are stored, and then 3437 we take that which is in position m in the corresponding lists of data 3438 The order of F at the place given by SS,m is returned together with the 3439 coefficient of minimum degree in the corresponding power series 3495 NOTE: F represents a rational function, thus the procedure must be 3496 called from R or R(d). 3497 SS contains the name of a local ring where rational places are 3498 stored, and then we take that which is in position m in the 3499 corresponding lists of data. 3500 The order of F at the place given by SS,m is returned together 3501 with the coefficient of minimum degree in the corresponding power 3502 series. 3440 3503 " 3441 3504 { 3442 3505 // computes the order of a rational function F at a RATIONAL place given by 3443 3506 // a local ring SS and a position "m" inside SS 3444 // warning : the procedure must be called from global projective ring "R" or "R(i)" 3507 // warning : the procedure must be called from global projective ring "R" or 3508 // "R(i)" 3445 3509 // returns a list with the order (int) and the "leading coefficient" (number) 3446 3510 def BR=basering; … … 3462 3526 3463 3527 3464 // ============================================================================ =3528 // ============================================================================ 3465 3529 3466 3530 3467 3531 proc Weierstrass (int P,int m,list CURVE) 3468 "USAGE: Weierstrass( int_expression, int_expression, list_expression ) 3469 3470 TYPE: list 3471 3472 PURPOSE: compute the Weierstrass semigroup up to a given bound and the 3473 associated rational functions 3474 3475 CREATE: @code{Weierstrass(i,m,CURVE);} returns a list WS of two lists: 3476 @format 3477 WS[1] is a list of integers (the Weierstrass semigroup of the 3478 curve at the place i up to m) 3479 WS[2] is a list of ideals (the associated rational functions) 3480 @end format 3481 3482 NOTE: The procedure must be called from the ring @code{CURVE[1][2]}, 3483 where @code{CURVE} is the output of the procedure @code{NSplaces}. 3484 @code{i} represents the place @code{CURVE[3][i]}. 3532 "USAGE: Weierstrass( i, m, CURVE ), where i,m are integers and CURVE a list 3533 3534 RETURN: list WS of two lists: 3535 @format 3536 WS[1] is a list of integers (the Weierstrass semigroup of the curve 3537 at the place i up to m) 3538 WS[2] is a list of ideals (the associated rational functions) 3539 @end format 3540 3541 3542 NOTE: The procedure must be called from the ring CURVE[1][2], 3543 where CURVE is the output of the procedure @code{NSplaces}. 3544 i represents the place CURVE[3][i]. 3485 3545 3486 3546 WARNING: the place must be rational, i.e., necessarily 3487 @code{CURVE[3][P][1]=1}.3547 CURVE[3][P][1]=1. 3488 3548 3489 3549 Rational functions are represented by nominator/denominator … … 3496 3556 { 3497 3557 // computes the Weierstrass semigroup at a RATIONAL place P up to a bound "m" 3498 // together with the functions achieving each value up to m, via BrillNoether 3499 // returns 2 lists : the first consists of all the poles up to m in increasing order 3500 // and the second consists of the corresponging rational functions 3558 // together with the functions achieving each value up to m, via 3559 // BrillNoether 3560 // returns 2 lists : the first consists of all the poles up to m in 3561 // increasing order and the second consists of the corresponging rational 3562 // functions 3501 3563 list Places=CURVE[3]; 3502 3564 intvec pl=Places[P]; … … 3505 3567 if (dP<>1) 3506 3568 { 3507 print("? error : the given place is not defined over the prime field"); 3508 return(); 3569 ERROR("the given place is not defined over the prime field"); 3509 3570 } 3510 3571 if (m<=0) … … 3524 3585 else 3525 3586 { 3526 print("? error : second argument must be nonnegative"); 3527 return(); 3587 ERROR("second argument must be nonnegative"); 3528 3588 } 3529 3589 } … … 3568 3628 if (polLmP[lmPi+1k]==maxpol) 3569 3629 { 3570 LmP[lmPi+1k]=sumRF(LmP[lmPi+1k],negRF(escprodRF(ordLmP[lmPi+1k][2]/ordLmP[lmPi+1][2],LmP[lmPi+1]))); 3630 LmP[lmPi+1k]=sumRF(LmP[lmPi+1k],negRF(escprodRF( 3631 ordLmP[lmPi+1k][2]/ordLmP[lmPi+1][2],LmP[lmPi+1]))); 3571 3632 } 3572 3633 else … … 3600 3661 3601 3662 3602 // ============================================================================ =3663 // ============================================================================ 3603 3664 3604 3665 … … 3607 3668 3608 3669 proc permute_L (L,P) 3609 "USAGE: permute_L( intvec_expression, intvec_expression ) 3610 permute_L( intvec_expression, list_expression ) 3611 permute_L( list_expression, intvec_expression ) 3612 permute_L( list_expression, list_expression ) 3613 3614 TYPE: list 3615 3616 PURPOSE: apply a permutation to an intvec/list 3617 3618 CREATE: @code{permute_L(L,P);} returns a list obtained from @code{L} by 3619 applying the permutation given by @code{P}. 3670 "USAGE: permute_L( L, P ), where L,P are either intvecs or lists 3671 3672 RETURN: list obtained from L by applying the permutation given by P. 3620 3673 3621 3674 NOTE: If P is a list, all entries must be integers. … … 3626 3679 " 3627 3680 { 3628 // permutes the list L according to the permutation P (both intvecs or lists of integers) 3681 // permutes the list L according to the permutation P (both intvecs or 3682 // lists of integers) 3629 3683 int s=size(L); 3630 3684 int n=size(P); … … 3660 3714 3661 3715 static proc evalRF (ideal F,SS,int m) 3662 "USAGE: evalRF(F,SS,m), where F is an ideal, SS is a ring and m is an integer 3663 RETURN: the evaluation (number) of F at the place given by SS,m if it is welldefined 3664 NOTE: F represents a rational function, thus the procedure must be called from R or R(d) 3665 SS contains the name of a local ring where rational places are stored, and then 3666 we take that which is in position m in the corresponding lists of data 3716 "USAGE: evalRF(F,SS,m), where F is an ideal, SS is a ring and m is an 3717 integer 3718 RETURN: the evaluation (number) of F at the place given by SS,m if it is 3719 welldefined 3720 NOTE: F represents a rational function, thus the procedure must be 3721 called from R or R(d). 3722 SS contains the name of a local ring where rational places are 3723 stored, and then we take that which is in position m in the 3724 corresponding lists of data. 3667 3725 " 3668 3726 { … … 3683 3741 else 3684 3742 { 3685 print("? error : the function is not welldefined at the given place"); 3686 return(); 3743 ERROR("the function is not welldefined at the given place"); 3687 3744 } 3688 3745 } … … 3721 3778 3722 3779 3723 // ============================================================================ =3780 // ============================================================================ 3724 3781 3725 3782 3726 3783 proc dual_code (matrix G) 3727 "USAGE: dual_code( matrix_expression ) 3728 3729 TYPE: matrix 3730 3731 PURPOSE: compute a generator matrix of the dual code 3784 "USAGE: dual_code(G), where G is a matrix of numbers 3785 3786 RETURN: a generator matrix of the dual code generated by G. 3732 3787 3733 3788 NOTE: The input should be a matrix G of numbers. @* … … 3839 3894 3840 3895 3841 // ============================================================================ =3896 // ============================================================================ 3842 3897 3843 3898 3844 3899 proc AGcode_L (intvec G,intvec D,list EC) 3845 "USAGE: AGcode_L( intvec_expression, intvec_expression, list_expression ) 3846 3847 TYPE: matrix 3848 3849 PURPOSE: @code{AGcode_L(G,D,EC)} computes a generator matrix for the 3850 evaluation AG code defined by the divisors G and D. 3851 3852 NOTE: The procedure must be called within the ring @code{EC[1][4]}, 3853 where @code{EC} is the output of @code{extcurve(d)} (or within 3854 the ring @code{EC[1][2]} if d=1). @* 3855 The entry i in the intvec @code{D} refers to the ith rational 3856 place in @code{EC[1][5]} (i.e., to @code{POINTS[i]}, etc., see 3857 @ref{extcurve}).@* 3858 The intvec @code{G} represents a rational divisor (see 3859 @ref{BrillNoether} for more details).@* 3900 "USAGE: AGcode_L( G, D, EC ), where G,D are intvec and EC is a list 3901 3902 RETURN: a generator matrix for the evaluation AG code defined by the 3903 divisors G and D. 3904 3905 NOTE: The procedure must be called within the ring EC[1][4], 3906 where EC is the output of @code{extcurve(d)} (or within 3907 the ring EC[1][2] if d=1). @* 3908 The entry i in the intvec D refers to the ith rational 3909 place in EC[1][5] (i.e., to POINTS[i], etc., see @ref{extcurve}).@* 3910 The intvec G represents a rational divisor (see @ref{BrillNoether} 3911 for more details).@* 3860 3912 The code evaluates the vector basis of L(G) at the rational 3861 3913 places given by D. … … 3871 3923 { 3872 3924 // returns a generator matrix for the evaluation AG code given by G and D 3873 // G must be a divisor defined over the prime field and D an intvec of "rational places" 3925 // G must be a divisor defined over the prime field and D an intvec of 3926 // "rational places" 3874 3927 // it must be called inside R or R(d) and requires previously "extcurve(d)" 3875 3928 def BR=basering; 3876 3929 if (disj_divs(G,D,EC)==0) 3877 3930 { 3878 print("? the divisors do not have disjoint supports, 0matrix returned"); 3931 dbprint(printlevel+3,"? the divisors do not have disjoint supports, 3932 0matrix returned ?"); 3879 3933 matrix answer; 3880 3934 return(answer); … … 3917 3971 // let us construct the corresponding evaluation AG code : 3918 3972 matrix C=AGcode_L(G,D,HC); 3919 // here is a linear code of type [8,5,>=3] over F_ 83973 // here is a linear code of type [8,5,>=3] over F_4 3920 3974 print(C); 3921 3975 printlevel=plevel; … … 3927 3981 3928 3982 proc AGcode_Omega (intvec G,intvec D,list EC) 3929 "USAGE: AGcode_Omega( intvec_expression, intvec_expression, list_expression ) 3930 3931 TYPE: matrix 3932 3933 PURPOSE: @code{AGcode_Omega(G,D,EC)} computes a generator matrix for the 3934 residual AG code defined by the divisors G and D. 3935 3936 NOTE: The procedure must be called within the ring @code{EC[1][4]}, 3937 where @code{EC} is the output of @code{extcurve(d)} (or within 3938 the ring @code{EC[1][2]} if d=1). @* 3939 The entry i in the intvec @code{D} refers to the ith rational place 3940 in @code{EC[1][5]} (i.e., to @code{POINTS[i]}, etc., see 3941 @ref{extcurve}).@* 3942 The intvec @code{G} represents a rational divisor (see 3943 @ref{BrillNoether} for more details).@* 3983 "USAGE: AGcode_Omega( G, D, EC ), where G,D are intvec and EC is a list 3984 3985 RETURN: a generator matrix for the residual AG code defined by the 3986 divisors G and D. 3987 3988 NOTE: The procedure must be called within the ring EC[1][4], 3989 where EC is the output of @code{extcurve(d)} (or within 3990 the ring EC[1][2] if d=1). @* 3991 The entry i in the intvec D refers to the ith rational 3992 place in EC[1][5] (i.e., to POINTS[i], etc., see @ref{extcurve}).@* 3993 The intvec G represents a rational divisor (see @ref{BrillNoether} 3994 for more details).@* 3944 3995 The code computes the residues of a vector space basis of 3945 3996 @math{\Omega(GD)} at the rational places given by D. 3946 3997 3947 WARNINGS: G should satisfy @math{ 2*genus2 < deg(G) < size(D) }, which is not3948 checked by the algorithm.3998 WARNINGS: G should satisfy @math{ 2*genus2 < deg(G) < size(D) }, which is 3999 not checked by the algorithm. 3949 4000 G and D should have disjoint supports (checked by the algorithm). 3950 4001 … … 3955 4006 { 3956 4007 // returns a generator matrix for the residual AG code given by G and D 3957 // G must be a divisor defined over the prime field and D an intvec or "rational places" 4008 // G must be a divisor defined over the prime field and D an intvec or 4009 // "rational places" 3958 4010 // it must be called inside R or R(d) and requires previously "extcurve(d)" 3959 4011 return(dual_code(AGcode_L(G,D,EC))); … … 3975 4027 // let us construct the corresponding residual AG code : 3976 4028 matrix C=AGcode_Omega(G,D,HC); 3977 // here is a linear code of type [8,3,>=5] over F_ 84029 // here is a linear code of type [8,3,>=5] over F_4 3978 4030 print(C); 3979 4031 printlevel=plevel; … … 3981 4033 3982 4034 3983 // ============================================================================ =3984 // ******* *auxiliary procedure to define AG codes over extensions ********3985 // ============================================================================ =4035 // ============================================================================ 4036 // ******* auxiliary procedure to define AG codes over extensions ******** 4037 // ============================================================================ 3986 4038 3987 4039 3988 4040 proc extcurve (int d,list CURVE) 3989 "USAGE: extcurve( int_expression, list_expression ) 3990 3991 TYPE: list 3992 3993 PURPOSE: create local rings over field extensions in order to have 3994 sufficiently many rational places (as needed for the construction 3995 of AG codes). 3996 3997 CREATE: If @code{d}>1 then @code{extcurve(d,CURVE);} creates a list L which 3998 is the update of the list @code{CURVE} with additional entries 4041 "USAGE: extcurve( d, CURVE ), where d is an integer and CURVE is a list 4042 4043 RETURN: list L which is the update of the list CURVE with additional 4044 entries 3999 4045 @format 4000 4046 L[1][3]: ring (p,a),(x,y),lp (affine), … … 4003 4049 L[2][3]: int (the number of rational places), 4004 4050 @end format 4005 the rings being defined over a field extension of degree @code{d}.4006 4007 If @code{d}<2 then @code{extcurve(d,CURVE);} creates a list L which4008 is the update of the list @code{CURVE}with additional entries4051 the rings being defined over a field extension of degree d. 4052 4053 If d<2 then @code{extcurve(d,CURVE);} creates a list L which 4054 is the update of the list CURVE with additional entries 4009 4055 @format 4010 4056 L[1][5]: ring p,(x,y,t),ls, … … 4012 4058 @end format 4013 4059 In both cases, in the ring L[1][5] lists with the data for all the 4014 rational places (after a field extension of degree @code{d}) are4060 rational places (after a field extension of degree d) are 4015 4061 created (see @ref{Adj_div}): 4016 4062 @format … … 4018 4064 @end format 4019 4065 4020 NOTE: The list_expression @code{CURVE} should be the output of 4021 @code{NSplaces} and has to contain (at least) all places up to 4022 degree @code{d}. @* 4066 NOTE: The list CURVE should be the output of @code{NSplaces} and has 4067 to contain (at least) all places up to degree d. @* 4023 4068 This procedure must be executed before constructing AG codes, 4024 4069 even if no extension is needed. The ring L[1][4] must be active … … 4030 4075 " 4031 4076 { 4032 // extends the underlying curve and all its associated objects to a larger base field 4033 // in order to evaluate points over such a extension 4034 // if d<2 then the only change is that a local ring "RatPl" (which is a copy of "S(1)") 4035 // is created in order to store the rational places where we can do evaluations 4036 // otherwise, such a ring contains all places which are rational over the extension 4037 // warning : list Places does not change so that only divisors which are "rational over 4038 // the prime field" are allowed; this probably will change in the future 4039 // warning : the places in RatPl are ranged in increasing degree, respecting the order 4040 // from list Places and placing the conjugate branches all together 4077 // extends the underlying curve and all its associated objects to a larger 4078 // base field in order to evaluate points over such a extension 4079 // if d<2 then the only change is that a local ring "RatPl" (which is a 4080 // copy of "S(1)") is created in order to store the rational places 4081 // where we can do evaluations 4082 // otherwise, such a ring contains all places which are rational over the 4083 // extension 4084 // warning : list Places does not change so that only divisors which are 4085 // "rational over the prime field" are allowed; this probably will 4086 // change in the future 4087 // warning : the places in RatPl are ranged in increasing degree, respecting 4088 // the order from list Places and placing the conjugate branches all 4089 // together 4041 4090 def BR=basering; 4042 4091 list ext_CURVE=CURVE; … … 4101 4150 LOC_EQS=insert(LOC_EQS,Frobenius(LOC_EQS[piv],1),counter); 4102 4151 BRANCHES=insert(BRANCHES,conj_b(BRANCHES[piv],1),counter); 4103 PARAMETRIZATIONS=insert(PARAMETRIZATIONS,Frobenius(PARAMETRIZATIONS[piv],1),counter); 4152 PARAMETRIZATIONS=insert(PARAMETRIZATIONS,Frobenius( 4153 PARAMETRIZATIONS[piv],1),counter); 4104 4154 counter=counter+1; 4105 4155 piv=counter; … … 4122 4172 counter=0; 4123 4173 POINTS=insert(POINTS,list(),0); 4124 POINTS[1][1]=number(importdatum(S(i),"POINTS["+string(j)+"][1]",olda)); 4125 POINTS[1][2]=number(importdatum(S(i),"POINTS["+string(j)+"][2]",olda)); 4126 POINTS[1][3]=number(importdatum(S(i),"POINTS["+string(j)+"][3]",olda)); 4127 LOC_EQS=insert(LOC_EQS,importdatum(S(i),"LOC_EQS["+string(j)+"]",olda),0); 4174 POINTS[1][1]=number(importdatum(S(i),"POINTS["+string(j) 4175 +"][1]",olda)); 4176 POINTS[1][2]=number(importdatum(S(i),"POINTS["+string(j) 4177 +"][2]",olda)); 4178 POINTS[1][3]=number(importdatum(S(i),"POINTS["+string(j) 4179 +"][3]",olda)); 4180 LOC_EQS=insert(LOC_EQS,importdatum(S(i),"LOC_EQS["+string(j) 4181 +"]",olda),0); 4128 4182 BRANCHES=insert(BRANCHES,list(),0); 4129 4183 setring S(i); … … 4144 4198 for (jj=1;jj<=n;jj=jj+1) 4145 4199 { 4146 Maux[ii,jj]=importdatum(S(i),"BRANCHES["+string(j)+"][1]["+string(ii)+","+string(jj)+"]",olda); 4200 Maux[ii,jj]=importdatum(S(i),"BRANCHES["+string(j) 4201 +"][1]["+string(ii)+","+string(jj)+"]",olda); 4147 4202 } 4148 4203 } … … 4166 4221 LOC_EQS=insert(LOC_EQS,Frobenius(LOC_EQS[piv],1),counter); 4167 4222 BRANCHES=insert(BRANCHES,conj_b(BRANCHES[piv],1),counter); 4168 PARAMETRIZATIONS=insert(PARAMETRIZATIONS,Frobenius(PARAMETRIZATIONS[piv],1),counter); 4223 PARAMETRIZATIONS=insert(PARAMETRIZATIONS,Frobenius( 4224 PARAMETRIZATIONS[piv],1),counter); 4169 4225 } 4170 4226 setring S(i); … … 4196 4252 ext_CURVE[1][4]=R(d); 4197 4253 dbprint(printlevel+1,""); 4198 dbprint(printlevel+2,"Total number of rational places : NrRatPl = "+string(NrRatPl)); 4254 dbprint(printlevel+2,"Total number of rational places : NrRatPl = " 4255 +string(NrRatPl)); 4199 4256 dbprint(printlevel+1,""); 4200 4257 return(ext_CURVE); … … 4202 4259 else 4203 4260 { 4204 print("? error :you must compute first all the places up to degree "+string(d));4261 ERROR("you must compute first all the places up to degree "+string(d)); 4205 4262 return(); 4206 4263 } … … 4226 4283 4227 4284 static proc Hamming_wt (matrix A) 4228 "USAGE: 4285 "USAGE: Hamming_wt(A), where A is any matrix 4229 4286 RETURN: the Hamming weight (number of nonzero entries) of the matrix A 4230 4287 " … … 4232 4289 // computes the Hamming weight (number of nonzero entries) of any matrix 4233 4290 // notice that "words" are represented by matrices of size 1xn 4234 // computing the Hamming distance between two matrices can be done by Hamming_wt(AB) 4291 // computing the Hamming distance between two matrices can be done by 4292 // Hamming_wt(AB) 4235 4293 int m=nrows(A); 4236 4294 int n=ncols(A); … … 4252 4310 4253 4311 // Basic Algorithm of Skorobogatov and Vladut for decoding AG codes 4254 // warning : the user must choose carefully the parameters for the code and the decoding4255 // since they will never be checked by the procedures4256 4257 4258 // ============================================================================ =4312 // warning : the user must choose carefully the parameters for the code and 4313 // the decoding since they will never be checked by the procedures 4314 4315 4316 // ============================================================================ 4259 4317 4260 4318 4261 4319 proc prepSV (intvec G,intvec D,intvec F,list EC) 4262 "USAGE: prepSV( intvec_expression, intvec_expression, intvec_expression, list_expression ) 4263 4264 TYPE: list 4265 4266 PURPOSE: preprocessing for the basic (SkorobogatovVladut) decoding 4267 algorithm 4268 4269 CREATE: @code{prepSV(G,D,F,EC);} returns a list E of size n+3, where 4270 n=size(D). All its entries but E[n+3] are matrices: 4320 "USAGE: prepSV( G, D, F, EC ), where G,D,F are intvec and EC is a list 4321 4322 RETURN: list E of size n+3, where n=size(D). All its entries but E[n+3] 4323 are matrices: 4271 4324 @format 4272 4325 E[1]: parity check matrix for the current AG code … … 4277 4330 @end format 4278 4331 4279 NOTE: The procedure must be called within the ring @code{EC[1][4]}, 4280 where @code{EC} is the output of @code{extcurve(d)} (or within 4281 the ring @code{EC[1][2]} if d=1). @* 4282 The intvec @code{G} and @code{F} represent rational divisors (see 4332 NOTE: Computes the preprocessing for the basic (SkorobogatovVladut) 4333 decoding algorithm.@* 4334 The procedure must be called within the ring EC[1][4], 4335 where EC is the output of @code{extcurve(d)} (or within 4336 the ring EC[1][2] if d=1). @* 4337 The intvec G and F represent rational divisors (see 4283 4338 @ref{BrillNoether} for more details).@* 4284 The intvec @code{D}refers to rational places (see @ref{AGcode_Omega}4339 The intvec D refers to rational places (see @ref{AGcode_Omega} 4285 4340 for more details.). 4286 4341 The current AG code is @code{AGcode_Omega(G,D,EC)}.@* … … 4291 4346 keep it during the decoding, you must previously permute D (using 4292 4347 @code{permute_L(D,P);}), e.g., according to the permutation 4293 @code{P}=L[3], L being the output of @code{sys_code}.4348 P=L[3], L being the output of @code{sys_code}. 4294 4349 4295 4350 WARNINGS: F must be a divisor with support disjoint to the support of D and … … 4298 4353 G should satisfy @math{ 2*genus2 < deg(G) < size(D) }, which is 4299 4354 not checked by the algorithm. 4300 G and D should also have disjoint supports (checked by the algorithm). 4355 G and D should also have disjoint supports (checked by the 4356 algorithm). 4301 4357 4302 4358 KEYWORDS: SVdecoding algorithm, preprocessing … … 4309 4365 if (disj_divs(F,D,EC)==0) 4310 4366 { 4311 print("? the divisors do not have disjoint supports, empty list returned"); 4367 dbprint(printlevel+3,"? the divisors do not have disjoint supports, 4368 empty list returned ?"); 4312 4369 return(list()); 4313 4370 } … … 4319 4376 if (e<1) 4320 4377 { 4321 print("? error : the correction capacity of the basic algorithm is zero"); 4378 dbprint(printlevel+3,"? the correction capacity of the basic algorithm 4379 is zero, empty list returned ?"); 4322 4380 return(list()); 4323 4381 } 4324 // deg(F)==e+genusX should be satisfied, and sup(D),sup(F) should be disjoint !!!! 4382 // deg(F)==e+genusX should be satisfied, and sup(D),sup(F) should be 4383 // disjoint !!!! 4325 4384 int n=size(D); 4326 4385 // 2*genusX2<m<n should also be satisfied !!!! … … 4363 4422 // we already have a rational divisor G and 8 more points over F_4; 4364 4423 // let us construct the corresponding residual AG code of type 4365 // [8,3,>=5] over F_ 84424 // [8,3,>=5] over F_4 4366 4425 matrix C=AGcode_Omega(G,D,HC); 4367 4426 // we can correct 1 error and the genus is 1, thus F must have … … 4379 4438 4380 4439 4381 // ============================================================================ =4440 // ============================================================================ 4382 4441 4383 4442 4384 4443 proc decodeSV (matrix y,list K) 4385 "USAGE: decodeSV( matrix_expression, list_expression ) 4386 4387 TYPE: matrix 4388 4389 PURPOSE: basic (SkorobogatovVladut) decoding algorithm 4390 4391 CREATE: a codeword (rowmatrix) if possible, resp. the 0matrix (of size 1) if 4392 decoding is impossible 4444 "USAGE: decodeSV( y, K ), where y is a rowmatrix and K is a list 4445 4446 RETURN: a codeword (rowmatrix) if possible, resp. the 0matrix (of size 4447 1) if decoding is impossible. 4448 For decoding the basic (SkorobogatovVladut) decoding algorithm 4449 is applied. 4393 4450 4394 4451 NOTE: The list_expression should be the output K of the procedure 4395 4452 @code{prepSV}.@* 4396 The matrix_expression should be a (1xn)matrix, where n=ncols(K[1]).@* 4453 The matrix_expression should be a (1 x n)matrix, where 4454 n = ncols(K[1]).@* 4397 4455 The decoding may fail if the number of errors is greater than 4398 4456 the correction capacity of the algorithm. … … 4424 4482 if (Hamming_wt(Ky)==0) 4425 4483 { 4426 print("? : no errorlocator found");4427 print("? : too many errors occur");4484 dbprint(printlevel+3,"? no errorlocator found ?"); 4485 dbprint(printlevel+3,"? too many errors occur, 0matrix returned ?"); 4428 4486 matrix answer; 4429 4487 return(answer); … … 4479 4537 sol=(number(1)/number(pivote))*sol; 4480 4538 } 4481 // check at least that the number of comitted errors is less that half the Goppa distance 4482 // imposing Hamming_wt(sol)<=K[n+3][1] would be more correct, but maybe is too strong 4483 // on the other hand, if Hamming_wt(sol) is too large the decoding may not be acceptable 4539 // check at least that the number of comitted errors is less than half 4540 // the Goppa distance 4541 // imposing Hamming_wt(sol)<=K[n+3][1] would be more correct, but maybe 4542 // is too strong 4543 // on the other hand, if Hamming_wt(sol) is too large the decoding may 4544 // not be acceptable 4484 4545 if ( Hamming_wt(sol) <= (K[n+3][2]1)/2 ) 4485 4546 { … … 4489 4550 else 4490 4551 { 4491 print("? : nonacceptable decoding");4552 dbprint(printlevel+3,"? nonacceptable decoding ?"); 4492 4553 } 4493 4554 } 4494 4555 else 4495 4556 { 4496 print("? : no solution found");4557 dbprint(printlevel+3,"? no solution found ?"); 4497 4558 } 4498 4559 } 4499 4560 else 4500 4561 { 4501 print("? : nonunique solution");4562 dbprint(printlevel+3,"? nonunique solution ?"); 4502 4563 } 4503 4564 option(set,opgt); 4504 print("? : too many errors occur");4565 dbprint(printlevel+3,"? too many errors occur, 0matrix returned ?"); 4505 4566 matrix answer; 4506 4567 return(answer); … … 4521 4582 // we already have a rational divisor G and 8 more points over F_4; 4522 4583 // let us construct the corresponding residual AG code of type 4523 // [8,3,>=5] over F_ 84584 // [8,3,>=5] over F_4 4524 4585 matrix C=AGcode_Omega(G,D,HC); 4525 4586 // we can correct 1 error and the genus is 1, thus F must have … … 4536 4597 4537 4598 4538 // ============================================================================ =4599 // ============================================================================ 4539 4600 4540 4601 4541 4602 proc sys_code (matrix C) 4542 "USAGE: sys_code( matrix_expression ) 4543 4544 TYPE: list 4545 4546 PURPOSE: computes a systematic code which is equivalent to the given one 4547 4548 CREATE: list L with: 4603 "USAGE: sys_code(C) where C is a matrix of constants 4604 4605 RETURN: list L with: 4549 4606 @format 4550 4607 L[1] is the generator matrix in standard form of an equivalent code, … … 4553 4610 @end format 4554 4611 4555 NOTE: The input should be a matrix of numbers.@* 4612 NOTE: Computes a systematic code which is equivalent to the given one.@* 4613 The input should be a matrix of numbers.@* 4556 4614 The output has to be interpreted as follows: if the input was 4557 4615 the generator matrix of an AG code then one should apply the … … 4639 4697 if (r<m) 4640 4698 { 4641 print("? error : the given matrix does not have maximum rank"); 4642 return(list()); 4699 ERROR("the given matrix does not have maximum rank"); 4643 4700 } 4644 4701 // set the corners to the beginning and construct the permutation … … 4707 4764 4708 4765 4709 // ============================================================================ =4710 // ******* *ADDITIONAL INFORMATION ABOUT THE LIBRARY ********4711 // ============================================================================ =4766 // ============================================================================ 4767 // ******* ADDITIONAL INFORMATION ABOUT THE LIBRARY ******** 4768 // ============================================================================ 4712 4769 4713 4770 … … 4846 4903 4847 4904 4848 // ============================================================================ =4849 // *** *Some "macros" with typical examples of curves in Coding Theory ****4850 // ============================================================================ =4905 // ============================================================================ 4906 // *** Some "macros" with typical examples of curves in Coding Theory **** 4907 // ============================================================================ 4851 4908 4852 4909 … … 4867 4924 HERMITE=NSplaces(2*m1,HERMITE); 4868 4925 HERMITE=extcurve(2*m,HERMITE); 4869 dbprint(printlevel+1,"Hermitian curve over F_("+string(r)+"^2) successfully constructed"); 4926 dbprint(printlevel+1,"Hermitian curve over F_("+string(r)+"^2) 4927 successfully constructed"); 4870 4928 return(HERMITE); 4871 4929 } … … 4893 4951 list CURVE=Adj_div(y9+y8+xy6+x2y3+y2+x3); 4894 4952 CURVE=NSplaces(4,CURVE); 4895 CURVE=extcurve(6,CU rve);4953 CURVE=extcurve(6,CURVE); 4896 4954 4897 4955
Note: See TracChangeset
for help on using the changeset viewer.