Changeset 327efa2 in git
 Timestamp:
 Sep 14, 2011, 2:38:38 PM (12 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
 Children:
 09723d9937585aae280f53597c2c61b2b3e6304a
 Parents:
 725e6002e0b07ad1474e14f72296c0c85a47ae4d
 Location:
 factory
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

factory/facFactorize.cc
r725e600 r327efa2 202 202 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++) 203 203 { 204 if (iter.getItem().factor().inCoeffDomain()) 205 continue; 204 206 iter.getItem()= CFFactor (iter.getItem().factor()/ 205 207 Lc (iter.getItem().factor()), … … 212 214 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++) 213 215 { 216 if (iter.getItem().factor().inCoeffDomain()) 217 continue; 214 218 iter.getItem()= CFFactor (iter.getItem().factor()/ 215 219 Lc (iter.getItem().factor()), … … 388 392 factors= bufFactors; 389 393 390 int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;391 392 int* liftBounds= liftingBounds (sqrfPartF, liftBound);393 394 394 395 bufFactors= factors; 395 factors.insert (LC (evalSqrfPartF.getFirst(), 1)); 396 CFMatrix M= CFMatrix (liftBound, factors.length()  1); 397 CFArray Pi; 398 CFList diophant; 399 henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, 400 false); 401 402 if (sqrfPartF.level() > 2) 403 factors= henselLift (evalSqrfPartF, factors, liftBounds, 404 sqrfPartF.level()  1, false); 405 406 CFList MOD; 407 for (int i= 0; i < sqrfPartF.level()  1; i++) 408 MOD.append (power (Variable (i + 2), liftBounds [i])); 409 410 CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(), 411 factors, MOD); 396 397 if (factors.length() > 1) 398 { 399 CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1); 400 401 CFArray leadingCoeffs= CFArray (factors.length()); 402 for (int i= 0; i < factors.length(); i++) 403 leadingCoeffs[i]= LC1; 404 for (CFListIterator i= factors; i.hasItem(); i++) 405 i.getItem() *= LC1 (0,2)/Lc (i.getItem()); 406 factors.insert (1); 407 408 CanonicalForm 409 newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length()  2); 410 411 int liftBound= degree (newSqrfPartF,2) + 1; 412 413 CFMatrix M= CFMatrix (liftBound, factors.length()  1); 414 CFArray Pi; 415 CFList diophant; 416 henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M, 417 leadingCoeffs, false); 418 419 if (sqrfPartF.level() > 2) 420 { 421 int* liftBounds= new int [sqrfPartF.level()  1]; 422 liftBounds [0]= liftBound; 423 bool noOneToOne= false; 424 CFList *leadingCoeffs2= new CFList [sqrfPartF.level()2]; 425 LC1= LC (evalSqrfPartF.getLast(), 1); 426 CFList LCs; 427 for (int i= 0; i < factors.length(); i++) 428 LCs.append (LC1); 429 leadingCoeffs2 [sqrfPartF.level()  3]= LCs; 430 for (int i= sqrfPartF.level()  1; i > 2; i) 431 { 432 for (CFListIterator j= LCs; j.hasItem(); j++) 433 j.getItem()= j.getItem() (0, i + 1); 434 leadingCoeffs2 [i  3]= LCs; 435 } 436 sqrfPartF= sqrfPartF*power (LC1, factors.length()1); 437 438 int liftBoundsLength= sqrfPartF.level()  1; 439 for (int i= 1; i < liftBoundsLength; i++) 440 liftBounds [i]= degree (sqrfPartF, i + 2) + 1; 441 evalSqrfPartF= evaluateAtZero (sqrfPartF); 442 evalSqrfPartF.removeFirst(); 443 factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2, 444 diophant, Pi, liftBounds, sqrfPartF.level()  1, noOneToOne); 445 delete [] leadingCoeffs2; 446 delete [] liftBounds; 447 } 448 } 449 else 450 factors= evalSqrfPartF.getLast(); 451 452 CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors); 412 453 413 454 CFList result; 
factory/facFqFactorize.cc
r725e600 r327efa2 1375 1375 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++) 1376 1376 { 1377 if (iter.getItem().factor().inCoeffDomain()) 1378 continue; 1377 1379 iter.getItem()= CFFactor (iter.getItem().factor()/ 1378 1380 Lc (iter.getItem().factor()), … … 1385 1387 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++) 1386 1388 { 1389 if (iter.getItem().factor().inCoeffDomain()) 1390 continue; 1387 1391 iter.getItem()= CFFactor (iter.getItem().factor()/ 1388 1392 Lc (iter.getItem().factor()), … … 1562 1566 factors= bufFactors; 1563 1567 1564 int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;1565 1566 int* liftBounds= liftingBounds (sqrfPartF, liftBound);1567 1568 1568 bufFactors= factors; 1569 factors.insert (LC (evalSqrfPartF.getFirst(), 1)); 1570 CFMatrix M= CFMatrix (liftBound, factors.length()  1); 1571 CFArray Pi; 1572 CFList diophant; 1573 henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, false); 1574 1575 if (sqrfPartF.level() > 2) 1576 factors= henselLift (evalSqrfPartF, factors, liftBounds, 1577 sqrfPartF.level()  1, false); 1578 1579 CFList MOD; 1580 for (int i= 0; i < sqrfPartF.level()  1; i++) 1581 MOD.append (power (Variable (i + 2), liftBounds [i])); 1582 1583 CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(), 1584 factors, MOD); 1569 1570 if (factors.length() > 1) 1571 { 1572 CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1); 1573 1574 CFArray leadingCoeffs= CFArray (factors.length()); 1575 for (int i= 0; i < factors.length(); i++) 1576 leadingCoeffs[i]= LC1; 1577 for (CFListIterator i= factors; i.hasItem(); i++) 1578 i.getItem() *= LC1 (0,2)/Lc (i.getItem()); 1579 factors.insert (1); 1580 1581 CanonicalForm 1582 newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length()  2); 1583 1584 int liftBound= degree (newSqrfPartF,2) + 1; 1585 1586 CFMatrix M= CFMatrix (liftBound, factors.length()  1); 1587 CFArray Pi; 1588 CFList diophant; 1589 henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M, 1590 leadingCoeffs, false); 1591 1592 if (sqrfPartF.level() > 2) 1593 { 1594 int* liftBounds= new int [sqrfPartF.level()  1]; 1595 liftBounds [0]= liftBound; 1596 bool noOneToOne= false; 1597 CFList *leadingCoeffs2= new CFList [sqrfPartF.level()2]; 1598 LC1= LC (evalSqrfPartF.getLast(), 1); 1599 CFList LCs; 1600 for (int i= 0; i < factors.length(); i++) 1601 LCs.append (LC1); 1602 leadingCoeffs2 [sqrfPartF.level()  3]= LCs; 1603 for (int i= sqrfPartF.level()  1; i > 2; i) 1604 { 1605 for (CFListIterator j= LCs; j.hasItem(); j++) 1606 j.getItem()= j.getItem() (0, i + 1); 1607 leadingCoeffs2 [i  3]= LCs; 1608 } 1609 sqrfPartF= sqrfPartF*power (LC1, factors.length()1); 1610 1611 int liftBoundsLength= sqrfPartF.level()  1; 1612 for (int i= 1; i < liftBoundsLength; i++) 1613 liftBounds [i]= degree (sqrfPartF, i + 2) + 1; 1614 evalSqrfPartF= evaluateAtZero (sqrfPartF); 1615 evalSqrfPartF.removeFirst(); 1616 factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2, 1617 diophant, Pi, liftBounds, sqrfPartF.level()  1, noOneToOne); 1618 delete [] leadingCoeffs2; 1619 delete [] liftBounds; 1620 } 1621 } 1622 else 1623 factors= evalSqrfPartF.getLast(); 1624 1625 CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors); 1585 1626 1586 1627 CFList result; 
factory/facHensel.cc
r725e600 r327efa2 2797 2797 2798 2798 Pi [0] += tmp[0]*xToJ*F.mvar(); 2799 2800 int degPi, degBuf; 2801 for (int l= 1; l < factors.length()  1; l++) 2802 { 2803 degPi= degree (Pi [l  1], x); 2804 degBuf= degree (bufFactors[l + 1], x); 2805 if (degPi > 0 && degBuf > 0) 2806 { 2807 M (j + 1, l + 1)= mulNTL (Pi [l  1] [j], bufFactors[l + 1] [j]); 2808 if (j + 2 <= M.rows()) 2809 M (j + 2, l + 1)= mulNTL (Pi [l  1][j + 1], bufFactors[l + 1] [j + 1]); 2810 } 2811 2812 if (degPi > 0 && degBuf > 0) 2813 uIZeroJ= mulNTL (Pi[l 1] [0], buf[l + 1]) + 2814 mulNTL (uIZeroJ, bufFactors[l+1] [0]); 2815 else if (degPi > 0) 2816 uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1]); 2817 else if (degBuf > 0) 2818 uIZeroJ= mulNTL (Pi[l  1], buf[1]); 2819 else 2820 uIZeroJ= 0; 2821 2822 Pi [l] += xToJ*uIZeroJ; 2823 2824 one= bufFactors [l + 1]; 2825 two= Pi [l  1]; 2826 if (degBuf > 0 && degPi > 0) 2827 { 2828 while (one.hasTerms() && one.exp() > j) one++; 2829 while (two.hasTerms() && two.exp() > j) two++; 2830 for (k= 1; k <= (int) ceil (j/2.0); k++) 2831 { 2832 if (k != j  k + 1) 2833 { 2834 if ((one.hasTerms() && one.exp() == j  k + 1) && 2835 (two.hasTerms() && two.exp() == j  k + 1)) 2836 { 2837 tmp[l] += mulNTL ((bufFactors[l + 1] [k] + one.coeff()), 2838 (Pi[l  1] [k] + two.coeff()))  M (k + 1, l + 1)  2839 M (j  k + 2, l + 1); 2840 one++; 2841 two++; 2842 } 2843 else if (one.hasTerms() && one.exp() == j  k + 1) 2844 { 2845 tmp[l] += mulNTL ((bufFactors[l + 1] [k] + one.coeff()), 2846 Pi[l  1] [k])  M (k + 1, l + 1); 2847 one++; 2848 } 2849 else if (two.hasTerms() && two.exp() == j  k + 1) 2850 { 2851 tmp[l] += mulNTL (bufFactors[l + 1] [k], 2852 (Pi[l  1] [k] + two.coeff()))  M (k + 1, l + 1); 2853 two++; 2854 } 2855 } 2856 else 2857 tmp[l] += M (k + 1, l + 1); 2858 } 2859 } 2860 2861 if (degPi >= j + 1 && degBuf >= j + 1) 2862 { 2863 if (j + 2 <= M.rows()) 2864 tmp [l] += mulNTL ((Pi [l  1] [j + 1]+ Pi [l  1] [0]), 2865 (bufFactors [l + 1] [j + 1] + bufFactors [l + 1] [0]) 2866 )  M(1,l+1)  M (j + 2,l+1); 2867 } 2868 else if (degPi >= j + 1) 2869 { 2870 if (degBuf > 0) 2871 tmp[l] += mulNTL (Pi [l  1] [j+1], bufFactors [l + 1] [0]); 2872 else 2873 tmp[l] += mulNTL (Pi [l  1] [j+1], bufFactors [l + 1]); 2874 } 2875 else if (degBuf >= j + 1) 2876 { 2877 if (degPi > 0) 2878 tmp[l] += mulNTL (Pi [l  1] [0], bufFactors [l + 1] [j + 1]); 2879 else 2880 tmp[l] += mulNTL (Pi [l  1], bufFactors [l + 1] [j + 1]); 2881 } 2882 2883 Pi[l] += tmp[l]*xToJ*F.mvar(); 2884 } 2799 2885 return; 2800 2886 } … … 2809 2895 CFList bufFactors2= factors; 2810 2896 bufFactors2.removeFirst(); 2811 CanonicalForm s,t; 2812 extgcd (bufFactors2.getFirst(), bufFactors2.getLast(), s, t); 2813 diophant= CFList(); 2814 diophant.append (t); 2815 diophant.append (s); 2897 diophant= diophantine (F[0], bufFactors2); 2816 2898 DEBOUTLN (cerr, "diophant= " << diophant); 2817 2899 … … 2846 2928 } 2847 2929 2930 for (i= 1; i < Pi.size(); i++) 2931 { 2932 if (degree (Pi[i1], x) > 0 && degree (bufFactors [i+1], x) > 0) 2933 { 2934 M (1,i+1)= mulNTL (Pi[i1] [0], bufFactors[i+1] [0]); 2935 Pi [i]= M (1,i+1) + (mulNTL (Pi[i1] [1], bufFactors[i+1] [0]) + 2936 mulNTL (Pi[i1] [0], bufFactors [i+1] [1]))*x; 2937 } 2938 else if (degree (Pi[i1], x) > 0) 2939 { 2940 M (1,i+1)= mulNTL (Pi[i1] [0], bufFactors [i+1]); 2941 Pi [i]= M(1,i+1) + mulNTL (Pi[i1] [1], bufFactors[i+1])*x; 2942 } 2943 else if (degree (bufFactors[i+1], x) > 0) 2944 { 2945 M (1,i+1)= mulNTL (Pi[i1], bufFactors [i+1] [0]); 2946 Pi [i]= M (1,i+1) + mulNTL (Pi[i1], bufFactors[i+1] [1])*x; 2947 } 2948 else 2949 { 2950 M (1,i+1)= mulNTL (Pi [i1], bufFactors [i+1]); 2951 Pi [i]= M (1,i+1); 2952 } 2953 } 2954 2848 2955 for (i= 1; i < l; i++) 2849 2956 henselStep122 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs); … … 2854 2961 return; 2855 2962 } 2963 2856 2964 2857 2965 /// solve \f$ E=sum_{i= 1}^{r}{\sigma_{i}prod_{j=1, j\neq i}^{r}{f_{i}}}\f$
Note: See TracChangeset
for help on using the changeset viewer.