Changeset d91c9d in git


Ignore:
Timestamp:
Jun 3, 2013, 6:32:51 PM (10 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
ee03c0b1a4536e17f4cf930bc9639e5a8f233eaf
Parents:
7588173ab3d1c57ed767ae98790e173380156ba4
git-author:
Hans Schoenemann <hannes@mathematik.uni-kl.de>2013-06-03 18:32:51+02:00
git-committer:
Martin Lee <martinlee84@web.de>2013-09-06 11:27:47+02:00
Message:
update by albert.heinle@rwth-aachen.de

Conflicts:

	Singular/LIB/ncfactor.lib
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/ncfactor.lib

    r758817 rd91c9d  
    44info="
    55LIBRARY: ncfactor.lib  Tools for factorization in some noncommutative algebras
    6 AUTHORS: Albert Heinle,     albert.heinle@rwth-aachen.de
     6AUTHORS: Albert Heinle,     aheinle@uwaterloo.ca
    77@*       Viktor Levandovskyy,     levandov@math.rwth-aachen.de
    88
    99OVERVIEW: In this library, new methods for factorization on polynomials
    10 @*  are implemented for two algebras, both generated by two generators (Weyl and
    11 @*  shift algebras) over a field K. Recall, that   the first Weyl algebra over K
    12 @*  is generated by x,d obeying the relation d*x=x*d+1.
     10  are implemented for two algebras, both generated by two generators (Weyl and
     11  shift algebras) over a field K. Recall, that   the first Weyl algebra over K
     12  is generated by x,d obeying the relation d*x=x*d+1.
    1313@* The first shift algebra over K is generated by x,s obeying the relation s*x=x*s+s.
    1414@* More detailled description of the algorithms can be found at
    … …  
    3535LIB "crypto.lib"; //for introot
    3636LIB "matrix.lib"; //for submatrix
     37LIB "solve.lib"; //right now not needed
    3738LIB "poly.lib"; //for content
    3839
    … …  
    11631164    dbprint(p,dbprintWhitespace +" Done");
    11641165  }
     1166  if (homogwithorder(h,intvec(-1,1)))
     1167  {
     1168    dbprint(p, dbprintWhitespace + " Polynomial was homogeneous, therefore we have
     1169already a complete factorization and do not have to go through the factors recursively.");
     1170    return(result);
     1171  }
    11651172  dbprint(p,dbprintWhitespace +" recursively check factors for irreducibility");
    11661173  list recursivetemp;
    … …  
    12021209    result = list(list(1,h));
    12031210  }//only the trivial factorization could be found
     1211  list resultWithInterchanges;
     1212  dbprint(p,dbprintWhitespace+ "And the result without interchanges with homogeneous factors is:");
     1213  dbprint(p,result);
     1214  for (i = 1; i <= size(result) ; i++)
     1215  {//applying the interchanges to result
     1216    resultWithInterchanges = resultWithInterchanges +
     1217                             checkForHomogInhomogInterchangability(result[i],2,size(result[i]));
     1218  }//applying the interchanges to result
    12041219  //now, refine the possible redundant list
    1205   return( delete_dublicates_noteval(result) );
     1220  return( delete_dublicates_noteval(resultWithInterchanges) );
    12061221}//proc facFirstWeyl
    12071222example
    … …  
    12181233/////BRANDNEW!!!!////////////////////
    12191234//////////////////////////////////////////////////
     1235
     1236static proc checkForHomogInhomogInterchangability(list factors, posLeft, posRight)
     1237"
     1238INPUT:  A list consisting of factors of a certain polynomial in the first Weyl
     1239        algebra, factors, and a position from the left and the right, where the last swap was done.
     1240OUTPUT: A list containing lists consisting of factors of a certain polynomial in the first Weyl
     1241        algebra.
     1242The purpose of this function is to check whether we can interchange certain inhomogeneous factors
     1243with homogeneous ones. If it is possible, this function returns a list of lists
     1244of possible interchanges.
     1245
     1246The idea came because of an example, where we need an extra swap in the end, otherwise we would
     1247not capture all factorizations. The example was
     1248h = x4d7+11x3d6+x2d7+x2d6+x3d4+29x2d5+xd6+8xd5+d6+5x2d3+14xd4+13d4+5xd2+d3+d;
     1249
     1250ASSUMPTIONS:
     1251
     1252- All factors are irreducible
     1253"
     1254{//checkForHomogInhomogInterchangability
     1255  int p = printlevel-voice+2;
     1256  string dbprintWhitespace = "";
     1257  int i; int j;
     1258  for (i = 1; i<=voice;i++)
     1259  {dbprintWhitespace = dbprintWhitespace + " ";}
     1260  if (size(factors) <= 2 || posLeft == posRight - 1)
     1261  {//easiest case: There is nothing to swap
     1262    return (list(factors));
     1263  }//easiest case: There is nothing to swap
     1264  list result = list(factors);
     1265  list tempResultEntries;
     1266  list tempSwaps;
     1267  list tempSwapsTempEntry;
     1268  list attemptToSwap;
     1269  intvec ivm11 = intvec(-1,1);
     1270  dbprint(p, dbprintWhitespace+"We try to swap elements in the following list:");
     1271  dbprint(p, factors);
     1272  for (i = posLeft; i < posRight; i++)
     1273  {//checking within the window posLeft <--> posRight, if there are interchanges possible
     1274    if (homogwithorder(factors[i],ivm11) && !homogwithorder(factors[i+1],ivm11))
     1275    {//position i is homogeneous, position i+1 is not ==> trying to swap
     1276      attemptToSwap = extractHomogeneousDivisorsRight(factors[i]*factors[i+1]);
     1277      if (size(attemptToSwap[1])>1)
     1278      {//Bingo, we were able to swap this one element
     1279        dbprint(p,dbprintWhitespace+"We can swap entry "+string(i)+" and "+ string(i+1));
     1280        dbprint(p,dbprintWhitespace+"The elements look like the following after the swap:");
     1281        dbprint(p,attemptToSwap);
     1282        tempSwapsTempEntry = list();
     1283        for (j = size(factors); j >=1; j--)
     1284        {//creating a new entry for the resulting list, replacing the swap in factors
     1285          if (j==i+1)
     1286          {tempSwapsTempEntry = insert(tempSwapsTempEntry, attemptToSwap[1][2]);}
     1287          else
     1288          {
     1289            if (j == i)
     1290            {tempSwapsTempEntry = insert(tempSwapsTempEntry, attemptToSwap[1][1]);}
     1291            else
     1292            {tempSwapsTempEntry = insert(tempSwapsTempEntry,factors[j]);}
     1293          }
     1294        }//creating a new entry for the resulting list, replacing the swap in factors
     1295        tempSwaps = insert(tempSwaps,list(list(i+1,posRight),tempSwapsTempEntry));
     1296      }//Bingo, we were able to swap this one element
     1297    }//position i is homogeneous, position i+1 is not ==> trying to swap
     1298    else
     1299    {
     1300      if(!homogwithorder(factors[i],ivm11) && homogwithorder(factors[i+1],ivm11))
     1301      {//position i+1 is homogeneous, position i is not ==> trying to swap
     1302        attemptToSwap = extractHomogeneousDivisorsLeft(factors[i]*factors[i+1]);
     1303        if (size(attemptToSwap[1])>1)
     1304        {//Bingo, we were able to swap this one element
     1305          dbprint(p,dbprintWhitespace+"We can swap entry "+string(i)+" and "+ string(i+1));
     1306          dbprint(p,dbprintWhitespace+"The elements look like the following after the swap:");
     1307          dbprint(p,attemptToSwap);
     1308          tempSwapsTempEntry = list();
     1309          for (j = size(factors); j >=1; j--)
     1310          {//creating a new entry for the resulting list, replacing the swap in factors
     1311            if (j==i+1)
     1312            {tempSwapsTempEntry = insert(tempSwapsTempEntry, attemptToSwap[1][2]);}
     1313            else
     1314            {
     1315              if (j == i)
     1316              {tempSwapsTempEntry = insert(tempSwapsTempEntry, attemptToSwap[1][1]);}
     1317              else
     1318              {tempSwapsTempEntry = insert(tempSwapsTempEntry,factors[j]);}
     1319            }
     1320          }//creating a new entry for the resulting list, replacing the swap in factors
     1321          tempSwaps = insert(tempSwaps,list(list(posLeft,i),tempSwapsTempEntry));
     1322        }//Bingo, we were able to swap this one element
     1323      }//position i+1 is homogeneous, position i is not ==> trying to swap
     1324    }
     1325  }//checking within the window posLeft <--> posRight, if there are interchanges possible
     1326
     1327  //Now we will recursively call the function for all swapped entries.
     1328  dbprint(p,dbprintWhitespace+ "Our list of different factorizations is now:");
     1329  dbprint(p,tempSwaps);
     1330  for (i = 1; i<=size(tempSwaps);i++)
     1331  {//recursive call to all formerly attempted swaps.
     1332    tempResultEntries=checkForHomogInhomogInterchangability(tempSwaps[i][2],
     1333                                                            tempSwaps[i][1][1],tempSwaps[i][1][2]);
     1334    result = result + tempResultEntries;
     1335  }//recursive call to all formerly attempted swaps.
     1336  result = delete_dublicates_noteval(result);
     1337  return(result);
     1338}//checkForHomogInhomogInterchangability
    12201339
    12211340static proc sfacwa(poly h)
    … …  
    12691388  }//Going through all different kinds of factorizations where we extracted homogeneous factors
    12701389  dbprint(p,dbprintWhitespace +" Done");
     1390  dbprint(p,dbprintWhitespace + "The set is:");
     1391  dbprint(p,inhomogeneousFactorsToFactorize);
    12711392  dbprint(p,dbprintWhitespace+ "Factorizing the different occuring inhomogeneous factors");
    12721393  for (i = 1; i<= size(inhomogeneousFactorsToFactorize); i++)
    … …  
    16391760  option(redSB);
    16401761  dbprint(p,dbprintWhitespace+" Calculating reduced Groebner Basis of that system.");
    1641   solutionSystemforqs = std(solutionSystemforqs);
     1762  solutionSystemforqs = slimgb(solutionSystemforqs);
    16421763  dbprint(p,dbprintWhitespace+" Done!, the solution for the system is:");
    16431764  dbprint(p,dbprintWhitespace+string(solutionSystemforqs));
    1644   if(vdim(std(solutionSystemforqs+theta))==0)
     1765  if(vdim(slimgb(solutionSystemforqs+theta))==0)
    16451766  {//No solution in this case. Return the empty list
    16461767    dbprint(p,dbprintWhitespace+"The Groebner Basis of the solution system was <1>.");
    … …  
    16481769    return(list());
    16491770  }//No solution in this case. Return the empty list
    1650   if(vdim(std(solutionSystemforqs+theta))==-1)
     1771  if(vdim(slimgb(solutionSystemforqs+theta))==-1)
    16511772  {//My conjecture is that this would never happen
    16521773    //ERROR("This is an counterexample to your conjecture. We have infinitely many solutions");
    … …  
    16591780  else
    16601781  {//We have finitely many solutions
    1661     if(vdim(std(solutionSystemforqs+theta))==1)
     1782    if(vdim(slimgb(solutionSystemforqs+theta))==1)
    16621783    {//exactly one solution
    16631784      for (i = 2; i<= size(qs)-1;i++)
    … …  
    17641885  string dbprintWhitespace = "";
    17651886  int i; int j; int k; int l;
     1887  list result;
    17661888  for (i = 1; i<=voice;i++)
    17671889  {dbprintWhitespace = dbprintWhitespace + " ";}
    … …  
    17691891  {//given polynomial was homogeneous already
    17701892    dbprint(p,dbprintWhitespace+"Polynomial was homogeneous. Just returning all factorizations.");
    1771     return(homogfacFirstWeyl_all(h));
     1893    result = homogfacFirstWeyl_all(h);
     1894    for (i = 1; i<=size(result);i++)
     1895    {//removing the first entry (coefficient) from the list result
     1896      result[i] = delete(result[i],1);
     1897    }//removing the first entry (coefficient) from the list result
     1898    return(result);
    17721899  }//given polynomial was homogeneous already
    1773   list result;
    17741900  dbprint(p,dbprintWhitespace+"Calculating list with all homogeneous left divisors extracted");
    17751901  list leftDivisionPossibilities = extractHomogeneousDivisorsLeft(h);
    … …  
    18952021  {//given polynomial was homogeneous already
    18962022    dbprint(p,dbprintWhitespace+"Polynomial was homogeneous. Just returning all factorizations.");
    1897     return(homogfacFirstWeyl_all(h));
     2023    result = homogfacFirstWeyl_all(h);
     2024    for (i = 1; i<=size(result);i++)
     2025    {//removing the first entry (coefficient) from the list result
     2026      result[i] = delete(result[i],1);
     2027    }//removing the first entry (coefficient) from the list result
     2028    return(result);
    18982029  }//given polynomial was homogeneous already
    18992030  list hlist = homogDistribution(h);
    … …  
    19992130  {//given polynomial was homogeneous already
    20002131    dbprint(p,dbprintWhitespace+"Polynomial was homogeneous. Just returning all factorizations.");
    2001     return(homogfacFirstWeyl_all(h));
     2132    result = homogfacFirstWeyl_all(h);
     2133    for (i = 1; i<=size(result);i++)
     2134    {//removing the first entry (coefficient) from the list result
     2135      result[i] = delete(result[i],1);
     2136    }//removing the first entry (coefficient) from the list result
     2137    return(result);
    20022138  }//given polynomial was homogeneous already
    20032139  list hlist = homogDistribution(h);
    … …  
    20792215  }
    20802216  return(result);
    2081 }//extractHomogeneousDivisorsLeft
     2217}//extractHomogeneousDivisorsRight
    20822218
    20832219static proc fromZeroHomogToThetaPoly(poly h)
    … …  
    22352371  //First, we are going to deal with our most hated guys: The Coefficients.
    22362372  //
    2237   list coeffTuplesMax = getAllCoeffTuplesComb(factorizeInt(int(f1[1][1])));
     2373  list coeffTuplesMax = getAllCoeffTuplesComb(factorizeInt(number(f1[1][1])));
    22382374  //We can assume without loss of generality, that p_max has a
    22392375  //nonnegative leading coefficient
    … …  
    22462382    }
    22472383  }//Deleting all tuples with negative entries for p_max
    2248   list coeffTuplesMin = getAllCoeffTuplesComb(factorizeInt(int(f2[1][1])));
     2384  list coeffTuplesMin = getAllCoeffTuplesComb(factorizeInt(number(f2[1][1])));
    22492385
    22502386  //Now, we will be actally dealing with the Combinations.
    … …  
    38093945  if (size(list_not_azero)!=0)
    38103946  {//Compute all possibilities to permute the x's resp. the y's in the list
    3811     if (list_not_azero[1] == x)
     3947    if (list_not_azero[1] == var(1))
    38123948    {//h had a negative weighted degree
    38133949      shift_sign = 1;
    3814       shiftvar = x;
     3950      shiftvar = var(1);
    38153951    }//h had a negative weighted degree
    38163952    else
    38173953    {//h had a positive weighted degree
    38183954      shift_sign = -1;
    3819       shiftvar = y;
     3955      shiftvar = var(2);
    38203956    }//h had a positive weighted degree
    38213957    result = permpp(list_azero + list_not_azero);
    … …  
    38904026      {//the jth entry is theta and can be written as x*y
    38914027        thetapos = j;
    3892         result[i]= insert(result[i],x,j-1);
     4028        result[i]= insert(result[i],var(1),j-1);
    38934029        j++;
    3894         result[i][j] = y;
     4030        result[i][j] = var(2);
    38954031        found_theta = 1;
    38964032        break;
    … …  
    38994035      {
    39004036        thetapos = j;
    3901         result[i] = insert(result[i],y,j-1);
     4037        result[i] = insert(result[i],var(2),j-1);
    39024038        j++;
    3903         result[i][j] = x;
     4039        result[i][j] = var(1);
    39044040        found_theta = 1;
    39054041        break;
    … …  
    39154051      rparts = list(rightpart);
    39164052      //first deal with the left part
    3917       if (leftpart[thetapos] == x)
     4053      if (leftpart[thetapos] == var(1))
    39184054      {
    39194055        shift_sign = 1;
    3920         shiftvar = x;
     4056        shiftvar = var(1);
    39214057      }
    39224058      else
    39234059      {
    39244060        shift_sign = -1;
    3925         shiftvar = y;
     4061        shiftvar = var(2);
    39264062      }
    39274063      for (j = size(leftpart); j>1;j--)
    … …  
    39494085      }//drip x resp. y
    39504086      //and now deal with the right part
    3951       if (rightpart[1] == x)
     4087      if (rightpart[1] == var(1))
    39524088      {
    39534089        shift_sign = 1;
    3954         shiftvar = x;
     4090        shiftvar = var(1);
    39554091      }
    39564092      else
    39574093      {
    39584094        shift_sign = -1;
    3959         shiftvar = y;
     4095        shiftvar = var(2);
    39604096      }
    39614097      for (j = 1 ; j < size(rightpart); j++)
    … …  
    43404476def R = nc_algebra(1,1);
    43414477setring R;
    4342 LIB "ncfactor.lib";
     4478LIB "/Users/albertheinle/Studium/forschung/ncfactor/versionen/ncfactor.lib";
    43434479poly t = x; poly D =d;
    43444480poly p = 2*t^2*D^8-6*t*D^8+2*t^2*D^7+8*t*D^7+12*D^7-2*t^4*D^6+6*t^3*D^6+12*t*D^6-20*D^6
Note: See TracChangeset for help on using the changeset viewer.