Changeset 5bccba in git
- Timestamp:
- Feb 11, 2019, 5:41:21 PM (5 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 77624bdb8f875aa938e9fda67d8720405651c08d
- Parents:
- 1bd40025d3997a6d11d72e7f8e2834d3fdd83ef9dfa15b9f0da1b32d9c4aff3f6014b3b03d8a72c2
- Files:
-
- 29 edited
- 2 moved
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/fpadim.lib
r1bd400 r5bccba 15 15 16 16 KEYWORDS: finitely presented algebra; Letterplace Groebner basis; K-basis; K-dimension; Hilbert series 17 18 PROCEDURES:19 lpKDimCheck(G); checks whether the K-dimension of A/<G> is finite20 lpKDim(G[,d,n]); computes the K-dimension of A/<G>21 lpMonomialBasis(d, donly, J); computes a list of monomials not contained in J22 lpHilbert(G[,d,n]); computes the truncated Hilbert series of A/<G>23 lpSickleDim(G[,d,n]); computes the mistletoes and the K-dimension of A/<G>24 17 25 18 NOTE: … … 73 66 [Stu] G. Studzinski: Dimension computations in non-commutative, 74 67 associative algebras, Diploma thesis, RWTH Aachen, 2010. 68 69 PROCEDURES: 70 lpKDimCheck(G); checks whether the K-dimension of A/<G> is finite 71 lpKDim(G[,d,n]); computes the K-dimension of A/<G> 72 lpMonomialBasis(d, donly, J); computes a list of monomials not contained in J 73 lpHilbert(G[,d,n]); computes the truncated Hilbert series of A/<G> 74 lpSickleDim(G[,d,n]); computes the mistletoes and the K-dimension of A/<G> 75 75 76 76 SEE ALSO: freegb_lib, fpaprops_lib, ncHilb_lib -
Singular/LIB/fpalgebras.lib
r1bd400 r5bccba 78 78 RETURN: ideal 79 79 ASSUME: basering has a letterplace ring structure and 80 @*A is a generalized Cartan matrix with integer entries80 A is a generalized Cartan matrix with integer entries 81 81 PURPOSE: compute the ideal of Serre's relations associated to A 82 82 EXAMPLE: example serreRelations; shows examples … … 145 145 RETURN: ring (and ideal) 146 146 PURPOSE: compute the inhomogeneous Serre's relations associated to A in given 147 @*variable names147 variable names 148 148 ASSUME: three ideals in the input are of the same sizes and contain merely 149 @*variables which are interpreted as follows: N resp. P stand for negative150 @*resp. positive roots, C stand for Cartan elements. d is the degree bound for151 @*letterplace ring, which will be returned.152 @*The matrix A is a generalized Cartan matrix with integer entries153 @*The result is the ideal called 'fsRel' in the returned ring.149 variables which are interpreted as follows: N resp. P stand for negative 150 resp. positive roots, C stand for Cartan elements. d is the degree bound for 151 letterplace ring, which will be returned. 152 The matrix A is a generalized Cartan matrix with integer entries 153 The result is the ideal called 'fsRel' in the returned ring. 154 154 EXAMPLE: example fullSerreRelations; shows examples 155 155 " … … 363 363 RETURN: ring (and exports ideal) 364 364 PURPOSE: compute the ideal of Adem relations for i<2j in characteristic 0 365 @*the ideal is exported under the name AdemRel in the output ring365 the ideal is exported under the name AdemRel in the output ring 366 366 EXAMPLE: example ademRelations; shows examples 367 367 " -
Singular/LIB/fpaprops.lib
r1bd400 r5bccba 55 55 "USAGE: lpNoetherian(G); G an ideal in a Letterplace ring 56 56 RETURN: int 57 @*0 not Noetherian58 @*1 left Noetherian59 @*2 right Noetherian60 @*3 Noetherian61 @*4 weak Noetherian57 0 not Noetherian 58 1 left Noetherian 59 2 right Noetherian 60 3 Noetherian 61 4 weak Noetherian 62 62 PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian 63 63 ASSUME: - basering is a Letterplace ring 64 @*- G is a Groebner basis64 - G is a Groebner basis 65 65 THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>. 66 66 If it gives an affirmative answer for one of the properties, then it … … 644 644 start. The parameter visited, cyclic and path should be 0. 645 645 RETURN: int 646 @*:Maximal number of distinct cycles646 Maximal number of distinct cycles 647 647 PURPOSE: Calculate the maximal number of distinct cycles in a single path starting at v 648 648 ASSUME: Basering is a Letterplace ring … … 730 730 proc lpUfGraph(ideal G, list #) 731 731 "USAGE: lpUfGraph(G); G a set of monomials in a letterplace ring. 732 @* lpUfGraph(G,1); G a set of monomials in a letterplace ring.733 732 RETURN: intmat or list 734 733 NOTE: lpUfGraph(G); returns intmat. lpUfGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal. … … 882 881 RETURN: int 883 882 PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> 884 @*-1 means positive infinite883 -1 means positive infinite 885 884 ASSUME: - basering is a Letterplace ring 886 @*- G is a Groebner basis885 - G is a Groebner basis 887 886 " 888 887 { -
Singular/LIB/freegb.lib
r1bd400 r5bccba 23 23 24 24 PROCEDURES: 25 freeAlgebra(r, d); creates a Letterplace ring out of given data26 25 isFreeAlgebra(r); check whether r is a letterplace ring (free algebra) 27 26 lpDegBound(R); returns the degree bound of a letterplace ring 28 27 lpVarBlockSize(R); returns the size of the letterplace blocks 29 30 letplaceGBasis(I); (deprecated, use twostd) two-sided Groebner basis of a letterplace ideal I 31 28 letplaceGBasis(I); (deprecated) two-sided Groebner basis of a letterplace ideal I 32 29 lpDivision(f,I); two-sided division with remainder 33 30 lpGBPres2Poly(L,I); reconstructs a polynomial from the output of lpDivision 34 35 31 lieBracket(a,b[, N]); Lie bracket ab-ba of two letterplace polynomials 36 32 isOrderingShiftInvariant(i); tests shift-invariance of the monomial ordering 37 33 isVar(p); check whether p is a power of a single variable 38 39 lpLmDivides(ideal I, poly p); tests whether there exists q in I, such that LM(q)|LM(p) 40 lpVarAt(poly p, int pos); returns the variable (as a poly) at position pos of the poly p 41 42 makeLetterplaceRing(d); (deprecated, use freeAlgebra) creates a Letterplace ring out of given data 34 makeLetterplaceRing(d); (deprecated) creates a Letterplace ring out of given data 43 35 setLetterplaceAttributes(R,d,b); (for testing purposes) supplies ring R with the letterplace structure 44 36 … … 62 54 63 55 LIB "qhmoduli.lib"; // for Max 64 LIB "bfun.lib"; // for inForm65 LIB "fpadim.lib"; // for intvec conversion66 56 LIB "fpalgebras.lib"; // for compatibility 67 57 … … 84 74 example isVar; 85 75 86 example lpLmDivides;87 example lpVarAt;88 89 76 example ivL2lpI; 90 77 example iv2lp; … … 100 87 RETURN: ring with special attributes set 101 88 PURPOSE: sets attributes for a letterplace ring: 102 @*'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where103 @*'uptodeg' stands for the degree bound,104 @*'lV' for the number of variables in the block 0.89 'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where 90 'uptodeg' stands for the degree bound, 91 'lV' for the number of variables in the block 0. 105 92 NOTE: Activate the resulting ring by using @code{setring} 106 93 " … … 340 327 RETURN: int 341 328 PURPOSE: check, whether leading monomial of p is a power of a single variable 342 @*from the basering. Returns the exponent or 0 if p is multivariate.329 from the basering. Returns the exponent or 0 if p is multivariate. 343 330 EXAMPLE: example isVar; shows examples 344 331 " … … 380 367 } 381 368 382 proc lpLmDivides(ideal I, poly p)383 "USAGE: lpLmDivides(I); I an ideal384 RETURN: boolean385 ASSUME: basering is a Letterplace ring386 PURPOSE: tests if there is a polynomial q in I with LM(q)|LM(p)387 EXAMPLE: example lpLmDivides; shows examples388 "389 {390 ERROR(" freegb.so not loaded");391 }392 example393 {394 "EXAMPLE:"; echo = 2;395 ring r = 0,(x,y),dp;396 def R = freeAlgebra(r, 5);397 setring R;398 poly p = x*y*y;399 lpLmDivides(y*y, p);400 lpLmDivides(y*x, p);401 lpLmDivides(ideal(y*y, y*x), p);402 }403 404 proc lpVarAt(poly p, int pos)405 "USAGE: lpVarAt(p, pos); p a poly, pos an int406 RETURN: poly407 ASSUME: basering is a Letterplace ring408 PURPOSE: returns the variable (as a poly) at position pos of the poly p409 EXAMPLE: example lpVarAt; shows examples410 "411 {412 ERROR(" freegb.so not loaded");413 }414 example415 {416 "EXAMPLE:"; echo = 2;417 ring r = 0,(x,y),dp;418 def R = freeAlgebra(r, 5);419 setring R;420 poly p = y*y*x;421 lpVarAt(p, 3);422 }423 424 369 proc letplaceGBasis(def I) 425 370 "USAGE: letplaceGBasis(I); I an ideal/module 426 371 RETURN: ideal/module 427 ASSUME: basering is a Letterplace ring, input consists of Letterplace 428 @* polynomials 429 PURPOSE: compute the two-sided Groebner basis of I via Letterplace 430 @* algorithm (legacy routine) 372 ASSUME: basering is a Letterplace ring, input consists of Letterplace polynomials 373 PURPOSE: compute the two-sided Groebner basis of I via Letterplace algorithm (legacy routine) 431 374 NOTE: the degree bound for this computation is read off the letterplace 432 @*structure of basering375 structure of basering 433 376 EXAMPLE: example letplaceGBasis; shows examples 434 377 " … … 469 412 PURPOSE:compute the Lie bracket [a,b] = ab - ba between letterplace polynomials 470 413 NOTE: if N>1 is specified, then the left normed bracket [a,[...[a,b]]]] is 471 @*computed.414 computed. 472 415 EXAMPLE: example lieBracket; shows examples 473 416 " … … 566 509 RETURN: ring 567 510 ASSUME: L has a special form. Namely, it is a list of modules, where 568 569 511 - each generator of every module stands for a monomial times coefficient in 570 @* free algebra, 571 512 free algebra, 572 513 - in such a vector generator, the 1st entry is a nonzero coefficient from the 573 @* ground field 574 514 ground field 575 515 - and each next entry hosts a variable from the basering. 576 516 PURPOSE: compute the two-sided Groebner basis of an ideal, encoded by L 577 @*in the free associative algebra, up to degree d517 in the free associative algebra, up to degree d 578 518 NOTE: Apply @code{lst2str} to the output in order to obtain a better readable 579 @*presentation519 presentation 580 520 EXAMPLE: example freeGBasis; shows examples 581 521 " … … 1054 994 def R = freeAlgebra(r, 7); 1055 995 isFreeAlgebra(R); 1056 }1057 1058 proc freeAlgebra(def r, int d)1059 "USAGE: freeAlgebra(r, d); r a ring, d an integer1060 RETURN: ring1061 PURPOSE: creates a letterplace ring with the ordering of r1062 EXAMPLE: example freeAlgebra; shows examples1063 "1064 {1065 ERROR(" freegb.so not loaded");1066 }1067 example1068 {1069 "EXAMPLE:"; echo = 2;1070 ring r = 0,(x,y,z),dp;1071 def R = freeAlgebra(r, 7);1072 R;1073 ring r2 = 0,(x,y,z),lp;1074 def R2 = freeAlgebra(r2, 7);1075 R2;1076 996 } 1077 997 … … 3231 3151 RETURN: int 3232 3152 NOTE: Tests whether the ordering of the current ring is shift invariant, which is the case, when LM(p) > LM(p') for all p and p' where p' is p shifted by any number of places. 3233 @* If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered. 3153 3154 If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered. 3234 3155 ASSUME: - basering is a Letterplace ring. 3235 3156 " … … 3886 3807 static proc mod_init() 3887 3808 { 3888 LIB"free gb.so";3889 } 3809 LIB"freealgebra.so"; 3810 } -
Singular/LIB/ncfactor.lib
rdfa15b r5bccba 1 1 /////////////////////////////////////////////////////////// 2 version="version ncfactor.lib 4. 1.1.0 Jan_2018 "; //$Id$2 version="version ncfactor.lib 4.0.0.0 _2017 "; //$Id$ 3 3 category="Noncommutative"; 4 4 info=" 5 5 LIBRARY: ncfactor.lib Tools for factorization in some noncommutative algebras 6 AUTHORS: Albert Heinle, aheinle@uwaterloo.ca 7 @* Viktor Levandovskyy, levandov@math.rwth-aachen.de 8 9 OVERVIEW: New methods for factorization on polynomials 10 are implemented for three types of algebras, all generated by 11 2*n, n in NN, generators (n'th Weyl, n'th shift and graded polynomials in n'th q-Weyl algebras) 12 over a field K. 6 AUTHORS: Albert Heinle, aheinle at uwaterloo.ca 7 @* Viktor Levandovskyy, levandov at math.rwth-aachen.de 8 9 OVERVIEW: In this library, new methods for factorization on polynomials 10 @* are implemented for several types of algebras, namely 11 @* - finitely presented (and also free) associative algebras (Letterplace subsystem) 12 @* - G-algebras (Plural subsystem), including (q)-Weyl and (q)-shift algebras in 2n variables 13 @* The determination of the best algorithm available for users input is done 14 @* automatically in the procedure ncfactor(). 15 13 16 @* More detailled description of the algorithms and related publications can be found at 14 17 @url{https://cs.uwaterloo.ca/\~aheinle/}. 15 18 16 19 PROCEDURES: 17 ncfactor(h); Factorization in any G-algebra.20 ncfactor(h); Factorization in any finitely presented algebra (incl. G-algebra) 18 21 facWeyl(h); Factorization in the n'th Weyl algebra 19 22 facFirstWeyl(h); Factorization in the first Weyl algebra … … 37 40 LIB "solve.lib"; //for solve 38 41 LIB "poly.lib"; //for content 42 LIB "fpadim.lib"; //for letterplace 39 43 40 44 proc tst_ncfactor() … … 128 132 } 129 133 print("Successful."); 130 print("Testing Min");131 if (!test_Min())132 {133 ERROR("Min is not working properly.");134 }135 print("Successful.");136 134 print("Testing isListEqual"); 137 135 if (!test_isListEqual()) … … 410 408 } 411 409 print("Successful."); 412 print("Testing delete_duplicates_noteval_and_sort"); 410 print("Testing getMaxDegreeVecLetterPlace"); 411 if(!test_getMaxDegreeVecLetterPlace()) 412 { 413 ERROR("getMaxDegreeVecLetterPlace is not working properly."); 414 } 415 print("Successful."); 416 print("Testing wordsWithMaxAppearance"); 417 if(!test_wordsWithMaxAppearance()) 418 { 419 ERROR("wordsWithMaxAppearance is not working properly."); 420 } 421 print("Successful."); 422 print("Testing monsSmallerThanLetterPlace"); 423 if(!test_monsSmallerThanLetterPlace()) 424 { 425 ERROR("monsSmallerThanLetterPlace is not working properly."); 426 } 427 print("Successful."); 428 print("Testing ncfactor_letterplace_poly_s"); 429 if(!test_ncfactor_letterplace_poly_s()) 430 { 431 ERROR("ncfactor_letterplace_poly_s is not working properly."); 432 } 433 print("Successful."); 434 print("Testing ncfactor_without_opt_letterplace"); 435 if(!test_ncfactor_without_opt_letterplace()) 436 { 437 ERROR("ncfactor_without_opt_letterplace is not working properly."); 438 } 439 print("Successful."); 413 440 print("All tests ran successfully."); 414 441 } … … 2041 2068 return(result); 2042 2069 }//testing increment_intvec 2043 2044 2045 //I know that Singular has this function in the package2046 //qhmoduli.lib. But I don't see the reason why I should clutter my2047 //namespace with functions to study Moduli Spaces of2048 //Semi-Quasihomogeneous Singularities (in case somebody wonders)2049 static proc Min(def lst)2050 "USAGE: Min(lst); list is an iterable element (list/ideal/intvec)2051 containing ordered elements.2052 PURPOSE: returns the minimal element in lst2053 ASSUME: lst contains at least one element2054 "{//proc Min2055 def minElem = lst[1];2056 int i;2057 for (i = 2; i<=size(lst);i++)2058 {2059 if (lst[i]<minElem)2060 {2061 minElem = lst[i];2062 }2063 }2064 return (minElem);2065 }//proc Min2066 2067 2068 static proc test_Min()2069 {//Testing Min2070 int result = 1;2071 //Test 1: One element list2072 int expected= 1;2073 int obtained = Min(list(1));2074 if (expected!=obtained)2075 {2076 print("Test 1 for Min failed.");2077 print("Expected:\n");2078 print(expected);2079 print("obtained:\n");2080 print(obtained);2081 result = 0;2082 }2083 //Test 2: Two element list, first one is Min2084 expected = 5;2085 obtained = Min(list(5,8));2086 if (expected!=obtained)2087 {2088 print("Test 2 for Min failed.");2089 print("Expected:\n");2090 print(expected);2091 print("obtained:\n");2092 print(obtained);2093 result = 0;2094 }2095 //Test 3: Two element list, second one is Min2096 expected = 5;2097 obtained = Min(list(8,5));2098 if (expected!=obtained)2099 {2100 print("Test 3 for Min failed.");2101 print("Expected:\n");2102 print(expected);2103 print("obtained:\n");2104 print(obtained);2105 result = 0;2106 }2107 //Test 4: A lot of elements, Min randomly in between.2108 expected = -11;2109 obtained = Min(list(5,8,7,2,8,0,-11,0,25));2110 if (expected!=obtained)2111 {2112 print("Test 4 for Min failed.");2113 print("Expected:\n");2114 print(expected);2115 print("obtained:\n");2116 print(obtained);2117 result = 0;2118 }2119 return(result);2120 }//Testing Min2121 2122 2070 2123 2071 static proc isListEqual(list l1, list l2) … … 3340 3288 " 3341 3289 {//isInCommutativeSubRing 3290 int i; int j; int k; 3291 intvec tempIntVec; 3292 int previouslyEncounteredVar = -1; 3293 if ( attrib(basering, "isLetterplaceRing") >= 1) 3294 {//separate department: letterplace case 3295 for (i = 1; i<=size(h); i++) 3296 {//iterating over the monomials of h 3297 tempIntVec = lp2iv(h[i]); 3298 if (size(tempIntVec) > 1) 3299 {//nontrivial monomial 3300 j = tempIntVec[1]; 3301 if (previouslyEncounteredVar != -1 and j != previouslyEncounteredVar) 3302 {//In this case, the previously encountered var is not equal to this one 3303 return(0); 3304 }//In this case, the previously encountered var is not equal to this one 3305 previouslyEncounteredVar = j; 3306 for (k = 2; k <= size(tempIntVec); k++) 3307 {//checking if each entry in the intvec is the same 3308 if (tempIntVec[k]!=j) 3309 {//more than one variable in monomial 3310 return(0); 3311 }//more than one variable in monomial 3312 }//checking if each entry in the intvec is the same 3313 }//nontrivial monomial 3314 else 3315 {i++; continue;} 3316 }//iterating over the monomials of h 3317 return(1); 3318 }//separate department: letterplace case 3342 3319 list tempRingList = ringlist(basering); 3343 3320 if (size(tempRingList)<=4) … … 3346 3323 }//In this case, the given ring was commutative 3347 3324 list appearing_variables; 3348 int i; int j;3349 3325 intvec degreeIntVec; 3350 3326 for (i = 1; i<=nvars(basering);i++) … … 3426 3402 { 3427 3403 print("Test 4 for isInCommutativeSubRing failed."); 3404 print("Expected:\n"); 3405 print(expected); 3406 print("obtained:\n"); 3407 print(obtained); 3408 result = 0; 3409 } 3410 return(result); 3411 //Test 5: Letterplace ring, negative example 3412 ring r2 = 0,(x,y,z),dp; 3413 int d =4; // degree bound 3414 def R2 = makeLetterplaceRing(d); 3415 setring R2; 3416 expected = 0; 3417 obtained = isInCommutativeSubRing(x + y); 3418 if (expected !=obtained) 3419 { 3420 print("Test 5 for isInCommutativeSubRing failed."); 3421 print("Expected:\n"); 3422 print(expected); 3423 print("obtained:\n"); 3424 print(obtained); 3425 result = 0; 3426 } 3427 //Test 6: Letterplace ring, positive example 3428 expected = 1; 3429 obtained = isInCommutativeSubRing(x + x*x); 3430 if (expected !=obtained) 3431 { 3432 print("Test 6 for isInCommutativeSubRing failed."); 3433 print("Expected:\n"); 3434 print(expected); 3435 print("obtained:\n"); 3436 print(obtained); 3437 result = 0; 3438 } 3439 //Test 7: Letterplace ring, previous bug 3440 expected = 0; 3441 obtained = isInCommutativeSubRing(x*x - y*y); 3442 if (expected !=obtained) 3443 { 3444 print("Test 7 for isInCommutativeSubRing failed."); 3428 3445 print("Expected:\n"); 3429 3446 print(expected); … … 3457 3474 if (deg(h)<=0) 3458 3475 { 3459 dbprint(p,dbprintWhitespace + "h is a constant. Returning 3460 immediately"); 3476 dbprint(p,dbprintWhitespace + "h is a constant. Returning immediately"); 3461 3477 return(list(list(h))); 3462 3478 } 3463 3479 def r = basering; 3464 3480 list factorizeOutput; 3465 if (size(ringlist(basering))<=4 )3481 if (size(ringlist(basering))<=4 && (attrib(r, "isLetterplaceRing") == 0) ) 3466 3482 {//commutative ring case 3467 dbprint(p,dbprintWhitespace + "We are in a commutative 3468 ring. Factoring h using factorize."); 3483 dbprint(p,dbprintWhitespace + "We are in a commutative ring. Factoring h using factorize."); 3469 3484 factorizeOutput = factorize(h); 3470 3485 }//commutative ring case 3471 3486 else 3472 3487 {//commutative subring case; 3473 dbprint(p,dbprintWhitespace + "We are in a commutative 3474 subring. Generating commutative ring.."); 3475 def rList = ringlist(basering); 3476 rList = delete(rList,5); 3477 rList = delete(rList,5); 3478 def tempRing = ring(rList); 3479 setring(tempRing); 3480 poly h = imap(r,h); 3481 dbprint(p, dbprintWhitespace+"Factoring h in commutative ring."); 3482 list tempResult = factorize(h); 3483 setring(r); 3484 factorizeOutput = imap(tempRing,tempResult); 3488 dbprint(p,dbprintWhitespace + "We are in a commutative subring. Generating commutative ring."); 3489 if (attrib(r, "isLetterplaceRing") == 0) 3490 {//G-algebra case 3491 def rList = ringlist(basering); 3492 rList = delete(rList,5); 3493 rList = delete(rList,5); 3494 def tempRing = ring(rList); 3495 setring(tempRing); 3496 poly h = imap(r,h); 3497 dbprint(p, dbprintWhitespace+"Factoring h in commutative ring."); 3498 list tempResult = factorize(h); 3499 setring(r); 3500 factorizeOutput = imap(tempRing,tempResult); 3501 }//G-algebra case 3502 else 3503 {//Letterplace case 3504 int theRightVar = lp2iv(h[1])[1]; 3505 list commFactInIv = list(); 3506 list tempMonomList = list(); 3507 def rList = ringlist(basering); 3508 rList[2] = list("@x"); 3509 rList[3] = list(list("dp", intvec(1)), 3510 list("C", 0)); 3511 def tempRing = ring(rList); 3512 setring(tempRing); 3513 ideal tempIdeal; 3514 for (i=1; i<=nvars(r); i++) 3515 {tempIdeal[i] = var(1);} 3516 map fromR = r, tempIdeal; 3517 poly h = fromR(h); 3518 dbprint(p, dbprintWhitespace+"Factoring h in commutative ring."); 3519 list tempResult = factorize(h); 3520 dbprint(p, dbprintWhitespace+"Done. The result is:"); 3521 dbprint(p, tempResult); 3522 dbprint(p, dbprintWhitespace+"Now translated into intvec representation:"); 3523 for (i = 1; i <= size(tempResult[1]); i++) 3524 {//translate all factorizations into lists of intvecs and coeffs 3525 commFactInIv[i] = list(); 3526 for (j = 1; j <= size(tempResult[1][i]); j++) 3527 {//iterate over each monomial 3528 commFactInIv[i][j] = list(leadcoef(tempResult[1][i][j])); 3529 if (deg(tempResult[1][i][j]) != 0) 3530 {//a power of @x 3531 commFactInIv[i][j] = commFactInIv[i][j] + list(theRightVar:deg(tempResult[1][i][j])); 3532 }//a power of @x 3533 }//iterate over each monomial 3534 }//translate all factorizations into lists of intvecs and coeffs 3535 dbprint(p, commFactInIv); 3536 setring(r); 3537 factorizeOutput = imap(tempRing,tempResult); 3538 list commFactInIv = imap(tempRing, commFactInIv); 3539 poly tempEntry; 3540 for (i = 1; i<=size(commFactInIv); i++) 3541 { 3542 tempEntry = 0; 3543 for (j=1; j<=size(commFactInIv[i]); j++) 3544 { 3545 if (size(commFactInIv[i][j]) == 1) 3546 {//simply a number 3547 tempEntry = tempEntry + commFactInIv[i][j][1]; 3548 }//simply a number 3549 else 3550 { 3551 tempEntry = tempEntry + commFactInIv[i][j][1]*iv2lp(commFactInIv[i][j][2]); 3552 } 3553 } 3554 factorizeOutput[1][i] = tempEntry; 3555 } 3556 }//Letterplace case 3485 3557 }//commutative subring case; 3486 dbprint(p,dbprintWhitespace + "Done commutatively factorizing. 3487 The result is:"); 3558 dbprint(p,dbprintWhitespace + "Done commutatively factorizing. The result isssssss:"); 3488 3559 dbprint(p,factorizeOutput); 3489 3560 dbprint(p,dbprintWhitespace+"Computing all permutations of this factorization."); … … 3526 3597 } 3527 3598 kill R; 3528 //Test 2: Non-commutative ring, constant3599 //Test 2: G-Algebra, constant 3529 3600 ring R = 0,(x,d),dp; 3530 3601 def r = nc_algebra(1,1); … … 3542 3613 } 3543 3614 kill r; kill R; 3544 //Test 3: Non-commutative ring, definitely commutative subring, irreducible3615 //Test 3: G-Algebra, definitely commutative subring, irreducible 3545 3616 ring R = 0,(x1,x2,d1,d2),dp; 3546 3617 def r = Weyl(); … … 3558 3629 } 3559 3630 kill r; kill R; 3560 //Test 4: Non-commutative ring, definitely commutative subring,3631 //Test 4: G-Algebra, definitely commutative subring, 3561 3632 //reducible 3562 3633 ring R = 0,(x1,x2,d1,d2),dp; … … 3579 3650 } 3580 3651 kill r; kill R; 3652 //Test 5: Letterplace ring, constant 3653 ring r = 0,(x,y,z),dp; 3654 int d =4; // degree bound 3655 def R = makeLetterplaceRing(d); 3656 setring R; 3657 list expected = list(list(poly(3445))); 3658 list obtained = factor_commutative(3445); 3659 if (!isListEqual(expected,obtained)) 3660 { 3661 print("Test 5 for factor_commutative failed."); 3662 print("Expected:\n"); 3663 print(expected); 3664 print("obtained:\n"); 3665 print(obtained); 3666 result = 0; 3667 } 3668 //Test 6: Letterplace ring, definitely commutative subring, irreducible 3669 expected = list(list(poly(1), x*x+ 2*x + 2)); 3670 obtained = factor_commutative(x*x+ 2*x + 2); 3671 if (!isListEqual(expected,obtained)) 3672 { 3673 print("Test 6 for factor_commutative failed."); 3674 print("Expected:\n"); 3675 print(expected); 3676 print("obtained:\n"); 3677 print(obtained); 3678 result = 0; 3679 } 3680 //Test 7: Letterplace ring, definitely commutative subring, 3681 //reducible 3682 expected = list(list(poly(1), x*x+ 2*x + 2, x*x- 2*x - 2), 3683 list(poly(1), x*x- 2*x - 2, x*x+ 2*x + 2)); 3684 obtained = factor_commutative((x*x+ 2*x + 2)*(x*x- 2*x - 2)); 3685 if (!isListEqual(expected,obtained)) 3686 { 3687 print("Test 7 for factor_commutative failed."); 3688 print("Expected:\n"); 3689 print(expected); 3690 print("obtained:\n"); 3691 print(obtained); 3692 result = 0; 3693 } 3694 //Test 8: Letterplace ring, using last variable 3695 expected = list(list(poly(1), z*z+ 2*z + 2, z*z - 2*z - 2), 3696 list(poly(1), z*z - 2*z - 2, z*z+ 2*z + 2)); 3697 obtained = factor_commutative((z*z+ 2*z + 2)*(z*z - 2*z - 2)); 3698 if (!isListEqual(expected,obtained)) 3699 { 3700 print("Test 8 for factor_commutative failed."); 3701 print("Expected:\n"); 3702 print(expected); 3703 print("obtained:\n"); 3704 print(obtained); 3705 result = 0; 3706 } 3581 3707 return(result); 3582 3708 }//testing factor_commutative … … 6730 6856 6731 6857 result = delete_duplicates_noteval_and_sort(result); 6732 //print(M);6733 6858 if (size(result) == 0) 6734 6859 {//no factorization found … … 6894 7019 } 6895 7020 hZeroinR = tempHList; 6896 //hBetweenDegrees = reverse(hBetweenDegrees);6897 7021 dbprint(p,dbprintWhitespace+" Done!"); 6898 7022 dbprint(p,dbprintWhitespace+" Moving everything into the ring K[theta]"); … … 8244 8368 list tempList = list(); 8245 8369 //First, we are going to deal with our most hated guys: The Coefficients. 8246 //8247 8370 dbprint(p,dbprintWhitespace + "We get all combinations for the coefficient of the 8248 8371 maximal homogeneous part"); … … 9746 9869 rlist[3][2][2]=intvec(0); 9747 9870 rlist = insert(rlist,ideal(0),3); 9748 //The following lines of code will become obsolete once bug #753 in9749 //Singular is fixed. Until then, this measure is unfortunately9750 //necessary.9751 //begin9752 intvec perms = 0:nvars(@r);9753 for (i =1; i<=nvars(@r);i++)9754 {//finding the right position of each input variable9755 for (j = 1; j<=size(inpList); j++)9756 {9757 if (var(i)==inpList[j])9758 {//found the correct spot9759 perms[i] = j;9760 break;9761 }//found the correct spot9762 }9763 }//finding the right position of each input variable9764 9871 def @r2 = ring(rlist); 9765 9872 setring(@r2); 9766 9873 def @r3 = Weyl(); 9767 9874 setring(@r3); 9768 ideal mappingIdeal; 9769 for (i = 1; i<=size(perms); i++) 9770 {//generating the mapping ideal 9771 if (perms[i]>0) 9772 {//only variables that are in the input list are permitted 9773 mappingIdeal[i] = var(perms[i]); 9774 }//only variables that are in the input list are permitted 9775 }//generating the mapping ideal 9776 map toR3 = @r, mappingIdeal; 9777 poly h = toR3(h); 9875 poly h = imap(@r,h); 9778 9876 list result = facWeyl(h); 9779 9877 setring(@r); 9780 ideal mappingIdeal; 9781 for (i = 1; i<=size(perms);i++) 9782 {//finding the correct permutation 9783 for (j = 1; j<=size(perms); j++) 9784 {//the spot needs to coincide 9785 if (perms[j]==i) 9786 {//found it 9787 mappingIdeal[i] = var(j); 9788 break; 9789 }//found it 9790 }//the spot needs to coincide 9791 }//finding the correct permutation 9792 map toR = @r3, mappingIdeal; 9793 list result = toR(result); 9794 //end 9795 //once bug is fixed, please uncomment the following lines and 9796 //discard the above 9797 /* def @r2 = ring(rlist); */ 9798 /* setring(@r2); */ 9799 /* def @r3 = Weyl(); */ 9800 /* setring(@r3); */ 9801 /* poly h = imap(@r,h); */ 9802 /* list result = facWeyl(h); */ 9803 /* setring(@r); */ 9804 /* list result = imap(@r3,result); */ 9878 list result = imap(@r3,result); 9805 9879 return(result); 9806 9880 }//proc facSubWeyl … … 10474 10548 - We have n parameters q_1,..., q_n given. 10475 10549 10476 SEE ALSO: homogfac FirstQWeyl, homogfacFirstQWeyl_all10550 SEE ALSO: homogfacNthWeyl, homogfacFirstQWeyl, homogfacFirstQWeyl_all 10477 10551 " 10478 10552 {//proc homogfacNthQWeyl_all … … 10992 11066 - There exists at least one variable in the ring. 10993 11067 NOTE: 11068 - works for both PLURAL and LETTERPLACE subsystems 10994 11069 - Every entry of the output list is a list with factors for one possible factorization. 10995 11070 The first factor is always a constant (1, if no nontrivial constant … … 11002 11077 for (i = 1; i<=voice;i++) 11003 11078 {dbprintWhitespace = dbprintWhitespace + " ";} 11004 dbprint(p,dbprintWhitespace + "Checking if the field fulfills 11079 dbprint(p,dbprintWhitespace + "Checking if the field fulfills\ 11005 11080 everything we assume."); 11006 11081 if (nvars(basering)<1) … … 11010 11085 if (minpoly !=0) 11011 11086 { 11012 ERROR("factorize does not support fields of type (p^n,a) ");11087 ERROR("factorize does not support fields of type (p^n,a) yet"); 11013 11088 return list(list()); 11014 11089 } 11015 11090 } 11016 dbprint(p,dbprintWhitespace + "Everything seems to be alright with 11091 dbprint(p,dbprintWhitespace + "Everything seems to be alright with\ 11017 11092 the ground field."); 11018 11093 if (deg(h)<=0) … … 11024 11099 dbprint(p,dbprintWhitespace+"Checking if a more improved algorithm\ 11025 11100 is available other than the naive ansatz-method."); 11026 dbprint(p,dbprintWhitespace+"1. Checking if h in commutative 11027 (sub)-ring"); 11101 dbprint(p,dbprintWhitespace+"1. Checking if h in commutative (sub)-ring"); 11028 11102 if (isInCommutativeSubRing(h)) 11029 11103 {//h is in a commutative subring 11030 11104 return(factor_commutative(h)); 11031 11105 }//h is in a commutative subring 11032 dbprint(p,dbprintWhitespace+"h was not in a commutative 11106 dbprint(p,dbprintWhitespace+"h was not in a commutative\ 11033 11107 (sub)-ring."); 11034 dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra 11035 over QQ"); 11108 dbprint(p,dbprintWhitespace+"2. Checking if h was in a letterplace ring"); 11109 if ( attrib(basering, "isLetterplaceRing") >= 1 ) 11110 { 11111 dbprint(p,dbprintWhitespace+ 11112 "We are indeed in a letterplace ring. Forwarding the computation " + 11113 "to ncfactor-without-opt-letterplace"); 11114 return(ncfactor_without_opt_letterplace(h)); 11115 } 11116 dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra over QQ"); 11036 11117 if (ncfactor_isWeyl()&&npars(basering)==0&&char(basering)==0) 11037 11118 { 11038 dbprint(p,dbprintWhitespace + "We are indeed in a Weyl11039 algebra. Forwarding computation to facWeyl");11119 dbprint(p,dbprintWhitespace + 11120 "We are indeed in a Weyl algebra. Forwarding computation to facWeyl"); 11040 11121 return(facWeyl(h)); 11041 11122 } 11042 11123 dbprint(p,dbprintWhitespace+"Our ring is not a Weyl algebra over QQ."); 11043 dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl 11044 algebra over QQ."); 11124 dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl algebra over QQ."); 11045 11125 if (ncfactor_isQWeyl()&&char(basering)==0) 11046 11126 { 11047 dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl 11127 dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl\ 11048 11128 algebra over QQ. Checking if homogeneous."); 11049 11129 if(homogwithorderNthWeyl(h)) 11050 11130 { 11051 dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding 11131 dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding\ 11052 11132 computation to homogfacqweyl."); 11053 11133 return(homogfacNthQWeyl_all(h)); … … 11055 11135 } 11056 11136 dbprint(p,dbprintWhitespace+"Our ring is not a q-Weyl algebra."); 11057 dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra 11137 dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra\ 11058 11138 that resembles the Weyl algebra"); 11059 11139 if(isInWeylSubAlg(h)&&npars(basering)==0&&char(basering)==0) 11060 11140 { 11061 dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is 11141 dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is\ 11062 11142 isomorphic to a Weyl algebra. Forwarding to facSubWeyl."); 11063 11143 return(facSubWeyl(h)); 11064 11144 } 11065 dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going 11145 dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going \ 11066 11146 for the ansatz method without optimization."); 11067 11147 return(ncfactor_without_opt(h)); … … 11070 11150 { 11071 11151 "EXAMPLE:";echo=2; 11152 // first, an example with PLURAL 11072 11153 def R = makeUsl2(); 11073 11154 setring(R); 11074 11155 poly p = e^3*f+e^2*f^2-e^3+e^2*f+2*e*f^2-3*e^2*h-2*e*f*h-8*e^2 11075 11156 +e*f+f^2-4*e*h-2*f*h-7*e+f-h; 11157 ncfactor(p); 11158 kill R; 11159 // an example with LETTERPLACE 11160 LIB "freegb.lib"; 11161 ring r = 0,(x,y),Dp; 11162 def R = freeAlgebra(r,5); setring(R); 11163 poly p = x*y*x - x; 11076 11164 ncfactor(p); 11077 11165 } … … 11286 11374 { 11287 11375 print("Test 10 for ncfactor failed."); 11376 print("Expected:\n"); 11377 print(expected); 11378 print("obtained:\n"); 11379 print(obtained); 11380 result = 0; 11381 } 11382 kill r; 11383 //Test 11: Generic Letterplace example 11384 ring r = 0,(x,y,z),dp; 11385 int d =4; // degree bound 11386 def R = makeLetterplaceRing(d); 11387 setring R; 11388 poly f1 = 6*x*y*x + 9*x; 11389 list obtained = ncfactor(f1); 11390 list expected = sortFactorizations( 11391 list( 11392 list(number(3), x, 2*y*x + 3), 11393 list(number(3), 2*x*y + 3, x) 11394 )); 11395 if (!isListEqual(expected,obtained)) 11396 { 11397 print("Test 11 for ncfactor failed."); 11288 11398 print("Expected:\n"); 11289 11399 print(expected); … … 11984 12094 }//testing factorize_nc_s 11985 12095 12096 12097 static proc getMaxDegreeVecLetterPlace(poly h) 12098 "USAGE: getMaxDegreeVecLetterPlace(h); h is a polynomial in a 12099 Letterplace ring. 12100 RETURN: intvec 12101 PURPOSE: Returns for each variable in the ring the maximal 12102 degree in which it appears in h. 12103 ASSUMING: The basering is 12104 " 12105 {//proc getMaxDegreeVecLetterPlace 12106 int lv = attrib(basering, "isLetterplaceRing"); // nvars of orig ring 12107 if (h == 0) { return (0:lv); } 12108 intvec tempIntVec1 = 0:lv; 12109 intvec maxDegrees = 0:lv; 12110 intvec tempIntVec2; 12111 int i; int j; 12112 for (i = 1; i<=size(h); i++) 12113 {//going through each monomial in h and finding the degree in each var 12114 tempIntVec2 = lp2iv(h[i]); 12115 if (tempIntVec2 == 0) 12116 { 12117 i++; continue; 12118 } 12119 tempIntVec1 = 0:lv; 12120 for (j=1; j<=size(tempIntVec2); j++) 12121 {//filling in the number of occurrences 12122 tempIntVec1[tempIntVec2[j]] = tempIntVec1[tempIntVec2[j]] + 1; 12123 }//filling in the number of occurrences 12124 for (j = 1; j<=lv; j++) 12125 {//putting the max into maxDegrees 12126 maxDegrees[j] = max(maxDegrees[j], tempIntVec1[j]); 12127 }//putting the max into maxDegrees 12128 }//going through each monomial in h and finding the degree in each var 12129 return(maxDegrees); 12130 }//proc getMaxDegreeVecLetterPlace 12131 12132 static proc test_getMaxDegreeVecLetterPlace() 12133 {//testing getMaxDegreeVecLetterPlace 12134 int result = 1; 12135 ring r = 0,(x,y,z),dp; 12136 int d =4; // degree bound 12137 def R = makeLetterplaceRing(d); 12138 setring R; 12139 //Test 1: 0 12140 intvec expected = 0:3; 12141 intvec obtained = getMaxDegreeVecLetterPlace(0); 12142 if (expected!=obtained) 12143 { 12144 print("Test 1 for getMaxDegreeVecLetterPlace failed."); 12145 print("Expected:\n"); 12146 print(expected); 12147 print("obtained:\n"); 12148 print(obtained); 12149 result = 0; 12150 } 12151 //Test 2: Constant neq 0 12152 expected = 0:3; 12153 obtained = getMaxDegreeVecLetterPlace(3); 12154 if (expected!=obtained) 12155 { 12156 print("Test 2 for getMaxDegreeVecLetterPlace failed."); 12157 print("Expected:\n"); 12158 print(expected); 12159 print("obtained:\n"); 12160 print(obtained); 12161 result = 0; 12162 } 12163 //Test 3: univariate, first variable 12164 expected = 2, 0, 0; 12165 obtained = getMaxDegreeVecLetterPlace(5*x*x + x + 1); 12166 if (expected!=obtained) 12167 { 12168 print("Test 3 for getMaxDegreeVecLetterPlace failed."); 12169 print("Expected:\n"); 12170 print(expected); 12171 print("obtained:\n"); 12172 print(obtained); 12173 result = 0; 12174 } 12175 //Test 4: univariate, another variable 12176 expected = 0, 0, 3; 12177 obtained = getMaxDegreeVecLetterPlace(5*z*z*z + z*z + 1); 12178 if (expected!=obtained) 12179 { 12180 print("Test 4 for getMaxDegreeVecLetterPlace failed."); 12181 print("Expected:\n"); 12182 print(expected); 12183 print("obtained:\n"); 12184 print(obtained); 12185 result = 0; 12186 } 12187 //Test 5: random polynomial 12188 expected = 3, 1, 2; 12189 obtained = getMaxDegreeVecLetterPlace(2*x*y*x*x + 4*y*z*z); 12190 if (expected!=obtained) 12191 { 12192 print("Test 5 for getMaxDegreeVecLetterPlace failed."); 12193 print("Expected:\n"); 12194 print(expected); 12195 print("obtained:\n"); 12196 print(obtained); 12197 result = 0; 12198 } 12199 return(result); 12200 }//testing getMaxDegreeVecLetterPlace 12201 12202 static proc wordsWithMaxAppearance(intvec maxDegInCoordinates, int upToDeg) 12203 "USAGE: wordsWithMaxAppearance(maxDegInCoordinates); 12204 maxDegreeInCoordinates is an intvec. 12205 RETURN: list 12206 PURPOSE: maxDegInCoordinates is a vector representing 12207 the maximum times a variable is allowed to appear in a monomial in 12208 letterplace representation. This function computes all possible words 12209 given this restriction. 12210 ASSUME: maxDegInCoordinates only has non-negative entries 12211 "{//wordsWithMaxAppearance 12212 int p=printlevel-voice+2;//for dbprint 12213 int i; int j; 12214 string dbprintWhitespace = ""; 12215 for (i = 1; i<=voice;i++) 12216 {dbprintWhitespace = dbprintWhitespace + " ";} 12217 list result; 12218 intvec tempMaxDegs; 12219 list recResult; 12220 for (i = 1; i<=size(maxDegInCoordinates); i++) 12221 {//For each coordinate not equal to zero, do a recursive call and concatenate 12222 if (maxDegInCoordinates[i] <= 0) 12223 {//Done with coordinate i 12224 i++; continue; 12225 }//Done with coordinate i 12226 tempMaxDegs = maxDegInCoordinates; 12227 tempMaxDegs[i] = tempMaxDegs[i] - 1; 12228 recResult = wordsWithMaxAppearance(tempMaxDegs, upToDeg); 12229 if (size(recResult) == 0 && upToDeg>=1) 12230 {//Single entry just needs to be there 12231 result = result + list(intvec(i)); 12232 }//Single entry just needs to be there 12233 result = result + recResult; 12234 for (j = 1; j<=size(recResult); j++) 12235 {//concatenate i to all elements in recResult 12236 if (size(recResult[j]) + 1 <= upToDeg) 12237 {//only concatenate if uptodeg is not exceeded 12238 recResult[j] = intvec(i, recResult[j]); 12239 }//only concatenate if uptodeg is not exceeded 12240 }//concatenate i to all elements in recResult 12241 result = result + recResult; 12242 }//For each coordinate not equal to zero, do a recursive call and concatenate 12243 return(delete_duplicates_noteval_and_sort(result)); 12244 }//wordsWithMaxAppearance 12245 12246 static proc test_wordsWithMaxAppearance() 12247 {//test_wordsWithMaxAppearance 12248 int result = 1; 12249 //Test 1: 0 intvec 12250 list expected = list(); 12251 list obtained = wordsWithMaxAppearance(intvec(0), 4); 12252 if (!isListEqual(expected,obtained)) 12253 { 12254 print("Test 1 for wordsWithMaxAppearance failed."); 12255 print("Expected:\n"); 12256 print(expected); 12257 print("obtained:\n"); 12258 print(obtained); 12259 result = 0; 12260 } 12261 //Test 2: 0 multiple entries intvec 12262 expected = list(); 12263 obtained = wordsWithMaxAppearance(0:10, 4); 12264 if (!isListEqual(expected,obtained)) 12265 { 12266 print("Test 2 for wordsWithMaxAppearance failed."); 12267 print("Expected:\n"); 12268 print(expected); 12269 print("obtained:\n"); 12270 print(obtained); 12271 result = 0; 12272 } 12273 //Test 3: Single letter 12274 expected = list(intvec(4)); 12275 obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 1, 0, 0), 4); 12276 if (!isListEqual(expected,obtained)) 12277 { 12278 print("Test 3 for wordsWithMaxAppearance failed."); 12279 print("Expected:\n"); 12280 print(expected); 12281 print("obtained:\n"); 12282 print(obtained); 12283 result = 0; 12284 } 12285 //Test 4: Two letters, one appearance 12286 expected = list(intvec(3), intvec(3,4), intvec(4), intvec(4,3)); 12287 obtained = wordsWithMaxAppearance(intvec(0, 0, 1, 1, 0, 0), 4); 12288 if (!isListEqual(expected,obtained)) 12289 { 12290 print("Test 4 for wordsWithMaxAppearance failed."); 12291 print("Expected:\n"); 12292 print(expected); 12293 print("obtained:\n"); 12294 print(obtained); 12295 result = 0; 12296 } 12297 //Test 5: One letter, degree 2 12298 expected = list(intvec(4), intvec(4,4)); 12299 obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 2, 0, 0), 4); 12300 if (!isListEqual(expected,obtained)) 12301 { 12302 print("Test 5 for wordsWithMaxAppearance failed."); 12303 print("Expected:\n"); 12304 print(expected); 12305 print("obtained:\n"); 12306 print(obtained); 12307 result = 0; 12308 } 12309 //Test 6: random example 12310 expected = list(intvec(1), 12311 intvec(1,4), 12312 intvec(1,4,4), 12313 intvec(4), 12314 intvec(4,1), 12315 intvec(4,1,4), 12316 intvec(4,4), 12317 intvec(4,4,1)); 12318 obtained = wordsWithMaxAppearance(intvec(1, 0, 0, 2, 0, 0), 4); 12319 if (!isListEqual(expected,obtained)) 12320 { 12321 print("Test 6 for wordsWithMaxAppearance failed."); 12322 print("Expected:\n"); 12323 print(expected); 12324 print("obtained:\n"); 12325 print(obtained); 12326 result = 0; 12327 } 12328 return(result); 12329 }//test_wordsWithMaxAppearance 12330 12331 static proc monsSmallerThanLetterPlace(poly e, intvec maxDegInCoordinates, int upToDeg) 12332 "USAGE: monsSmallerThanLetterPlace(e, maxDegInCoordinates); e is a 12333 monomial. 12334 maxDegreeInCoordinates encodes the maximal degree we wish to encounter 12335 in each variable. 12336 RETURN: list 12337 PURPOSE: Computes all monomials in the basering which are degree-wise 12338 smaller than the leading monomial of e. 12339 "{//monsSmallerThanLetterPlace 12340 int p=printlevel-voice+2;//for dbprint 12341 int i; 12342 string dbprintWhitespace = ""; 12343 for (i = 1; i<=voice;i++) 12344 {dbprintWhitespace = dbprintWhitespace + " ";} 12345 list result; 12346 int maxLen = min(sum(maxDegInCoordinates), lpDegBound(basering)); 12347 dbprint(p,dbprintWhitespace + "maxLength: " + string(maxLen)); 12348 list allPossibilities = wordsWithMaxAppearance(maxDegInCoordinates, upToDeg); 12349 dbprint(p,dbprintWhitespace + "words with max appearance: " + string(allPossibilities)); 12350 poly candidate; 12351 intvec candidateMaxDeg; 12352 for (i = 1; i<=size(allPossibilities); i++) 12353 {//checking for monomials with smaller degree than e 12354 candidate = iv2lp(allPossibilities[i]); 12355 dbprint(p,dbprintWhitespace + "Checking candidate: " + string(candidate)); 12356 candidateMaxDeg = getMaxDegreeVecLetterPlace(candidate); 12357 if (candidate < e && candidateMaxDeg <= maxDegInCoordinates) 12358 {//successfully found a candidate 12359 result = insert(result, candidate); 12360 }//successfully found a candidate 12361 }//checking for monomials with smaller degree than e 12362 return(result); 12363 }//monsSmallerThanLetterPlace 12364 12365 static proc test_monsSmallerThanLetterPlace() 12366 {//test_monsSmallerThanLetterPlace 12367 int result = 1; 12368 ring r = 0,(x,y,z,d,w),dp; 12369 int upToDegBound = 10; // degree bound 12370 def R = makeLetterplaceRing(upToDegBound); 12371 setring R; 12372 //Test 1: 0, 0 12373 poly input1 = 0; 12374 intvec input2 = intvec(0,0,0,0,0); 12375 list expected = list(); 12376 list obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound); 12377 if (!isListEqual(expected,obtained)) 12378 { 12379 print("Test 1 for monsSmallerThanLetterPlace failed."); 12380 print("Expected:\n"); 12381 print(expected); 12382 print("obtained:\n"); 12383 print(obtained); 12384 result = 0; 12385 } 12386 //Test 2: 0, nontrivial maxdegree 12387 input1 = 0; 12388 input2 = intvec(0,0,2,1,0); 12389 expected = list(); 12390 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound ); 12391 if (!isListEqual(expected,obtained)) 12392 { 12393 print("Test 2 for monsSmallerThanLetterPlace failed."); 12394 print("Expected:\n"); 12395 print(expected); 12396 print("obtained:\n"); 12397 print(obtained); 12398 result = 0; 12399 } 12400 //Test 3: constant, nontrivial maxdegree 12401 input1 = 7; 12402 input2 = intvec(0,0,2,1,0); 12403 expected = list(); 12404 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound); 12405 if (!isListEqual(expected,obtained)) 12406 { 12407 print("Test 3 for monsSmallerThanLetterPlace failed."); 12408 print("Expected:\n"); 12409 print(expected); 12410 print("obtained:\n"); 12411 print(obtained); 12412 result = 0; 12413 } 12414 //Test 4: single variable smallest, nontrivial maxdegree 12415 input1 = w; 12416 input2 = intvec(0,0,2,1,0); 12417 expected = list(); 12418 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound ); 12419 if (!isListEqual(expected,obtained)) 12420 { 12421 print("Test 4 for monsSmallerThanLetterPlace failed."); 12422 print("Expected:\n"); 12423 print(expected); 12424 print("obtained:\n"); 12425 print(obtained); 12426 result = 0; 12427 } 12428 //Test 5: single variable highest, nontrivial maxdegree 12429 input1 = x; 12430 input2 = intvec(0,0,2,1,0); 12431 expected = list(d, z); 12432 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound); 12433 if (!isListEqual(expected,obtained)) 12434 { 12435 print("Test 5 for monsSmallerThanLetterPlace failed."); 12436 print("Expected:\n"); 12437 print(expected); 12438 print("obtained:\n"); 12439 print(obtained); 12440 result = 0; 12441 } 12442 //Test 6: single variable highest, nontrivial maxdegree 12443 input1 = x; 12444 input2 = intvec(0,0,2,1,0); 12445 expected = list(d, z); 12446 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound ); 12447 if (!isListEqual(expected,obtained)) 12448 { 12449 print("Test 6 for monsSmallerThanLetterPlace failed."); 12450 print("Expected:\n"); 12451 print(expected); 12452 print("obtained:\n"); 12453 print(obtained); 12454 result = 0; 12455 } 12456 //Test 7: nontrivial monomial, nontrivial maxdegree 12457 input1 = z*z*d*d; 12458 input2 = intvec(0,0,2,1,0); 12459 expected = list(d*z*z, 12460 d*z, 12461 d, 12462 z*d*z, 12463 z*d, 12464 z*z*d, 12465 z*z, 12466 z); 12467 obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound); 12468 if (!isListEqual(expected,obtained)) 12469 { 12470 print("Test 7 for monsSmallerThanLetterPlace failed."); 12471 print("Expected:\n"); 12472 print(expected); 12473 print("obtained:\n"); 12474 print(obtained); 12475 result = 0; 12476 } 12477 return(result); 12478 }//test_monsSmallerThanLetterPlace 12479 12480 static proc ncfactor_letterplace_poly_s(poly h) 12481 "USAGE: ncfactor_letterplace_poly_s(h); h is a polynomial in a 12482 letterplace algebra 12483 RETURN: list(list) 12484 PURPOSE: Compute all factorizations of h 12485 THEORY: Implements an ansatz-driven factorization method as outlined 12486 by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite 12487 Factorization Domains\". 12488 ASSUME: 12489 - basering is a Letterplace ring 12490 - basefield is such, that factorize() can factor any univariate and 12491 multivariate commutative polynomial over it. 12492 - h is not a constant or 0. 12493 NOTE: 12494 - Every entry of the output list is a list with factors for one possible factorization. 12495 The first factor is always a constant (1, if no nontrivial constant 12496 could be excluded). 12497 SEE ALSO: ncfactor 12498 "{//proc ncfactor_letterplace_poly_s 12499 int p=printlevel-voice+2;//for dbprint 12500 int i; int j; int k; int l; 12501 string dbprintWhitespace = ""; 12502 for (i = 1; i<=voice;i++) 12503 {dbprintWhitespace = dbprintWhitespace + " ";} 12504 list result; 12505 // Producing the set M of the paper (permutation of the variables in 12506 // the leading monomial) 12507 dbprint(p,dbprintWhitespace + "Generating the set M."); 12508 def r = basering; 12509 intvec maxDegrees = getMaxDegreeVecLetterPlace(h); 12510 dbprint(p,dbprintWhitespace + "The maximum degrees for each var are given by: "+ 12511 string(maxDegrees)); 12512 intvec expVec = lp2iv(leadmonom(h)); 12513 dbprint(p, dbprintWhitespace + "The leading monomial of h is: " + string(expVec)); 12514 list M; 12515 for (i = 1; i<size(expVec); i++) 12516 {//The set M consists of all posssible two-word-combinations of the leading monomial 12517 M = M + list(list(intvec(expVec[1..i]), intvec(expVec[i+1..size(expVec)]))); 12518 } 12519 dbprint(p,dbprintWhitespace+"The set M is:"); 12520 dbprint(p, M); 12521 list list_UpToA; 12522 list list_UpToB; 12523 list tempSringlist = ringlist(r); 12524 list clearSlateRingList = ringlist(r); 12525 clearSlateRingList[2] = list(); 12526 clearSlateRingList[3] = list(); 12527 if (size(clearSlateRingList) == 6) 12528 {//some non-commutative relations defined 12529 clearSlateRingList = delete(clearSlateRingList, 6); 12530 clearSlateRingList = delete(clearSlateRingList, 5); 12531 } 12532 else 12533 {//It is still possible that we have a 5th entry 12534 if (size(clearSlateRingList) == 5) 12535 { 12536 clearSlateRingList = delete(clearSlateRingList, 5); 12537 } 12538 } 12539 intvec tempIntVec; 12540 def S; def W; def W2; 12541 list MEntry; 12542 poly tempA; 12543 poly tempB; 12544 int filterFlag; 12545 int jj = 1; int sizeOfSol = 1; 12546 for (i = 1; i<=size(M); i++) 12547 {//Iterating over all two-combinations in the set M 12548 MEntry = M[i]; 12549 tempA = iv2lp(MEntry[1]); 12550 tempB = iv2lp(MEntry[2]); 12551 dbprint(p,dbprintWhitespace + "The potential leading combination of a is " + string(tempA)); 12552 dbprint(p,dbprintWhitespace + "The potential leading combination of b is " + string(tempB)); 12553 dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than A"); 12554 list_UpToA = monsSmallerThanLetterPlace(leadmonom(tempA), 12555 maxDegrees - getMaxDegreeVecLetterPlace(tempB), 12556 lpDegBound(r)); 12557 dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToA)); 12558 dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than B"); 12559 list_UpToB = monsSmallerThanLetterPlace(leadmonom(tempB), 12560 maxDegrees - getMaxDegreeVecLetterPlace(tempA), 12561 lpDegBound(r)); 12562 dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToB)); 12563 //we need to filter out lm(tempA) and lm(tempB); 12564 for (k = size(list_UpToA); k>0; k--) 12565 {//removing the leading monomial from list_UpToA and invalid parts 12566 if (list_UpToA[k] == leadmonom(tempA)) 12567 {//found it 12568 list_UpToA = delete(list_UpToA,k); 12569 continue; 12570 }//found it 12571 if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToA[k]))) 12572 {//total degree exceeds 12573 list_UpToA = delete(list_UpToA,k); 12574 continue; 12575 }//total degree exceeds 12576 }//removing the leading monomial from list_UpToA and invalid parts 12577 for (k = size(list_UpToB); k>0; k--) 12578 {//removing the leading monomial from list_UpToA 12579 if (list_UpToB[k] == leadmonom(tempB)) 12580 {//found it 12581 list_UpToB = delete(list_UpToB,k); 12582 continue; 12583 }//found it 12584 if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToB[k]))) 12585 {//total degree exceeds 12586 list_UpToB = delete(list_UpToB,k); 12587 continue; 12588 }//total degree exceeds 12589 }//removing the leading monomial from list_UpToA 12590 if (typeof(tempSringlist[1]) == "int") 12591 {//No extra parameters in the original ring 12592 tempSringlist[1] = list(tempSringlist[1],list(), list(list())); 12593 }//No extra parameters in the original ring 12594 for (k = size(list_UpToB)+1; k>=0; k--) 12595 {//fill in b-coefficients as variables 12596 tempSringlist[1][2] = insert(tempSringlist[1][2],"@b("+string(k)+")"); 12597 clearSlateRingList[2] = insert(clearSlateRingList[2],"@b("+string(k)+")"); 12598 }//fill in b-coefficients as variables 12599 for (k = size(list_UpToA); k>=0; k--) 12600 {//fill in a-coefficients as variables 12601 tempSringlist[1][2] = insert(tempSringlist[1][2],"@a("+string(k)+")"); 12602 clearSlateRingList[2] = insert(clearSlateRingList[2], "@a("+string(k)+")"); 12603 }//fill in a-coefficients as variables 12604 tempIntVec = 0; 12605 for(k=1; k<=size(list_UpToA) + size(list_UpToB)+3; k++) 12606 {tempIntVec[k] = 1;} 12607 clearSlateRingList[3] = 12608 list(list("lp",tempIntVec),list("C",intvec(0))); 12609 if (size(tempSringlist[1][3][1]) == 0) 12610 {//No values in there before 12611 tempSringlist[1][3][1] = 12612 list("lp", tempIntVec); 12613 tempSringlist[1][4] = ideal(0); 12614 }//No values in there before 12615 else 12616 {//there were other parameters 12617 tempSringlist[1][3][1][2] = tempSringlist[1][3][1][2], tempIntVec; 12618 }//there were other parameters 12619 attrib(tempSringlist, "isLetterplaceRing", attrib(r,"isLetterplaceRing")); 12620 attrib(tempSringlist, "maxExp", 1); 12621 if (defined(S)) { 12622 kill S; 12623 } 12624 def S = ring(tempSringlist); setring S; 12625 attrib(S, "uptodeg", lpDegBound(r)); 12626 attrib(S, "isLetterplaceRing", attrib(r,"isLetterplaceRing")); 12627 dbprint(p,dbprintWhitespace+"Done generating ring S:"); 12628 dbprint(p,dbprintWhitespace+string(S)); 12629 dbprint(p,dbprintWhitespace+"Generate the ansatz."); 12630 dbprint(p,dbprintWhitespace+"The new ring is: " + string(basering)); 12631 setring(S); 12632 poly h = imap(r, h); 12633 poly a = imap(r,tempA); 12634 poly b = imap(r,tempB); 12635 if (!defined(list_UpToA)) 12636 {list list_UpToA = imap(r,list_UpToA);} 12637 if (!defined(list_UpToB)) 12638 {list list_UpToB = imap(r,list_UpToB);} 12639 b = b*par(size(list_UpToA)+size(list_UpToB)+3); 12640 for (k = size(list_UpToB); k>0; k--) 12641 {b = b + par(size(list_UpToA)+2+k)*list_UpToB[k];} 12642 b = b + par(size(list_UpToA) + 2); 12643 dbprint(p,dbprintWhitespace + "The ansatz for b is " + string(b)); 12644 for (k = size(list_UpToA); k>0; k--) 12645 {a = a + par(k+1)*list_UpToA[k];} 12646 a = a + par(1); 12647 dbprint(p,dbprintWhitespace + "The ansatz for a is " + string(a)); 12648 poly ansatzPoly = a*b - h; 12649 dbprint(p,dbprintWhitespace + "The ansatzpoly is " + string(ansatzPoly)); 12650 ideal listOfRelations = coeffs(ansatzPoly, var(1)); 12651 for (k = 2;k<=nvars(r);k++) 12652 {listOfRelations = coeffs(listOfRelations,var(k));} 12653 setring(r); 12654 W = ring(clearSlateRingList); // comm ring of coeffs of the ansatz 12655 W2 = W+r; // first coeffs, then orig letterplace vars 12656 setring(W); 12657 ideal listOfRelations = imap(S, listOfRelations); 12658 option(redSB); 12659 option(redTail); 12660 dbprint(p,dbprintWhitespace + "Calculating the solutions of:"); 12661 dbprint(p,listOfRelations); 12662 if (!defined(sol)) 12663 { 12664 def sol = facstd(listOfRelations); 12665 } 12666 else 12667 { 12668 sol = facstd(listOfRelations); 12669 } 12670 dbprint(p,dbprintWhitespace + "Filtering the solutions that are " + 12671 "not in the base-field."); 12672 for(k = 1; k <=size(sol);k++) 12673 {//filtering what is not in the ground-field 12674 filterFlag = 0; 12675 for (l=1; l<=size(sol[k]); l++) 12676 { 12677 if ((deg(sol[k][l])>1) or ((sol[k][l]/leadcoef(sol[k][l])==1))) 12678 {//Not in the ground field 12679 filterFlag = 1; 12680 break; 12681 }//Not in the ground field 12682 } 12683 if (filterFlag or (vdim(std(sol[k]))<0)) 12684 {//In this case, we can delete that whole entry and move on 12685 sol= delete(sol,k); 12686 continue; 12687 }//In this case, we can delete that whole entry and move on 12688 }//filtering what is not in the ground-field 12689 dbprint(p,dbprintWhitespace + "Solutions for the coefficients are:"); 12690 dbprint(p,sol); 12691 setring S; 12692 ideal a_coef; jj=1; 12693 while (a[jj]!=0) 12694 { 12695 a_coef[jj]=leadcoef(a[jj]); 12696 jj++; 12697 } 12698 ideal b_coef; 12699 jj=1; 12700 while (b[jj]!=0) 12701 { 12702 b_coef[jj]=leadcoef(b[jj]); 12703 jj++; 12704 } 12705 setring W; //W = ring of coeffs_variables 12706 ideal a_coef = imap(S, a_coef); 12707 ideal b_coef = imap(S, b_coef); 12708 sizeOfSol = size(sol); 12709 if (!defined(tempResultCoeffs)) { 12710 list tempResultCoeffs; 12711 } 12712 tempResultCoeffs = list(); 12713 for (k=1; k<=sizeOfSol; k++) 12714 { 12715 sol[k] = std(sol[k]); 12716 tempResultCoeffs = insert(tempResultCoeffs, list( 12717 NF(a_coef, sol[k]), // element-wise 12718 NF(b_coef, sol[k]))); // element-wise 12719 } 12720 setring S; 12721 if(!defined(tempResultCoeffs)) { 12722 list tempResultCoeffs = imap(W, tempResultCoeffs); 12723 } 12724 if (!(defined(tempResult))) 12725 {list tempResult;} 12726 poly ared; 12727 poly bred; 12728 for (k = 1; k <= size(tempResultCoeffs); k++) 12729 {//Creating the resulting polynomials with the respective coeffs. 12730 jj=1; 12731 ared=0; 12732 bred=0; 12733 while (a[jj]!=0) 12734 {//Going through all monomials of a 12735 ared= ared+leadcoef(tempResultCoeffs[k][1][jj])*leadmonom(a[jj]); 12736 jj++; 12737 }//Going through all monomials of a 12738 jj=1; 12739 while (b[jj]!=0) 12740 {//Going through all monomials of b 12741 bred= bred+leadcoef(tempResultCoeffs[k][2][jj])*leadmonom(b[jj]); 12742 jj++; 12743 }//Going through all monomials of b 12744 tempResult = insert(tempResult,list(ared,bred)); 12745 }//Creating the resulting polynomials with the respective coeffs. 12746 setring(r); 12747 if (!defined(tempResult)) 12748 {def tempResult = imap(S,tempResult);} 12749 for (k=1; k<= size(tempResult);k++) 12750 { 12751 result = insert(result,tempResult[k]); 12752 } 12753 kill tempResult; 12754 clearSlateRingList[2] = list(); 12755 clearSlateRingList[3] = list(); 12756 tempSringlist = ringlist(r); 12757 }//Iterating over all two-combinations in the set M 12758 if(size(result)==0) 12759 { 12760 return (list(list(h))); 12761 } 12762 return(delete_duplicates_noteval_and_sort(result)); 12763 }//proc ncfactor_letterplace_poly_s 12764 12765 12766 static proc test_ncfactor_letterplace_poly_s() 12767 "Tests the basic functionality." 12768 {//proc test_ncfactor_letterplace_poly_s() 12769 int result = 1; 12770 ring r = 0,(x,y,z),dp; 12771 int d =4; // degree bound 12772 def R = makeLetterplaceRing(d); 12773 setring R; 12774 //TEST 1: power of 2 12775 poly f1 = (x + y)*(x + y); 12776 list obtained = ncfactor_letterplace_poly_s(f1); 12777 list expected = sortFactorizations( 12778 list( 12779 list(x + y, x + y) 12780 )); 12781 if (!isListEqual(expected,obtained)) 12782 { 12783 print("Test 1 for ncfactor_letterplace_poly_s failed."); 12784 print("Expected:\n"); 12785 print(expected); 12786 print("obtained:\n"); 12787 print(obtained); 12788 result = 0; 12789 } 12790 //TEST 2: Monomial 12791 f1 = x*z; 12792 obtained = ncfactor_letterplace_poly_s(f1); 12793 expected = sortFactorizations( 12794 list( 12795 list(x, z) 12796 )); 12797 if (!isListEqual(expected,obtained)) 12798 { 12799 print("Test 2 for ncfactor_letterplace_poly_s failed."); 12800 print("Expected:\n"); 12801 print(expected); 12802 print("obtained:\n"); 12803 print(obtained); 12804 result = 0; 12805 } 12806 //TEST 3: Generic product with all variables 12807 f1 = (x*y + z*x)*(x+ z+ y); 12808 obtained = ncfactor_letterplace_poly_s(f1); 12809 expected = sortFactorizations( 12810 list( 12811 list( 12812 x*y + z*x, 12813 x+ z+ y)) 12814 ); 12815 if (!isListEqual(expected,obtained)) 12816 { 12817 print("Test 3 for ncfactor_letterplace_poly_s failed."); 12818 print("Expected:\n"); 12819 print(expected); 12820 print("obtained:\n"); 12821 print(obtained); 12822 result = 0; 12823 } 12824 //TEST 4: More than one factorization 12825 f1 = x*y*x + x; 12826 obtained = ncfactor_letterplace_poly_s(f1); 12827 expected = sortFactorizations( 12828 list( 12829 list(x, y*x + 1), 12830 list(x*y + 1, x)) 12831 ); 12832 if (!isListEqual(expected,obtained)) 12833 { 12834 print("Test 4 for ncfactor_letterplace_poly_s failed."); 12835 print("Expected:\n"); 12836 print(expected); 12837 print("obtained:\n"); 12838 print(obtained); 12839 result = 0; 12840 } 12841 return (result); 12842 }//proc test_ncfactor_letterplace_poly_s() 12843 12844 static proc ncfactor_without_opt_letterplace(poly h) 12845 "USAGE: ncfactor_without_opt_letterplace(h); h is a polynomial in a 12846 letterplace ring over a field k. 12847 RETURN: list(list) 12848 PURPOSE: Compute all factorizations of h, without making any 12849 sanity-checks 12850 THEORY: Implements an ansatz-driven factorization method as outlined 12851 by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite 12852 Factorization Domains\". 12853 ASSUME: 12854 - the basering is a Letterplace ring. 12855 - k is a ring, such that factorize can factor any univariate and 12856 multivariate commutative polynomial over k. 12857 - There exists at least one variable in the ring. 12858 - h is not a constant or 0. 12859 NOTE: 12860 - Every entry of the output list is a list with factors for one possible factorization. 12861 The first factor is always a constant (1, if no nontrivial constant 12862 could be excluded). 12863 SEE ALSO: facWeyl, facSubWeyl, testNCfac, ncfactor 12864 "{//ncfactor_without_opt_letterplace 12865 int p = printlevel-voice+2; 12866 int i; int j; int k; int l; 12867 string dbprintWhitespace = ""; 12868 for (i = 1; i<=voice;i++) 12869 {dbprintWhitespace = dbprintWhitespace + " ";} 12870 number commonCoefficient = content(h); 12871 poly hath = h/commonCoefficient; 12872 dbprint(p,dbprintWhitespace + "Calculating all possibilities of h as 12873 a combination of two factors."); 12874 list result = ncfactor_letterplace_poly_s(hath); 12875 result = delete_duplicates_noteval_and_sort(result); 12876 dbprint(p,dbprintWhitespace + "Done. The result is:"); 12877 dbprint(p,result); 12878 dbprint(p,dbprintWhitespace+"Recursively check factors for 12879 irreducibility"); 12880 list recursivetemp; 12881 int changedSomething; 12882 for(i = 1; i<=size(result);i++) 12883 {//recursively factorize factors 12884 if(size(result[i])>1) 12885 {//Nontrivial factorization 12886 for (j=1;j<=size(result[i]);j++) 12887 {//Factorize every factor 12888 recursivetemp = ncfactor_letterplace_poly_s(result[i][j]); 12889 recursivetemp = delete_duplicates_noteval(recursivetemp); 12890 changedSomething = 0; 12891 for(k=1; k<=size(recursivetemp);k++) 12892 {//insert factorized factors 12893 if(size(recursivetemp[k])>1) 12894 {//nontrivial 12895 changedSomething = 1; 12896 result = insert(result,result[i],i); 12897 for(l = size(recursivetemp[k]);l>=1;l--) 12898 { 12899 result[i+1] = insert(result[i+1],recursivetemp[k][l],j); 12900 } 12901 result[i+1] = delete(result[i+1],j); 12902 }//nontrivial 12903 }//insert factorized factors 12904 if (changedSomething) 12905 {break;} 12906 }//Factorize every factor 12907 if(changedSomething) 12908 { 12909 result = delete(result,i); 12910 continue; 12911 } 12912 }//Nontrivial factorization 12913 }//recursively factorize factors 12914 dbprint(p,dbprintWhitespace +" Done"); 12915 dbprint(p,dbprintWhitespace + "Removing duplicates from the list"); 12916 result = delete_duplicates_noteval_and_sort(result); 12917 for (i = 1; i<=size(result);i++) 12918 {//Putting the content everywhere 12919 result[i] = insert(result[i],commonCoefficient); 12920 }//Putting the content everywhere 12921 result = normalizeFactors(result); 12922 result = delete_duplicates_noteval_and_sort(result); 12923 dbprint(p,dbprintWhitespace +" Done"); 12924 return(result); 12925 }//ncfactor_without_opt_letterplace 12926 12927 static proc test_ncfactor_without_opt_letterplace() 12928 "Tests the basic functionality." 12929 {//test_ncfactor_without_opt_letterplace 12930 int result = 1; 12931 ring r = 0,(x,y,z),dp; 12932 int d =4; // degree bound 12933 def R = makeLetterplaceRing(d); 12934 setring R; 12935 //TEST 1: power of 2 12936 poly f1 = 4*(x + y)*(x + y); 12937 list obtained = ncfactor_without_opt_letterplace(f1); 12938 list expected = sortFactorizations( 12939 list( 12940 list(number(4), x + y, x + y) 12941 )); 12942 if (!isListEqual(expected,obtained)) 12943 { 12944 print("Test 1 for ncfactor_without_opt_letterplace failed."); 12945 print("Expected:\n"); 12946 print(expected); 12947 print("obtained:\n"); 12948 print(obtained); 12949 result = 0; 12950 } 12951 //TEST 2: Monomial 12952 f1 = 11*x*z; 12953 obtained = ncfactor_without_opt_letterplace(f1); 12954 expected = sortFactorizations( 12955 list( 12956 list(number(11), x, z) 12957 )); 12958 if (!isListEqual(expected,obtained)) 12959 { 12960 print("Test 2 for ncfactor_without_opt_letterplace failed."); 12961 print("Expected:\n"); 12962 print(expected); 12963 print("obtained:\n"); 12964 print(obtained); 12965 result = 0; 12966 } 12967 //TEST 3: Generic product with all variables 12968 f1 = (2*x*y + 4*z*x)*(x+z+y); 12969 obtained = ncfactor_without_opt_letterplace(f1); 12970 expected = sortFactorizations( 12971 list( 12972 list(number(2), x*y + 2*z*x, x+z+y) 12973 )); 12974 if (!isListEqual(expected,obtained)) 12975 { 12976 print("Test 3 for ncfactor_without_opt_letterplace failed."); 12977 print("Expected:\n"); 12978 print(expected); 12979 print("obtained:\n"); 12980 print(obtained); 12981 result = 0; 12982 } 12983 //TEST 4: More than one factorization 12984 f1 = 6*x*y*x + 9*x; 12985 obtained = ncfactor_without_opt_letterplace(f1); 12986 expected = sortFactorizations( 12987 list( 12988 list(number(3), x, 2*y*x + 3), 12989 list(number(3), 2*x*y + 3, x) 12990 )); 12991 if (!isListEqual(expected,obtained)) 12992 { 12993 print("Test 4 for ncfactor_without_opt_letterplace failed."); 12994 print("Expected:\n"); 12995 print(expected); 12996 print("obtained:\n"); 12997 print(obtained); 12998 result = 0; 12999 } 13000 //Test 5: At least one recursive call 13001 f1 = f1*(x + y); 13002 obtained = ncfactor_without_opt_letterplace(f1); 13003 expected = sortFactorizations( 13004 list( 13005 list(number(3), x, 2*y*x + 3, x + y), 13006 list(number(3), 2*x*y + 3, x, x + y) 13007 )); 13008 if (!isListEqual(expected,obtained)) 13009 { 13010 print("Test 5 for ncfactor_without_opt_letterplace failed."); 13011 print("Expected:\n"); 13012 print(expected); 13013 print("obtained:\n"); 13014 print(obtained); 13015 result = 0; 13016 } 13017 return (result); 13018 }//test_ncfactor_without_opt_letterplace 13019 13020 11986 13021 //================================================== 11987 13022 // EASY EXAMPLES FOR WEYL ALGEBRA … … 12217 13252 12218 13253 /* recent bufgixes (2) Jan 2018; exs from Viktor and Johannes Hoffmann 12219 // Original bug: found only (x+d)^2*x as fa ktorization13254 // Original bug: found only (x+d)^2*x as factorization 12220 13255 LIB "nctools.lib"; 12221 13256 ring r = 0,(x,d),dp; … … 12225 13260 12226 13261 //====================================================================== 12227 // Hard examples not yet c alculatable in feasible amount of time13262 // Hard examples not yet computable in feasible amount of time 12228 13263 //====================================================================== 12229 13264 -
Singular/LIB/nctools.lib
r1bd400 r5bccba 1396 1396 1397 1397 /////////////////////////////////////////////////////////////////////////////// 1398 proc rightStd(def I) 1398 proc rightStd(def I)// just an alias for compatibility 1399 1399 "USAGE: rightStd(I); I an ideal/ module 1400 1400 PURPOSE: compute a right Groebner basis of I … … 1403 1403 " 1404 1404 { 1405 def A = basering; 1406 def Aopp = opposite(A); 1407 setring Aopp; 1408 def Iopp = oppose(A,I); 1409 def Jopp = groebner(Iopp); 1410 setring A; 1411 def J = oppose(Aopp,Jopp); 1412 return(J); 1405 return(rightstd(I)); 1413 1406 } 1414 1407 example … … 1771 1764 RETURN: ring 1772 1765 PURPOSE: create a copy of a given ring equipped with the 1773 @*elimination ordering for module components @code{(c,<)}1766 elimination ordering for module components @code{(c,<)} 1774 1767 NOTE: usually the list argument contains a ring to work with 1775 1768 EXAMPLE: example makeModElimRing; shows an example -
Singular/checklibs.c
r1bd400 r5bccba 7 7 #define LINE_LEN 200 8 8 #define RECOMMENDED_LEN 100 9 VARFILE *f;10 VARint trailing_spaces=0;11 VARint tabs=0;12 VARint verylong_lines=0;13 VARint lines=0;14 VARunsigned char buf[LINE_LEN];15 VARint proc_cnt=0;16 VARunsigned char *proc[NUM_PROC];17 VARunsigned char have_doc[NUM_PROC];18 VARunsigned char have_example[NUM_PROC];19 VARunsigned char proc_found[NUM_PROC];20 VARint non_ascii=0;21 VARint non_ascii_line=0;22 VARint star_nl=0;23 VARint footer=0;24 VARint header=0;25 VARint crlf=0;26 VARint proc_help_lines=0;27 VARint proc_help_texinfo=0;9 FILE *f; 10 int trailing_spaces=0; 11 int tabs=0; 12 int verylong_lines=0; 13 int lines=0; 14 unsigned char buf[LINE_LEN]; 15 int proc_cnt=0; 16 unsigned char *proc[NUM_PROC]; 17 unsigned char have_doc[NUM_PROC]; 18 unsigned char have_example[NUM_PROC]; 19 unsigned char proc_found[NUM_PROC]; 20 int non_ascii=0; 21 int non_ascii_line=0; 22 int star_nl=0; 23 int footer=0; 24 int header=0; 25 int crlf=0; 26 int proc_help_lines=0; 27 int proc_help_texinfo=0; 28 28 29 29 void get_next() -
Singular/dyn_modules/Makefile.am
r1bd400 r5bccba 1 1 ACLOCAL_AMFLAGS = -I ../m4 2 2 3 SUBDIRS=staticdemo bigintm subsets syzextra pyobject customstd gfanlib python gitfan polymake singmathic Order interval cohomo free gb3 SUBDIRS=staticdemo bigintm subsets syzextra pyobject customstd gfanlib python gitfan polymake singmathic Order interval cohomo freealgebra -
Singular/dyn_modules/freealgebra/Makefile.am
r1bd400 r5bccba 1 1 ACLOCAL_AMFLAGS = -I ../../m4 2 2 3 if SI_BUILTIN_FREE GB4 noinst_LTLIBRARIES=free gb.la3 if SI_BUILTIN_FREEALGEBRA 4 noinst_LTLIBRARIES=freealgebra.la 5 5 P_PROCS_MODULE_LDFLAGS = -module 6 6 P_PROCS_CPPFLAGS_COMMON = -DSTATIC_VERSION 7 7 else 8 module_LTLIBRARIES=free gb.la8 module_LTLIBRARIES=freealgebra.la 9 9 moduledir = $(libexecdir)/singular/MOD 10 10 P_PROCS_CPPFLAGS_COMMON = -DDYNAMIC_VERSION … … 18 18 19 19 20 free gb_la_CPPFLAGS = ${MYINCLUDES} ${P_PROCS_CPPFLAGS_COMMON}21 free gb_la_LDFLAGS = ${AM_LDFLAGS} ${P_PROCS_MODULE_LDFLAGS} $(SINGULAR_LDFLAGS)22 SOURCES = free gb.cc23 free gb_la_SOURCES = $(SOURCES)20 freealgebra_la_CPPFLAGS = ${MYINCLUDES} ${P_PROCS_CPPFLAGS_COMMON} 21 freealgebra_la_LDFLAGS = ${AM_LDFLAGS} ${P_PROCS_MODULE_LDFLAGS} $(SINGULAR_LDFLAGS) 22 SOURCES = freealgebra.cc 23 freealgebra_la_SOURCES = $(SOURCES) 24 24 -
Singular/dyn_modules/freealgebra/freealgebra.cc
r1bd400 r5bccba 2 2 3 3 #ifdef HAVE_SHIFTBBA 4 static BOOLEAN free gb(leftv res, leftv args)4 static BOOLEAN freeAlgebra(leftv res, leftv args) 5 5 { 6 6 const short t1[]={2,RING_CMD,INT_CMD}; … … 80 80 } 81 81 82 /*==================== divide-test for freeGB =================*/83 82 static BOOLEAN lpLmDivides(leftv res, leftv h) 84 83 { … … 112 111 } 113 112 114 /*==================== get var for freeGB ====================*/115 113 static BOOLEAN lpVarAt(leftv res, leftv h) 116 114 { … … 130 128 //------------------------------------------------------------------------ 131 129 // initialisation of the module 132 extern "C" int SI_MOD_INIT(free gb)(SModulFunctions* p)130 extern "C" int SI_MOD_INIT(freealgebra)(SModulFunctions* p) 133 131 { 134 132 #ifdef HAVE_SHIFTBBA 135 p->iiAddCproc("free gb.so","freeAlgebra",FALSE,freegb);136 p->iiAddCproc("free gb.so","lpLmDivides",FALSE,lpLmDivides);137 p->iiAddCproc("free gb.so","lpVarAt",FALSE,lpVarAt);138 p->iiAddCproc("free gb.so","stest",TRUE,stest);139 p->iiAddCproc("free gb.so","btest",TRUE,btest);133 p->iiAddCproc("freealgebra.so","freeAlgebra",FALSE,freeAlgebra); 134 p->iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides); 135 p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt); 136 p->iiAddCproc("freealgebra.so","stest",TRUE,stest); 137 p->iiAddCproc("freealgebra.so","btest",TRUE,btest); 140 138 #endif 141 139 return (MAX_TOK); -
Singular/iparith.cc
r1bd400 r5bccba 5116 5116 } 5117 5117 #endif 5118 5118 #ifdef HAVE_SHIFTBBA // do not place above jjSTD in this file because we need to reference it 5119 static BOOLEAN jjRIGHTSTD(leftv res, leftv v) 5120 { 5121 if (rIsLPRing(currRing)) 5122 { 5123 if (rField_is_numeric(currRing)) 5124 WarnS("groebner base computations with inexact coefficients can not be trusted due to rounding errors"); 5125 ideal result; 5126 ideal v_id=(ideal)v->Data(); 5127 /* intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD); */ 5128 /* tHomog hom=testHomog; */ 5129 /* if (w!=NULL) */ 5130 /* { */ 5131 /* if (!idTestHomModule(v_id,currRing->qideal,w)) */ 5132 /* { */ 5133 /* WarnS("wrong weights"); */ 5134 /* w=NULL; */ 5135 /* } */ 5136 /* else */ 5137 /* { */ 5138 /* hom=isHomog; */ 5139 /* w=ivCopy(w); */ 5140 /* } */ 5141 /* } */ 5142 /* result=kStd(v_id,currRing->qideal,hom,&w); */ 5143 result = rightgb(v_id, currRing->qideal); 5144 idSkipZeroes(result); 5145 res->data = (char *)result; 5146 if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD); 5147 /* if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD); */ 5148 return FALSE; 5149 } 5150 else if (rIsPluralRing(currRing)) 5151 { 5152 ideal I=(ideal)v->Data(); 5153 5154 ring A = currRing; 5155 ring Aopp = rOpposite(A); 5156 currRing = Aopp; 5157 ideal Iopp = idOppose(A, I, Aopp); 5158 ideal Jopp = kStd(Iopp,currRing->qideal,testHomog,NULL); 5159 currRing = A; 5160 ideal J = idOppose(Aopp, Jopp, A); 5161 5162 id_Delete(&Iopp, Aopp); 5163 id_Delete(&Jopp, Aopp); 5164 rDelete(Aopp); 5165 5166 idSkipZeroes(J); 5167 res->data = (char *)J; 5168 if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD); 5169 return FALSE; 5170 } 5171 else 5172 { 5173 return jjSTD(res, v); 5174 } 5175 } 5176 #endif 5119 5177 static BOOLEAN jjTYPEOF(leftv res, leftv v) 5120 5178 { -
Singular/table.h
r1bd400 r5bccba 245 245 ,{D(jjDUMMY), RESOLUTION_CMD, RESOLUTION_CMD, RESOLUTION_CMD, ALLOW_PLURAL |ALLOW_RING} 246 246 ,{D(jjRESTART), RESTART_CMD, NONE, INT_CMD, ALLOW_NC |ALLOW_RING} 247 #ifdef HAVE_SHIFTBBA 248 ,{D(jjRIGHTSTD), RIGHTSTD_CMD, IDEAL_CMD, IDEAL_CMD , ALLOW_NC |NO_RING} 249 #endif 247 250 ,{D(jjRINGLIST), RINGLIST_CMD, LIST_CMD, RING_CMD , ALLOW_NC |ALLOW_RING} 248 251 ,{D(jjRINGLIST_C), RING_LIST_CMD, LIST_CMD, CRING_CMD , ALLOW_NC |ALLOW_RING} … … 1168 1171 { "return", 0, RETURN , RETURN}, 1169 1172 { "RETURN", 0, END_GRAMMAR , RETURN}, 1173 #ifdef HAVE_SHIFTBBA 1174 { "rightstd", 0, RIGHTSTD_CMD , CMD_1}, 1175 #endif /* HAVE_PLURAL */ 1170 1176 { "ring", 0, RING_CMD , RING_CMD}, 1171 1177 { "ringlist", 0, RINGLIST_CMD , CMD_1}, -
Singular/tok.h
r1bd400 r5bccba 169 169 RESTART_CMD, 170 170 RESULTANT_CMD, 171 RIGHTSTD_CMD, 171 172 RINGLIST_CMD, 172 173 RING_LIST_CMD, -
configure.ac
r1bd400 r5bccba 249 249 AC_CONFIG_FILES([Singular/dyn_modules/staticdemo/Makefile]) 250 250 AC_CONFIG_FILES([Singular/dyn_modules/subsets/Makefile]) 251 AC_CONFIG_FILES([Singular/dyn_modules/free gb/Makefile])251 AC_CONFIG_FILES([Singular/dyn_modules/freealgebra/Makefile]) 252 252 AC_CONFIG_FILES([Singular/dyn_modules/gitfan/Makefile]) 253 253 AC_CONFIG_FILES([Singular/dyn_modules/interval/Makefile]) -
doc/Makefile.bsp
rdfa15b r5bccba 134 134 info: singular.hlp 135 135 136 singular.hlp: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex 136 singular.hlp: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex 137 137 - ${MAKEINFO} --no-split singular.tex 138 138 … … 140 140 dvi: manual.dvi usercard.dvi 141 141 142 singular.dvi: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex 142 singular.dvi: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex 143 143 tex singular.tex 144 144 texindex singular.cp … … 147 147 tex singular.tex 148 148 149 singular.pdf: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex 149 singular.pdf: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex 150 150 ${TEXI2PDF} singular.tex 151 151 152 manual.dvi: ${MANUAL_FILES} manual.tex s-plural.tex s-plulibs.tex 152 manual.dvi: ${MANUAL_FILES} manual.tex s-plural.tex s-plulibs.tex s-letterplace.tex 153 153 tex manual.tex 154 154 texindex manual.cp … … 174 174 sed -e "s/BR_PLURAL_BR/(plural)/g" <plulibs.tex >s-plulibs.tex 175 175 176 s-letterplace.tex: letterplace.tex 177 sed -e "s/BR_LETTERPLACE_BR/(letterplace)/g" <letterplace.tex >s-letterplace.tex 178 176 179 # postscript stuff 177 180 ps: dvi manual.ps usercard.ps … … 270 273 # 271 274 html: ${TMP_DIR} ${HTML_SUBDIR}/${HTML_MANUAL_TOP} ${IMAGES_HTML} $(STANDALONE_TEXI_FILES) 272 ${HTML_SUBDIR}/${HTML_MANUAL_TOP}: ${TEXI2HTML_INIT} ${TEXI2HTML} singular.tex s-plural.tex 275 ${HTML_SUBDIR}/${HTML_MANUAL_TOP}: ${TEXI2HTML_INIT} ${TEXI2HTML} singular.tex s-plural.tex s-letterplace.tex 273 276 ${PERL} ${TEXI2HTML} ${TEXI2HTML_OPTS} -prefix ${HTML_MANUAL_PREFIX} \ 274 277 -top_file ${HTML_MANUAL_TOP} singular.tex … … 384 387 /bin/rm -f *.fn *.fns *.ky *.kys *.log *.pg *.pgs *.toc *.tp 385 388 /bin/rm -f *.tps *.vr *.vrs *.dvi *.ps 386 /bin/rm -f s-plural.tex 389 /bin/rm -f s-plural.tex s-plulibs.tex s-letterplace.tex 387 390 /bin/rm -f singular.hlp manual.hlp ${DOC2TEX_FILES} singular.idx 388 391 /bin/rm -f manual.hlp -
kernel/GBEngine/kstd1.cc
r1bd400 r5bccba 2093 2093 2094 2094 #ifdef HAVE_SHIFTBBA 2095 if(rIsLPRing(currRing)) return freegb(F );2095 if(rIsLPRing(currRing)) return freegb(F, Q); 2096 2096 #endif 2097 2097 -
kernel/GBEngine/kstd1.h
r1bd400 r5bccba 41 41 ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** mw, intvec *hilb=NULL, 42 42 int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE); 43 44 ideal freegb(ideal F, ideal Q); 45 ideal rightgb(ideal F, ideal Q); 43 46 44 47 /* the following global data are defined in kutil.cc */ -
kernel/GBEngine/kstd2.cc
r1bd400 r5bccba 4459 4459 4460 4460 4461 ideal freegb(ideal F )4461 ideal freegb(ideal F, ideal Q) 4462 4462 { 4463 4463 assume(rIsLPRing(currRing)); 4464 4464 assume(idIsInV(F)); 4465 ideal RS = kStdShift(F, NULL, testHomog, NULL);4465 ideal RS = kStdShift(F, Q, testHomog, NULL); 4466 4466 idSkipZeroes(RS); // is this even necessary? 4467 4467 assume(idIsInV(RS)); -
kernel/GBEngine/kutil.h
r1bd400 r5bccba 861 861 int redFirstShift (LObject* h,kStrategy strat); // ok 862 862 863 ideal freegb(ideal F);864 ideal rightgb(ideal F, ideal Q);865 866 863 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat); 867 864 // test syz strategy: // will be removed soon -
kernel/ideals.h
r1bd400 r5bccba 140 140 ideal idLiftStd (ideal h1, matrix *m, tHomog h=testHomog, ideal *syz=NULL, GbVariant a=GbDefault); 141 141 142 ideal idLift (ideal mod, ideal su mod,ideal * rest=NULL,142 ideal idLift (ideal mod, ideal submod,ideal * rest=NULL, 143 143 BOOLEAN goodShape=FALSE, BOOLEAN isSB=TRUE,BOOLEAN divide=FALSE, 144 144 matrix *unit=NULL, GbVariant a=GbDefault); -
kernel/polys.cc
r1bd400 r5bccba 7 7 #include "kernel/ideals.h" 8 8 #include "polys/clapsing.h" 9 #include "polys/clapconv.h" 9 10 10 11 /// Widely used global variable which specifies the current polynomial ring for Singular interpreter and legacy implementatins. … … 50 51 if(p_GetComp(p,r)==0) 51 52 { 52 if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN) 53 if((rFieldType(r)==n_transExt) 54 &&(convSingTrP(p,r)) 55 &&(convSingTrP(q,r))) 56 { 57 poly res=singclap_pdivide(p, q, r); 58 p_Delete(&p,r); 59 p_Delete(&q,r); 60 return res; 61 } 62 else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN) 53 63 &&(!rField_is_Ring(r))) 54 64 { … … 71 81 SI_RESTORE_OPT1(save_opt); 72 82 if (r!=save_ring) rChangeCurrRing(save_ring); 73 if (idIs0(R)) 74 { 75 matrix T = id_Module2formatedMatrix(m,1,1,r); 76 p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL; 77 id_Delete((ideal *)&T,r); 78 } 79 else p=NULL; 83 matrix T = id_Module2formatedMatrix(m,1,1,r); 84 p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL; 85 id_Delete((ideal *)&T,r); 80 86 id_Delete((ideal *)&U,r); 81 87 id_Delete(&R,r); … … 109 115 if (I->m[i]!=NULL) 110 116 { 111 if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN) 117 if((rFieldType(r)==n_transExt) 118 &&(convSingTrP(I->m[i],r)) 119 &&(convSingTrP(q,r))) 120 { 121 h=singclap_pdivide(I->m[i],q,r); 122 } 123 else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN) 112 124 &&(!rField_is_Ring(r))) 113 125 h=singclap_pdivide(I->m[i],q,r); … … 164 176 return p_DivideM(p,q,r); 165 177 } 166 return FALSE; 178 return NULL; 179 } 180 181 poly p_DivRem(poly p, poly q, poly &rest, const ring r) 182 { 183 assume(q!=NULL); 184 rest=NULL; 185 if (q==NULL) 186 { 187 WerrorS("div. by 0"); 188 return NULL; 189 } 190 if (p==NULL) 191 { 192 p_Delete(&q,r); 193 return NULL; 194 } 195 if (rIsLPRing(r)) 196 { 197 WerrorS("not implemented for letterplace rings"); 198 return NULL; 199 } 200 if(p_GetComp(p,r)==0) 201 { 202 if((rFieldType(r)==n_transExt) 203 &&(convSingTrP(p,r)) 204 &&(convSingTrP(q,r))) 205 { 206 poly res=singclap_pdivide(p, q, r); 207 rest=singclap_pmod(p,q,r); 208 p_Delete(&p,r); 209 p_Delete(&q,r); 210 return res; 211 } 212 else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN) 213 &&(!rField_is_Ring(r))) 214 { 215 poly res=singclap_pdivide(p, q, r); 216 rest=singclap_pmod(p,q,r); 217 p_Delete(&p,r); 218 p_Delete(&q,r); 219 return res; 220 } 221 else 222 { 223 ideal vi=idInit(1,1); vi->m[0]=q; 224 ideal ui=idInit(1,1); ui->m[0]=p; 225 ideal R; matrix U; 226 ring save_ring=currRing; 227 if (r!=currRing) rChangeCurrRing(r); 228 int save_opt; 229 SI_SAVE_OPT1(save_opt); 230 si_opt_1 &= ~(Sy_bit(OPT_PROT)); 231 ideal m = idLift(vi,ui,&R, FALSE,TRUE,TRUE,&U); 232 SI_RESTORE_OPT1(save_opt); 233 if (r!=save_ring) rChangeCurrRing(save_ring); 234 matrix T = id_Module2formatedMatrix(m,1,1,r); 235 p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL; 236 id_Delete((ideal *)&T,r); 237 T = id_Module2formatedMatrix(R,1,1,r); 238 rest=MATELEM(T,1,1); MATELEM(T,1,1)=NULL; 239 id_Delete((ideal *)&T,r); 240 id_Delete((ideal *)&U,r); 241 id_Delete(&R,r); 242 //vi->m[0]=NULL; ui->m[0]=NULL; 243 id_Delete(&vi,r); 244 id_Delete(&ui,r); 245 return p; 246 } 247 } 248 return NULL; 167 249 } 168 250 -
kernel/polys.h
r1bd400 r5bccba 160 160 #endif 161 161 162 /// polynomial division , ignoring the rest162 /// polynomial division a/b, ignoring the rest 163 163 /// via singclap_pdivide resp. idLift 164 164 /// destroyes a,b 165 165 poly p_Divide(poly a, poly b, const ring r); 166 poly p_DivRem(poly a, poly b, poly &rest, const ring r); /*julia*/ 166 167 167 168 /// polynomial gcd -
libpolys/polys/clapconv.cc
r1bd400 r5bccba 290 290 while ( p!=NULL ) 291 291 { 292 n_Normalize(p_GetCoeff(p, r), r->cf);292 //n_Normalize(p_GetCoeff(p, r), r->cf); 293 293 294 294 // test if denominator is constant 295 if (! p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing) && !errorreported)295 if (!errorreported && !p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing)) 296 296 WerrorS("conversion error: denominator!= 1"); 297 297 … … 316 316 } 317 317 return result; 318 } 319 320 BOOLEAN convSingTrP(poly p, const ring r ) 321 { 322 while ( p!=NULL ) 323 { 324 n_Normalize(p_GetCoeff(p, r), r->cf); 325 326 // test if denominator is constant 327 if (!p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing)) 328 return FALSE; 329 pIter(p); 330 } 331 return TRUE; 318 332 } 319 333 -
libpolys/polys/clapconv.h
r1bd400 r5bccba 30 30 31 31 CanonicalForm convSingTrPFactoryP ( poly p, const ring r ); 32 BOOLEAN convSingTrP(poly p, const ring r ); 32 33 poly convFactoryPSingTrP ( const CanonicalForm & f, const ring r ); 33 34 -
libpolys/polys/clapsing.cc
r1bd400 r5bccba 84 84 else 85 85 { 86 convSingTrP(f,r); 87 convSingTrP(g,r); 86 88 CanonicalForm F( convSingTrPFactoryP( f,r ) ), G( convSingTrPFactoryP( g,r ) ); 87 89 res= convFactoryPSingTrP( gcd( F, G ),r ); -
libpolys/polys/monomials/ring.cc
r1bd400 r5bccba 5130 5130 int lb = rBlocks(r) - 2; 5131 5131 return (r->order[lb] == ringorder_c || r->order[lb] == ringorder_C); 5132 }5133 5134 n_coeffType rFieldType(ring r)5135 {5136 return (r->cf->type);5137 if (rField_is_Zp(r)) return n_Zp;5138 if (rField_is_Q(r)) return n_Q;5139 if (rField_is_R(r)) return n_R;5140 if (rField_is_GF(r)) return n_GF;5141 if (rField_is_long_R(r)) return n_long_R;5142 if (rField_is_Zp_a(r)) return getCoeffType(r->cf);5143 if (rField_is_Q_a(r)) return getCoeffType(r->cf);5144 if (rField_is_long_C(r)) return n_long_C;5145 if (rField_is_Z(r)) return n_Z;5146 if (rField_is_Zn(r)) return n_Zn;5147 if (rField_is_Ring_PtoM(r)) return n_Znm;5148 if (rField_is_Ring_2toM(r)) return n_Z2m;5149 5150 return n_unknown;5151 5132 } 5152 5133 -
libpolys/polys/monomials/ring.h
r1bd400 r5bccba 548 548 { assume(r != NULL); assume(r->cf != NULL); return nCoeff_has_simple_Alloc(r->cf); } 549 549 550 n_coeffType rFieldType(const ring r); 550 /// the type of the coefficient filed of r (n_Zp, n_Q, etc) 551 static inline n_coeffType rFieldType(const ring r) { return (r->cf->type); } 551 552 552 553 /// this needs to be called whenever a new ring is created: new fields -
m4/options.m4
r1bd400 r5bccba 321 321 bi_staticdemo=false 322 322 bi_subsets=false 323 bi_free gb=false323 bi_freealgebra=false 324 324 bi_syzextra=false 325 325 bi_pyobject=false … … 357 357 staticdemo ) bi_staticdemo=true;; 358 358 subsets ) bi_subsets=true;; 359 free gb ) bi_freegb=true;;359 freealgebra ) bi_freealgebra=true;; 360 360 syzextra ) bi_syzextra=true ;; 361 361 pyobject ) bi_pyobject=true ;; … … 396 396 AM_CONDITIONAL([SI_BUILTIN_STATICDEMO], [test x$bi_staticdemo = xtrue]) 397 397 AM_CONDITIONAL([SI_BUILTIN_SUBSETS], [test x$bi_subsets = xtrue]) 398 AM_CONDITIONAL([SI_BUILTIN_FREE GB], [test x$bi_freegb= xtrue])398 AM_CONDITIONAL([SI_BUILTIN_FREEALGEBRA], [test x$bi_freealgebra = xtrue]) 399 399 AM_CONDITIONAL([SI_BUILTIN_SYZEXTRA], [test x$bi_syzextra = xtrue]) 400 400 AM_CONDITIONAL([SI_BUILTIN_PYOBJECT], [test x$bi_pyobject = xtrue])
Note: See TracChangeset
for help on using the changeset viewer.