1 /*****************************************************************************\ 2 * Computer Algebra System SINGULAR 3 \*****************************************************************************/ 4 /** @file facBivar.h 5 * 6 * bivariate factorization over Q(a) 7 * 8 * @author Martin Lee 9 * 10 **/ 11 /*****************************************************************************/ 12 13 #ifndef FAC_BIVAR_H 14 #define FAC_BIVAR_H 15 16 // #include "config.h" 17 18 #include "cf_assert.h" 19 #include "timing.h" 20 21 #include "facFqBivarUtil.h" 22 #include "DegreePattern.h" 23 #include "cf_util.h" 24 #include "facFqSquarefree.h" 25 #include "cf_map.h" 26 #include "cf_algorithm.h" 27 #include "cfNewtonPolygon.h" 28 #include "fac_util.h" 29 #include "cf_algorithm.h" 30 31 TIMING_DEFINE_PRINT(fac_bi_sqrf) 32 TIMING_DEFINE_PRINT(fac_bi_factor_sqrf) 33 34 /// @return @a biFactorize returns a list of factors of F. If F is not monic 35 /// its leading coefficient is not outputted. 36 CFList 37 biFactorize (const CanonicalForm& F, ///< [in] a sqrfree bivariate poly 38 const Variable& v ///< [in] some algebraic variable 39 ); 40 41 /// factorize a squarefree bivariate polynomial over \f$ Q(\alpha) \f$. 42 /// 43 /// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first 44 /// element is the leading coefficient. 45 inline 46 CFList 47 ratBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly 48 const Variable& v= Variable (1) ///< [in] algebraic variable 49 ) 50 { 51 CFMap N; 52 CanonicalForm F= compress (G, N); 53 CanonicalForm contentX= content (F, 1); //erwarte hier primitiven input: primitiv über Z bzw. Z[a] 54 CanonicalForm contentY= content (F, 2); 55 F /= (contentX*contentY); 56 CFFList contentXFactors, contentYFactors; 57 if (v.level() != 1) 58 { 59 contentXFactors= factorize (contentX, v); 60 contentYFactors= factorize (contentY, v); 61 } 62 else 63 { 64 contentXFactors= factorize (contentX); 65 contentYFactors= factorize (contentY); 66 } 67 if (contentXFactors.getFirst().factor().inCoeffDomain()) 68 contentXFactors.removeFirst(); 69 if (contentYFactors.getFirst().factor().inCoeffDomain()) 70 contentYFactors.removeFirst(); 71 if (F.inCoeffDomain()) 72 { 73 CFList result; 74 for (CFFListIterator i= contentXFactors; i.hasItem(); i++) 75 result.append (N (i.getItem().factor())); 76 for (CFFListIterator i= contentYFactors; i.hasItem(); i++) 77 result.append (N (i.getItem().factor())); 78 if (isOn (SW_RATIONAL)) 79 { 80 normalize (result); 81 result.insert (Lc (G)); 82 } 83 return result; 84 } 85 86 mpz_t * M=new mpz_t [4]; 87 mpz_init (M[0]); 88 mpz_init (M[1]); 89 mpz_init (M[2]); 90 mpz_init (M[3]); 91 92 mpz_t * S=new mpz_t [2]; 93 mpz_init (S[0]); 94 mpz_init (S[1]); 95 96 F= compress (F, M, S); 97 CFList result= biFactorize (F, v); 98 for (CFListIterator i= result; i.hasItem(); i++) 99 i.getItem()= N (decompress (i.getItem(), M, S)); 100 for (CFFListIterator i= contentXFactors; i.hasItem(); i++) 101 result.append (N(i.getItem().factor())); 102 for (CFFListIterator i= contentYFactors; i.hasItem(); i++) 103 result.append (N (i.getItem().factor())); 104 if (isOn (SW_RATIONAL)) 105 { 106 normalize (result); 107 result.insert (Lc (G)); 108 } 109 110 mpz_clear (M[0]); 111 mpz_clear (M[1]); 112 mpz_clear (M[2]); 113 mpz_clear (M[3]); 114 delete [] M; 115 116 mpz_clear (S[0]); 117 mpz_clear (S[1]); 118 delete [] S; 119 120 return result; 121 } 122 123 /// factorize a bivariate polynomial over \f$ Q(\alpha) \f$ 124 /// 125 /// @return @a ratBiFactorize returns a list of monic factors with 126 /// multiplicity, the first element is the leading coefficient. 127 inline 128 CFFList 129 ratBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly 130 const Variable& v= Variable (1), ///< [in] algebraic variable 131 bool substCheck= true ///< [in] enables substitute check 132 ) 133 { 134 CFMap N; 135 CanonicalForm F= compress (G, N); 136 137 if (substCheck) 138 { 139 bool foundOne= false; 140 int * substDegree= new int [F.level()]; 141 for (int i= 1; i <= F.level(); i++) 142 { 143 substDegree[i-1]= substituteCheck (F, Variable (i)); 144 if (substDegree [i-1] > 1) 145 { 146 foundOne= true; 147 subst (F, F, substDegree[i-1], Variable (i)); 148 } 149 } 150 if (foundOne) 151 { 152 CFFList result= ratBiFactorize (F, v, false); 153 CFFList newResult, tmp; 154 CanonicalForm tmp2; 155 newResult.insert (result.getFirst()); 156 result.removeFirst(); 157 for (CFFListIterator i= result; i.hasItem(); i++) 158 { 159 tmp2= i.getItem().factor(); 160 for (int j= 1; j <= F.level(); j++) 161 { 162 if (substDegree[j-1] > 1) 163 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j)); 164 } 165 tmp= ratBiFactorize (tmp2, v, false); 166 tmp.removeFirst(); 167 for (CFFListIterator j= tmp; j.hasItem(); j++) 168 newResult.append (CFFactor (j.getItem().factor(), 169 j.getItem().exp()*i.getItem().exp())); 170 } 171 decompress (newResult, N); 172 delete [] substDegree; 173 return newResult; 174 } 175 delete [] substDegree; 176 } 177 178 CanonicalForm LcF= Lc (F); 179 CanonicalForm contentX= content (F, 1); 180 CanonicalForm contentY= content (F, 2); 181 F /= (contentX*contentY); 182 CFFList contentXFactors, contentYFactors; 183 if (v.level() != 1) 184 { 185 contentXFactors= factorize (contentX, v); 186 contentYFactors= factorize (contentY, v); 187 } 188 else 189 { 190 contentXFactors= factorize (contentX); 191 contentYFactors= factorize (contentY); 192 } 193 if (contentXFactors.getFirst().factor().inCoeffDomain()) 194 contentXFactors.removeFirst(); 195 if (contentYFactors.getFirst().factor().inCoeffDomain()) 196 contentYFactors.removeFirst(); 197 decompress (contentXFactors, N); 198 decompress (contentYFactors, N); 199 CFFList result, resultRoot; 200 if (F.inCoeffDomain()) 201 { 202 result= Union (contentXFactors, contentYFactors); 203 if (isOn (SW_RATIONAL)) 204 { 205 normalize (result); 206 if (v.level() == 1) 207 { 208 for (CFFListIterator i= result; i.hasItem(); i++) 209 { 210 LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp()); 211 i.getItem()= CFFactor (i.getItem().factor()* 212 bCommonDen(i.getItem().factor()), i.getItem().exp()); 213 } 214 } 215 result.insert (CFFactor (LcF, 1)); 216 } 217 return result; 218 } 219 220 mpz_t * M=new mpz_t [4]; 221 mpz_init (M[0]); 222 mpz_init (M[1]); 223 mpz_init (M[2]); 224 mpz_init (M[3]); 225 226 mpz_t * S=new mpz_t [2]; 227 mpz_init (S[0]); 228 mpz_init (S[1]); 229 230 F= compress (F, M, S); 231 TIMING_START (fac_bi_sqrf); 232 CFFList sqrfFactors= sqrFree (F); 233 TIMING_END_AND_PRINT (fac_bi_sqrf, 234 "time for bivariate sqrf factors over Q: "); 235 for (CFFListIterator i= sqrfFactors; i.hasItem(); i++) 236 { 237 TIMING_START (fac_bi_factor_sqrf); 238 CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v); 239 TIMING_END_AND_PRINT (fac_bi_factor_sqrf, 240 "time to factor bivariate sqrf factors over Q: "); 241 for (CFListIterator j= tmp; j.hasItem(); j++) 242 { 243 if (j.getItem().inCoeffDomain()) continue; 244 result.append (CFFactor (N (decompress (j.getItem(), M, S)), 245 i.getItem().exp())); 246 } 247 } 248 result= Union (result, contentXFactors); 249 result= Union (result, contentYFactors); 250 if (isOn (SW_RATIONAL)) 251 { 252 normalize (result); 253 if (v.level() == 1) 254 { 255 for (CFFListIterator i= result; i.hasItem(); i++) 256 { 257 LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp()); 258 i.getItem()= CFFactor (i.getItem().factor()* 259 bCommonDen(i.getItem().factor()), i.getItem().exp()); 260 } 261 } 262 result.insert (CFFactor (LcF, 1)); 263 } 264 265 mpz_clear (M[0]); 266 mpz_clear (M[1]); 267 mpz_clear (M[2]); 268 mpz_clear (M[3]); 269 delete [] M; 270 271 mpz_clear (S[0]); 272 mpz_clear (S[1]); 273 delete [] S; 274 275 return result; 276 } 277 278 /// convert a CFFList to a CFList by dropping the multiplicity 279 CFList conv (const CFFList& L ///< [in] a CFFList 280 ); 281 282 /// compute p^k larger than the bound on the coefficients of a factor of @a f 283 /// over Q (mipo) 284 modpk 285 coeffBound (const CanonicalForm & f, ///< [in] poly over Z[a] 286 int p, ///< [in] some positive integer 287 const CanonicalForm& mipo ///< [in] minimal polynomial with 288 ///< denominator 1 289 ); 290 291 /// find a big prime p from our tables such that no term of f vanishes mod p 292 void findGoodPrime(const CanonicalForm &f, ///< [in] poly over Z or Z[a] 293 int &start ///< [in,out] index of big prime in 294 /// cf_primetab.h 295 ); 296 297 /// compute p^k larger than the bound on the coefficients of a factor of @a f 298 /// over Z 299 modpk 300 coeffBound (const CanonicalForm & f, ///< [in] poly over Z 301 int p ///< [in] some positive integer 302 ); 303 304 #endif 305 306