Index: Singular/LIB/algebra.lib
===================================================================
--- Singular/LIB/algebra.lib	(revision de63d0a0a404b70806e92102e65c5461a0914009)
+++ Singular/LIB/algebra.lib	(revision 9050cae84ee67262b9d08045bac6f3b36c2cc66b)
@@ -1,8 +1,8 @@
 ///////////////////////////////////////////////////////////////////////////////
-version="$Id: algebra.lib,v 1.1 1999-07-19 14:54:07 obachman Exp $";
+version="$Id: algebra.lib,v 1.2 1999-07-26 13:41:33 Singular Exp $";
 info="
 LIBRARY:  algebra.lib   PROCEDURES FOR COMPUTING WITH ALGBRAS AND MAPS
-AUTHORS:  Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de
-          Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de
+AUTHORS:  Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de,
+          Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de,
           Gerhard Pfister, email: pfister@mathematik.uni-kl.de
 
@@ -11,13 +11,18 @@
  module_containment();  query of module containment over a subalgebra
  inSubring(p,I);        test whether poly p is in subring generated by I
- algDependence(I);      computes algebraic relations between generators of I
- alg_kernel(phi);           computes the kernel of the ringmap phi
+ algDependent(I);       computes algebraic relations between generators of I
+ alg_kernel(phi);       computes the kernel of the ringmap phi
  is_injective(phi);     test for injectivity of ringmap phi
  is_surjective(phi);    test for surjectivity of ringmap phi
  is_bijective(phi);     test for bijectivity of ring map phi
+ noetherNormal(id);     noether normalization of ideal id
+ mapIsFinite(R,phi,I);  query for finiteness of map phi:R --> basering/I
+ finitenessTest(i,z);   find variables which occur as pure power in lead(i)
 ";
 
  LIB "inout.lib";
  LIB "elim.lib";
+ LIB "ring.lib";
+ LIB "matrix.lib";
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -28,15 +33,15 @@
 RETURN:  - k=0 (or if k is not given) an integer:
            1    : if p is contained in the subalgebra K[A[1],...,A[m]]
-           0    : if p is not contained in K[A[1],...,A[m]] 
+           0    : if p is not contained in K[A[1],...,A[m]]
          - k=1: a list, say l, of size 2, l[1] integer, l[2] ring, satisfying
            l[1]=1 if p is in the subalgebra K[A[1],...,A[m]] and then the ring
-           l[2] contains the poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m])
+           l[2] contains poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m])
            l[1]=0 if p is in not the subalgebra K[A[1],...,A[m]] and then
-           l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies 
+           l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies
            the nonlinear relation p = h(x,A[1],...,A[m]) where
            x = x(1),...,x(n) denote the variables of the basering
 DISPLAY: if k=0, polynomial h(y(1),...,y(m)) if p=h(A[1],...,A[m]) is contained
          in the subalgebra, provided printlevel >= voice+1 (default)
-NOTE:    The proc inSubring uses a different algorithm which is sometimes faster
+NOTE:    The proc inSubring uses different algorithm which is sometimes faster
 THEORY:  The ideal of algebraic relations of the algebra generators A[1],...,
          A[m] is computed introducing new variables y(i) and the product
@@ -47,8 +52,8 @@
 "
 { int DEGB = degBound;
-  degBound = 0; 
+  degBound = 0;
     if (size(#)==0)
     { #[1] = 0;
-    }      
+    }
     def br=basering;
     int n = nvars(br);
@@ -68,5 +73,5 @@
     A=std(A);
     check=reduce(check,A);
-    /*alternatively we could use reduce(check,A,1) which is a little faster 
+    /*alternatively we could use reduce(check,A,1) which is a little faster
       but result is bigger since it is not tail-reduced
     */
@@ -74,5 +79,5 @@
   // if so, then the sum of the first n leading exponents is 0, hence i=1
   // use i also to control the display
-    i = (sum(leadexp(check),1..n)==0);   
+    i = (sum(leadexp(check),1..n)==0);
   degBound = DEGB;
     if( #[1] == 0 )
@@ -83,11 +88,11 @@
     { list l = i,R;
       kill A,vars,emb;
-      export check;       
+      export check;
       dbprint(printlevel-voice+3,"
-// 'algebra_containment' created a ring as 2nd element of the list. 
+// 'algebra_containment' created a ring as 2nd element of the list.
 // This ring contains the poly check which defines the algebraic relation.
 // To access to the ring and see check you must give the ring a name, e.g.:
      def S = l[2]; setring S; check;
-	");
+        ");
      return(l);
     }
@@ -98,12 +103,12 @@
    ring R = 0,(x,y,z),dp;
    ideal A=x2+y2,z2,x4+y4,1,x2z-1y2z,xyz,x3y-1xy3;
-   poly p1=z; 
+   poly p1=z;
    poly p2=x10z3-x8y2z3+2x6y4z3-2x4y6z3+x2y8z3-y10z3+x6z4+3x4y2z4+3x2y4z4+y6z4;
-   
+
    algebra_containment(p1,A);
    algebra_containment(p2,A);
    list L = algebra_containment(p2,A,1);
    L[1];
-   def S = L[2]; setring S;   
+   def S = L[2]; setring S;
    check;
    printlevel = p;
@@ -113,5 +118,5 @@
 proc module_containment(poly p, ideal P, ideal S, list #)
 "USAGE:   module_containment(p,P,M[,k]); p poly, P ideal, M ideal, k int
-         P = P[1],...,P[n] generators of a subalgebra of the basering, 
+         P = P[1],...,P[n] generators of a subalgebra of the basering,
          M = M[1],...,M[m] generators of a module over the subalgebra K[P]
 ASSUME:  ncols(P) = nvars(basering), the P[i] are algebraically independent
@@ -121,8 +126,8 @@
          - k=1, a list, say l, of size 2, l[1] integer, l[2] ring:
            l[1]=1 : if p is in <M[1],...,M[m]> and then the ring l[2] contains
-             the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if 
+             the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if
              p = h(M[1],...,M[m],P[1],...,P[n])
-           l[1]=0 : if p is in not in <M[1],...,M[m]> and then l[2] contains the
-             polynomial check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies 
+           l[1]=0 : if p is in not in <M[1],...,M[m]>, then l[2] contains the
+             poly check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies
              the nonlinear relation p = h(x,M[1],...,M[m],P[1],...,P[n]) where
              x = x(1),...,x(n) denote the variables of the basering
@@ -150,5 +155,5 @@
     string mp=string(minpoly);
   // ---------- create new ring with extra variables --------------------
-    execute 
+    execute
    ("ring R=("+charstr(br)+"),(x(1..n),y(1..m),z(1..n)),(lp(n),dp(m),lp(n));");
     execute ("minpoly=number("+mp+");");
@@ -169,5 +174,5 @@
   //--- checking whether all variables from old ring have disappeared ------
   // if so, then the sum of the first n leading exponents is 0
-    i = (sum(leadexp(check),1..n)==0);   
+    i = (sum(leadexp(check),1..n)==0);
     if( #[1] == 0 )
     { dbprint(i*(printlevel-voice+3),"// "+string(check));
@@ -177,8 +182,8 @@
     { list l = i,R;
       kill I,vars,emb,P,S;
-      export check;       
+      export check;
       dbprint(printlevel-voice+3,"
-// 'module_containment' created a ring as 2nd element of the list. 
-// This ring contains the poly check which defines the algebraic relation for p.
+// 'module_containment' created a ring as 2nd element of the list.
+// This ring contains the poly check which defines the algebraic relation for p
 // To access to the ring and see check you must give the ring a name, e.g.:
      def S = l[2]; setring S; check;
@@ -211,7 +216,7 @@
 "USAGE:   inSubring(p,i); p poly, i ideal
 RETURN:  a list, say l,of size 2, l[1] integer, l[2] string
-         l[1]=1 iff p is in the subring generated by i=i[1],...,i[k], 
-                and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k]) 
-         l[1]=0 iff p is in not the subring generated by i, 
+         l[1]=1 iff p is in the subring generated by i=i[1],...,i[k],
+                and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k])
+         l[1]=0 iff p is in not the subring generated by i,
                 and then l[2] = h(y(0),y(1),...,y(k) where p satisfies the
                 nonlinear relation h(p,i[1],...,i[k])=0.
@@ -265,26 +270,26 @@
 //////////////////////////////////////////////////////////////////////////////
 
-proc algDependence( ideal A, list # )
-"USAGE:   algDependence(f[,c]); f ideal (say, f = f1,...,fm), c integer
+proc algDependent( ideal A, list # )
+"USAGE:   algDependent(f[,c]); f ideal (say, f = f1,...,fm), c integer
 RETURN:  a list, say l, of size 2, l[1] integer, l[2] ring:
          l[1] = 1 if f1,...,fm are algebraic dependent, 0 if not
-         l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 
-         basering has n variables. It contains the ideal 'ker', depending 
-         onIy on the y(i) and generating the algebraic relations between the 
+         l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the
+         basering has n variables. It contains the ideal 'ker', depending
+         onIy on the y(i) and generating the algebraic relations between the
          f[i], i.e. substituting y(i) by f[i] yields 0.
-         Three differnt algorithms are used depending on c = 1,2,3. 
+         Three differnt algorithms are used depending on c = 1,2,3.
          If c is not given or c=0, a heuristically best method is choosen.
          The basering may be a quotient ring.
          To access to the ring l[2] and see ker you must give the ring a name,
-         e.g. def S=l[2]; setring S; ker; 
+         e.g. def S=l[2]; setring S; ker;
 DISPLAY: The above comment is displayed if printlevel >= 0 (default).
-EXAMPLE: example algDependence; shows an example
-"
-{   
+EXAMPLE: example algDependent; shows an example
+"
+{
     int bestoption = 3;
     // bestoption is the default algorithm, it may be set to 1,2 or 3;
     // it should be changed, if another algorithm turns out to be faster
     // in general. Is perhaps dependent on the input (# vars, size ...)
-    int tt; 
+    int tt;
     if( size(#) > 0 )
     { if( typeof(#[1]) == "int" )
@@ -294,5 +299,5 @@
     if( size(#) == 0 or tt == 0 )
     { tt = bestoption;
-    }   
+    }
     def br=basering;
     int n = nvars(br);
@@ -303,19 +308,20 @@
     string mp = string(minpoly);
  // --------------------- 1st variant of algorithm ----------------------
+ // use internal preimage command (should be equivalent to 2nd variant)
     if ( tt == 1 )
-    {  
+    {
       execute ("ring R1=("+charstr(br)+"),y(1..m),dp;");
-      execute ("minpoly=number("+mp+");"); 
-      setring br; 
+      execute ("minpoly=number("+mp+");");
+      setring br;
       map phi = R1,A;
       setring R1;
-      ideal ker = preimage(br,phi,B);             
+      ideal ker = preimage(br,phi,B);
     }
  // ---------- create new ring with extra variables --------------------
-    execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);"); 
+    execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);");
     execute ("minpoly=number("+mp+");");
     if( tt == 1 )
     {
-      ideal ker = imap(R1,ker); 
+      ideal ker = imap(R1,ker);
     }
     else
@@ -323,16 +329,20 @@
       ideal vars = x(1..n);
       map emb = br,vars;
-      ideal A = emb(A); 
+      ideal A = emb(A);
       for (i=1; i<=m; i=i+1)
       { A[i] = A[i]-y(i);
       }
  // --------------------- 2nd variant of algorithm ----------------------
- // eliminate does not work in qrings
+ // use internal eliminate for eliminating m variables x(i) from
+ // ideal A[i] - y(i) (uses extra eliminating 'first row', a-order)
       if ( s == 0 and  tt == 2  )
       { ideal ker = eliminate(A,product(vars));
       }
       else
+ // eliminate does not work in qrings
  // --------------------- 3rd variant of algorithm ----------------------
-      { execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));");
+ // eliminate m variables x(i) from ideal A[i] - y(i) by choosing product
+ // order
+       {execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));");
         execute ("minpoly=number("+mp+");");
         if ( s != 0 )
@@ -344,5 +354,5 @@
         }
         ideal A = imap(R2,A);
-        A=std(A);
+        A = std(A);
         ideal ker = nselect(A,1,n);
         setring R2;
@@ -357,5 +367,5 @@
     }
  // --------------------------- return ----------------------------------
-    s = size(ker); 
+    s = size(ker);
     list L = (s!=0), R2;
     export(ker);
@@ -363,9 +373,9 @@
 // The 2nd element of the list, say l, is a ring with variables x(1),...,x(n),
 // y(1),...,y(m) if the basering has n variables and the ideal is f[1],...,f[m]
-// It contains the ideal ker only depending on the y(i) and generating the 
+// It contains the ideal ker only depending on the y(i) and generating the
 // relations between the f[i], i.e. substituting y(i) by f[i] yields 0.
 // To access to the ring and see ker you must give the ring a name, e.g.:
      def S = l[2]; setring S; ker;
-	");
+        ");
     return (L);
 }
@@ -376,5 +386,5 @@
    ideal I = xyzu2w-1yzu2w2+u4w2-1xu2vw+u2vw2+xyz-1yzw+2u2w-1xv+vw+2,
              x-w, u2w+1, yz-v;
-   list l = algDependence(I);
+   list l = algDependent(I);
    l[1];
    def S = l[2]; setring S;
@@ -384,16 +394,16 @@
 //////////////////////////////////////////////////////////////////////////////
 proc alg_kernel( map phi, pr, list #)
-"USAGE:   alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring, 
+"USAGE:   alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring,
          s string (name of kernel in pr), c integer
 RETURN:  a string, the kernel of phi as string
-         If, moreover, a string s is given, the algorithm creates, in pr, 
+         If, moreover, a string s is given, the algorithm creates, in pr,
          the kernel of phi with name equal to s.
-         Three differnt algorithms are used depending on c = 1,2,3. 
+         Three differnt algorithms are used depending on c = 1,2,3.
          If c is not given or c=0, a heuristically best method is choosen.
          (alogrithm 1 uses the preimage command)
 NOTE:    The basering may be a quotient ring.
-EXAMPLE: example kernel; shows an example
-"
-{   int tt; 
+EXAMPLE: example alg_kernel; shows an example
+"
+{   int tt;
    if( size(#) >0 )
    { if( typeof(#[1]) == "int")
@@ -423,6 +433,6 @@
     A=A,j;
     A=A[1..m];
-    list L = algDependence(A,tt);
-    // algDependence is called with "bestoption" if tt = 0
+    list L = algDependent(A,tt);
+    // algDependent is called with "bestoption" if tt = 0
     def S = L[2];
     execute ("ring R=("+charstr(basering)+"),(@(1..n),"+varstr(pr)+"),(dp);");
@@ -443,6 +453,6 @@
    ideal I = x-w,u2w+1,yz-v;
    map phi = r,I;                   // a map from r to s:
-   alg_kernel(phi,r);                   // a,b,c ---> x-w,u2w+1,yz-v
-  
+   alg_kernel(phi,r);               // a,b,c ---> x-w,u2w+1,yz-v
+
    ring S = 0,(a,b,c),ds;
    ring R = 0,(x,y,z),dp;
@@ -450,5 +460,5 @@
    ideal i = x, y, x2-y3;
    map phi = S,i;                    // a map to a quotient ring
-   alg_kernel(phi,S,"ker",3);            // uses algorithm 3
+   alg_kernel(phi,S,"ker",3);        // uses algorithm 3
    setring S;                        // you have access to kernel in preimage
    // setring preimage(phi);      ## wenn realisiert ##
@@ -459,20 +469,22 @@
 proc is_injective( map phi, pr,list #)
 "USAGE:   is_injective(phi[,c,s]); phi map, pr reimage ring, c int, s string
-RETURN:  - 1 (type int) if phi is injective, 0 if not (if s is not given). 
+RETURN:  - 1 (type int) if phi is injective, 0 if not (if s is not given).
          - If s is given, return a list, say l, of size 2, l[1] int, l[2] ring:
            l[1] = 1 if phi is injective, 0 if not
-           l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 
-           basering has n variables and the map m components, it contains the 
+           l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the
+           basering has n variables and the map m components, it contains the
            ideal 'ker', depending only on the y(i), the kernel of the given map
-         Three differnt algorithms are used depending on c = 1,2,3. 
+         Three differnt algorithms are used depending on c = 1,2,3.
          If c is not given or c=0, a heuristically best method is choosen.
-NOTE:    The basering may be a quotient ring.
+NOTE:    The basering may be a quotient ring. However, if the preimage ring is
+         a quotient ring, say pr = P/I, consider phi as a map from P and then
+         the algorithm returns 1 if the kernel of phi is 0 mod I.
          To access to the ring l[2] and see ker you must give the ring a name,
-         e.g. def S=l[2]; setring S; ker; 
+         e.g. def S=l[2]; setring S; ker;
 DISPLAY: The above comment is displayed if printlevel >= 0 (default).
 EXAMPLE: example is_injective; shows an example
 "
-{  def bsr = basering; 
-   int tt; 
+{  def bsr = basering;
+   int tt;
    if( size(#) >0 )
    { if( typeof(#[1]) == "int")
@@ -502,5 +514,5 @@
     A=A,j;
     A=A[1..m];
-    list L = algDependence(A,tt);
+    list L = algDependent(A,tt);
     L[1] = L[1]==0;
 // the preimage ring may be a quotient ring, we still have to check whether
@@ -510,5 +522,5 @@
     { def S = L[2];
       ideal proj;
-      proj [n+1..m] = maxideal(1);
+      proj [n+1..n+m] = maxideal(1);
       map psi = S,proj;
       L[1] = size(NF(psi(ker),std(0))) == 0;
@@ -518,5 +530,5 @@
     }
     else
-    { 
+    {
       dbprint(printlevel-voice+3,"
 // The 2nd element of the list is a ring with variables x(1),...,x(n),y(1),
@@ -525,5 +537,5 @@
 // To access to the ring and see ker you must give the ring a name, e.g.:
      def S = l[2]; setring S; ker;
-	");
+        ");
       return(L);
     }
@@ -544,5 +556,5 @@
    def S = l[2]; setring S;
    ker;
-   
+
    printlevel = p;
  }
@@ -552,8 +564,10 @@
 "USAGE:   is_surjective(phi); phi map to basering, or ideal defining it
 RETURN:  an integer,  1 if phi is surjective, 0 if not
-NOTE:    The algorithm returns 1 iff all the variables of the basering are 
+NOTE:    The algorithm returns 1 iff all the variables of the basering are
          contained in the polynomial subalgebra generated by the polynomials
-         defining phi. Hence, if the basering has local or mixed ordering then
-         the return value 1 means surjectivity in this sense.
+         defining phi. Hence, if the basering has local or mixed ordering
+         or if the preimage ring is a quotient ring (in which case the map
+         may not be well defined) then the return value 1 means
+         \"surjectivity\" in this sense.
 EXAMPLE: example is_surjective; shows an example
 "
@@ -584,5 +598,5 @@
     }
     A=std(A);
-  // ------------- check whether the x(i) are in the image -----------------   
+  // ------------- check whether the x(i) are in the image -----------------
     poly check;
     for (ii=1; ii<=n; ii++ )
@@ -618,6 +632,6 @@
 RETURN:  an integer,  1 if phi is bijective, 0 if not
 NOTE:    The algorithm checks first injectivity and then surjectivity
-         To interprete this for local or mixed orderings, type
-         help is_surjective;
+         To interprete this for local/mixed orderings, or for quotient rings
+         type help is_surjective; and help is_injective;
 DISPLAY: Comment if printlevel >= voice-1 (default)
 EXAMPLE: example is_bijective; shows an example
@@ -656,5 +670,4 @@
     A=std(A);
     def bsr = basering;
-    
  // ------- checking whether phi is injective by computing the kernel -------
     ideal ker = nselect(A,1,n);
@@ -662,9 +675,9 @@
     setring pr;
     if ( size(ideal(pr)) != 0 )
-    { 
+    {
       ideal proj;
-      proj [n+1..m] = maxideal(1);
+      proj[n+1..n+m] = maxideal(1);
       map psi = bsr,proj;
-      t = size(NF(psi(ker),std(0))) == 0;
+      t = size(NF(psi(ker),std(0)));
     }
     if ( t != 0 )
@@ -688,5 +701,5 @@
      if ( t == 0 )
      {  dbprint(printlevel-voice+3,"// map injective, but not surjective" );
-     }    
+     }
      return(t);
    }
@@ -701,5 +714,5 @@
    qring Q = std(z-x2+y3);
    is_bijective(ideal(x,y,x2-y3),Q);
-   
+
    ring S = 0,(a,b,c,d),dp;
    map psi = R,ideal(a,a+b,c-a2+b3,0); // a map from R to S,
@@ -708,7 +721,229 @@
    map chi = Q,a,b,a2-b3;              // amap between two quotient rings
    is_bijective(chi,Q);
-   
+
    printlevel = p;
 }
-
 ///////////////////////////////////////////////////////////////////////////////
+
+proc noetherNormal(ideal i, list #)
+"USAGE:   noetherNormal(id[,p]);  id ideal, p integer
+RETURN:  a list of two ideals, say I,J: I is generated by a subset of the
+         variables with size(I) = dim(id) and J defines a map (coordinate
+         change in the basering), such that, if we define  map phi=basering,J;
+         then k[var(1),...,var(n)]/phi(id) is finite over k[I]
+         If p is given, 0<=p<=100, a sparse coordinate change with p percent
+         of the matrix entries being 0 (default: p=0 i.e. dense)
+NOTE:    designed for characteristic 0, works also in char k > 0 if it
+         terminates, may result in an infinite loop in small characteristic
+EXAMPLE: example noetherNormal; shows an example
+"
+{
+   int p;
+   if( size(#) != 0 )
+   {
+     p = #[1];
+   }
+   def r = basering;
+   int n = nvars(r);
+   list good;
+   // ------------------------ change of ordering ---------------------------
+   //a procedure from ring.lib changing the order to dp creating a new
+   //basering @R in order to compute the dimension d of i
+   changeord("@R","dp");
+   ideal i = imap(r,i);
+   list j = mstd(i);
+   i = j[2];
+   int d = dim(j[1]);
+   if ( d == 0)
+   {
+     setring r;
+     list l = ideal(0),maxideal(1);
+     return( l );
+   }
+   // ------------------------ change of ordering ---------------------------
+   //Now change the order to (dp(n-d),lp) creating a new basering @S
+    string s ="dp("+string(n-d)+"),lp";
+   changeord("@S",s);
+   ideal m;
+
+   // ----------------- sparse-random coordinate change  --------------------
+   //creating lower triangular random generators for the maximal ideal
+   //a procedure from random.lib, as sparse as possible
+   if(  char(@S) >  0 )
+   {
+      m=ideal(sparsetriag(n,n,p,char(@S)+1)*transpose(maxideal(1)));
+   }
+   if(  char(@S) == 0 )
+   {
+      if ( voice <= 6 )
+      {
+        m=ideal(sparsetriag(n,n,p,10)*transpose(maxideal(1)));
+      }
+     if( voice > 6 and voice <= 11)
+     {
+        m=ideal(sparsetriag(n,n,p,100)*transpose(maxideal(1)));
+      }
+      if ( voice > 11 )
+      {
+        m=ideal(sparsetriag(n,n,p,30000)*transpose(maxideal(1)));
+      }
+   }
+
+   map phi=r,m;
+   //map phi=@R,m;
+   ideal i=std(phi(i));
+
+   // ----------------------- test for finiteness ---------------------------
+   //We need a test whether the coordinate change was random enough, if yes
+   //we are ready, else call noetherNormal again
+   list l=finitenessTest(i);
+
+   setring r;
+   list l=imap(@S,l);
+
+   if(size(l[3]) == d)                    //the generic case
+   {
+      good = fetch(@S,m),l[3];
+      kill @S,@R;
+      return(good);
+   }
+   else                                   //the bad case
+   { kill @S,@R;
+      if ( voice >= 21 )
+      {
+       "// WARNING: In case of a finite ground field";
+       "// the characteristic may be too small.";
+       "// This could result in an infinte loop.";
+       "// Loop in noetherNormal, voice:";, voice;"";
+      }
+     if ( voice >= 16 )
+     {
+       "// Switch to dense coordinate change";"";
+       return(noetherNormal(i));
+     }
+     return(noetherNormal(i,p));
+   }
+}
+example
+{ "EXAMPLE:"; echo = 2;
+   ring r=0,(x,y,z),dp;
+   ideal i= xy,xz;
+   noetherNormal(i);
+}
+///////////////////////////////////////////////////////////////////////////////
+
+proc finitenessTest(ideal i,list #)
+"USAGE:   finitenessTest(J[,v]); J ideal, v intvec (say v1,...,vr)
+RETURN:  a list, say l, with l[1] integer, l[2], l[3] ideals
+         l[1] = 1 if var(v1),...,var(vr) are in l[2] and 0 else
+         l[2] (resp. l[3]) contains those variables which occur, (resp. occur
+         not) as pure power in the leading term of one of the generators of J
+         (default: v = [1,2,..,nvars(basering)])
+THEORY:  If J is a standard basis of an ideal generated by x_1 - f_1(y),...,
+         x_n - f_n with y_j ordered lexicographically and y_j >> x_i, then,
+         if y_i appears as pure power in the leading term of J[k], J[k] defines
+         an integral relation for y_i over the y_(i+1),... and the f's.
+         Moreover, in this situation, if l[2] = y_1,...,y_r, then K[y_1,...y_r]
+         is finite over K[f_1..f_n]. If J contains furthermore polynomials
+         h_j(y), then K[y_1,...y_z]/<h_j> is finite over K[f_1..f_n].
+EXAMPLE: example finitenessTest; shows an example
+"
+{  intvec V = 1..nvars(basering);
+   if (size(#) != 0 )
+   {
+     V = #[1];
+   }
+   intvec v,w;
+   int j,z;
+   // ---------------------- check leading exponents -------------------------
+   for(j=1;j<=ncols(i);j++)
+   {
+      w=leadexp(i[j]);
+      if(size(ideal(w))==1)           //the leading term of i[j] is a
+      {                               //pure power of some variable
+         v=v+w;
+      }
+   }
+   // ----------------- pick the corresponding variables ---------------------
+   //the nonzero entries of v correspond to variables which occur as
+   //pure power in the leading term of some polynomial in i
+   ideal zero, nonzero;
+   for(j=1; j<=size(v); j++)
+   {
+      if(v[j]==0)
+      {
+         zero[size(zero)+1]=var(j);
+      }
+      else
+      {
+        nonzero[size(nonzero)+1]=var(j);
+      }
+   }
+   // ---------------- do we have all pure powers we want? -------------------
+   // test this by dividing the product of corresponding variables
+   ideal max = maxideal(1);
+   max = max[V];
+   z = (product(nonzero)/product(max) != 0);
+   return(list(z,nonzero,zero));
+}
+example
+{ "EXAMPLE:"; echo = 2;
+   ring s = 0,(x,y,z,a,b,c),(lp(3),dp);
+   ideal i= a -(xy)^3+x2-z, b -y2-1, c -z3;
+   ideal j = a -(xy)^3+x2-z, b -y2-1, c -z3, xy;
+   finitenessTest(std(i),1..3);
+   finitenessTest(std(j),1..3);
+}
+///////////////////////////////////////////////////////////////////////////////
+
+proc mapIsFinite(map phi, R, list #)
+"USAGE:   mapIsFinite(phi,R[,J]); R a ring, phi: R ---> basering a map
+         [J an ideal in the basering, J = 0 if not given]
+RETURN:  1 if R ---> basering/J is finite and 0 else
+EXAMPLE: example mapIsFinite; shows an example
+"
+{
+  def bsr = basering;
+  ideal J;
+  if( size(#) != 0 )
+  {
+    J = #[1];
+  }
+  string os = ordstr(bsr);
+  int m = nvars(bsr);
+  int n = nvars(R);
+  ideal PHI = ideal(phi);
+  if ( ncols(PHI) < n )
+  { PHI[n]=0;
+  }
+  // --------------------- change of variable names -------------------------
+  execute("ring @bsr = ("+charstr(bsr)+"),y(1..m),("+os+");");
+  ideal J = fetch(bsr,J);
+  ideal PHI = fetch(bsr,PHI);
+
+  // --------------------------- enlarging ring -----------------------------
+  execute("ring @rr = ("+charstr(bsr)+"),(y(1..m),x(1..n)),(lp(m),dp);");
+  ideal J = imap(@bsr,J);
+  ideal PHI = imap(@bsr,PHI);
+  ideal M;
+  int i;
+
+  for(i=1;i<=n;i++)
+  {
+    M[i]=x(i)-PHI[i];
+  }
+  M=std(M+J);
+  // ----------------------- test for finiteness ---------------------------
+  list l = finitenessTest(M,1..m);
+  return(l[1]);
+}
+example
+{ "EXAMPLE:"; echo = 2;
+   ring r = 0,(a,b,c),dp;
+   ring s = 0,(x,y,z),dp;
+   ideal i= xy;
+   map phi= r,(xy)^3+x2+z,y2-1,z3;
+   mapIsFinite(phi,r,i);
+}
+//////////////////////////////////////////////////////////////////////////////
+
Index: Singular/LIB/primdec.lib
===================================================================
--- Singular/LIB/primdec.lib	(revision de63d0a0a404b70806e92102e65c5461a0914009)
+++ Singular/LIB/primdec.lib	(revision 9050cae84ee67262b9d08045bac6f3b36c2cc66b)
@@ -1,3 +1,3 @@
-// $Id: primdec.lib,v 1.39 1999-07-07 14:39:12 obachman Exp $
+// $Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $
 ////////////////////////////////////////////////////////////////////////////////
 // primdec.lib                                                                //
@@ -11,25 +11,20 @@
 ////////////////////////////////////////////////////////////////////////////////
 
-version="$Id: primdec.lib,v 1.39 1999-07-07 14:39:12 obachman Exp $";
+version="$Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $";
 info="
-LIBRARY: primdec.lib PROCEDURE FOR PRIMARY DECOMPOSITION
-
-AUTHORS: Gerhard Pfister, Wolfram Decker, Hans Schoenemann
+LIBRARY: primdec.lib      PROCEDURES FOR PRIMARY DECOMPOSITION
+AUTHORS:  Gerhard Pfister, email: pfister@mathematik.uni-kl.de (GTZ)
+          Wolfram Decker, email: decker@math.uni-sb.de         (SY)
+          Hans Schoenemann, email: hannes@mathematik.uni-kl.de (SY)
 
 PROCEDURES:
-  minAssGTZ(I);     computes the minimal associated primes
-                      via Gianni,Trager,Zacharias
-  minAssChar(I);    computes the minimal associated primes
-                      using characteristic sets
-  primdecGTZ(I);    computes a complete primary decomposition
-                      via Gianni,Trager,Zacharias
-  primdecSY(I);     computes a complete primary decomposition
-                      via Shimoyama-Yokoyama
-  testPrimary(L,k); tests whether the result of the primary
-                      decomposition is correct
+  primdecGTZ(I);    complete primary decomposition via Gianni,Trager,Zacharias
+  primdecSY(I);     complete primary decomposition via Shimoyama-Yokoyama
+  minAssGTZ(I);     the minimal associated primes via Gianni,Trager,Zacharias
+  minAssChar(I);    the minimal associated primes using characteristic sets
+  testPrimary(L,k); tests the result of the primary decomposition
   radical(I);       computes the radical of the ideal I
-  equiRadical(I);   computes the radical of the equidimensional part
-                      of the ideal I
-  prepareAss(I);    computes the radicals of the equidimensional parts of I
+  equiRadical(I);   the radical of the equidimensional part of the ideal I
+  prepareAss(I);    list of radicals of the equidimensional components of I
 
 REMARK:
@@ -468,9 +463,10 @@
       i[m]=poly(e)^e*leadcoef(i[m])^(e-1)*i[m];
 
-      if(i[m]==0)
+      if((i[m]==0)&&(voice>=15))
       {
          "Warning: The characteristic ist too small to use";
          "the Algorithm of Gianni/Trager/Zacharias.";
          "This may result in an infinte loop";
+         " current nesting level in primaryTest",voice;
       }
       if (reduce(i[m]-t^e,prm,1) !=0)
@@ -777,5 +773,5 @@
   }
 
-//withe the factors new ideals (hopefully the primary decomposition)
+//with the factors new ideals (hopefully the primary decomposition)
 //are created
 
@@ -1528,5 +1524,4 @@
          minAssPrimes(i,1); i ideal  (to use also the factorizing Groebner)
 RETURN:  list = the minimal associated prime ideals of i
-NOTE:
 EXAMPLE: example minAssPrimes; shows an example
 "
@@ -1650,5 +1645,5 @@
    list pr= minAssPrimes(i);
    pr;
-   pr= minAssPrimes(i,1);
+   minAssPrimes(i,1);
 }
 
@@ -1947,5 +1942,5 @@
   //look for subring such that the intersection with the ideal is zero
   //j intersected with K[var(indep[3]+1),...,var(nvar] is zero,
-  //indep[1] is the new varstring and indep[2] the string for the block-ordering
+  //indep[1] is the new varstring and indep[2] the string for block-ordering
   //------------------------------------------------------------------
 
@@ -2057,6 +2052,6 @@
      //leading coefficients of the polynomials  there (polynomials in
      //K[var(nnp+1),..,var(nva)]) are collected in the list h,
-     //we need their ggt, gh, because of the following:
-     //let (j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..]
+     //we need their ggt, gh, because of the following: let
+     //(j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..]
      //intersected with K[var(1),...,var(nva)] is (j:gh^n)
      //on the other hand j=(j,gh^n) intersected with (j:gh^n)
@@ -2064,6 +2059,6 @@
      //------------------------------------------------------------------------------------
 
-     //the arrangement for the quotientring K(var(nnp+1),..,var(nva))[..the rest..]
-     //and the map phi:K[var(1),...,var(nva)] ----->K(var(nnpr+1),..,var(nva))[..the rest..]
+     //arrangement for quotientring K(var(nnp+1),..,var(nva))[..the rest..] and
+     //map phi:K[var(1),...,var(nva)] -->K(var(nnpr+1),..,var(nva))[..rest..]
      //-------------------------------------------------------------------------------------
 
@@ -2112,6 +2107,6 @@
      //but fi polynomials, then the intersection of q with the polynomialring
      //is the saturation of the ideal generated by f1,...,fr with respect to
-     //h which is the lcm of the leading coefficients of the fi considered in the
-     //quotientring: this is coded in saturn
+     //h which is the lcm of the leading coefficients of the fi considered
+     //in the quotientring: this is coded in saturn
 
      list saturn;
@@ -4008,8 +4003,8 @@
 proc primdecGTZ(ideal i)
 "USAGE:  primdecGTZ(i); i ideal
-RETURN:  list = list of primary ideals
-                and their associated primes
+RETURN:  a list, say pr, of primary ideals and their associated primes
+         pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component
 NOTE:    Algorithm of Gianni, Traeger, Zacharias
-         designed for characteristic 0, works also in char k >> 0,
+         designed for characteristic 0, works also in char k > 0,
          may result in an infinite loop in small characteristic
 EXAMPLE: example primdecGTZ; shows an example
@@ -4031,9 +4026,9 @@
 proc primdecSY(ideal i)
 "USAGE:  primdecSY(i); i ideal
-RETURN:  list = list of primary ideals
-                and their associated primes
+RETURN:  a list, say pr, of primary ideals and their associated primes
+         pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component
 NOTE:    Algorithm of Shimoyama-Yokoyama
-         implemented for characteristic 0, works also in char k >> 0,
-         the result may be not compltely decomposed in small characteristic
+         implemented for characteristic 0, works also in char k > 0,
+         the result may be not completely decomposed in small characteristic
 EXAMPLE: example primdecSY; shows an example
 "
@@ -4054,5 +4049,6 @@
 "USAGE:  minAssGTZ(i); i ideal
 RETURN:  list = the minimal associated prime ideals of i
-NOTE:    designed for characteristic 0, works also in char k >> 0,
+NOTE:    designed for characteristic 0, works also in char k > 0
+         if it terminates,
          may result in an infinite loop in small characteristic
 EXAMPLE: example minAssGTZ; shows an example
@@ -4075,7 +4071,7 @@
 "USAGE:  minAssChar(i); i ideal
 RETURN:  list = the minimal associated prime ideals of i
-NOTE:    implemented for characteristic 0, works also in char k >> 0,
-         the result may be not compltely decomposed in small characteristic
-EXAMPLE: example primdecSY; shows an example
+NOTE:    implemented for characteristic 0, works also in char k > 0,
+         the result may be not completely decomposed in small characteristic
+EXAMPLE: example minAssChar; shows an example
 "
 {
@@ -4094,7 +4090,7 @@
 proc equiRadical(ideal i)
 "USAGE:  equiRadical(i); i ideal
-RETURN:  ideal = the intersection of associated primes
-         of i of dimension of i
-NOTE:    designed for characteristic 0, works also in char k >> 0,
+RETURN:  ideal, intersection of associated primes of i of maximal  dimension
+NOTE:    designed for characteristic 0, works also in char k > 0
+         if it terminates,
          may result in an infinite loop in small characteristic
 EXAMPLE: example equiRadical; shows an example
@@ -4118,5 +4114,6 @@
 NOTE:    a combination of the algorithms of Krick/Logar
          and Eisenbud/Huneke/Vasconcelos
-         designed for characteristic 0, works also in char k >> 0,
+         designed for characteristic 0, works also in char k > 0
+         if it termintes,
          may result in an infinite loop in small characteristic
 EXAMPLE: example radical; shows an example
@@ -4213,6 +4210,6 @@
 proc prepareAss(ideal i)
 "USAGE:  prepareAss(i); i ideal
-RETURN:  list = the radicals of the equidimensional parts of i
-NOTE:    algorithm of Eisenbud,Huneke and Vasconcelos
+RETURN:  list = the radicals of the maximal dimensional components of i
+NOTE:    uses algorithm of Eisenbud,Huneke and Vasconcelos
 EXAMPLE: example prepareAss; shows an example
 "
@@ -4254,8 +4251,6 @@
 
 proc testPrimary(list pr, ideal k)
-"USAGE:   testPrimary(pr,k) pr=primdecGTZ(k) or primdecSY(k)
-RETURN:   int = 1, if the intersection of the primary ideals
-                in pr is k, 0 if not
-NOTE:
+"USAGE:   testPrimary(pr,k); pr a list, result of primdecGTZ(k) or primdecSY(k)
+RETURN:  int = 1, if intersection of the primary ideals in pr is k, 0 if not
 EXAMPLE: example testPrimary ; shows an example
 "
