Changeset ac38de1 in git for Singular/LIB


Ignore:
Timestamp:
Oct 11, 2010, 2:48:14 PM (14 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
32378f5bd525032b437ebb1823d9c2430b3665a4
Parents:
3b81b813dd9fe8524513396ba07bb5ed8fbbae92
Message:
doc format

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

Legend:

Unmodified
Added
Removed

  • Singular/LIB/ncfactor.lib

    r3b81b81 rac38de1  
    66AUTHORS: Albert Heinle,     albert.heinle@rwth-aachen.de
    77@*       Viktor Levandovskyy,     levandov@math.rwth-aachen.de
    8 OVERVIEW: In this library, new methods for factorization on polynomials
    9 
    10 are implemented for two algebras over a field K. Recall, that
    11 
    12 the first Weyl algebra over K is generated by x,d obeying the relation d*x=x*d+1.
    13 
    14 The first shift algebra over K is generated by x,s obeying the relation s*x=x*s+s.
     8OVERVIEW: In this library, new methods for factorization on polynomials
     9  are implemented for two algebras over a field K. Recall, that
     10  the first Weyl algebra over K is generated by x,d obeying the relation d*x=x*d+1.
     11  The first shift algebra over K is generated by x,s obeying the relation s*x=x*s+s.
    1512
    1613PROCEDURES:
    17 facFirstWeyl(h);    factorization in the first Weyl algebra
    18 testNCfac(l[,h]);   tests factorizations from a given list for correctness
    19 facSubWeyl(h,X,D);  factorization in the first Weyl algebra as a subalgebra
    20 facFirstShift(h);   factorization in the first shift algebra
     14  facFirstWeyl(h);    factorization in the first Weyl algebra
     15  testNCfac(l[,h]);   tests factorizations from a given list for correctness
     16  facSubWeyl(h,X,D);  factorization in the first Weyl algebra as a subalgebra
     17  facFirstShift(h);   factorization in the first shift algebra
    2118";
    2219
    … …  
    5047      if (size(l[i])!= size(l[j]))
    5148      {//different sizes => not equal
    52         j++;
    53         continue;
     49        j++;
     50        continue;
    5451      }//different sizes => not equal
    5552      is_equal = 1;
    5653      for (k = 1; k <= size(l[i]);k++)
    5754      {//Compare every entry
    58         if (l[i][k]!=l[j][k])
    59         {
    60           is_equal = 0;
    61           break;
    62         }
     55        if (l[i][k]!=l[j][k])
     56        {
     57          is_equal = 0;
     58          break;
     59        }
    6360      }//Compare every entry
    6461      if (is_equal == 1)
    6562      {//Delete this entry, because there is another equal one int the list
    66         result = delete(result, i-deleted);
    67         deleted = deleted+1;
    68         break;
     63        result = delete(result, i-deleted);
     64        deleted = deleted+1;
     65        break;
    6966      }//Delete this entry, because there is another equal one int the list
    7067    }//Compare the i'th factorization to the j'th
    … …  
    8885      if (product(result[i]) == product(result[j]))
    8986      {//There are two equal results; throw away that one with the smaller size
    90         if (size(result[i])>=size(result[j]))
    91         {//result[i] has more entries
    92           result = delete(result,j);
    93           continue;
    94         }//result[i] has more entries
    95         else
    96         {//result[j] has more entries
    97           result = delete(result,i);
    98           i--;
    99           break;
    100         }//result[j] has more entries
     87        if (size(result[i])>=size(result[j]))
     88        {//result[i] has more entries
     89          result = delete(result,j);
     90          continue;
     91        }//result[i] has more entries
     92        else
     93        {//result[j] has more entries
     94          result = delete(result,i);
     95          i--;
     96          break;
     97        }//result[j] has more entries
    10198      }//There are two equal results; throw away that one with the smaller size
    10299    }//comparing with the other elements
    … …  
    146143    {//shifting the window of combinable factors to the left
    147144      //fc below stands for "factors combined"
    148       fc = combinekfinlf(list(g[(j)..(j+nofgl - i)]),nof - i + 1,limits); 
     145      fc = combinekfinlf(list(g[(j)..(j+nofgl - i)]),nof - i + 1,limits);
    149146      for (k = 1; k<=size(fc); k++)
    150147      {//iterating over the different solutions of the smaller problem
    151         if (j>1)
    152         {//There are g_i before the combination
    153           if (j+nofgl -i < nofgl)
    154           {//There are g_i after the combination
    155             temp = list(g[1..(j-1)]) + fc[k] + list(g[(j+nofgl-i+1)..nofgl]);
    156           }//There are g_i after the combination
    157           else
    158           {//There are no g_i after the combination
    159             temp = list(g[1..(j-1)]) + fc[k];
    160           }//There are no g_i after the combination
    161         }//There are g_i before the combination
    162         if (j==1)
    163         {//There are no g_i before the combination
    164           if (j+ nofgl -i <nofgl)
    165           {//There are g_i after the combination
    166             temp = fc[k]+ list(g[(j + nofgl - i +1)..nofgl]);
    167           }//There are g_i after the combination
    168         }//There are no g_i before the combination
    169         if (limitcheck(temp,limits))
    170         {
    171           result = result + list(temp);
    172         }
     148        if (j>1)
     149        {//There are g_i before the combination
     150          if (j+nofgl -i < nofgl)
     151          {//There are g_i after the combination
     152            temp = list(g[1..(j-1)]) + fc[k] + list(g[(j+nofgl-i+1)..nofgl]);
     153          }//There are g_i after the combination
     154          else
     155          {//There are no g_i after the combination
     156            temp = list(g[1..(j-1)]) + fc[k];
     157          }//There are no g_i after the combination
     158        }//There are g_i before the combination
     159        if (j==1)
     160        {//There are no g_i before the combination
     161          if (j+ nofgl -i <nofgl)
     162          {//There are g_i after the combination
     163            temp = fc[k]+ list(g[(j + nofgl - i +1)..nofgl]);
     164          }//There are g_i after the combination
     165        }//There are no g_i before the combination
     166        if (limitcheck(temp,limits))
     167        {
     168          result = result + list(temp);
     169        }
    173170      }//iterating over the different solutions of the smaller problem
    174171    }//shifting the window of combinable factors to the left
    … …  
    263260      if (f[i] == g[j])
    264261      {//we have an equal pair
    265         M = M + list(list(i,j));
     262        M = M + list(list(i,j));
    266263      }//we have an equal pair
    267264    }//... with g
    … …  
    284281      if (M[i][1]<=temp[1])
    285282      {//a possible candidate that is smaller than temp could have been found
    286         if (M[i][1]==temp[1])
    287         {//In this case we must look at the second number
    288           if (M[i][2]< temp[2])
    289           {//the candidate is smaller
    290             temp = M[i];
    291             temppos = i;
    292           }//the candidate is smaller
    293         }//In this case we must look at the second number
    294         else
    295         {//The candidate is definately smaller
    296           temp = M[i];
    297           temppos = i;
    298         }//The candidate is definately smaller
     283        if (M[i][1]==temp[1])
     284        {//In this case we must look at the second number
     285          if (M[i][2]< temp[2])
     286          {//the candidate is smaller
     287            temp = M[i];
     288            temppos = i;
     289          }//the candidate is smaller
     290        }//In this case we must look at the second number
     291        else
     292        {//The candidate is definately smaller
     293          temp = M[i];
     294          temppos = i;
     295        }//The candidate is definately smaller
    299296      }//a possible candidate that is smaller than temp could have been found
    300297    }//finding the minimal element of M
    … …  
    304301      if (temp[1]<size(f))
    305302      {//The most common case
    306         //first the combinations ignoring common factors
    307         pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits);
    308         post = merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
    309         for (i = 1; i <= size(pre); i++)
    310         {//all possible pre's...
    311           for (j = 1; j<= size(post); j++)
    312           {//...combined with all possible post's
    313             candidate = pre[i]+list(f[temp[1]])+post[j];
    314             if (limitcheck(candidate,limits))
    315             {
    316               result = result + list(candidate);
    317             }
    318           }//...combined with all possible post's
    319         }//all possible pre's...
    320         //Now the combinations with respect to common factors
    321         post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
    322         if (size(post)>0)
    323         {//There are factors to combine
    324           for (i = 1; i <= size(pre); i++)
    325           {//all possible pre's...
    326             for (j = 1; j<= size(post); j++)
    327             {//...combined with all possible post's
    328               candidate= pre[i]+list(f[temp[1]])+post[j];
    329               if (limitcheck(candidate,limits))
    330               {
    331                 result = result + list(candidate);
    332               }
    333             }//...combined with all possible post's
    334           }//all possible pre's...
    335         }//There are factors to combine
     303        //first the combinations ignoring common factors
     304        pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits);
     305        post = merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
     306        for (i = 1; i <= size(pre); i++)
     307        {//all possible pre's...
     308          for (j = 1; j<= size(post); j++)
     309          {//...combined with all possible post's
     310            candidate = pre[i]+list(f[temp[1]])+post[j];
     311            if (limitcheck(candidate,limits))
     312            {
     313              result = result + list(candidate);
     314            }
     315          }//...combined with all possible post's
     316        }//all possible pre's...
     317        //Now the combinations with respect to common factors
     318        post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
     319        if (size(post)>0)
     320        {//There are factors to combine
     321          for (i = 1; i <= size(pre); i++)
     322          {//all possible pre's...
     323            for (j = 1; j<= size(post); j++)
     324            {//...combined with all possible post's
     325              candidate= pre[i]+list(f[temp[1]])+post[j];
     326              if (limitcheck(candidate,limits))
     327              {
     328                result = result + list(candidate);
     329              }
     330            }//...combined with all possible post's
     331          }//all possible pre's...
     332        }//There are factors to combine
    336333      }//The most common case
    337334      else
    338335      {//the last factor is the common one
    339         pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits);
    340         for (i = 1; i<= size(pre); i++)
    341         {//iterating over the possible pre-factors
    342           candidate = pre[i]+list(f[temp[1]]);
    343           if (limitcheck(candidate,limits))
    344           {
    345             result = result + list(candidate);
    346           }
    347         }//iterating over the possible pre-factors
     336        pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits);
     337        for (i = 1; i<= size(pre); i++)
     338        {//iterating over the possible pre-factors
     339          candidate = pre[i]+list(f[temp[1]]);
     340          if (limitcheck(candidate,limits))
     341          {
     342            result = result + list(candidate);
     343          }
     344        }//iterating over the possible pre-factors
    348345      }//the last factor is the common one
    349346    }//There are factors to combine before the equal factor
    … …  
    352349      if (temp[1]<size(f))
    353350      {//Just a check for security
    354         //first without common factors
    355         post=merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
    356         for (i = 1; i<=size(post); i++)
    357         {
    358           candidate = list(f[temp[1]])+post[i];
    359           if (limitcheck(candidate,limits))
    360           {
    361             result = result + list(candidate);
    362           }
    363         }
    364         //Now with common factors
    365         post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
    366         if(size(post)>0)
    367         {//we could find other combinations
    368           for (i = 1; i<=size(post); i++)
    369           {
    370             candidate = list(f[temp[1]])+post[i];
    371             if (limitcheck(candidate,limits))
    372             {
    373               result = result + list(candidate);
    374             }
    375           }
    376         }//we could find other combinations
     351        //first without common factors
     352        post=merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
     353        for (i = 1; i<=size(post); i++)
     354        {
     355          candidate = list(f[temp[1]])+post[i];
     356          if (limitcheck(candidate,limits))
     357          {
     358            result = result + list(candidate);
     359          }
     360        }
     361        //Now with common factors
     362        post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits);
     363        if(size(post)>0)
     364        {//we could find other combinations
     365          for (i = 1; i<=size(post); i++)
     366          {
     367            candidate = list(f[temp[1]])+post[i];
     368            if (limitcheck(candidate,limits))
     369            {
     370              result = result + list(candidate);
     371            }
     372          }
     373        }//we could find other combinations
    377374      }//Just a check for security
    378375    }//There are no factors to combine before the equal factor
    … …  
    477474      for (i = 1; i<=-m; i++)
    478475      {
    479         result = result + list(var(1));
     476        result = result + list(var(1));
    480477      }
    481478    }//There are more x than y
    … …  
    485482      for (i = 1; i<=m;i++)
    486483      {
    487         result = result + list(var(2));
     484        result = result + list(var(2));
    488485      }
    489486    }//There are more y than x
    … …  
    600597      if (list_azero[i+1]==var(2))
    601598      {
    602         list_azero[i] = var(1)*var(2);
    603         list_azero = delete(list_azero,i+1);
     599        list_azero[i] = var(1)*var(2);
     600        list_azero = delete(list_azero,i+1);
    604601      }
    605602    }
    … …  
    608605      if (list_azero[i+1]==var(1))
    609606      {
    610         list_azero[i] = var(2)*var(1);
    611         list_azero = delete(list_azero,i+1);
     607        list_azero[i] = var(2)*var(1);
     608        list_azero = delete(list_azero,i+1);
    612609      }
    613610    }
    … …  
    615612  if(deg(h,intvec(-1,1))!=0)
    616613  {//list_not_azero is not empty
    617     list_not_azero = 
     614    list_not_azero =
    618615      one_hom_fac[(size(one_hom_fac)-absValue(deg(h,intvec(-1,1)))+1)..size(one_hom_fac)];
    619616    is_list_not_azero_empty = 0;
    … …  
    625622  map thetamap = r,x,y;
    626623  if(!is_list_not_azero_empty)
    627   {//Mapping in Singular is only possible, if the list before 
     624  {//Mapping in Singular is only possible, if the list before
    628625    //contained at least one element of the other ring
    629626    list list_not_azero = thetamap(list_not_azero);
    630   }//Mapping in Singular is only possible, if the list before 
     627  }//Mapping in Singular is only possible, if the list before
    631628  //contained at least one element of the other ring
    632629  if(!is_list_azero_empty)
    633   {//Mapping in Singular is only possible, if the list before 
     630  {//Mapping in Singular is only possible, if the list before
    634631    //contained at least one element of the other ring
    635632    list list_azero= thetamap(list_azero);
    636   }//Mapping in Singular is only possible, if the list before 
     633  }//Mapping in Singular is only possible, if the list before
    637634  //contained at least one element of the other ring
    638635  list k_factor = thetamap(k_factor);
    … …  
    650647      for (k = 0; k < leadexp(tempmons[j])[2];k++)
    651648      {
    652         entry = entry*(theta-k);
     649        entry = entry*(theta-k);
    653650      }
    654651      tempmons[j] = entry;
    … …  
    679676      for (j=1; j<=size(result[i]);j++)
    680677      {
    681         if (result[i][j]==shiftvar)
    682         {
    683           shift = shift + shift_sign;
    684         }
    685         else
    686         {
    687           result[i][j] = subst(result[i][j],theta,theta + shift);
    688         }
     678        if (result[i][j]==shiftvar)
     679        {
     680          shift = shift + shift_sign;
     681        }
     682        else
     683        {
     684          result[i][j] = subst(result[i][j],theta,theta + shift);
     685        }
    689686      }
    690687    }//adjust the a_0-parts
    … …  
    714711      if (result[i][j]==theta)
    715712      {//the jth entry is theta and can be written as x*y
    716         thetapos = j;
    717         result[i]= insert(result[i],x,j-1);
    718         j++;
    719         result[i][j] = y;
    720         found_theta = 1;
    721         break;
     713        thetapos = j;
     714        result[i]= insert(result[i],x,j-1);
     715        j++;
     716        result[i][j] = y;
     717        found_theta = 1;
     718        break;
    722719      }//the jth entry is theta and can be written as x*y
    723720      if(result[i][j] == theta +1)
    724721      {
    725         thetapos = j;
    726         result[i] = insert(result[i],y,j-1);
    727         j++;
    728         result[i][j] = x;
    729         found_theta = 1;
    730         break;
     722        thetapos = j;
     723        result[i] = insert(result[i],y,j-1);
     724        j++;
     725        result[i][j] = x;
     726        found_theta = 1;
     727        break;
    731728      }
    732729    }
    … …  
    742739      if (leftpart[thetapos] == x)
    743740      {
    744         shift_sign = 1;
    745         shiftvar = x;
     741        shift_sign = 1;
     742        shiftvar = x;
    746743      }
    747744      else
    748745      {
    749         shift_sign = -1;
    750         shiftvar = y;
     746        shift_sign = -1;
     747        shiftvar = y;
    751748      }
    752749      for (j = size(leftpart); j>1;j--)
    753750      {//drip x resp. y
    754         if (leftpart[j-1]==shiftvar)
    755         {//commutative
    756           j--;
    757           continue;
    758         }//commutative
    759         if (deg(leftpart[j-1],intvec(-1,1,0))!=0)
    760         {//stop here
    761           break;
    762         }//stop here
    763         //Here, we can only have a a0- part
    764         leftpart[j] = subst(leftpart[j-1],theta, theta + shift_sign);
    765         leftpart[j-1] = shiftvar;
    766         lparts = lparts + list(leftpart);
     751        if (leftpart[j-1]==shiftvar)
     752        {//commutative
     753          j--;
     754          continue;
     755        }//commutative
     756        if (deg(leftpart[j-1],intvec(-1,1,0))!=0)
     757        {//stop here
     758          break;
     759        }//stop here
     760        //Here, we can only have a a0- part
     761        leftpart[j] = subst(leftpart[j-1],theta, theta + shift_sign);
     762        leftpart[j-1] = shiftvar;
     763        lparts = lparts + list(leftpart);
    767764      }//drip x resp. y
    768765      //and now deal with the right part
    769766      if (rightpart[1] == x)
    770767      {
    771         shift_sign = 1;
    772         shiftvar = x;
     768        shift_sign = 1;
     769        shiftvar = x;
    773770      }
    774771      else
    775772      {
    776         shift_sign = -1;
    777         shiftvar = y;
     773        shift_sign = -1;
     774        shiftvar = y;
    778775      }
    779776      for (j = 1 ; j < size(rightpart); j++)
    780777      {
    781         if (rightpart[j+1] == shiftvar)
    782         {
    783           j++;
    784           continue;
    785         }
    786         if (deg(rightpart[j+1],intvec(-1,1,0))!=0)
    787         {
    788           break;
    789         }
    790         rightpart[j] = subst(rightpart[j+1], theta, theta - shift_sign);
    791         rightpart[j+1] = shiftvar;
    792         rparts = rparts + list(rightpart);
     778        if (rightpart[j+1] == shiftvar)
     779        {
     780          j++;
     781          continue;
     782        }
     783        if (deg(rightpart[j+1],intvec(-1,1,0))!=0)
     784        {
     785          break;
     786        }
     787        rightpart[j] = subst(rightpart[j+1], theta, theta - shift_sign);
     788        rightpart[j+1] = shiftvar;
     789        rparts = rparts + list(rightpart);
    793790      }
    794791      //And now, we put all possibilities together
    … …  
    796793      for (j = 1; j<=size(lparts); j++)
    797794      {
    798         for (k = 1; k<=size(rparts);k++)
    799         {
    800           tempadd = tempadd + list(lparts[j]+rparts[k]);
    801         }
     795        for (k = 1; k<=size(rparts);k++)
     796        {
     797          tempadd = tempadd + list(lparts[j]+rparts[k]);
     798        }
    802799      }
    803800      tempadd = delete(tempadd,1); // The first entry is already in the list
    … …  
    880877      if (l_without_double[j] == l[i])
    881878      {
    882         double_entry = 1;
    883         break;
     879        double_entry = 1;
     880        break;
    884881      }
    885882    }
    … …  
    934931  {
    935932    def r = basering;
    936     ring tempRing = ringlist(r)[1][1],(x,y),Ws(-1,1); // very strange: 
     933    ring tempRing = ringlist(r)[1][1],(x,y),Ws(-1,1); // very strange:
    937934    // setting Wp(-1,1) leads to SegFault; to clarify why!!!
    938935    def NTR = nc_algebra(1,1);
    … …  
    952949      for (j=2;j<=size(result[i]);j++)
    953950      {//Factorize every factor
    954         recursivetemp = facFirstWeyl(result[i][j]);
    955         if(size(recursivetemp)>1)
    956         {//we have a nontrivial factorization
    957           for(k=1; k<=size(recursivetemp);k++)
    958           {//insert factorized factors
    959             if(size(recursivetemp[k])>2)
    960             {//nontrivial
    961               result = insert(result,result[i],i);
    962               for(l = size(recursivetemp[k]);l>=2;l--)
    963               {
    964                 result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
    965               }
    966               result[i+1] = delete(result[i+1],j);
    967             }//nontrivial
    968           }//insert factorized factors
    969         }//we have a nontrivial factorization
     951        recursivetemp = facFirstWeyl(result[i][j]);
     952        if(size(recursivetemp)>1)
     953        {//we have a nontrivial factorization
     954          for(k=1; k<=size(recursivetemp);k++)
     955          {//insert factorized factors
     956            if(size(recursivetemp[k])>2)
     957            {//nontrivial
     958              result = insert(result,result[i],i);
     959              for(l = size(recursivetemp[k]);l>=2;l--)
     960              {
     961                result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
     962              }
     963              result[i+1] = delete(result[i+1],j);
     964            }//nontrivial
     965          }//insert factorized factors
     966        }//we have a nontrivial factorization
    970967      }//Factorize every factor
    971968    }//Nontrivial factorization
    … …  
    10391036      if (deg(h,intvec(-1,1))<=deg(h-product(M[i]),intvec(-1,1)))
    10401037      {
    1041         M = delete(M,i);
    1042         continue;
     1038        M = delete(M,i);
     1039        continue;
    10431040      }
    10441041      if (deg(h,intvec(1,-1))<=deg(h-product(M[i]),intvec(1,-1)))
    10451042      {
    1046         M = delete(M,i);
    1047         continue;
     1043        M = delete(M,i);
     1044        continue;
    10481045      }
    10491046    }
    … …  
    10601057      if (involution(NF(involution(hath,invo), std(involution(ideal(M[i][1]),invo))),invo)==0)
    10611058      {//hath and h have a common factor on the left
    1062         j = 1;
    1063         f1 = M[i];
    1064         if (j+1<=size(f1))
    1065         {//Checking for more than one common factor
    1066           while(involution(NF(involution(hath,invo),std(involution(ideal(product(f1[1..(j+1)])),invo))),invo)==0)
    1067           {
    1068             if (j+1<size(f1))
    1069             {
    1070               j++;
    1071             }
    1072             else
    1073             {
    1074               break;
    1075             }
    1076           }
    1077         }//Checking for more than one common factor
    1078         f2 = list(f1[1..j])+list(involution(lift(involution(product(f1[1..j]),invo),involution(hath,invo))[1,1],invo));
    1079         temp = temp + merge_cf(f2,f1,limits);
     1059        j = 1;
     1060        f1 = M[i];
     1061        if (j+1<=size(f1))
     1062        {//Checking for more than one common factor
     1063          while(involution(NF(involution(hath,invo),std(involution(ideal(product(f1[1..(j+1)])),invo))),invo)==0)
     1064          {
     1065            if (j+1<size(f1))
     1066            {
     1067              j++;
     1068            }
     1069            else
     1070            {
     1071              break;
     1072            }
     1073          }
     1074        }//Checking for more than one common factor
     1075        f2 = list(f1[1..j])+list(involution(lift(involution(product(f1[1..j]),invo),involution(hath,invo))[1,1],invo));
     1076        temp = temp + merge_cf(f2,f1,limits);
    10801077      }//hath and h have a common factor on the left
    10811078      if (reduce(hath, std(ideal(M[i][size(M[i])])))==0)
    10821079      {//hath and h have a common factor on the right
    1083         j = size(M[i]);
    1084         f1 = M[i];
    1085         if (j-1>0)
    1086         {//Checking for more than one factor
    1087           while(reduce(hath,std(ideal(product(f1[(j-1)..size(f1)]))))==0)
    1088           {
    1089             if (j-1>1)
    1090             {
    1091               j--;
    1092             }
    1093             else
    1094             {
    1095               break;
    1096             }
    1097           }
    1098         }//Checking for more than one factor
    1099         f2 = list(lift(product(f1[j..size(f1)]),hath)[1,1])+list(f1[j..size(f1)]);
    1100         temp = temp + merge_cf(f2,M[i],limits);
     1080        j = size(M[i]);
     1081        f1 = M[i];
     1082        if (j-1>0)
     1083        {//Checking for more than one factor
     1084          while(reduce(hath,std(ideal(product(f1[(j-1)..size(f1)]))))==0)
     1085          {
     1086            if (j-1>1)
     1087            {
     1088              j--;
     1089            }
     1090            else
     1091            {
     1092              break;
     1093            }
     1094          }
     1095        }//Checking for more than one factor
     1096        f2 = list(lift(product(f1[j..size(f1)]),hath)[1,1])+list(f1[j..size(f1)]);
     1097        temp = temp + merge_cf(f2,M[i],limits);
    11011098      }//hath and h have a common factor on the right
    11021099      //and now the homogeneous
    … …  
    11071104      for (j = 1; j<=size(f1);j++)
    11081105      {
    1109         for (k=1; k<=size(f2);k++)
    1110         {
    1111           homogtemp = mergence(f1[j],f2[k],limits);
    1112         }
     1106        for (k=1; k<=size(f2);k++)
     1107        {
     1108          homogtemp = mergence(f1[j],f2[k],limits);
     1109        }
    11131110      }
    11141111      for (j = 1; j<= size(homogtemp); j++)
    11151112      {
    1116         temp = temp + mergence(homogtemp[j],M[i],limits);
     1113        temp = temp + mergence(homogtemp[j],M[i],limits);
    11171114      }
    11181115      for (j = 1; j<=size(temp); j++)
    11191116      {//filtering invalid entries in temp
    1120         if(product(temp[j])==h)
    1121         {//This is already a result
    1122           result = result + list(temp[j]);
    1123           temp = delete(temp,j);
    1124           continue;
    1125         }//This is already a result
    1126         if (deg(hath,intvec(-1,1))<=deg(hath-product(temp[j]),intvec(-1,1)))
    1127         {
    1128           temp = delete(temp,j);
    1129           continue;
    1130         }
     1117        if(product(temp[j])==h)
     1118        {//This is already a result
     1119          result = result + list(temp[j]);
     1120          temp = delete(temp,j);
     1121          continue;
     1122        }//This is already a result
     1123        if (deg(hath,intvec(-1,1))<=deg(hath-product(temp[j]),intvec(-1,1)))
     1124        {
     1125          temp = delete(temp,j);
     1126          continue;
     1127        }
    11311128      }//filtering invalid entries in temp
    11321129      hatM = hatM + temp;
    … …  
    11371134      if (h == product(M[i]))
    11381135      {
    1139         result = result + list(M[i]);
    1140         M = delete(M,i);
    1141         continue;
     1136        result = result + list(M[i]);
     1137        M = delete(M,i);
     1138        continue;
    11421139      }
    11431140    }//checking for complete factorizations
    … …  
    12291226      if (size(result)>0)
    12301227      {
    1231         if (product(l[i])!=result[size(l)-i])
    1232         {
    1233           valid = 0;
    1234           break;
    1235         }
     1228        if (product(l[i])!=result[size(l)-i])
     1229        {
     1230          valid = 0;
     1231          break;
     1232        }
    12361233      }
    12371234      result = insert(result, product(l[i]));
    … …  
    12501247      if (product(l[i])!=#[1])
    12511248      {
    1252         valid = 0;
     1249        valid = 0;
    12531250      }
    12541251      result = insert(result, product(l[i]));
    … …  
    12931290"USAGE:  facSubWeyl(h,x,y); h, X, D polynomials
    12941291RETURN: list
    1295 ASSUME: X and D are variables of a basering, which satisfy DX = XD +1. 
     1292ASSUME: X and D are variables of a basering, which satisfy DX = XD +1.
    12961293@* That is,  they generate the copy of the first Weyl algebra in a basering.
    12971294@* Moreover, h is a polynomial in X and D only.
    … …  
    13131310  poly w = D*X-X*D-1; // [D,X]=1
    13141311  poly u = D*X-X*D+1; // [X,D]=1
    1315   if (u*w!=0) 
     1312  if (u*w!=0)
    13161313  {
    13171314    // that is no combination gives Weyl
    … …  
    13241321    // hence w != 0, swap X<->D later
    13251322    isReverted = 1;
    1326     //    w = D; D=X; X=w; 
     1323    //    w = D; D=X; X=w;
    13271324  }
    13281325  // else: do nothing
    1329   // DONE with assumptions       
     1326  // DONE with assumptions
    13301327  //Input successfuy checked
    13311328  intvec lexpofX = leadexp(X);
    … …  
    13541351  {
    13551352    ring firstweyl = 0,(var(varnumD),var(varnumX)),dp;
    1356     def Firstweyl = nc_algebra(1,1); 
     1353    def Firstweyl = nc_algebra(1,1);
    13571354    setring Firstweyl;
    13581355    ideal M = 0:nvars(@r);
    … …  
    13711368  list result = facFirstWeyl(h);
    13721369  setring @r;
    1373   list result; 
     1370  list result;
    13741371  if (isReverted)
    13751372  {
    … …  
    13941391  setring R;
    13951392  poly h = (x^2*z^2+x)*x;
    1396   list fact1 = facSubWeyl(h,x,z); 
     1393  list fact1 = facSubWeyl(h,x,z);
    13971394  // compare with facFirstWeyl:
    13981395  ring s = 0,(z,x),dp;
    … …  
    14081405//==================================================
    14091406//************From here: Shift-Algebra**************
    1410                         //==================================================
    1411 
    1412                         //==================================================*
    1413                         //one factorization of a homogeneous polynomial
    1414                         //in the first Shift Algebra
     1407                        //==================================================
     1408
     1409                        //==================================================*
     1410                        //one factorization of a homogeneous polynomial
     1411                        //in the first Shift Algebra
    14151412static proc homogfacFirstShift(poly h)
    14161413{//proc homogfacFirstShift
    … …  
    14871484      if (result[i][j]==var(2))
    14881485      {
    1489         shiftcounter++;
     1486        shiftcounter++;
    14901487      }
    14911488      else
    14921489      {
    1493         result[i][j] = subst(result[i][j], var(1), var(1)-shiftcounter);
     1490        result[i][j] = subst(result[i][j], var(1), var(1)-shiftcounter);
    14941491      }
    14951492    }
    … …  
    15441541    //    result = transfback(resulttemp);
    15451542  }
    1546   else 
     1543  else
    15471544  {
    15481545    if ( @p == var(2)) // usual shift algebra
    1549     { 
     1546    {
    15501547      setring(tempRingnc);
    15511548      map transf = r, var(1), var(2);
    … …  
    15731570      for (j=2;j<=size(result[i]);j++)
    15741571      {//Factorize every factor
    1575         recursivetemp = facFirstShift(result[i][j]);
    1576         if(size(recursivetemp)>1)
    1577         {//we have a nontrivial factorization
    1578           for(k=1; k<=size(recursivetemp);k++)
    1579           {//insert factorized factors
    1580             if(size(recursivetemp[k])>2)
    1581             {//nontrivial
    1582               result = insert(result,result[i],i);
    1583               for(l = size(recursivetemp[k]);l>=2;l--)
    1584               {
    1585                 result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
    1586               }
    1587               result[i+1] = delete(result[i+1],j);
    1588             }//nontrivial
    1589           }//insert factorized factors
    1590         }//we have a nontrivial factorization
     1572        recursivetemp = facFirstShift(result[i][j]);
     1573        if(size(recursivetemp)>1)
     1574        {//we have a nontrivial factorization
     1575          for(k=1; k<=size(recursivetemp);k++)
     1576          {//insert factorized factors
     1577            if(size(recursivetemp[k])>2)
     1578            {//nontrivial
     1579              result = insert(result,result[i],i);
     1580              for(l = size(recursivetemp[k]);l>=2;l--)
     1581              {
     1582                result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
     1583              }
     1584              result[i+1] = delete(result[i+1],j);
     1585            }//nontrivial
     1586          }//insert factorized factors
     1587        }//we have a nontrivial factorization
    15911588      }//Factorize every factor
    15921589    }//Nontrivial factorization
    … …  
    16551652      if (deg(h,intvec(0,1))<=deg(h-product(M[i]),intvec(0,1)))
    16561653      {
    1657         M = delete(M,i);
    1658         continue;
     1654        M = delete(M,i);
     1655        continue;
    16591656      }
    16601657      if (deg(h,intvec(0,-1))<=deg(h-product(M[i]),intvec(0,-1)))
    16611658      {
    1662         M = delete(M,i);
    1663         continue;
     1659        M = delete(M,i);
     1660        continue;
    16641661      }
    16651662    }
    … …  
    16761673      if (involution(NF(involution(hath,invo), std(involution(ideal(M[i][1]),invo))),invo)==0)
    16771674      {//hath and h have a common factor on the left
    1678         j = 1;
    1679         f1 = M[i];
    1680         if (j+1<=size(f1))
    1681         {//Checking for more than one common factor
    1682           while(involution(NF(involution(hath,invo),std(involution(ideal(product(f1[1..(j+1)])),invo))),invo)==0)
    1683           {
    1684             if (j+1<size(f1))
    1685             {
    1686               j++;
    1687             }
    1688             else
    1689             {
    1690               break;
    1691             }
    1692           }
    1693         }//Checking for more than one common factor
    1694         if (deg(product(f1[1..j]),intvec(1,1))!=0)
    1695         {
    1696           f2 = list(f1[1..j])+list(involution(lift(involution(product(f1[1..j]),invo),involution(hath,invo))[1,1],invo));
    1697         }
    1698         else
    1699         {
    1700           f2 = list(f1[1..j])+list(involution(lift(product(f1[1..j]),involution(hath,invo))[1,1],invo));
    1701         }
    1702         temp = temp + merge_cf(f2,f1,limits);
     1675        j = 1;
     1676        f1 = M[i];
     1677        if (j+1<=size(f1))
     1678        {//Checking for more than one common factor
     1679          while(involution(NF(involution(hath,invo),std(involution(ideal(product(f1[1..(j+1)])),invo))),invo)==0)
     1680          {
     1681            if (j+1<size(f1))
     1682            {
     1683              j++;
     1684            }
     1685            else
     1686            {
     1687              break;
     1688            }
     1689          }
     1690        }//Checking for more than one common factor
     1691        if (deg(product(f1[1..j]),intvec(1,1))!=0)
     1692        {
     1693          f2 = list(f1[1..j])+list(involution(lift(involution(product(f1[1..j]),invo),involution(hath,invo))[1,1],invo));
     1694        }
     1695        else
     1696        {
     1697          f2 = list(f1[1..j])+list(involution(lift(product(f1[1..j]),involution(hath,invo))[1,1],invo));
     1698        }
     1699        temp = temp + merge_cf(f2,f1,limits);
    17031700      }//hath and h have a common factor on the left
    17041701      if (reduce(hath, std(ideal(M[i][size(M[i])])))==0)
    17051702      {//hath and h have a common factor on the right
    1706         j = size(M[i]);
    1707         f1 = M[i];
    1708         if (j-1>0)
    1709         {//Checking for more than one factor
    1710           while(reduce(hath,std(ideal(product(f1[(j-1)..size(f1)]))))==0)
    1711           {
    1712             if (j-1>1)
    1713             {
    1714               j--;
    1715             }
    1716             else
    1717             {
    1718               break;
    1719             }
    1720           }
    1721         }//Checking for more than one factor
    1722         f2 = list(lift(product(f1[j..size(f1)]),hath)[1,1])+list(f1[j..size(f1)]);
    1723         temp = temp + merge_cf(f2,M[i],limits);
     1703        j = size(M[i]);
     1704        f1 = M[i];
     1705        if (j-1>0)
     1706        {//Checking for more than one factor
     1707          while(reduce(hath,std(ideal(product(f1[(j-1)..size(f1)]))))==0)
     1708          {
     1709            if (j-1>1)
     1710            {
     1711              j--;
     1712            }
     1713            else
     1714            {
     1715              break;
     1716            }
     1717          }
     1718        }//Checking for more than one factor
     1719        f2 = list(lift(product(f1[j..size(f1)]),hath)[1,1])+list(f1[j..size(f1)]);
     1720        temp = temp + merge_cf(f2,M[i],limits);
    17241721      }//hath and h have a common factor on the right
    17251722      //and now the homogeneous
    … …  
    17301727      for (j = 1; j<=size(f1);j++)
    17311728      {
    1732         for (k=1; k<=size(f2);k++)
    1733         {
    1734           homogtemp = mergence(f1[j],f2[k],limits);
    1735         }
     1729        for (k=1; k<=size(f2);k++)
     1730        {
     1731          homogtemp = mergence(f1[j],f2[k],limits);
     1732        }
    17361733      }
    17371734      for (j = 1; j<= size(homogtemp); j++)
    17381735      {
    1739         temp = temp + mergence(homogtemp[j],M[i],limits);
     1736        temp = temp + mergence(homogtemp[j],M[i],limits);
    17401737      }
    17411738      for (j = 1; j<=size(temp); j++)
    17421739      {//filtering invalid entries in temp
    1743         if(product(temp[j])==h)
    1744         {//This is already a result
    1745           result = result + list(temp[j]);
    1746           temp = delete(temp,j);
    1747           continue;
    1748         }//This is already a result
    1749         if (deg(hath,intvec(0,1))<=deg(hath-product(temp[j]),intvec(0,1)))
    1750         {
    1751           temp = delete(temp,j);
    1752           continue;
    1753         }
     1740        if(product(temp[j])==h)
     1741        {//This is already a result
     1742          result = result + list(temp[j]);
     1743          temp = delete(temp,j);
     1744          continue;
     1745        }//This is already a result
     1746        if (deg(hath,intvec(0,1))<=deg(hath-product(temp[j]),intvec(0,1)))
     1747        {
     1748          temp = delete(temp,j);
     1749          continue;
     1750        }
    17541751      }//filtering invalid entries in temp
    17551752      hatM = hatM + temp;
    … …  
    17601757      if (h == product(M[i]))
    17611758      {
    1762         result = result + list(M[i]);
    1763         M = delete(M,i);
    1764         continue;
     1759        result = result + list(M[i]);
     1760        M = delete(M,i);
     1761        continue;
    17651762      }
    17661763    }//checking for complete factorizations
    … …  
    18031800}
    18041801
    1805 /* very hard things from Martin Lee: 
     1802/* very hard things from Martin Lee:
    18061803// ex1, ex2
    18071804ring s = 0,(z,x),Ws(-1,1);
    … …  
    18171814ring r = 0,(x,y,z),dp;
    18181815matrix D[3][3]; D[1,3]=-1;
    1819 def R = nc_algebra(1,D); 
     1816def R = nc_algebra(1,D);
    18201817setring R;
    18211818poly g= 7*z4*x+62*z3+26*z;
Note: See TracChangeset for help on using the changeset viewer.