////////// Procedures to Compute SH-bases of subalgebra///////// LIB "algebra.lib"; LIB"elim.lib"; //////////////////////////////////////////////// //// For a polynomial f, following procedure compute the maximal part of f. proc interm (poly g) "USAGE: interm(f); f polynomial. RETURN: a polynomial h. " { int n=deg(g); poly f=g; poly h; while (deg(f)==n) { h=h+f[1]; f=f-f[1]; } return(h); } //// SINGULAR Example // ring r= 0,(x,y),dp; // poly f= x3y+xy3+x2y+xy; // interm(f); // x3y+xy3 /////////////////////////////////////// ////// For the given set of generators, following procedure compute the maximal part of each generator. proc intermI (ideal I) "USAGE: intermI(I); I ideal. RETURN: an ideal j. " { ideal i=I; ideal j; int n,z; n=size(i); for (z=1;z<=n;z++) { j[z]=interm(i[z]); } return(j); } //// SINGULAR Example // ring r= 0,(x,y),dp; // ideal I= x3y+xy3+x2y+xy,x+y+1,xy+x2-y; // intermI(I); //_[1]=x3y+xy3 //_[2]=x+y //_[3]=x2+xy /////////////////////////// Procedure to compute iterative d-reduction (Algorithm 1)///////////////// //////////// For a polynomial f and a finite set of polynomials G, following procedure //////////// perform iterated d-reductions of f with respect to G. proc shred(poly f,ideal I) "USAGE: shred(f,I ); f polynomial, I ideal. RETURN: a polynomial h. " { ideal G=I; poly h=f; poly h1,j; list L; map psi; while(h!=0 && h1!=h) { L= algebra_containment(interm(h),intermI(G),1); h1=h; //change (to terminate) if (L[1]==1) { def s= L[2]; psi= s,maxideal(1),G; j= psi(check); h=h-j; kill s; } } return (h); } //// SINGULAR Example // ring r= 0,(x,y),dp; // poly f= x3y+xy3+x2y+xy; // ideal I=x2,y2,xy+y; // shred(f,I); // -y3+xy ///////////////////////////////////// /// For a finite set of polynomials G, following procedure Compute the < P_1(G),....P_m(G)> such that P_1,...P_m /// are the generators of the ideal of algberiac relations betweem the maximal part of the polynomial in G. proc shSpoly(ideal id) "USAGE: shSpoly(I); I ideal. RETURN: an ideal P ." { def bsr= basering ; ideal vars = maxideal(1) ; int n=nvars(bsr) ; int m=ncols(id) ; int z; ideal p; if(id==0) { return(p); } else { execute("ring R1=("+charstr(bsr)+"),("+varstr(bsr)+", @y(1..m)),(Dp(n),Dp(m)) ;") ; ideal id =imap(bsr,id) ; ideal A ; for (z=1;z<=m;z++) { A[z]= @y(z)-interm(id[z]) ; } A=std(A) ; ideal kern=nselect(A,1..n); setring bsr ; map phi= R1,vars,id; p=simplify(phi(kern),2) ; return (p); } } //// SINGULAR Example // ring r= 0,(x,y),dp; // ideal I=x2,y2,xy+y; // shSpoly(I); // _[1]=-2xy2-y2 /////////////////// SH-Basis Construction Algorithm (Algorithm 2)/////////////////////// /// For a given set of generators, following procedure compute the SH-basis of the subalgebra generated by G. proc sh(ideal id) "USAGE: sh(I); I ideal. RETURN: an ideal S." { ideal S,oldS,Red ; list L ; int z; int n; S=id ; while( size(S)!=size(oldS)) { L=shSpoly(S) ; n=size(L); for (z=1;z<=n;z++) { Red=L[1][z]; Red=shred(Red[1],S); //change2 (Red is not a poly) oldS=S ; S=S+Red ; } } return(S); } //// SINGULAR Example // ring r= 0,(x,y),dp; // ideal I=x2,y2,xy+y; // sh(I); // _[1]=x2 // _[2]=y2 // _[3]=xy+y // _[4]=-2xy2-y2 ///////////////////////// Partial SH-bases Construction/////////////////// /// For a given set of generators and integer c, following procedure compute the SH-basis of the subalgebra generated by G upto step c. proc shpart(ideal id, int c) "USAGE: sh(I,c); I ideal, integer c. RETURN: an ideal S." { ideal S,oldS,Red ; int counter; list L ; int z; int n; S=id ; while( size(S)!=size(oldS) && (counter<=c)) { L=shSpoly(S) ; n=size(L); for (z=1;z<=n;z++) { Red=L[1][z]; Red=shred(Red[1],S); //change2 (Red is not a poly) oldS=S ; S=S+Red ; counter=counter+1; } } return(S); } //// SINGULAR Example // ring r= 0,(x,y,z),dp; // ideal I=xz+y,xyz,xy2z; // shpart(I,3); //_[1]=xz+y //_[2]=xyz //_[3]=xy2z //_[4]=xy3z //_[5]=xy4z //_[6]=xy5z //_[7]=xy6z