Changeset 73c222 in git
 Timestamp:
 Jul 31, 2013, 4:59:25 PM (11 years ago)
 Branches:
 (u'fiekerDuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '4188d308699580d975efd0f6cca8dcb41c396f70')
 Children:
 091b25018851d6b7049240bf5eb739710e97cb1a
 Parents:
 c43ab090c8ddfd806239f1a22762fa741b0864e7
 gitauthor:
 Martin Lee <martinlee84@web.de>20130731 16:59:25+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20130830 13:48:23+02:00
 Location:
 factory
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

factory/facAbsFact.cc
rc43ab0 r73c222 35 35 TIMING_DEFINE_PRINT(fac_Qa_factorize) 36 36 TIMING_DEFINE_PRINT(fac_evalpoint) 37 38 CFAFList uniAbsFactorize (const CanonicalForm& F) 39 { 40 CFFList rationalFactors= factorize (F); 41 CFFListIterator i= rationalFactors; 42 i++; 43 Variable alpha; 44 CFAFList result; 45 CFFList QaFactors; 46 CFFListIterator iter; 47 for (; i.hasItem(); i++) 48 { 49 if (degree (i.getItem().factor()) == 1) 50 { 51 result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp())); 52 continue; 53 } 54 alpha= rootOf (i.getItem().factor()); 55 QaFactors= factorize (i.getItem().factor(), alpha); 56 iter= QaFactors; 57 if (iter.getItem().factor().inCoeffDomain()) 58 iter++; 59 for (;iter.hasItem(); iter++) 60 { 61 if (degree (iter.getItem().factor()) == 1) 62 { 63 result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha), 64 i.getItem().exp())); 65 break; 66 } 67 } 68 } 69 result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1)); 70 return result; 71 } 72 73 74 /// absolute factorization of bivariate poly over Q 75 /// 76 /// @return absFactorize returns a list whose entries contain three entities: 77 /// an absolute irreducible factor, an irreducible univariate polynomial 78 /// that defines the minimal field extension over which the irreducible 79 /// factor is defined and the multiplicity of the absolute irreducible 80 /// factor 81 CFAFList absBiFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q 82 ) 83 { 84 //TODO handle homogeneous input 85 ASSERT (getNumVars (G) <= 2, "expected bivariate input"); 86 ASSERT (getCharacteristic() == 0, "expected poly over Q"); 87 88 CFMap N; 89 CanonicalForm F= compress (G, N); 90 bool isRat= isOn (SW_RATIONAL); 91 if (isRat) 92 F *= bCommonDen (F); 93 94 Off (SW_RATIONAL); 95 F /= icontent (F); 96 if (isRat) 97 On (SW_RATIONAL); 98 99 CanonicalForm contentX= content (F, 1); 100 CanonicalForm contentY= content (F, 2); 101 F /= (contentX*contentY); 102 CFAFList contentXFactors, contentYFactors; 103 contentXFactors= uniAbsFactorize (contentX); 104 contentYFactors= uniAbsFactorize (contentY); 105 106 if (contentXFactors.getFirst().factor().inCoeffDomain()) 107 contentXFactors.removeFirst(); 108 if (contentYFactors.getFirst().factor().inCoeffDomain()) 109 contentYFactors.removeFirst(); 110 if (F.inCoeffDomain()) 111 { 112 CFAFList result; 113 for (CFAFListIterator i= contentXFactors; i.hasItem(); i++) 114 result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(), 115 i.getItem().exp())); 116 for (CFAFListIterator i= contentYFactors; i.hasItem(); i++) 117 result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(), 118 i.getItem().exp())); 119 normalize (result); 120 result.insert (CFAFactor (Lc (G), 1, 1)); 121 return result; 122 } 123 CFFList rationalFactors= factorize (F); 124 125 CFAFList result, resultBuf; 126 127 CFAFListIterator iter; 128 CFFListIterator i= rationalFactors; 129 i++; 130 for (; i.hasItem(); i++) 131 { 132 resultBuf= absBiFactorizeMain (i.getItem().factor()); 133 for (iter= resultBuf; iter.hasItem(); iter++) 134 iter.getItem()= CFAFactor (iter.getItem().factor(), 135 iter.getItem().minpoly(), i.getItem().exp()); 136 result= Union (result, resultBuf); 137 } 138 139 for (CFAFListIterator i= result; i.hasItem(); i++) 140 i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(), 141 i.getItem().exp()); 142 for (CFAFListIterator i= contentXFactors; i.hasItem(); i++) 143 result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(), 144 i.getItem().exp())); 145 for (CFAFListIterator i= contentYFactors; i.hasItem(); i++) 146 result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(), 147 i.getItem().exp())); 148 normalize (result); 149 result.insert (CFAFactor (Lc(G), 1, 1)); 150 151 return result; 152 } 37 153 38 154 //TODO optimize choice of p > choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting) … … 104 220 105 221 //G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed 106 CFAFList abs FactorizeMain (const CanonicalForm& G)222 CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full) 107 223 { 108 224 CanonicalForm F= bCommonDen (G)*G; … … 519 635 (F, earlySuccess, earlyFactors, degs, liftBound, 520 636 uniFactors, dummy, evaluation, b, den); 637 521 638 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 522 639 … … 549 666 for (CFListIterator i= biFactors; i.hasItem(); i++) 550 667 { 668 if (full) 669 result.append (CFAFactor (i.getItem(), getMipo (alpha), 1)); 670 551 671 if (totaldegree (i.getItem()) == minTdeg) 552 672 { 553 result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1)); 673 if (!full) 674 result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1)); 554 675 found= true; 555 break; 676 677 if (!full) 678 break; 556 679 } 557 680 } 
factory/facAbsFact.h
rc43ab0 r73c222 29 29 /// factor is defined and the multiplicity of the absolute irreducible 30 30 /// factor 31 CFAFList absFactorizeMain (const CanonicalForm& F ///<[in] s.a. 32 ); 31 CFAFList absBiFactorizeMain (const CanonicalForm& F, ///<[in] s.a. 32 bool full= false 33 ); 33 34 #endif 34 35 … … 49 50 /// factor is defined and the multiplicity of the absolute irreducible 50 51 /// factor 51 static inline52 52 CFAFList uniAbsFactorize (const CanonicalForm& F ///<[in] univariate poly over Q 53 ) 54 { 55 CFFList rationalFactors= factorize (F); 56 CFFListIterator i= rationalFactors; 57 i++; 58 Variable alpha; 59 CFAFList result; 60 CFFList QaFactors; 61 CFFListIterator iter; 62 for (; i.hasItem(); i++) 63 { 64 if (degree (i.getItem().factor()) == 1) 65 { 66 result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp())); 67 continue; 68 } 69 alpha= rootOf (i.getItem().factor()); 70 QaFactors= factorize (i.getItem().factor(), alpha); 71 iter= QaFactors; 72 if (iter.getItem().factor().inCoeffDomain()) 73 iter++; 74 for (;iter.hasItem(); iter++) 75 { 76 if (degree (iter.getItem().factor()) == 1) 77 { 78 result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha), 79 i.getItem().exp())); 80 break; 81 } 82 } 83 } 84 result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1)); 85 return result; 86 } 53 ); 87 54 88 55 /*BEGINPUBLIC*/ 89 56 90 57 #ifdef HAVE_NTL 91 CFAFList abs Factorize (const CanonicalForm& G);58 CFAFList absBiFactorize (const CanonicalForm& G); 92 59 #endif 93 60
Note: See TracChangeset
for help on using the changeset viewer.