Changeset 66bd95 in git


Ignore:
Timestamp:
Oct 15, 2010, 1:34:09 PM (14 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b4f17ed1d25f93d46dbe29e4b499baecc2fd51bb')
Children:
d692ae49dab0ddddc8488ff64821b70c93c6a26e
Parents:
fa932acebab34d79952f33e66135a857adfb0248
Message:
format

git-svn-id: file:///usr/local/Singular/svn/trunk@13505 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/sagbi.lib

    rfa932ac r66bd95  
    1010OVERVIEW:
    1111SAGBI stands for 'subalgebra bases analogous to Groebner bases for ideals'.
    12 SAGBI bases provide important tools for working with finitely presented 
     12SAGBI bases provide important tools for working with finitely presented
    1313subalgebras of a polynomial ring. Note that in contrast to Groebner
    1414bases, SAGBI bases may be infinite.
    … …  
    2828";
    2929
    30 LIB "elim.lib"; 
     30LIB "elim.lib";
    3131LIB "toric.lib";
    3232LIB "algebra.lib";
    … …  
    6565  ideal varsBasering=maxideal(1);
    6666  int numTotalAdditionalVars=ncols(leadTermsAlgebra);
    67   string variableName=uniqueVariableName("@y"); //get a variable name different from existing variables
    68 
    69   //-------- extend current baserring r with new variables @y, one for each new element in ideal algebra  -------------
     67  string variableName=uniqueVariableName("@y");
     68  //get a variable name different from existing variables
     69
     70  //-------- extend current baserring r with new variables @y,
     71  // one for each new element in ideal algebra  -------------
    7072  list l = ringlist(r);
    7173  for (i=nvars(r)-nvars(br)+1; i<=numTotalAdditionalVars;i++)
    … …  
    9799static proc stdKernPhi(ideal kernNew, ideal kernOld, ideal leadTermsAlgebra,int method)
    98100{
    99   /* Computes Groebner basis of kernNew+kernOld, where kernOld already is a Groebner basis
     101  /* Computes Groebner basis of kernNew+kernOld, where kernOld already is a GB
    100102   * and kernNew contains elements of the form @y(i)-leadTermsAlgebra[i] added to it.
    101103   * The techniques chosen is specified by the integer method
    … …  
    108110    kern=kernOld+kernNew;
    109111    kern=std(kern);
    110     //kern=std(kernOld,kernNew); //Found bug using this method. TODO Change if bug is removed
    111     //this call of std return Groebner Basis of ideal kernNew+kernOld given that kernOld is a Groebner basis
     112    //kern=std(kernOld,kernNew); //Found bug using this method.
     113    // TODO Change if bug is removed
     114    //this call of std return Groebner Basis of ideal kernNew+kernOld
     115    // given that kernOld is a Groebner basis
    112116  }
    113117  if (method==1)
    … …  
    135139  ideal varsBasering=maxideal(1);
    136140  ideal leadTermsAlgebra=lead(algebra);
    137   //save leading terms as ordering in ring extension may not be compatible with ordering in basering
     141  //save leading terms as ordering in ring extension
     142  //may not be compatible with ordering in basering
    138143  int numGenerators=ncols(algebra);
    139144
    140   def rNew=extendRing(r,leadTermsAlgebra,method); // important: br has to be active here
     145  def rNew=extendRing(r,leadTermsAlgebra,method);
     146  // important: br has to be active here
    141147  setring r;
    142   if (!defined(kern)) //only true for first run of spolynomialGB in sagbi construction algorithms
     148  if (!defined(kern))
     149  //only true for first run of spolynomialGB in sagbi construction algorithms
    143150  {
    144151    ideal kern=0;
    … …  
    146153  }
    147154  setring rNew;
    148   //-------------------------- transfer object to new ring rNew ----------------------------------------
     155  //-------------------------- transfer object to new ring rNew ----------------------
    149156  ideal varsBasering=fetch(br,varsBasering);
    150157  ideal kernOld,algebraicRelationsOld;
    … …  
    153160  ideal leadTermsAlgebra=fetch(br,leadTermsAlgebra);
    154161  ideal listOfVariables=maxideal(1);
    155   //-----------------------define kernNew containing elements to be added to the ideal kern -------------
     162  //---------define kernNew containing elements to be added to the ideal kern --------
    156163  ideal kernNew;
    157164  for (int i=nvars(r)-nvars(br)+1; i<=numGenerators; i++)
    … …  
    159166    kernNew[i-nvars(r)+nvars(br)]=leadTermsAlgebra[i]-listOfVariables[i+nvars(br)];
    160167  }
    161   //-------------------------- calulate kernel of Phi depending on method choosen -----------------------
     168  //--------------- calulate kernel of Phi depending on method choosen ---------------
    162169
    163170  attrib(kernOld,"isSB",1);
    … …  
    167174  attrib(algebraicRelationsOld,"isSB",1);
    168175  ideal algebraicRelationsNew=reduce(algebraicRelations,algebraicRelationsOld);
    169   /*        algebraicRelationsOld is a groebner basis by construction (as variable ordering is
     176  /*        algebraicRelationsOld is a groebner basis by construction (as variable
     177   *        ordering is
    170178   *        block ordering we have an elemination ordering for the varsBasering)
    171179   *        Therefore, to only get the new algebraic relations, calculate
    … …  
    204212    }
    205213  }
    206   //The columns of the matrix A are now the exponent vectors of the leadings monomials in algebra.
     214  //The columns of the matrix A are now the exponent vectors
     215  //of the leadings monomials in algebra.
    207216  intmat A[n][m]=intmat(tempVec,n,m);
    208217  //Create the preimage ring K[@y(1),...,@y(m)], where m=ncols(algebra).
    … …  
    235244static proc reductionGB(ideal F, ideal algebra,r, int tailreduction,int method,int parRed)
    236245{
    237   /* This procedure does the actual SAGBI/subalgebra reduction using Groebner basis methods and is
     246  /* This procedure does the actual SAGBI/subalgebra reduction using GB methods and is
    238247   * called by the procedures sagbiReduce,sagbi and sagbiPart
    239    * If r already is an extension of the basering and contains the ideal kern needed for the subalgebra reduction,
     248   * If r already is an extension of the basering
     249   * and contains the ideal kern needed for the subalgebra reduction,
    240250   * the reduction can be started directly, at each reduction step using the fact that
    241251   * p=reduce(leadF,kern) in K[@y(1),...,@y(m)] <=> leadF in K[lead(algebra)]
    … …  
    249259  if (numVarsBasering==nvars(r))
    250260  {
    251     /* Case that ring r is the same ring as the basering. Using proc extendRing, stdKernPhi
     261    /* Case that ring r is the same ring as the basering. Using proc extendRing,
     262     * stdKernPhi
    252263     * one construct the extension of the current baserring with new variables @y, one for each element
    253264     * in ideal algebra and calculates the kernel of Phi, where
    254      * Phi: r---->br, x_i-->x_i, y_i-->f_i, algebra={f_1,...f_m}, br=K[x1,...,x_n] und r=K[x1,...x_n,@y1,...@y_m]
    255      * This is similarly done (however step by step for each run of the SAGBI construction algorithm) in the procedure spolynomialsGB
     265     * Phi: r---->br, x_i-->x_i, y_i-->f_i,
     266     * algebra={f_1,...f_m}, br=K[x1,...,x_n] und r=K[x1,...x_n,@y1,...@y_m]
     267     * This is similarly dones
     268     * (however step by step for each run of the SAGBI construction algorithm)
     269     * in the procedure spolynomialsGB
    256270     */
    257271    ideal leadTermsAlgebra=lead(algebra);
    … …  
    275289  poly p,normalform,leadF;
    276290  intvec tempExp;
    277   //------------------algebraic reduction for each polynomial F[i] ---------------------------------------
     291  //-------------algebraic reduction for each polynomial F[i] ------------------------
    278292  for (i=1; i<=ncols(F);i++)
    279293  {
    … …  
    282296    {
    283297      leadF=lead(F[i]);
    284       if(leadmonom(leadF)==1) { //K is always contained in the subalgebra, thus the remainder is zero in this case
     298      if(leadmonom(leadF)==1)
     299      {
     300      //K is always contained in the subalgebra,
     301      //thus the remainder is zero in this case
    285302        if (parRed) { break; }
    286303        else { F[i]=0; break; }
    287304      }
    288       //note: as the ordering in br and r might not be compatible it can be that lead(F[i]) in r is
    289       //different from lead(F[i]) in br. To take the "correct" leading term therefore take lead(F[i])
     305      //note: as the ordering in br and r might not be compatible
     306      //it can be that lead(F[i]) in r is
     307      //different from lead(F[i]) in br.
     308      //To take the "correct" leading term therefore take lead(F[i])
    290309      //in br and transfer it to the extension r
    291310      setring r;
    … …  
    293312      p=reduce(leadF,kern);
    294313      if (leadmonom(p)<varsBasering[numVarsBasering])
    295       {        //as choosen ordering is a block ordering, lm(p) in K[y_1...y_m] is equivalent to lm(p)<x_n
     314      {
     315        //as choosen ordering is a block ordering,
     316        //lm(p) in K[y_1...y_m] is equivalent to lm(p)<x_n
    296317        //Needs to be changed, if no block ordering is used!
    297318        setring br;
    … …  
    322343
    323344static proc reduceByMonomials(ideal algebra)
    324 /*This procedures uses the sagbiReduce procedure to reduce all polynomials in algebra, which
    325  * are not monomials, by the subset of all monomials.
     345/*This procedures uses the sagbiReduce procedure to reduce all polynomials in algebra,
     346 * which are not monomials, by the subset of all monomials.
    326347 */
    327348{
    … …  
    340361    }
    341362  }
    342   //Monomials now contains the subset of all monomials in algebra, algebra contains the non-monomials.
     363  //Monomials now contains the subset of all monomials in algebra,
     364  //algebra contains the non-monomials.
    343365  if(size(monomials)>0)
    344366  {
    … …  
    358380
    359381static proc sagbiConstruction(ideal algebra, int iterations, int tailreduction, int method,int parRed)
    360 /* This procedure is the SAGBI construction algorithm and does the actual computation both for
    361  * the procedure sagbi and sagbiPart.
    362  * - If the sagbi procedure calls this procedure, iterations==-1 and this procedure only stops
    363  *   if all S-Polynomials reduce to zero (criterion for termination of SAGBI construction algorithm).
    364  * - If the sagbiPart procedure calls this procedure, iterations>=0 and iterations specifies the
     382/* This procedure is the SAGBI construction algorithm and does the actual computation
     383 * both for the procedure sagbi and sagbiPart.
     384 * - If the sagbi procedure calls this procedure, iterations==-1
     385 *   and this procedure only stops
     386 *   if all S-Polynomials reduce to zero
     387 *   (criterion for termination of SAGBI construction algorithm).
     388 * - If the sagbiPart procedure calls this procedure, iterations>=0
     389 *   and iterations specifies the
    365390 *   number of iterations. A degree boundary is not used here.
    366  * Note that parRed is used for testing a special modification and can be ignored (assume parRed==0).
     391 * Note that parRed is used for testing a special modification
     392 * and can be ignored (assume parRed==0).
    367393 */
    368394{
    … …  
    384410    iterations=1;
    385411  }
    386   ideal P=1; //note: P is initialized this way, so that the while loop is entered. P gets overriden there, anyhow.
     412  ideal P=1;
     413  //note: P is initialized this way, so that the while loop is entered.
     414  //P gets overriden there, anyhow.
    387415  ideal varsBasering=maxideal(1);
    388416  map phi;
    … …  
    397425    phi=r,varsBasering,algebra;
    398426    spolynomialsNew=simplify(phi(algebraicRelationsNew),6);
    399     //By construction spolynomialsNew only contains the spolynomials, that have not already
     427    //By construction spolynomialsNew only contains the spolynomials,
     428    //that have not already
    400429    //been calculated in the steps before.
    401430    P=reductionGB(spolynomialsNew,algebra,r,tailreduction,method,parRed);
    … …  
    414443    if (parRed==0)
    415444    {
    416       P=reduceByMonomials(P);  //Reducing with monomials is cheap and can only result in less terms
    417       P=simplify(simplify(P,3),4); //Avoid that zeros are added to the bases or one element in P more than once
     445      P=reduceByMonomials(P);
     446      //Reducing with monomials is cheap and can only result in less terms
     447      P=simplify(simplify(P,3),4);
     448      //Avoid that zeros are added to the bases or one element in P more than once
    418449    }
    419450    else
    … …  
    421452      P=simplify(P,6);
    422453    }
    423     algebra=algebra,P;         //Note that elements and order of elements must in algebra must not be changed, otherwise the already calculated
     454    algebra=algebra,P;
     455    //Note that elements and order of elements must in algebra must not be changed,
     456    //otherwise the already calculated
    424457    //ideal in r will give wrong results. Thus it is important to use a komma here.
    425458    i=i+step;
    … …  
    430463    {
    431464      dbprint(4-voice,
    432               "//SAGBI construction algorithm terminated after "+string(i-1)+" iterations, as all SAGBI S-polynomials reduced to 0.
     465              "//SAGBI construction algorithm terminated after "+string(i-1)
     466              +" iterations, as all SAGBI S-polynomials reduced to 0.
    433467//Returned generators therefore are a SAGBI basis.");
    434468    }
    … …  
    436470    {
    437471      dbprint(4-voice,
    438               "//SAGBI construction algorithm stopped as it reached the limit of "+string(iterations)+" iterations.
     472              "//SAGBI construction algorithm stopped as it reached the limit of "
     473              +string(iterations)+" iterations.
    439474//In general the returned generators are no SAGBI basis for the given algebra.");
    440475    }
    … …  
    640675  ideal P=p1,p2;
    641676  //---------------------------------------------
    642   //SAGBI reduction of polynomial p1 by algebra A. Default call, that is, no tail-reduction is done.
     677  //SAGBI reduction of polynomial p1 by algebra A.
     678  //Default call, that is, no tail-reduction is done.
    643679  sagbiReduce(p1,A);
    644680  //---------------------------------------------
    645   //SAGBI reduction of set of polynomials P by algebra A, now tail-reduction is done.
     681  //SAGBI reduction of set of polynomials P by algebra A,
     682  //now tail-reduction is done.
    646683  sagbiReduce(P,A,1);
    647684}
    … …  
    943980
    944981  //In quotient rings, SINGULAR, usually does not reduce polynomials w.r.t the
    945   //quotient ideal,therefore we should first  reduce ,when it is necessary for computations,
     982  //quotient ideal,therefore we should first  reduce,
     983  //when it is necessary for computations,
    946984  // to have a uniquely determined representant for each equivalent
    947985  //class,which is the case of this algorithm.
Note: See TracChangeset for help on using the changeset viewer.