IMPLEMENTATION OF SASBI BASIS ALGORITHMS IN
SINGULAR

We will give an overview of the main procedures which we have implemented
in SINGULAR. In this overview we will present these procedures and give by
concrete SINGULAR examples to explain their usage. We have implemented
three types of procedures:

1) Weak sasbi Normal form procedure

" WSNF procedure": It is an implementation of Algorithm 3 (ecart driven
normal form) to obtain weak sasbi normal form of a polynomial.
SINGULAR Procedure:

LIB"algebra.lib" ;// we need this library for "algebra containment"
// procedure

proc WSNF(poly f,ideal I)
{
 ideal G=I ;
 poly h=f ;
 poly h1,j ;
 list L ;
 map psi ;
 while(h!=0 && h1!=h)
 {
  L= algebra containment(lead(h),lead(G),1) ;
  if (L[1]==1)
  {
   def s= L[2] ;
   psi= s,maxideal(1),G ;
   j= psi(check) ;
   if (ecart(h)<ecart(j))
   {
    G[size(G)+1]=h ;
   }
   h1=h ;
   h=h-j ;
   kill s ;
  }
 }
return (h) ;

}

SINGULAR Example 1

ring r=0, (x,y), Ds ;
ideal i=x2,x4+x5+x6,x7,y2,y3+x8 ;
poly f=x4y3+y5 ;
WSNF(f, i) ;
=> x5y3-x6y3-x8y2-x12-x13-x14


ring r=0, (x), ls ; 
ideal i=x3+x4 ;
poly g=x3+x6, x-x2;
WSNF(g, i) ;
=> 0


2) Procedure to compute S-polynomials

"sasbiSpoly procedure": This procedure computes the generators of AR(G)
 which are S-polynomials.
SINGULAR Procedure:

LIB"elim.lib" ; // we need this library for "nselect" procedure

proc sasbiSpoly(ideal id)
{
 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)+"),(@y(1..m),"+varstr(bsr)+"),(ds(m),ds(n));");
  ideal id =imap(bsr,id) ;
  ideal A ;
  for (z=1; z<=m; z++)
  {
   A[z]=lead(id[z])-@y(z) ;
  }
  A=std(A) ;
  ideal kern=nselect(A,m+1,m+n) ;
  export kern,A ;
  setring bsr ;
  map phi= R1,id ;
  p=simplify(phi(kern),1) ;
  return (p) ;
 }
}

SINGULAR Example 2:

ring r=0, (x,y), Ds ;
ideal i=x2,x4+x5+x6,x7,y2,y3+x8 ;
sasbiSpoly(i);
[1]=x5+x6
[2]=x8y3+1/2x16

3) SASBI BASIS construction algorithm

"Sasbi procedure": It is an iterative consequence of previous procedures to
compute sasbi basis.

SINGULAR Procedure:

proc Sasbi(ideal id)
{
 ideal S,oldS,Red ;
 list L ;
 int z,n ;
 S=id ;
 while( size(S)!=size(oldS))
 {
  L=sasbiSpoly(S) ;
  n=size(L) ;
  for (z=1; z<=n; z++)
  {
   Red=L[1][z] ;
   Red=WSNF(Red[1],S) ;
   oldS=S ;
   S=S+Red ;
  }
 }
return(S) ;
}


SINGULAR Example 3:

ring r=0, (x,y), Ds ;

ideal i=x2,x4+x5+x6,x7,y2,y3+x8 ;
Sasbi(i);
[1]=x2
[2]=x4+x5+x6
[3]=x7
[4]=y2
[5]=y3+x8
[6]=x5+x6