Changeset 9050ca in git


Ignore:
Timestamp:
Jul 26, 1999, 3:41:33 PM (25 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
58e9e019da7b571ce9d96e5da7f9b760e9a799aa
Parents:
de63d0a0a404b70806e92102e65c5461a0914009
Message:
*hannes: GMG's fixes


git-svn-id: file:///usr/local/Singular/svn/trunk@3360 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular/LIB
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/algebra.lib

    rde63d0 r9050ca  
    11///////////////////////////////////////////////////////////////////////////////
    2 version="$Id: algebra.lib,v 1.1 1999-07-19 14:54:07 obachman Exp $";
     2version="$Id: algebra.lib,v 1.2 1999-07-26 13:41:33 Singular Exp $";
    33info="
    44LIBRARY:  algebra.lib   PROCEDURES FOR COMPUTING WITH ALGBRAS AND MAPS
    5 AUTHORS:  Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de
    6           Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de
     5AUTHORS:  Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de,
     6          Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de,
    77          Gerhard Pfister, email: pfister@mathematik.uni-kl.de
    88
     
    1111 module_containment();  query of module containment over a subalgebra
    1212 inSubring(p,I);        test whether poly p is in subring generated by I
    13  algDependence(I);      computes algebraic relations between generators of I
    14  alg_kernel(phi);           computes the kernel of the ringmap phi
     13 algDependent(I);       computes algebraic relations between generators of I
     14 alg_kernel(phi);       computes the kernel of the ringmap phi
    1515 is_injective(phi);     test for injectivity of ringmap phi
    1616 is_surjective(phi);    test for surjectivity of ringmap phi
    1717 is_bijective(phi);     test for bijectivity of ring map phi
     18 noetherNormal(id);     noether normalization of ideal id
     19 mapIsFinite(R,phi,I);  query for finiteness of map phi:R --> basering/I
     20 finitenessTest(i,z);   find variables which occur as pure power in lead(i)
    1821";
    1922
    2023 LIB "inout.lib";
    2124 LIB "elim.lib";
     25 LIB "ring.lib";
     26 LIB "matrix.lib";
    2227
    2328///////////////////////////////////////////////////////////////////////////////
     
    2833RETURN:  - k=0 (or if k is not given) an integer:
    2934           1    : if p is contained in the subalgebra K[A[1],...,A[m]]
    30            0    : if p is not contained in K[A[1],...,A[m]] 
     35           0    : if p is not contained in K[A[1],...,A[m]]
    3136         - k=1: a list, say l, of size 2, l[1] integer, l[2] ring, satisfying
    3237           l[1]=1 if p is in the subalgebra K[A[1],...,A[m]] and then the ring
    33            l[2] contains the poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m])
     38           l[2] contains poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m])
    3439           l[1]=0 if p is in not the subalgebra K[A[1],...,A[m]] and then
    35            l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies 
     40           l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies
    3641           the nonlinear relation p = h(x,A[1],...,A[m]) where
    3742           x = x(1),...,x(n) denote the variables of the basering
    3843DISPLAY: if k=0, polynomial h(y(1),...,y(m)) if p=h(A[1],...,A[m]) is contained
    3944         in the subalgebra, provided printlevel >= voice+1 (default)
    40 NOTE:    The proc inSubring uses a different algorithm which is sometimes faster
     45NOTE:    The proc inSubring uses different algorithm which is sometimes faster
    4146THEORY:  The ideal of algebraic relations of the algebra generators A[1],...,
    4247         A[m] is computed introducing new variables y(i) and the product
     
    4752"
    4853{ int DEGB = degBound;
    49   degBound = 0; 
     54  degBound = 0;
    5055    if (size(#)==0)
    5156    { #[1] = 0;
    52     }     
     57    }
    5358    def br=basering;
    5459    int n = nvars(br);
     
    6873    A=std(A);
    6974    check=reduce(check,A);
    70     /*alternatively we could use reduce(check,A,1) which is a little faster 
     75    /*alternatively we could use reduce(check,A,1) which is a little faster
    7176      but result is bigger since it is not tail-reduced
    7277    */
     
    7479  // if so, then the sum of the first n leading exponents is 0, hence i=1
    7580  // use i also to control the display
    76     i = (sum(leadexp(check),1..n)==0);   
     81    i = (sum(leadexp(check),1..n)==0);
    7782  degBound = DEGB;
    7883    if( #[1] == 0 )
     
    8388    { list l = i,R;
    8489      kill A,vars,emb;
    85       export check;       
     90      export check;
    8691      dbprint(printlevel-voice+3,"
    87 // 'algebra_containment' created a ring as 2nd element of the list. 
     92// 'algebra_containment' created a ring as 2nd element of the list.
    8893// This ring contains the poly check which defines the algebraic relation.
    8994// To access to the ring and see check you must give the ring a name, e.g.:
    9095     def S = l[2]; setring S; check;
    91         ");
     96        ");
    9297     return(l);
    9398    }
     
    98103   ring R = 0,(x,y,z),dp;
    99104   ideal A=x2+y2,z2,x4+y4,1,x2z-1y2z,xyz,x3y-1xy3;
    100    poly p1=z; 
     105   poly p1=z;
    101106   poly p2=x10z3-x8y2z3+2x6y4z3-2x4y6z3+x2y8z3-y10z3+x6z4+3x4y2z4+3x2y4z4+y6z4;
    102    
     107
    103108   algebra_containment(p1,A);
    104109   algebra_containment(p2,A);
    105110   list L = algebra_containment(p2,A,1);
    106111   L[1];
    107    def S = L[2]; setring S;   
     112   def S = L[2]; setring S;
    108113   check;
    109114   printlevel = p;
     
    113118proc module_containment(poly p, ideal P, ideal S, list #)
    114119"USAGE:   module_containment(p,P,M[,k]); p poly, P ideal, M ideal, k int
    115          P = P[1],...,P[n] generators of a subalgebra of the basering, 
     120         P = P[1],...,P[n] generators of a subalgebra of the basering,
    116121         M = M[1],...,M[m] generators of a module over the subalgebra K[P]
    117122ASSUME:  ncols(P) = nvars(basering), the P[i] are algebraically independent
     
    121126         - k=1, a list, say l, of size 2, l[1] integer, l[2] ring:
    122127           l[1]=1 : if p is in <M[1],...,M[m]> and then the ring l[2] contains
    123              the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if 
     128             the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if
    124129             p = h(M[1],...,M[m],P[1],...,P[n])
    125            l[1]=0 : if p is in not in <M[1],...,M[m]> and then l[2] contains the
    126              polynomial check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies
     130           l[1]=0 : if p is in not in <M[1],...,M[m]>, then l[2] contains the
     131             poly check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies
    127132             the nonlinear relation p = h(x,M[1],...,M[m],P[1],...,P[n]) where
    128133             x = x(1),...,x(n) denote the variables of the basering
     
    150155    string mp=string(minpoly);
    151156  // ---------- create new ring with extra variables --------------------
    152     execute 
     157    execute
    153158   ("ring R=("+charstr(br)+"),(x(1..n),y(1..m),z(1..n)),(lp(n),dp(m),lp(n));");
    154159    execute ("minpoly=number("+mp+");");
     
    169174  //--- checking whether all variables from old ring have disappeared ------
    170175  // if so, then the sum of the first n leading exponents is 0
    171     i = (sum(leadexp(check),1..n)==0);   
     176    i = (sum(leadexp(check),1..n)==0);
    172177    if( #[1] == 0 )
    173178    { dbprint(i*(printlevel-voice+3),"// "+string(check));
     
    177182    { list l = i,R;
    178183      kill I,vars,emb,P,S;
    179       export check;       
     184      export check;
    180185      dbprint(printlevel-voice+3,"
    181 // 'module_containment' created a ring as 2nd element of the list. 
    182 // This ring contains the poly check which defines the algebraic relation for p.
     186// 'module_containment' created a ring as 2nd element of the list.
     187// This ring contains the poly check which defines the algebraic relation for p
    183188// To access to the ring and see check you must give the ring a name, e.g.:
    184189     def S = l[2]; setring S; check;
     
    211216"USAGE:   inSubring(p,i); p poly, i ideal
    212217RETURN:  a list, say l,of size 2, l[1] integer, l[2] string
    213          l[1]=1 iff p is in the subring generated by i=i[1],...,i[k], 
    214                 and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k]) 
    215          l[1]=0 iff p is in not the subring generated by i, 
     218         l[1]=1 iff p is in the subring generated by i=i[1],...,i[k],
     219                and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k])
     220         l[1]=0 iff p is in not the subring generated by i,
    216221                and then l[2] = h(y(0),y(1),...,y(k) where p satisfies the
    217222                nonlinear relation h(p,i[1],...,i[k])=0.
     
    265270//////////////////////////////////////////////////////////////////////////////
    266271
    267 proc algDependence( ideal A, list # )
    268 "USAGE:   algDependence(f[,c]); f ideal (say, f = f1,...,fm), c integer
     272proc algDependent( ideal A, list # )
     273"USAGE:   algDependent(f[,c]); f ideal (say, f = f1,...,fm), c integer
    269274RETURN:  a list, say l, of size 2, l[1] integer, l[2] ring:
    270275         l[1] = 1 if f1,...,fm are algebraic dependent, 0 if not
    271          l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 
    272          basering has n variables. It contains the ideal 'ker', depending 
    273          onIy on the y(i) and generating the algebraic relations between the 
     276         l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the
     277         basering has n variables. It contains the ideal 'ker', depending
     278         onIy on the y(i) and generating the algebraic relations between the
    274279         f[i], i.e. substituting y(i) by f[i] yields 0.
    275          Three differnt algorithms are used depending on c = 1,2,3. 
     280         Three differnt algorithms are used depending on c = 1,2,3.
    276281         If c is not given or c=0, a heuristically best method is choosen.
    277282         The basering may be a quotient ring.
    278283         To access to the ring l[2] and see ker you must give the ring a name,
    279          e.g. def S=l[2]; setring S; ker; 
     284         e.g. def S=l[2]; setring S; ker;
    280285DISPLAY: The above comment is displayed if printlevel >= 0 (default).
    281 EXAMPLE: example algDependence; shows an example
    282 "
    283 {   
     286EXAMPLE: example algDependent; shows an example
     287"
     288{
    284289    int bestoption = 3;
    285290    // bestoption is the default algorithm, it may be set to 1,2 or 3;
    286291    // it should be changed, if another algorithm turns out to be faster
    287292    // in general. Is perhaps dependent on the input (# vars, size ...)
    288     int tt; 
     293    int tt;
    289294    if( size(#) > 0 )
    290295    { if( typeof(#[1]) == "int" )
     
    294299    if( size(#) == 0 or tt == 0 )
    295300    { tt = bestoption;
    296     }   
     301    }
    297302    def br=basering;
    298303    int n = nvars(br);
     
    303308    string mp = string(minpoly);
    304309 // --------------------- 1st variant of algorithm ----------------------
     310 // use internal preimage command (should be equivalent to 2nd variant)
    305311    if ( tt == 1 )
    306     { 
     312    {
    307313      execute ("ring R1=("+charstr(br)+"),y(1..m),dp;");
    308       execute ("minpoly=number("+mp+");"); 
    309       setring br; 
     314      execute ("minpoly=number("+mp+");");
     315      setring br;
    310316      map phi = R1,A;
    311317      setring R1;
    312       ideal ker = preimage(br,phi,B);             
     318      ideal ker = preimage(br,phi,B);
    313319    }
    314320 // ---------- create new ring with extra variables --------------------
    315     execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);"); 
     321    execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);");
    316322    execute ("minpoly=number("+mp+");");
    317323    if( tt == 1 )
    318324    {
    319       ideal ker = imap(R1,ker); 
     325      ideal ker = imap(R1,ker);
    320326    }
    321327    else
     
    323329      ideal vars = x(1..n);
    324330      map emb = br,vars;
    325       ideal A = emb(A); 
     331      ideal A = emb(A);
    326332      for (i=1; i<=m; i=i+1)
    327333      { A[i] = A[i]-y(i);
    328334      }
    329335 // --------------------- 2nd variant of algorithm ----------------------
    330  // eliminate does not work in qrings
     336 // use internal eliminate for eliminating m variables x(i) from
     337 // ideal A[i] - y(i) (uses extra eliminating 'first row', a-order)
    331338      if ( s == 0 and  tt == 2  )
    332339      { ideal ker = eliminate(A,product(vars));
    333340      }
    334341      else
     342 // eliminate does not work in qrings
    335343 // --------------------- 3rd variant of algorithm ----------------------
    336       { execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));");
     344 // eliminate m variables x(i) from ideal A[i] - y(i) by choosing product
     345 // order
     346       {execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));");
    337347        execute ("minpoly=number("+mp+");");
    338348        if ( s != 0 )
     
    344354        }
    345355        ideal A = imap(R2,A);
    346         A=std(A);
     356        A = std(A);
    347357        ideal ker = nselect(A,1,n);
    348358        setring R2;
     
    357367    }
    358368 // --------------------------- return ----------------------------------
    359     s = size(ker); 
     369    s = size(ker);
    360370    list L = (s!=0), R2;
    361371    export(ker);
     
    363373// The 2nd element of the list, say l, is a ring with variables x(1),...,x(n),
    364374// y(1),...,y(m) if the basering has n variables and the ideal is f[1],...,f[m]
    365 // It contains the ideal ker only depending on the y(i) and generating the 
     375// It contains the ideal ker only depending on the y(i) and generating the
    366376// relations between the f[i], i.e. substituting y(i) by f[i] yields 0.
    367377// To access to the ring and see ker you must give the ring a name, e.g.:
    368378     def S = l[2]; setring S; ker;
    369         ");
     379        ");
    370380    return (L);
    371381}
     
    376386   ideal I = xyzu2w-1yzu2w2+u4w2-1xu2vw+u2vw2+xyz-1yzw+2u2w-1xv+vw+2,
    377387             x-w, u2w+1, yz-v;
    378    list l = algDependence(I);
     388   list l = algDependent(I);
    379389   l[1];
    380390   def S = l[2]; setring S;
     
    384394//////////////////////////////////////////////////////////////////////////////
    385395proc alg_kernel( map phi, pr, list #)
    386 "USAGE:   alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring, 
     396"USAGE:   alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring,
    387397         s string (name of kernel in pr), c integer
    388398RETURN:  a string, the kernel of phi as string
    389          If, moreover, a string s is given, the algorithm creates, in pr, 
     399         If, moreover, a string s is given, the algorithm creates, in pr,
    390400         the kernel of phi with name equal to s.
    391          Three differnt algorithms are used depending on c = 1,2,3. 
     401         Three differnt algorithms are used depending on c = 1,2,3.
    392402         If c is not given or c=0, a heuristically best method is choosen.
    393403         (alogrithm 1 uses the preimage command)
    394404NOTE:    The basering may be a quotient ring.
    395 EXAMPLE: example kernel; shows an example
    396 "
    397 {   int tt; 
     405EXAMPLE: example alg_kernel; shows an example
     406"
     407{   int tt;
    398408   if( size(#) >0 )
    399409   { if( typeof(#[1]) == "int")
     
    423433    A=A,j;
    424434    A=A[1..m];
    425     list L = algDependence(A,tt);
    426     // algDependence is called with "bestoption" if tt = 0
     435    list L = algDependent(A,tt);
     436    // algDependent is called with "bestoption" if tt = 0
    427437    def S = L[2];
    428438    execute ("ring R=("+charstr(basering)+"),(@(1..n),"+varstr(pr)+"),(dp);");
     
    443453   ideal I = x-w,u2w+1,yz-v;
    444454   map phi = r,I;                   // a map from r to s:
    445    alg_kernel(phi,r);                   // a,b,c ---> x-w,u2w+1,yz-v
    446  
     455   alg_kernel(phi,r);               // a,b,c ---> x-w,u2w+1,yz-v
     456
    447457   ring S = 0,(a,b,c),ds;
    448458   ring R = 0,(x,y,z),dp;
     
    450460   ideal i = x, y, x2-y3;
    451461   map phi = S,i;                    // a map to a quotient ring
    452    alg_kernel(phi,S,"ker",3);            // uses algorithm 3
     462   alg_kernel(phi,S,"ker",3);        // uses algorithm 3
    453463   setring S;                        // you have access to kernel in preimage
    454464   // setring preimage(phi);      ## wenn realisiert ##
     
    459469proc is_injective( map phi, pr,list #)
    460470"USAGE:   is_injective(phi[,c,s]); phi map, pr reimage ring, c int, s string
    461 RETURN:  - 1 (type int) if phi is injective, 0 if not (if s is not given). 
     471RETURN:  - 1 (type int) if phi is injective, 0 if not (if s is not given).
    462472         - If s is given, return a list, say l, of size 2, l[1] int, l[2] ring:
    463473           l[1] = 1 if phi is injective, 0 if not
    464            l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 
    465            basering has n variables and the map m components, it contains the 
     474           l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the
     475           basering has n variables and the map m components, it contains the
    466476           ideal 'ker', depending only on the y(i), the kernel of the given map
    467          Three differnt algorithms are used depending on c = 1,2,3. 
     477         Three differnt algorithms are used depending on c = 1,2,3.
    468478         If c is not given or c=0, a heuristically best method is choosen.
    469 NOTE:    The basering may be a quotient ring.
     479NOTE:    The basering may be a quotient ring. However, if the preimage ring is
     480         a quotient ring, say pr = P/I, consider phi as a map from P and then
     481         the algorithm returns 1 if the kernel of phi is 0 mod I.
    470482         To access to the ring l[2] and see ker you must give the ring a name,
    471          e.g. def S=l[2]; setring S; ker; 
     483         e.g. def S=l[2]; setring S; ker;
    472484DISPLAY: The above comment is displayed if printlevel >= 0 (default).
    473485EXAMPLE: example is_injective; shows an example
    474486"
    475 {  def bsr = basering; 
    476    int tt; 
     487{  def bsr = basering;
     488   int tt;
    477489   if( size(#) >0 )
    478490   { if( typeof(#[1]) == "int")
     
    502514    A=A,j;
    503515    A=A[1..m];
    504     list L = algDependence(A,tt);
     516    list L = algDependent(A,tt);
    505517    L[1] = L[1]==0;
    506518// the preimage ring may be a quotient ring, we still have to check whether
     
    510522    { def S = L[2];
    511523      ideal proj;
    512       proj [n+1..m] = maxideal(1);
     524      proj [n+1..n+m] = maxideal(1);
    513525      map psi = S,proj;
    514526      L[1] = size(NF(psi(ker),std(0))) == 0;
     
    518530    }
    519531    else
    520     { 
     532    {
    521533      dbprint(printlevel-voice+3,"
    522534// The 2nd element of the list is a ring with variables x(1),...,x(n),y(1),
     
    525537// To access to the ring and see ker you must give the ring a name, e.g.:
    526538     def S = l[2]; setring S; ker;
    527         ");
     539        ");
    528540      return(L);
    529541    }
     
    544556   def S = l[2]; setring S;
    545557   ker;
    546    
     558
    547559   printlevel = p;
    548560 }
     
    552564"USAGE:   is_surjective(phi); phi map to basering, or ideal defining it
    553565RETURN:  an integer,  1 if phi is surjective, 0 if not
    554 NOTE:    The algorithm returns 1 iff all the variables of the basering are 
     566NOTE:    The algorithm returns 1 iff all the variables of the basering are
    555567         contained in the polynomial subalgebra generated by the polynomials
    556          defining phi. Hence, if the basering has local or mixed ordering then
    557          the return value 1 means surjectivity in this sense.
     568         defining phi. Hence, if the basering has local or mixed ordering
     569         or if the preimage ring is a quotient ring (in which case the map
     570         may not be well defined) then the return value 1 means
     571         \"surjectivity\" in this sense.
    558572EXAMPLE: example is_surjective; shows an example
    559573"
     
    584598    }
    585599    A=std(A);
    586   // ------------- check whether the x(i) are in the image -----------------   
     600  // ------------- check whether the x(i) are in the image -----------------
    587601    poly check;
    588602    for (ii=1; ii<=n; ii++ )
     
    618632RETURN:  an integer,  1 if phi is bijective, 0 if not
    619633NOTE:    The algorithm checks first injectivity and then surjectivity
    620          To interprete this for local or mixed orderings, type
    621          help is_surjective;
     634         To interprete this for local/mixed orderings, or for quotient rings
     635         type help is_surjective; and help is_injective;
    622636DISPLAY: Comment if printlevel >= voice-1 (default)
    623637EXAMPLE: example is_bijective; shows an example
     
    656670    A=std(A);
    657671    def bsr = basering;
    658    
    659672 // ------- checking whether phi is injective by computing the kernel -------
    660673    ideal ker = nselect(A,1,n);
     
    662675    setring pr;
    663676    if ( size(ideal(pr)) != 0 )
    664     { 
     677    {
    665678      ideal proj;
    666       proj [n+1..m] = maxideal(1);
     679      proj[n+1..n+m] = maxideal(1);
    667680      map psi = bsr,proj;
    668       t = size(NF(psi(ker),std(0))) == 0;
     681      t = size(NF(psi(ker),std(0)));
    669682    }
    670683    if ( t != 0 )
     
    688701     if ( t == 0 )
    689702     {  dbprint(printlevel-voice+3,"// map injective, but not surjective" );
    690      }   
     703     }
    691704     return(t);
    692705   }
     
    701714   qring Q = std(z-x2+y3);
    702715   is_bijective(ideal(x,y,x2-y3),Q);
    703    
     716
    704717   ring S = 0,(a,b,c,d),dp;
    705718   map psi = R,ideal(a,a+b,c-a2+b3,0); // a map from R to S,
     
    708721   map chi = Q,a,b,a2-b3;              // amap between two quotient rings
    709722   is_bijective(chi,Q);
    710    
     723
    711724   printlevel = p;
    712725}
    713 
    714726///////////////////////////////////////////////////////////////////////////////
     727
     728proc noetherNormal(ideal i, list #)
     729"USAGE:   noetherNormal(id[,p]);  id ideal, p integer
     730RETURN:  a list of two ideals, say I,J: I is generated by a subset of the
     731         variables with size(I) = dim(id) and J defines a map (coordinate
     732         change in the basering), such that, if we define  map phi=basering,J;
     733         then k[var(1),...,var(n)]/phi(id) is finite over k[I]
     734         If p is given, 0<=p<=100, a sparse coordinate change with p percent
     735         of the matrix entries being 0 (default: p=0 i.e. dense)
     736NOTE:    designed for characteristic 0, works also in char k > 0 if it
     737         terminates, may result in an infinite loop in small characteristic
     738EXAMPLE: example noetherNormal; shows an example
     739"
     740{
     741   int p;
     742   if( size(#) != 0 )
     743   {
     744     p = #[1];
     745   }
     746   def r = basering;
     747   int n = nvars(r);
     748   list good;
     749   // ------------------------ change of ordering ---------------------------
     750   //a procedure from ring.lib changing the order to dp creating a new
     751   //basering @R in order to compute the dimension d of i
     752   changeord("@R","dp");
     753   ideal i = imap(r,i);
     754   list j = mstd(i);
     755   i = j[2];
     756   int d = dim(j[1]);
     757   if ( d == 0)
     758   {
     759     setring r;
     760     list l = ideal(0),maxideal(1);
     761     return( l );
     762   }
     763   // ------------------------ change of ordering ---------------------------
     764   //Now change the order to (dp(n-d),lp) creating a new basering @S
     765    string s ="dp("+string(n-d)+"),lp";
     766   changeord("@S",s);
     767   ideal m;
     768
     769   // ----------------- sparse-random coordinate change  --------------------
     770   //creating lower triangular random generators for the maximal ideal
     771   //a procedure from random.lib, as sparse as possible
     772   if(  char(@S) >  0 )
     773   {
     774      m=ideal(sparsetriag(n,n,p,char(@S)+1)*transpose(maxideal(1)));
     775   }
     776   if(  char(@S) == 0 )
     777   {
     778      if ( voice <= 6 )
     779      {
     780        m=ideal(sparsetriag(n,n,p,10)*transpose(maxideal(1)));
     781      }
     782     if( voice > 6 and voice <= 11)
     783     {
     784        m=ideal(sparsetriag(n,n,p,100)*transpose(maxideal(1)));
     785      }
     786      if ( voice > 11 )
     787      {
     788        m=ideal(sparsetriag(n,n,p,30000)*transpose(maxideal(1)));
     789      }
     790   }
     791
     792   map phi=r,m;
     793   //map phi=@R,m;
     794   ideal i=std(phi(i));
     795
     796   // ----------------------- test for finiteness ---------------------------
     797   //We need a test whether the coordinate change was random enough, if yes
     798   //we are ready, else call noetherNormal again
     799   list l=finitenessTest(i);
     800
     801   setring r;
     802   list l=imap(@S,l);
     803
     804   if(size(l[3]) == d)                    //the generic case
     805   {
     806      good = fetch(@S,m),l[3];
     807      kill @S,@R;
     808      return(good);
     809   }
     810   else                                   //the bad case
     811   { kill @S,@R;
     812      if ( voice >= 21 )
     813      {
     814       "// WARNING: In case of a finite ground field";
     815       "// the characteristic may be too small.";
     816       "// This could result in an infinte loop.";
     817       "// Loop in noetherNormal, voice:";, voice;"";
     818      }
     819     if ( voice >= 16 )
     820     {
     821       "// Switch to dense coordinate change";"";
     822       return(noetherNormal(i));
     823     }
     824     return(noetherNormal(i,p));
     825   }
     826}
     827example
     828{ "EXAMPLE:"; echo = 2;
     829   ring r=0,(x,y,z),dp;
     830   ideal i= xy,xz;
     831   noetherNormal(i);
     832}
     833///////////////////////////////////////////////////////////////////////////////
     834
     835proc finitenessTest(ideal i,list #)
     836"USAGE:   finitenessTest(J[,v]); J ideal, v intvec (say v1,...,vr)
     837RETURN:  a list, say l, with l[1] integer, l[2], l[3] ideals
     838         l[1] = 1 if var(v1),...,var(vr) are in l[2] and 0 else
     839         l[2] (resp. l[3]) contains those variables which occur, (resp. occur
     840         not) as pure power in the leading term of one of the generators of J
     841         (default: v = [1,2,..,nvars(basering)])
     842THEORY:  If J is a standard basis of an ideal generated by x_1 - f_1(y),...,
     843         x_n - f_n with y_j ordered lexicographically and y_j >> x_i, then,
     844         if y_i appears as pure power in the leading term of J[k], J[k] defines
     845         an integral relation for y_i over the y_(i+1),... and the f's.
     846         Moreover, in this situation, if l[2] = y_1,...,y_r, then K[y_1,...y_r]
     847         is finite over K[f_1..f_n]. If J contains furthermore polynomials
     848         h_j(y), then K[y_1,...y_z]/<h_j> is finite over K[f_1..f_n].
     849EXAMPLE: example finitenessTest; shows an example
     850"
     851{  intvec V = 1..nvars(basering);
     852   if (size(#) != 0 )
     853   {
     854     V = #[1];
     855   }
     856   intvec v,w;
     857   int j,z;
     858   // ---------------------- check leading exponents -------------------------
     859   for(j=1;j<=ncols(i);j++)
     860   {
     861      w=leadexp(i[j]);
     862      if(size(ideal(w))==1)           //the leading term of i[j] is a
     863      {                               //pure power of some variable
     864         v=v+w;
     865      }
     866   }
     867   // ----------------- pick the corresponding variables ---------------------
     868   //the nonzero entries of v correspond to variables which occur as
     869   //pure power in the leading term of some polynomial in i
     870   ideal zero, nonzero;
     871   for(j=1; j<=size(v); j++)
     872   {
     873      if(v[j]==0)
     874      {
     875         zero[size(zero)+1]=var(j);
     876      }
     877      else
     878      {
     879        nonzero[size(nonzero)+1]=var(j);
     880      }
     881   }
     882   // ---------------- do we have all pure powers we want? -------------------
     883   // test this by dividing the product of corresponding variables
     884   ideal max = maxideal(1);
     885   max = max[V];
     886   z = (product(nonzero)/product(max) != 0);
     887   return(list(z,nonzero,zero));
     888}
     889example
     890{ "EXAMPLE:"; echo = 2;
     891   ring s = 0,(x,y,z,a,b,c),(lp(3),dp);
     892   ideal i= a -(xy)^3+x2-z, b -y2-1, c -z3;
     893   ideal j = a -(xy)^3+x2-z, b -y2-1, c -z3, xy;
     894   finitenessTest(std(i),1..3);
     895   finitenessTest(std(j),1..3);
     896}
     897///////////////////////////////////////////////////////////////////////////////
     898
     899proc mapIsFinite(map phi, R, list #)
     900"USAGE:   mapIsFinite(phi,R[,J]); R a ring, phi: R ---> basering a map
     901         [J an ideal in the basering, J = 0 if not given]
     902RETURN:  1 if R ---> basering/J is finite and 0 else
     903EXAMPLE: example mapIsFinite; shows an example
     904"
     905{
     906  def bsr = basering;
     907  ideal J;
     908  if( size(#) != 0 )
     909  {
     910    J = #[1];
     911  }
     912  string os = ordstr(bsr);
     913  int m = nvars(bsr);
     914  int n = nvars(R);
     915  ideal PHI = ideal(phi);
     916  if ( ncols(PHI) < n )
     917  { PHI[n]=0;
     918  }
     919  // --------------------- change of variable names -------------------------
     920  execute("ring @bsr = ("+charstr(bsr)+"),y(1..m),("+os+");");
     921  ideal J = fetch(bsr,J);
     922  ideal PHI = fetch(bsr,PHI);
     923
     924  // --------------------------- enlarging ring -----------------------------
     925  execute("ring @rr = ("+charstr(bsr)+"),(y(1..m),x(1..n)),(lp(m),dp);");
     926  ideal J = imap(@bsr,J);
     927  ideal PHI = imap(@bsr,PHI);
     928  ideal M;
     929  int i;
     930
     931  for(i=1;i<=n;i++)
     932  {
     933    M[i]=x(i)-PHI[i];
     934  }
     935  M=std(M+J);
     936  // ----------------------- test for finiteness ---------------------------
     937  list l = finitenessTest(M,1..m);
     938  return(l[1]);
     939}
     940example
     941{ "EXAMPLE:"; echo = 2;
     942   ring r = 0,(a,b,c),dp;
     943   ring s = 0,(x,y,z),dp;
     944   ideal i= xy;
     945   map phi= r,(xy)^3+x2+z,y2-1,z3;
     946   mapIsFinite(phi,r,i);
     947}
     948//////////////////////////////////////////////////////////////////////////////
     949
  • Singular/LIB/primdec.lib

    rde63d0 r9050ca  
    1 // $Id: primdec.lib,v 1.39 1999-07-07 14:39:12 obachman Exp $
     1// $Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $
    22////////////////////////////////////////////////////////////////////////////////
    33// primdec.lib                                                                //
     
    1111////////////////////////////////////////////////////////////////////////////////
    1212
    13 version="$Id: primdec.lib,v 1.39 1999-07-07 14:39:12 obachman Exp $";
     13version="$Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $";
    1414info="
    15 LIBRARY: primdec.lib PROCEDURE FOR PRIMARY DECOMPOSITION
    16 
    17 AUTHORS: Gerhard Pfister, Wolfram Decker, Hans Schoenemann
     15LIBRARY: primdec.lib      PROCEDURES FOR PRIMARY DECOMPOSITION
     16AUTHORS:  Gerhard Pfister, email: pfister@mathematik.uni-kl.de (GTZ)
     17          Wolfram Decker, email: decker@math.uni-sb.de         (SY)
     18          Hans Schoenemann, email: hannes@mathematik.uni-kl.de (SY)
    1819
    1920PROCEDURES:
    20   minAssGTZ(I);     computes the minimal associated primes
    21                       via Gianni,Trager,Zacharias
    22   minAssChar(I);    computes the minimal associated primes
    23                       using characteristic sets
    24   primdecGTZ(I);    computes a complete primary decomposition
    25                       via Gianni,Trager,Zacharias
    26   primdecSY(I);     computes a complete primary decomposition
    27                       via Shimoyama-Yokoyama
    28   testPrimary(L,k); tests whether the result of the primary
    29                       decomposition is correct
     21  primdecGTZ(I);    complete primary decomposition via Gianni,Trager,Zacharias
     22  primdecSY(I);     complete primary decomposition via Shimoyama-Yokoyama
     23  minAssGTZ(I);     the minimal associated primes via Gianni,Trager,Zacharias
     24  minAssChar(I);    the minimal associated primes using characteristic sets
     25  testPrimary(L,k); tests the result of the primary decomposition
    3026  radical(I);       computes the radical of the ideal I
    31   equiRadical(I);   computes the radical of the equidimensional part
    32                       of the ideal I
    33   prepareAss(I);    computes the radicals of the equidimensional parts of I
     27  equiRadical(I);   the radical of the equidimensional part of the ideal I
     28  prepareAss(I);    list of radicals of the equidimensional components of I
    3429
    3530REMARK:
     
    468463      i[m]=poly(e)^e*leadcoef(i[m])^(e-1)*i[m];
    469464
    470       if(i[m]==0)
     465      if((i[m]==0)&&(voice>=15))
    471466      {
    472467         "Warning: The characteristic ist too small to use";
    473468         "the Algorithm of Gianni/Trager/Zacharias.";
    474469         "This may result in an infinte loop";
     470         " current nesting level in primaryTest",voice;
    475471      }
    476472      if (reduce(i[m]-t^e,prm,1) !=0)
     
    777773  }
    778774
    779 //withe the factors new ideals (hopefully the primary decomposition)
     775//with the factors new ideals (hopefully the primary decomposition)
    780776//are created
    781777
     
    15281524         minAssPrimes(i,1); i ideal  (to use also the factorizing Groebner)
    15291525RETURN:  list = the minimal associated prime ideals of i
    1530 NOTE:
    15311526EXAMPLE: example minAssPrimes; shows an example
    15321527"
     
    16501645   list pr= minAssPrimes(i);
    16511646   pr;
    1652    pr= minAssPrimes(i,1);
     1647   minAssPrimes(i,1);
    16531648}
    16541649
     
    19471942  //look for subring such that the intersection with the ideal is zero
    19481943  //j intersected with K[var(indep[3]+1),...,var(nvar] is zero,
    1949   //indep[1] is the new varstring and indep[2] the string for the block-ordering
     1944  //indep[1] is the new varstring and indep[2] the string for block-ordering
    19501945  //------------------------------------------------------------------
    19511946
     
    20572052     //leading coefficients of the polynomials  there (polynomials in
    20582053     //K[var(nnp+1),..,var(nva)]) are collected in the list h,
    2059      //we need their ggt, gh, because of the following:
    2060      //let (j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..]
     2054     //we need their ggt, gh, because of the following: let
     2055     //(j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..]
    20612056     //intersected with K[var(1),...,var(nva)] is (j:gh^n)
    20622057     //on the other hand j=(j,gh^n) intersected with (j:gh^n)
     
    20642059     //------------------------------------------------------------------------------------
    20652060
    2066      //the arrangement for the quotientring K(var(nnp+1),..,var(nva))[..the rest..]
    2067      //and the map phi:K[var(1),...,var(nva)] ----->K(var(nnpr+1),..,var(nva))[..the rest..]
     2061     //arrangement for quotientring K(var(nnp+1),..,var(nva))[..the rest..] and
     2062     //map phi:K[var(1),...,var(nva)] -->K(var(nnpr+1),..,var(nva))[..rest..]
    20682063     //-------------------------------------------------------------------------------------
    20692064
     
    21122107     //but fi polynomials, then the intersection of q with the polynomialring
    21132108     //is the saturation of the ideal generated by f1,...,fr with respect to
    2114      //h which is the lcm of the leading coefficients of the fi considered in the
    2115      //quotientring: this is coded in saturn
     2109     //h which is the lcm of the leading coefficients of the fi considered
     2110     //in the quotientring: this is coded in saturn
    21162111
    21172112     list saturn;
     
    40084003proc primdecGTZ(ideal i)
    40094004"USAGE:  primdecGTZ(i); i ideal
    4010 RETURN:  list = list of primary ideals
    4011                 and their associated primes
     4005RETURN:  a list, say pr, of primary ideals and their associated primes
     4006         pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component
    40124007NOTE:    Algorithm of Gianni, Traeger, Zacharias
    4013          designed for characteristic 0, works also in char k >> 0,
     4008         designed for characteristic 0, works also in char k > 0,
    40144009         may result in an infinite loop in small characteristic
    40154010EXAMPLE: example primdecGTZ; shows an example
     
    40314026proc primdecSY(ideal i)
    40324027"USAGE:  primdecSY(i); i ideal
    4033 RETURN:  list = list of primary ideals
    4034                 and their associated primes
     4028RETURN:  a list, say pr, of primary ideals and their associated primes
     4029         pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component
    40354030NOTE:    Algorithm of Shimoyama-Yokoyama
    4036          implemented for characteristic 0, works also in char k >> 0,
    4037          the result may be not compltely decomposed in small characteristic
     4031         implemented for characteristic 0, works also in char k > 0,
     4032         the result may be not completely decomposed in small characteristic
    40384033EXAMPLE: example primdecSY; shows an example
    40394034"
     
    40544049"USAGE:  minAssGTZ(i); i ideal
    40554050RETURN:  list = the minimal associated prime ideals of i
    4056 NOTE:    designed for characteristic 0, works also in char k >> 0,
     4051NOTE:    designed for characteristic 0, works also in char k > 0
     4052         if it terminates,
    40574053         may result in an infinite loop in small characteristic
    40584054EXAMPLE: example minAssGTZ; shows an example
     
    40754071"USAGE:  minAssChar(i); i ideal
    40764072RETURN:  list = the minimal associated prime ideals of i
    4077 NOTE:    implemented for characteristic 0, works also in char k >> 0,
    4078          the result may be not compltely decomposed in small characteristic
    4079 EXAMPLE: example primdecSY; shows an example
     4073NOTE:    implemented for characteristic 0, works also in char k > 0,
     4074         the result may be not completely decomposed in small characteristic
     4075EXAMPLE: example minAssChar; shows an example
    40804076"
    40814077{
     
    40944090proc equiRadical(ideal i)
    40954091"USAGE:  equiRadical(i); i ideal
    4096 RETURN:  ideal = the intersection of associated primes
    4097          of i of dimension of i
    4098 NOTE:    designed for characteristic 0, works also in char k >> 0,
     4092RETURN:  ideal, intersection of associated primes of i of maximal  dimension
     4093NOTE:    designed for characteristic 0, works also in char k > 0
     4094         if it terminates,
    40994095         may result in an infinite loop in small characteristic
    41004096EXAMPLE: example equiRadical; shows an example
     
    41184114NOTE:    a combination of the algorithms of Krick/Logar
    41194115         and Eisenbud/Huneke/Vasconcelos
    4120          designed for characteristic 0, works also in char k >> 0,
     4116         designed for characteristic 0, works also in char k > 0
     4117         if it termintes,
    41214118         may result in an infinite loop in small characteristic
    41224119EXAMPLE: example radical; shows an example
     
    42134210proc prepareAss(ideal i)
    42144211"USAGE:  prepareAss(i); i ideal
    4215 RETURN:  list = the radicals of the equidimensional parts of i
    4216 NOTE:    algorithm of Eisenbud,Huneke and Vasconcelos
     4212RETURN:  list = the radicals of the maximal dimensional components of i
     4213NOTE:    uses algorithm of Eisenbud,Huneke and Vasconcelos
    42174214EXAMPLE: example prepareAss; shows an example
    42184215"
     
    42544251
    42554252proc testPrimary(list pr, ideal k)
    4256 "USAGE:   testPrimary(pr,k) pr=primdecGTZ(k) or primdecSY(k)
    4257 RETURN:   int = 1, if the intersection of the primary ideals
    4258                 in pr is k, 0 if not
    4259 NOTE:
     4253"USAGE:   testPrimary(pr,k); pr a list, result of primdecGTZ(k) or primdecSY(k)
     4254RETURN:  int = 1, if intersection of the primary ideals in pr is k, 0 if not
    42604255EXAMPLE: example testPrimary ; shows an example
    42614256"
Note: See TracChangeset for help on using the changeset viewer.