Changeset d91c9d in git
 Timestamp:
 Jun 3, 2013, 6:32:51 PM (10 years ago)
 Branches:
 (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
 Children:
 ee03c0b1a4536e17f4cf930bc9639e5a8f233eaf
 Parents:
 7588173ab3d1c57ed767ae98790e173380156ba4
 gitauthor:
 Hans Schoenemann <hannes@mathematik.unikl.de>20130603 18:32:51+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20130906 11:27:47+02:00
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/ncfactor.lib
r758817 rd91c9d 4 4 info=" 5 5 LIBRARY: ncfactor.lib Tools for factorization in some noncommutative algebras 6 AUTHORS: Albert Heinle, a lbert.heinle@rwthaachen.de6 AUTHORS: Albert Heinle, aheinle@uwaterloo.ca 7 7 @* Viktor Levandovskyy, levandov@math.rwthaachen.de 8 8 9 9 OVERVIEW: In this library, new methods for factorization on polynomials 10 @*are implemented for two algebras, both generated by two generators (Weyl and11 @*shift algebras) over a field K. Recall, that the first Weyl algebra over K12 @*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. 13 13 @* The first shift algebra over K is generated by x,s obeying the relation s*x=x*s+s. 14 14 @* More detailled description of the algorithms can be found at … … 35 35 LIB "crypto.lib"; //for introot 36 36 LIB "matrix.lib"; //for submatrix 37 LIB "solve.lib"; //right now not needed 37 38 LIB "poly.lib"; //for content 38 39 … … 1163 1164 dbprint(p,dbprintWhitespace +" Done"); 1164 1165 } 1166 if (homogwithorder(h,intvec(1,1))) 1167 { 1168 dbprint(p, dbprintWhitespace + " Polynomial was homogeneous, therefore we have 1169 already a complete factorization and do not have to go through the factors recursively."); 1170 return(result); 1171 } 1165 1172 dbprint(p,dbprintWhitespace +" recursively check factors for irreducibility"); 1166 1173 list recursivetemp; … … 1202 1209 result = list(list(1,h)); 1203 1210 }//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 1204 1219 //now, refine the possible redundant list 1205 return( delete_dublicates_noteval(result ) );1220 return( delete_dublicates_noteval(resultWithInterchanges) ); 1206 1221 }//proc facFirstWeyl 1207 1222 example … … 1218 1233 /////BRANDNEW!!!!//////////////////// 1219 1234 ////////////////////////////////////////////////// 1235 1236 static proc checkForHomogInhomogInterchangability(list factors, posLeft, posRight) 1237 " 1238 INPUT: 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. 1240 OUTPUT: A list containing lists consisting of factors of a certain polynomial in the first Weyl 1241 algebra. 1242 The purpose of this function is to check whether we can interchange certain inhomogeneous factors 1243 with homogeneous ones. If it is possible, this function returns a list of lists 1244 of possible interchanges. 1245 1246 The idea came because of an example, where we need an extra swap in the end, otherwise we would 1247 not capture all factorizations. The example was 1248 h = x4d7+11x3d6+x2d7+x2d6+x3d4+29x2d5+xd6+8xd5+d6+5x2d3+14xd4+13d4+5xd2+d3+d; 1249 1250 ASSUMPTIONS: 1251 1252  All factors are irreducible 1253 " 1254 {//checkForHomogInhomogInterchangability 1255 int p = printlevelvoice+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 1220 1339 1221 1340 static proc sfacwa(poly h) … … 1269 1388 }//Going through all different kinds of factorizations where we extracted homogeneous factors 1270 1389 dbprint(p,dbprintWhitespace +" Done"); 1390 dbprint(p,dbprintWhitespace + "The set is:"); 1391 dbprint(p,inhomogeneousFactorsToFactorize); 1271 1392 dbprint(p,dbprintWhitespace+ "Factorizing the different occuring inhomogeneous factors"); 1272 1393 for (i = 1; i<= size(inhomogeneousFactorsToFactorize); i++) … … 1639 1760 option(redSB); 1640 1761 dbprint(p,dbprintWhitespace+" Calculating reduced Groebner Basis of that system."); 1641 solutionSystemforqs = s td(solutionSystemforqs);1762 solutionSystemforqs = slimgb(solutionSystemforqs); 1642 1763 dbprint(p,dbprintWhitespace+" Done!, the solution for the system is:"); 1643 1764 dbprint(p,dbprintWhitespace+string(solutionSystemforqs)); 1644 if(vdim(s td(solutionSystemforqs+theta))==0)1765 if(vdim(slimgb(solutionSystemforqs+theta))==0) 1645 1766 {//No solution in this case. Return the empty list 1646 1767 dbprint(p,dbprintWhitespace+"The Groebner Basis of the solution system was <1>."); … … 1648 1769 return(list()); 1649 1770 }//No solution in this case. Return the empty list 1650 if(vdim(s td(solutionSystemforqs+theta))==1)1771 if(vdim(slimgb(solutionSystemforqs+theta))==1) 1651 1772 {//My conjecture is that this would never happen 1652 1773 //ERROR("This is an counterexample to your conjecture. We have infinitely many solutions"); … … 1659 1780 else 1660 1781 {//We have finitely many solutions 1661 if(vdim(s td(solutionSystemforqs+theta))==1)1782 if(vdim(slimgb(solutionSystemforqs+theta))==1) 1662 1783 {//exactly one solution 1663 1784 for (i = 2; i<= size(qs)1;i++) … … 1764 1885 string dbprintWhitespace = ""; 1765 1886 int i; int j; int k; int l; 1887 list result; 1766 1888 for (i = 1; i<=voice;i++) 1767 1889 {dbprintWhitespace = dbprintWhitespace + " ";} … … 1769 1891 {//given polynomial was homogeneous already 1770 1892 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); 1772 1899 }//given polynomial was homogeneous already 1773 list result;1774 1900 dbprint(p,dbprintWhitespace+"Calculating list with all homogeneous left divisors extracted"); 1775 1901 list leftDivisionPossibilities = extractHomogeneousDivisorsLeft(h); … … 1895 2021 {//given polynomial was homogeneous already 1896 2022 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); 1898 2029 }//given polynomial was homogeneous already 1899 2030 list hlist = homogDistribution(h); … … 1999 2130 {//given polynomial was homogeneous already 2000 2131 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); 2002 2138 }//given polynomial was homogeneous already 2003 2139 list hlist = homogDistribution(h); … … 2079 2215 } 2080 2216 return(result); 2081 }//extractHomogeneousDivisors Left2217 }//extractHomogeneousDivisorsRight 2082 2218 2083 2219 static proc fromZeroHomogToThetaPoly(poly h) … … 2235 2371 //First, we are going to deal with our most hated guys: The Coefficients. 2236 2372 // 2237 list coeffTuplesMax = getAllCoeffTuplesComb(factorizeInt( int(f1[1][1])));2373 list coeffTuplesMax = getAllCoeffTuplesComb(factorizeInt(number(f1[1][1]))); 2238 2374 //We can assume without loss of generality, that p_max has a 2239 2375 //nonnegative leading coefficient … … 2246 2382 } 2247 2383 }//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]))); 2249 2385 2250 2386 //Now, we will be actally dealing with the Combinations. … … 3809 3945 if (size(list_not_azero)!=0) 3810 3946 {//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)) 3812 3948 {//h had a negative weighted degree 3813 3949 shift_sign = 1; 3814 shiftvar = x;3950 shiftvar = var(1); 3815 3951 }//h had a negative weighted degree 3816 3952 else 3817 3953 {//h had a positive weighted degree 3818 3954 shift_sign = 1; 3819 shiftvar = y;3955 shiftvar = var(2); 3820 3956 }//h had a positive weighted degree 3821 3957 result = permpp(list_azero + list_not_azero); … … 3890 4026 {//the jth entry is theta and can be written as x*y 3891 4027 thetapos = j; 3892 result[i]= insert(result[i], x,j1);4028 result[i]= insert(result[i],var(1),j1); 3893 4029 j++; 3894 result[i][j] = y;4030 result[i][j] = var(2); 3895 4031 found_theta = 1; 3896 4032 break; … … 3899 4035 { 3900 4036 thetapos = j; 3901 result[i] = insert(result[i], y,j1);4037 result[i] = insert(result[i],var(2),j1); 3902 4038 j++; 3903 result[i][j] = x;4039 result[i][j] = var(1); 3904 4040 found_theta = 1; 3905 4041 break; … … 3915 4051 rparts = list(rightpart); 3916 4052 //first deal with the left part 3917 if (leftpart[thetapos] == x)4053 if (leftpart[thetapos] == var(1)) 3918 4054 { 3919 4055 shift_sign = 1; 3920 shiftvar = x;4056 shiftvar = var(1); 3921 4057 } 3922 4058 else 3923 4059 { 3924 4060 shift_sign = 1; 3925 shiftvar = y;4061 shiftvar = var(2); 3926 4062 } 3927 4063 for (j = size(leftpart); j>1;j) … … 3949 4085 }//drip x resp. y 3950 4086 //and now deal with the right part 3951 if (rightpart[1] == x)4087 if (rightpart[1] == var(1)) 3952 4088 { 3953 4089 shift_sign = 1; 3954 shiftvar = x;4090 shiftvar = var(1); 3955 4091 } 3956 4092 else 3957 4093 { 3958 4094 shift_sign = 1; 3959 shiftvar = y;4095 shiftvar = var(2); 3960 4096 } 3961 4097 for (j = 1 ; j < size(rightpart); j++) … … 4340 4476 def R = nc_algebra(1,1); 4341 4477 setring R; 4342 LIB " ncfactor.lib";4478 LIB "/Users/albertheinle/Studium/forschung/ncfactor/versionen/ncfactor.lib"; 4343 4479 poly t = x; poly D =d; 4344 4480 poly p = 2*t^2*D^86*t*D^8+2*t^2*D^7+8*t*D^7+12*D^72*t^4*D^6+6*t^3*D^6+12*t*D^620*D^6
Note: See TracChangeset
for help on using the changeset viewer.