1 | /*****************************************************************************\ |
---|
2 | * Computer Algebra System SINGULAR |
---|
3 | \*****************************************************************************/ |
---|
4 | /** @file facFactorize.cc |
---|
5 | * |
---|
6 | * multivariate factorization over Q(a) |
---|
7 | * |
---|
8 | * @author Martin Lee |
---|
9 | * |
---|
10 | **/ |
---|
11 | /*****************************************************************************/ |
---|
12 | |
---|
13 | #include "config.h" |
---|
14 | |
---|
15 | #include "assert.h" |
---|
16 | #include "debug.h" |
---|
17 | #include "timing.h" |
---|
18 | |
---|
19 | #include "cf_algorithm.h" |
---|
20 | #include "facFqFactorizeUtil.h" |
---|
21 | #include "facFactorize.h" |
---|
22 | #include "facFqFactorize.h" |
---|
23 | #include "cf_random.h" |
---|
24 | #include "facHensel.h" |
---|
25 | #include "cf_gcd_smallp.h" |
---|
26 | #include "cf_map_ext.h" |
---|
27 | #include "algext.h" |
---|
28 | #include "cf_reval.h" |
---|
29 | #include "facSparseHensel.h" |
---|
30 | |
---|
31 | TIMING_DEFINE_PRINT(fac_bi_factorizer) |
---|
32 | TIMING_DEFINE_PRINT(fac_hensel_lift) |
---|
33 | TIMING_DEFINE_PRINT(fac_factor_recombination) |
---|
34 | TIMING_DEFINE_PRINT(fac_shift_to_zero) |
---|
35 | TIMING_DEFINE_PRINT(fac_precompute_leadcoeff) |
---|
36 | TIMING_DEFINE_PRINT(fac_evaluation) |
---|
37 | TIMING_DEFINE_PRINT(fac_recover_factors) |
---|
38 | TIMING_DEFINE_PRINT(fac_preprocess_and_content) |
---|
39 | TIMING_DEFINE_PRINT(fac_bifactor_total) |
---|
40 | TIMING_DEFINE_PRINT(fac_luckswang) |
---|
41 | TIMING_DEFINE_PRINT(fac_lcheuristic) |
---|
42 | TIMING_DEFINE_PRINT(fac_cleardenom) |
---|
43 | TIMING_DEFINE_PRINT(fac_content) |
---|
44 | TIMING_DEFINE_PRINT(fac_compress) |
---|
45 | |
---|
46 | #ifdef HAVE_NTL |
---|
47 | CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E) |
---|
48 | { |
---|
49 | CFList result; |
---|
50 | Variable x= Variable (1); |
---|
51 | |
---|
52 | bool found= false; |
---|
53 | bool allZero= true; |
---|
54 | bool foundZero= false; |
---|
55 | CanonicalForm deriv_x, gcd_deriv; |
---|
56 | CFListIterator iter; |
---|
57 | do |
---|
58 | { |
---|
59 | eval.insert (F); |
---|
60 | bool bad= false; |
---|
61 | for (int i= E.max(); i >= E.min(); i--) |
---|
62 | { |
---|
63 | eval.insert (eval.getFirst()( E [i], i)); |
---|
64 | result.append (E[i]); |
---|
65 | if (!E[i].isZero()) |
---|
66 | allZero= false; |
---|
67 | else |
---|
68 | foundZero= true; |
---|
69 | if (!allZero && foundZero) |
---|
70 | { |
---|
71 | result= CFList(); |
---|
72 | eval= CFList(); |
---|
73 | bad= true; |
---|
74 | foundZero= false; |
---|
75 | break; |
---|
76 | } |
---|
77 | if (degree (eval.getFirst(), i - 1) != degree (F, i - 1)) |
---|
78 | { |
---|
79 | result= CFList(); |
---|
80 | eval= CFList(); |
---|
81 | bad= true; |
---|
82 | break; |
---|
83 | } |
---|
84 | } |
---|
85 | |
---|
86 | if (bad) |
---|
87 | { |
---|
88 | E.nextpoint(); |
---|
89 | continue; |
---|
90 | } |
---|
91 | |
---|
92 | if (degree (eval.getFirst()) != degree (F, 1)) |
---|
93 | { |
---|
94 | result= CFList(); |
---|
95 | eval= CFList(); |
---|
96 | E.nextpoint(); |
---|
97 | continue; |
---|
98 | } |
---|
99 | |
---|
100 | deriv_x= deriv (eval.getFirst(), x); |
---|
101 | gcd_deriv= gcd (eval.getFirst(), deriv_x); |
---|
102 | if (degree (gcd_deriv) > 0) |
---|
103 | { |
---|
104 | result= CFList(); |
---|
105 | eval= CFList(); |
---|
106 | E.nextpoint(); |
---|
107 | continue; |
---|
108 | } |
---|
109 | iter= eval; |
---|
110 | iter++; |
---|
111 | CanonicalForm contentx= content (iter.getItem(), x); |
---|
112 | if (degree (contentx) > 0) |
---|
113 | { |
---|
114 | result= CFList(); |
---|
115 | eval= CFList(); |
---|
116 | E.nextpoint(); |
---|
117 | continue; |
---|
118 | } |
---|
119 | found= true; |
---|
120 | } |
---|
121 | while (!found); |
---|
122 | |
---|
123 | if (!eval.isEmpty()) |
---|
124 | eval.removeFirst(); |
---|
125 | return result; |
---|
126 | } |
---|
127 | |
---|
128 | void |
---|
129 | factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval, |
---|
130 | int& minFactorsLength, bool& irred, |
---|
131 | const Variable& w) |
---|
132 | { |
---|
133 | Variable x= Variable (1); |
---|
134 | minFactorsLength= 0; |
---|
135 | irred= false; |
---|
136 | Variable v; |
---|
137 | CFList factors; |
---|
138 | CanonicalForm LCA= LC (A,1); |
---|
139 | for (int j= 0; j < A.level() - 2; j++) |
---|
140 | { |
---|
141 | if (!Aeval[j].isEmpty()) |
---|
142 | { |
---|
143 | v= Variable (Aeval[j].getFirst().level()); |
---|
144 | |
---|
145 | factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w); |
---|
146 | if (factors.getFirst().inCoeffDomain()) |
---|
147 | factors.removeFirst(); |
---|
148 | |
---|
149 | if (minFactorsLength == 0) |
---|
150 | minFactorsLength= factors.length(); |
---|
151 | else |
---|
152 | minFactorsLength= tmin (minFactorsLength, factors.length()); |
---|
153 | |
---|
154 | if (factors.length() == 1) |
---|
155 | { |
---|
156 | irred= true; |
---|
157 | return; |
---|
158 | } |
---|
159 | sortList (factors, x); |
---|
160 | Aeval [j]= factors; |
---|
161 | } |
---|
162 | } |
---|
163 | } |
---|
164 | |
---|
165 | CFList |
---|
166 | multiFactorize (const CanonicalForm& F, const Variable& v) |
---|
167 | { |
---|
168 | if (F.inCoeffDomain()) |
---|
169 | return CFList (F); |
---|
170 | |
---|
171 | TIMING_START (fac_preprocess_and_content); |
---|
172 | // compress and find main Variable |
---|
173 | CFMap N; |
---|
174 | TIMING_START (fac_compress) |
---|
175 | CanonicalForm A= myCompress (F, N); |
---|
176 | TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ") |
---|
177 | |
---|
178 | //univariate case |
---|
179 | if (F.isUnivariate()) |
---|
180 | { |
---|
181 | CFList result; |
---|
182 | if (v.level() != 1) |
---|
183 | result= conv (factorize (F, v)); |
---|
184 | else |
---|
185 | result= conv (factorize (F,true)); |
---|
186 | if (result.getFirst().inCoeffDomain()) |
---|
187 | result.removeFirst(); |
---|
188 | return result; |
---|
189 | } |
---|
190 | |
---|
191 | //bivariate case |
---|
192 | if (A.level() == 2) |
---|
193 | { |
---|
194 | CFList buf= biFactorize (F, v); |
---|
195 | return buf; |
---|
196 | } |
---|
197 | |
---|
198 | Variable x= Variable (1); |
---|
199 | Variable y= Variable (2); |
---|
200 | |
---|
201 | // remove content |
---|
202 | TIMING_START (fac_content); |
---|
203 | CFList contentAi; |
---|
204 | CanonicalForm lcmCont= lcmContent (A, contentAi); |
---|
205 | A /= lcmCont; |
---|
206 | TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: "); |
---|
207 | |
---|
208 | // trivial after content removal |
---|
209 | CFList contentAFactors; |
---|
210 | if (A.inCoeffDomain()) |
---|
211 | { |
---|
212 | for (CFListIterator i= contentAi; i.hasItem(); i++) |
---|
213 | { |
---|
214 | if (i.getItem().inCoeffDomain()) |
---|
215 | continue; |
---|
216 | else |
---|
217 | { |
---|
218 | lcmCont /= i.getItem(); |
---|
219 | contentAFactors= |
---|
220 | Union (multiFactorize (lcmCont, v), |
---|
221 | multiFactorize (i.getItem(), v)); |
---|
222 | break; |
---|
223 | } |
---|
224 | } |
---|
225 | decompress (contentAFactors, N); |
---|
226 | if (isOn (SW_RATIONAL)) |
---|
227 | normalize (contentAFactors); |
---|
228 | return contentAFactors; |
---|
229 | } |
---|
230 | |
---|
231 | // factorize content |
---|
232 | TIMING_START (fac_content); |
---|
233 | contentAFactors= multiFactorize (lcmCont, v); |
---|
234 | TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: "); |
---|
235 | |
---|
236 | // univariate after content removal |
---|
237 | CFList factors; |
---|
238 | if (A.isUnivariate ()) |
---|
239 | { |
---|
240 | if (v.level() != 1) |
---|
241 | factors= conv (factorize (A, v)); |
---|
242 | else |
---|
243 | factors= conv (factorize (A,true)); |
---|
244 | append (factors, contentAFactors); |
---|
245 | decompress (factors, N); |
---|
246 | return factors; |
---|
247 | } |
---|
248 | |
---|
249 | A *= bCommonDen (A); |
---|
250 | CFList Aeval, list, evaluation, bufEvaluation, bufAeval; |
---|
251 | int factorNums= 1; |
---|
252 | CFList biFactors, bufBiFactors; |
---|
253 | CanonicalForm evalPoly; |
---|
254 | int lift, bufLift, lengthAeval2= A.level()-2; |
---|
255 | CFList* bufAeval2= new CFList [lengthAeval2]; |
---|
256 | CFList* Aeval2= new CFList [lengthAeval2]; |
---|
257 | int counter; |
---|
258 | int differentSecondVar= 0; |
---|
259 | CanonicalForm bufA; |
---|
260 | TIMING_END_AND_PRINT (fac_preprocess_and_content, |
---|
261 | "time to preprocess poly and extract content over Q: "); |
---|
262 | |
---|
263 | // several bivariate factorizations |
---|
264 | TIMING_START (fac_bifactor_total); |
---|
265 | REvaluation E (2, A.level(), IntRandom (25)); |
---|
266 | for (int i= 0; i < factorNums; i++) |
---|
267 | { |
---|
268 | counter= 0; |
---|
269 | bufA= A; |
---|
270 | bufAeval= CFList(); |
---|
271 | TIMING_START (fac_evaluation); |
---|
272 | bufEvaluation= evalPoints (bufA, bufAeval, E); |
---|
273 | TIMING_END_AND_PRINT (fac_evaluation, |
---|
274 | "time to find evaluation point over Q: "); |
---|
275 | E.nextpoint(); |
---|
276 | evalPoly= 0; |
---|
277 | |
---|
278 | TIMING_START (fac_evaluation); |
---|
279 | evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A); |
---|
280 | TIMING_END_AND_PRINT (fac_evaluation, |
---|
281 | "time to eval wrt diff second vars over Q: "); |
---|
282 | |
---|
283 | for (int j= 0; j < lengthAeval2; j++) |
---|
284 | { |
---|
285 | if (!bufAeval2[j].isEmpty()) |
---|
286 | counter++; |
---|
287 | } |
---|
288 | |
---|
289 | bufLift= degree (A, y) + 1 + degree (LC(A, x), y); |
---|
290 | |
---|
291 | TIMING_START (fac_bi_factorizer); |
---|
292 | bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v); |
---|
293 | TIMING_END_AND_PRINT (fac_bi_factorizer, |
---|
294 | "time for bivariate factorization: "); |
---|
295 | bufBiFactors.removeFirst(); |
---|
296 | |
---|
297 | if (bufBiFactors.length() == 1) |
---|
298 | { |
---|
299 | factors.append (A); |
---|
300 | appendSwapDecompress (factors, contentAFactors, N, 0, 0, x); |
---|
301 | if (isOn (SW_RATIONAL)) |
---|
302 | normalize (factors); |
---|
303 | delete [] bufAeval2; |
---|
304 | delete [] Aeval2; |
---|
305 | return factors; |
---|
306 | } |
---|
307 | |
---|
308 | if (i == 0) |
---|
309 | { |
---|
310 | Aeval= bufAeval; |
---|
311 | evaluation= bufEvaluation; |
---|
312 | biFactors= bufBiFactors; |
---|
313 | lift= bufLift; |
---|
314 | for (int j= 0; j < lengthAeval2; j++) |
---|
315 | Aeval2 [j]= bufAeval2 [j]; |
---|
316 | differentSecondVar= counter; |
---|
317 | } |
---|
318 | else |
---|
319 | { |
---|
320 | if (bufBiFactors.length() < biFactors.length() || |
---|
321 | ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) || |
---|
322 | counter > differentSecondVar) |
---|
323 | { |
---|
324 | Aeval= bufAeval; |
---|
325 | evaluation= bufEvaluation; |
---|
326 | biFactors= bufBiFactors; |
---|
327 | lift= bufLift; |
---|
328 | for (int j= 0; j < lengthAeval2; j++) |
---|
329 | Aeval2 [j]= bufAeval2 [j]; |
---|
330 | differentSecondVar= counter; |
---|
331 | } |
---|
332 | } |
---|
333 | int k= 0; |
---|
334 | for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++) |
---|
335 | evalPoly += j.getItem()*power (x, k); |
---|
336 | list.append (evalPoly); |
---|
337 | } |
---|
338 | |
---|
339 | delete [] bufAeval2; |
---|
340 | |
---|
341 | sortList (biFactors, x); |
---|
342 | |
---|
343 | int minFactorsLength; |
---|
344 | bool irred= false; |
---|
345 | TIMING_START (fac_bi_factorizer); |
---|
346 | factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v); |
---|
347 | TIMING_END_AND_PRINT (fac_bi_factorizer, |
---|
348 | "time for bivariate factorization wrt diff second vars over Q: "); |
---|
349 | |
---|
350 | TIMING_END_AND_PRINT (fac_bifactor_total, |
---|
351 | "total time for eval and bivar factors over Q: "); |
---|
352 | if (irred) |
---|
353 | { |
---|
354 | factors.append (A); |
---|
355 | appendSwapDecompress (factors, contentAFactors, N, 0, 0, x); |
---|
356 | if (isOn (SW_RATIONAL)) |
---|
357 | normalize (factors); |
---|
358 | delete [] Aeval2; |
---|
359 | return factors; |
---|
360 | } |
---|
361 | |
---|
362 | if (minFactorsLength == 0) |
---|
363 | minFactorsLength= biFactors.length(); |
---|
364 | else if (biFactors.length() > minFactorsLength) |
---|
365 | refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength); |
---|
366 | |
---|
367 | if (differentSecondVar == lengthAeval2) |
---|
368 | { |
---|
369 | bool zeroOccured= false; |
---|
370 | for (CFListIterator iter= evaluation; iter.hasItem(); iter++) |
---|
371 | { |
---|
372 | if (iter.getItem().isZero()) |
---|
373 | { |
---|
374 | zeroOccured= true; |
---|
375 | break; |
---|
376 | } |
---|
377 | } |
---|
378 | if (!zeroOccured) |
---|
379 | { |
---|
380 | factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, |
---|
381 | minFactorsLength); |
---|
382 | if (factors.length() == biFactors.length()) |
---|
383 | { |
---|
384 | appendSwapDecompress (factors, contentAFactors, N, 0, 0, x); |
---|
385 | normalize (factors); |
---|
386 | delete [] Aeval2; |
---|
387 | return factors; |
---|
388 | } |
---|
389 | else |
---|
390 | factors= CFList(); |
---|
391 | //TODO case where factors.length() > 0 |
---|
392 | } |
---|
393 | } |
---|
394 | |
---|
395 | CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y); |
---|
396 | |
---|
397 | sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation); |
---|
398 | |
---|
399 | CFList * oldAeval= new CFList [lengthAeval2]; |
---|
400 | for (int i= 0; i < lengthAeval2; i++) |
---|
401 | oldAeval[i]= Aeval2[i]; |
---|
402 | |
---|
403 | getLeadingCoeffs (A, Aeval2); |
---|
404 | |
---|
405 | CFList biFactorsLCs; |
---|
406 | for (CFListIterator i= biFactors; i.hasItem(); i++) |
---|
407 | biFactorsLCs.append (LC (i.getItem(), 1)); |
---|
408 | |
---|
409 | Variable w; |
---|
410 | TIMING_START (fac_precompute_leadcoeff); |
---|
411 | CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x, |
---|
412 | evaluation, Aeval2, lengthAeval2, w); |
---|
413 | |
---|
414 | if (w.level() != 1) |
---|
415 | { |
---|
416 | A= swapvar (A, y, w); |
---|
417 | int i= A.level(); |
---|
418 | CanonicalForm evalPoint; |
---|
419 | for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--) |
---|
420 | { |
---|
421 | if (i == w.level()) |
---|
422 | { |
---|
423 | evalPoint= iter.getItem(); |
---|
424 | iter.getItem()= evaluation.getLast(); |
---|
425 | evaluation.removeLast(); |
---|
426 | evaluation.append (evalPoint); |
---|
427 | break; |
---|
428 | } |
---|
429 | } |
---|
430 | for (i= 0; i < lengthAeval2; i++) |
---|
431 | { |
---|
432 | if (oldAeval[i].isEmpty()) |
---|
433 | continue; |
---|
434 | if (oldAeval[i].getFirst().level() == w.level()) |
---|
435 | { |
---|
436 | CFArray tmp= copy (oldAeval[i]); |
---|
437 | oldAeval[i]= biFactors; |
---|
438 | for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++) |
---|
439 | iter.getItem()= swapvar (iter.getItem(), w, y); |
---|
440 | for (int ii= 0; ii < tmp.size(); ii++) |
---|
441 | tmp[ii]= swapvar (tmp[ii], w, y); |
---|
442 | CFArray tmp2= CFArray (tmp.size()); |
---|
443 | CanonicalForm buf; |
---|
444 | for (int ii= 0; ii < tmp.size(); ii++) |
---|
445 | { |
---|
446 | buf= tmp[ii] (evaluation.getLast(),y); |
---|
447 | buf /= Lc (buf); |
---|
448 | tmp2[findItem (uniFactors, buf)-1]=tmp[ii]; |
---|
449 | } |
---|
450 | biFactors= CFList(); |
---|
451 | for (int j= 0; j < tmp2.size(); j++) |
---|
452 | biFactors.append (tmp2[j]); |
---|
453 | } |
---|
454 | } |
---|
455 | } |
---|
456 | |
---|
457 | CFListIterator iter; |
---|
458 | CanonicalForm oldA= A; |
---|
459 | CFList oldBiFactors= biFactors; |
---|
460 | if (!leadingCoeffs.getFirst().inCoeffDomain()) |
---|
461 | { |
---|
462 | CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1); |
---|
463 | A *= tmp; |
---|
464 | tmp= leadingCoeffs.getFirst(); |
---|
465 | iter= evaluation; |
---|
466 | for (int i= A.level(); i > 2; i--, iter++) |
---|
467 | tmp= tmp (iter.getItem(), i); |
---|
468 | if (!tmp.inCoeffDomain()) |
---|
469 | { |
---|
470 | for (CFListIterator i= biFactors; i.hasItem(); i++) |
---|
471 | { |
---|
472 | i.getItem() *= tmp/LC (i.getItem(), 1); |
---|
473 | i.getItem() /= Lc (i.getItem()); |
---|
474 | } |
---|
475 | } |
---|
476 | } |
---|
477 | |
---|
478 | CanonicalForm LCmultiplier= leadingCoeffs.getFirst(); |
---|
479 | bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain(); |
---|
480 | leadingCoeffs.removeFirst(); |
---|
481 | |
---|
482 | //prepare leading coefficients |
---|
483 | CFList* leadingCoeffs2= new CFList [lengthAeval2]; |
---|
484 | prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors, |
---|
485 | evaluation); |
---|
486 | |
---|
487 | |
---|
488 | Aeval= evaluateAtEval (A, evaluation, 2); |
---|
489 | |
---|
490 | CanonicalForm hh= 1/Lc (Aeval.getFirst()); |
---|
491 | |
---|
492 | for (iter= Aeval; iter.hasItem(); iter++) |
---|
493 | iter.getItem() *= hh; |
---|
494 | |
---|
495 | A *= hh; |
---|
496 | |
---|
497 | CFListIterator iter2; |
---|
498 | CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1]; |
---|
499 | bufBiFactors= biFactors; |
---|
500 | bufA= A; |
---|
501 | CanonicalForm bufLCmultiplier= LCmultiplier; |
---|
502 | CanonicalForm testVars; |
---|
503 | if (!LCmultiplierIsConst) |
---|
504 | { |
---|
505 | testVars= Variable (2); |
---|
506 | for (int i= 0; i < lengthAeval2; i++) |
---|
507 | { |
---|
508 | if (!oldAeval[i].isEmpty()) |
---|
509 | testVars *= oldAeval[i].getFirst().mvar(); |
---|
510 | } |
---|
511 | } |
---|
512 | TIMING_END_AND_PRINT(fac_precompute_leadcoeff, |
---|
513 | "time to precompute LC over Q: "); |
---|
514 | |
---|
515 | TIMING_START (fac_luckswang); |
---|
516 | CFList bufFactors= CFList(); |
---|
517 | bool LCheuristic= false; |
---|
518 | if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1], |
---|
519 | factors)) |
---|
520 | { |
---|
521 | int check= biFactors.length(); |
---|
522 | int * index= new int [factors.length()]; |
---|
523 | CFList oldFactors= factors; |
---|
524 | factors= recoverFactors (A, factors, index); |
---|
525 | |
---|
526 | if (check == factors.length()) |
---|
527 | { |
---|
528 | if (w.level() != 1) |
---|
529 | { |
---|
530 | for (iter= factors; iter.hasItem(); iter++) |
---|
531 | iter.getItem()= swapvar (iter.getItem(), w, y); |
---|
532 | } |
---|
533 | |
---|
534 | appendSwapDecompress (factors, contentAFactors, N, 0, 0, x); |
---|
535 | normalize (factors); |
---|
536 | delete [] index; |
---|
537 | delete [] Aeval2; |
---|
538 | TIMING_END_AND_PRINT (fac_luckswang, |
---|
539 | "time for successful LucksWang over Q: "); |
---|
540 | return factors; |
---|
541 | } |
---|
542 | else if (factors.length() > 0) |
---|
543 | { |
---|
544 | int oneCount= 0; |
---|
545 | CFList l; |
---|
546 | for (int i= 0; i < check; i++) |
---|
547 | { |
---|
548 | if (index[i] == 1) |
---|
549 | { |
---|
550 | iter=biFactors; |
---|
551 | for (int j=1; j <= i-oneCount; j++) |
---|
552 | iter++; |
---|
553 | iter.remove (1); |
---|
554 | for (int j= 0; j < lengthAeval2; j++) |
---|
555 | { |
---|
556 | l= leadingCoeffs2[j]; |
---|
557 | iter= l; |
---|
558 | for (int k=1; k <= i-oneCount; k++) |
---|
559 | iter++; |
---|
560 | iter.remove (1); |
---|
561 | leadingCoeffs2[j]=l; |
---|
562 | } |
---|
563 | oneCount++; |
---|
564 | } |
---|
565 | } |
---|
566 | bufFactors= factors; |
---|
567 | factors= CFList(); |
---|
568 | } |
---|
569 | else if (!LCmultiplierIsConst && factors.length() == 0) |
---|
570 | { |
---|
571 | LCheuristic= true; |
---|
572 | factors= oldFactors; |
---|
573 | CanonicalForm cont; |
---|
574 | CFList contents, LCs; |
---|
575 | int index=1; |
---|
576 | bool foundTrueMultiplier= false; |
---|
577 | for (iter= factors; iter.hasItem(); iter++, index++) |
---|
578 | { |
---|
579 | cont= content (iter.getItem(), 1); |
---|
580 | cont= gcd (cont , LCmultiplier); |
---|
581 | contents.append (cont); |
---|
582 | if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there |
---|
583 | { |
---|
584 | foundTrueMultiplier= true; |
---|
585 | int index2= 1; |
---|
586 | for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++, |
---|
587 | index2++) |
---|
588 | { |
---|
589 | if (index2 == index) |
---|
590 | continue; |
---|
591 | iter2.getItem() /= LCmultiplier; |
---|
592 | } |
---|
593 | A= oldA; |
---|
594 | leadingCoeffs= leadingCoeffs2[lengthAeval2-1]; |
---|
595 | for (int i= lengthAeval2-1; i > -1; i--) |
---|
596 | leadingCoeffs2[i]= CFList(); |
---|
597 | prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, |
---|
598 | biFactors, evaluation ); |
---|
599 | Aeval= evaluateAtEval (A, evaluation, 2); |
---|
600 | |
---|
601 | hh= 1/Lc (Aeval.getFirst()); |
---|
602 | |
---|
603 | for (iter2= Aeval; iter2.hasItem(); iter2++) |
---|
604 | iter2.getItem() *= hh; |
---|
605 | |
---|
606 | A *= hh; |
---|
607 | break; |
---|
608 | } |
---|
609 | else |
---|
610 | LCs.append (LC (iter.getItem()/cont, 1)); |
---|
611 | } |
---|
612 | if (!foundTrueMultiplier) |
---|
613 | { |
---|
614 | index= 1; |
---|
615 | iter2= factors; |
---|
616 | bool foundMultiplier= false; |
---|
617 | for (iter= contents; iter.hasItem(); iter++, iter2++, index++) |
---|
618 | { |
---|
619 | if (fdivides (iter.getItem(), LCmultiplier)) |
---|
620 | { |
---|
621 | if ((LCmultiplier/iter.getItem()).inCoeffDomain() && |
---|
622 | !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff |
---|
623 | { |
---|
624 | int index2= 1; |
---|
625 | for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1]; |
---|
626 | iter3.hasItem(); iter3++, index2++) |
---|
627 | { |
---|
628 | if (index2 == index) |
---|
629 | { |
---|
630 | iter3.getItem() /= LCmultiplier; |
---|
631 | break; |
---|
632 | } |
---|
633 | } |
---|
634 | A /= LCmultiplier; |
---|
635 | foundMultiplier= true; |
---|
636 | iter.getItem()= 1; |
---|
637 | } |
---|
638 | } |
---|
639 | } |
---|
640 | // coming from above: divide out more LCmultiplier if possible |
---|
641 | if (foundMultiplier) |
---|
642 | { |
---|
643 | foundMultiplier= false; |
---|
644 | index=1; |
---|
645 | iter2= factors; |
---|
646 | for (iter= contents; iter.hasItem(); iter++, iter2++, index++) |
---|
647 | { |
---|
648 | if (!iter.getItem().isOne() && |
---|
649 | fdivides (iter.getItem(), LCmultiplier)) |
---|
650 | { |
---|
651 | if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff |
---|
652 | { |
---|
653 | int index2= 1; |
---|
654 | for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); |
---|
655 | iter2++, index2++) |
---|
656 | { |
---|
657 | if (index2 == index) |
---|
658 | { |
---|
659 | iter2.getItem() /= iter.getItem(); |
---|
660 | foundMultiplier= true; |
---|
661 | break; |
---|
662 | } |
---|
663 | } |
---|
664 | A /= iter.getItem(); |
---|
665 | LCmultiplier /= iter.getItem(); |
---|
666 | iter.getItem()= 1; |
---|
667 | } |
---|
668 | else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff |
---|
669 | { |
---|
670 | Variable xx= Variable (2); |
---|
671 | CanonicalForm vars; |
---|
672 | vars= power (xx, degree (LC (getItem(oldBiFactors, index),1), |
---|
673 | xx)); |
---|
674 | for (int i= 0; i < lengthAeval2; i++) |
---|
675 | { |
---|
676 | if (oldAeval[i].isEmpty()) |
---|
677 | continue; |
---|
678 | xx= oldAeval[i].getFirst().mvar(); |
---|
679 | vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1), |
---|
680 | xx)); |
---|
681 | } |
---|
682 | if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1)) |
---|
683 | /myGetVars (LCmultiplier) == vars) |
---|
684 | { |
---|
685 | int index2= 1; |
---|
686 | for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); |
---|
687 | iter2++, index2++) |
---|
688 | { |
---|
689 | if (index2 == index) |
---|
690 | { |
---|
691 | iter2.getItem() /= LCmultiplier; |
---|
692 | foundMultiplier= true; |
---|
693 | break; |
---|
694 | } |
---|
695 | } |
---|
696 | A /= LCmultiplier; |
---|
697 | iter.getItem()= 1; |
---|
698 | } |
---|
699 | } |
---|
700 | } |
---|
701 | } |
---|
702 | } |
---|
703 | else |
---|
704 | { |
---|
705 | CanonicalForm pLCs= prod (LCs); |
---|
706 | if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A |
---|
707 | { |
---|
708 | A= oldA; |
---|
709 | iter2= leadingCoeffs2[lengthAeval2-1]; |
---|
710 | for (iter= contents; iter.hasItem(); iter++, iter2++) |
---|
711 | iter2.getItem() /= iter.getItem(); |
---|
712 | foundMultiplier= true; |
---|
713 | } |
---|
714 | if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars)) |
---|
715 | { |
---|
716 | Variable xx; |
---|
717 | CFList vars1; |
---|
718 | CFFList sqrfMultiplier= sqrFree (LCmultiplier); |
---|
719 | if (sqrfMultiplier.getFirst().factor().inCoeffDomain()) |
---|
720 | sqrfMultiplier.removeFirst(); |
---|
721 | sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier); |
---|
722 | xx= Variable (2); |
---|
723 | for (iter= oldBiFactors; iter.hasItem(); iter++) |
---|
724 | vars1.append (power (xx, degree (LC (iter.getItem(),1), xx))); |
---|
725 | for (int i= 0; i < lengthAeval2; i++) |
---|
726 | { |
---|
727 | if (oldAeval[i].isEmpty()) |
---|
728 | continue; |
---|
729 | xx= oldAeval[i].getFirst().mvar(); |
---|
730 | iter2= vars1; |
---|
731 | for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++) |
---|
732 | iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx)); |
---|
733 | } |
---|
734 | CanonicalForm tmp; |
---|
735 | iter2= vars1; |
---|
736 | for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, |
---|
737 | iter2++) |
---|
738 | { |
---|
739 | tmp= iter.getItem()/LCmultiplier; |
---|
740 | for (int i=1; i <= tmp.level(); i++) |
---|
741 | { |
---|
742 | if (degree(tmp,i) > 0 && |
---|
743 | (degree(iter2.getItem(),i) > degree (tmp,i))) |
---|
744 | iter2.getItem() /= power (Variable (i), degree (tmp,i)); |
---|
745 | } |
---|
746 | } |
---|
747 | int multi; |
---|
748 | for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++) |
---|
749 | { |
---|
750 | multi= 0; |
---|
751 | for (iter= vars1; iter.hasItem(); iter++) |
---|
752 | { |
---|
753 | tmp= iter.getItem(); |
---|
754 | while (fdivides (myGetVars (ii.getItem().factor()), tmp)) |
---|
755 | { |
---|
756 | multi++; |
---|
757 | tmp /= myGetVars (ii.getItem().factor()); |
---|
758 | } |
---|
759 | } |
---|
760 | if (multi == ii.getItem().exp()) |
---|
761 | { |
---|
762 | index= 1; |
---|
763 | for (iter= vars1; iter.hasItem(); iter++, index++) |
---|
764 | { |
---|
765 | while (fdivides (myGetVars(ii.getItem().factor()), |
---|
766 | iter.getItem() |
---|
767 | ) |
---|
768 | ) |
---|
769 | { |
---|
770 | int index2= 1; |
---|
771 | for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); |
---|
772 | iter2++, index2++) |
---|
773 | { |
---|
774 | if (index2 == index) |
---|
775 | continue; |
---|
776 | else |
---|
777 | { |
---|
778 | tmp= ii.getItem().factor(); |
---|
779 | iter2.getItem() /= tmp; |
---|
780 | CFListIterator iter3= evaluation; |
---|
781 | for (int jj= A.level(); jj > 2; jj--, iter3++) |
---|
782 | tmp= tmp (iter3.getItem(), jj); |
---|
783 | if (!tmp.inCoeffDomain()) |
---|
784 | { |
---|
785 | int index3= 1; |
---|
786 | for (iter3= biFactors; iter3.hasItem(); iter3++, |
---|
787 | index3++) |
---|
788 | { |
---|
789 | if (index3 == index2) |
---|
790 | { |
---|
791 | iter3.getItem() /= tmp; |
---|
792 | iter3.getItem() /= Lc (iter3.getItem()); |
---|
793 | break; |
---|
794 | } |
---|
795 | } |
---|
796 | } |
---|
797 | A /= ii.getItem().factor(); |
---|
798 | } |
---|
799 | } |
---|
800 | iter.getItem() /= getVars (ii.getItem().factor()); |
---|
801 | } |
---|
802 | } |
---|
803 | } |
---|
804 | else |
---|
805 | { |
---|
806 | index= 1; |
---|
807 | for (iter= vars1; iter.hasItem(); iter++, index++) |
---|
808 | { |
---|
809 | if (!fdivides (myGetVars (ii.getItem().factor()), |
---|
810 | iter.getItem() |
---|
811 | ) |
---|
812 | ) |
---|
813 | { |
---|
814 | int index2= 1; |
---|
815 | for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); |
---|
816 | iter2++, index2++) |
---|
817 | { |
---|
818 | if (index2 == index) |
---|
819 | { |
---|
820 | tmp= power (ii.getItem().factor(), ii.getItem().exp()); |
---|
821 | iter2.getItem() /= tmp; |
---|
822 | A /= tmp; |
---|
823 | CFListIterator iter3= evaluation; |
---|
824 | for (int jj= A.level(); jj > 2; jj--, iter3++) |
---|
825 | tmp= tmp (iter3.getItem(), jj); |
---|
826 | if (!tmp.inCoeffDomain()) |
---|
827 | { |
---|
828 | int index3= 1; |
---|
829 | for (iter3= biFactors; iter3.hasItem(); iter3++, |
---|
830 | index3++) |
---|
831 | { |
---|
832 | if (index3 == index2) |
---|
833 | { |
---|
834 | iter3.getItem() /= tmp; |
---|
835 | iter3.getItem() /= Lc (iter3.getItem()); |
---|
836 | break; |
---|
837 | } |
---|
838 | } |
---|
839 | } |
---|
840 | } |
---|
841 | } |
---|
842 | } |
---|
843 | } |
---|
844 | } |
---|
845 | } |
---|
846 | } |
---|
847 | } |
---|
848 | |
---|
849 | // patch everything together again |
---|
850 | leadingCoeffs= leadingCoeffs2[lengthAeval2-1]; |
---|
851 | for (int i= lengthAeval2-1; i > -1; i--) |
---|
852 | leadingCoeffs2[i]= CFList(); |
---|
853 | prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors, |
---|
854 | evaluation); |
---|
855 | Aeval= evaluateAtEval (A, evaluation, 2); |
---|
856 | |
---|
857 | hh= 1/Lc (Aeval.getFirst()); |
---|
858 | |
---|
859 | for (CFListIterator i= Aeval; i.hasItem(); i++) |
---|
860 | i.getItem() *= hh; |
---|
861 | |
---|
862 | A *= hh; |
---|
863 | } |
---|
864 | factors= CFList(); |
---|
865 | if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1]))) |
---|
866 | { |
---|
867 | LCheuristic= false; |
---|
868 | A= bufA; |
---|
869 | biFactors= bufBiFactors; |
---|
870 | leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2; |
---|
871 | LCmultiplier= bufLCmultiplier; |
---|
872 | } |
---|
873 | } |
---|
874 | else |
---|
875 | factors= CFList(); |
---|
876 | delete [] index; |
---|
877 | } |
---|
878 | TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: "); |
---|
879 | |
---|
880 | TIMING_START (fac_lcheuristic); |
---|
881 | if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty() |
---|
882 | && fdivides (getVars (LCmultiplier), testVars)) |
---|
883 | { |
---|
884 | LCheuristic= true; |
---|
885 | int index; |
---|
886 | Variable xx; |
---|
887 | CFList vars1; |
---|
888 | CFFList sqrfMultiplier= sqrFree (LCmultiplier); |
---|
889 | if (sqrfMultiplier.getFirst().factor().inCoeffDomain()) |
---|
890 | sqrfMultiplier.removeFirst(); |
---|
891 | sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier); |
---|
892 | xx= Variable (2); |
---|
893 | for (iter= oldBiFactors; iter.hasItem(); iter++) |
---|
894 | vars1.append (power (xx, degree (LC (iter.getItem(),1), xx))); |
---|
895 | for (int i= 0; i < lengthAeval2; i++) |
---|
896 | { |
---|
897 | if (oldAeval[i].isEmpty()) |
---|
898 | continue; |
---|
899 | xx= oldAeval[i].getFirst().mvar(); |
---|
900 | iter2= vars1; |
---|
901 | for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++) |
---|
902 | iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx)); |
---|
903 | } |
---|
904 | CanonicalForm tmp; |
---|
905 | iter2= vars1; |
---|
906 | for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++) |
---|
907 | { |
---|
908 | tmp= iter.getItem()/LCmultiplier; |
---|
909 | for (int i=1; i <= tmp.level(); i++) |
---|
910 | { |
---|
911 | if (degree(tmp,i) > 0 && (degree(iter2.getItem(),i) > degree (tmp,i))) |
---|
912 | iter2.getItem() /= power (Variable (i), degree (tmp,i)); |
---|
913 | } |
---|
914 | } |
---|
915 | int multi; |
---|
916 | for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++) |
---|
917 | { |
---|
918 | multi= 0; |
---|
919 | for (iter= vars1; iter.hasItem(); iter++) |
---|
920 | { |
---|
921 | tmp= iter.getItem(); |
---|
922 | while (fdivides (myGetVars (ii.getItem().factor()), tmp)) |
---|
923 | { |
---|
924 | multi++; |
---|
925 | tmp /= myGetVars (ii.getItem().factor()); |
---|
926 | } |
---|
927 | } |
---|
928 | if (multi == ii.getItem().exp()) |
---|
929 | { |
---|
930 | index= 1; |
---|
931 | for (iter= vars1; iter.hasItem(); iter++, index++) |
---|
932 | { |
---|
933 | while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem())) |
---|
934 | { |
---|
935 | int index2= 1; |
---|
936 | for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++, |
---|
937 | index2++) |
---|
938 | { |
---|
939 | if (index2 == index) |
---|
940 | continue; |
---|
941 | else |
---|
942 | { |
---|
943 | tmp= ii.getItem().factor(); |
---|
944 | iter2.getItem() /= tmp; |
---|
945 | CFListIterator iter3= evaluation; |
---|
946 | for (int jj= A.level(); jj > 2; jj--, iter3++) |
---|
947 | tmp= tmp (iter3.getItem(), jj); |
---|
948 | if (!tmp.inCoeffDomain()) |
---|
949 | { |
---|
950 | int index3= 1; |
---|
951 | for (iter3= biFactors; iter3.hasItem(); iter3++, index3++) |
---|
952 | { |
---|
953 | if (index3 == index2) |
---|
954 | { |
---|
955 | iter3.getItem() /= tmp; |
---|
956 | iter3.getItem() /= Lc (iter3.getItem()); |
---|
957 | break; |
---|
958 | } |
---|
959 | } |
---|
960 | } |
---|
961 | A /= ii.getItem().factor(); |
---|
962 | } |
---|
963 | } |
---|
964 | iter.getItem() /= getVars (ii.getItem().factor()); |
---|
965 | } |
---|
966 | } |
---|
967 | } |
---|
968 | else |
---|
969 | { |
---|
970 | index= 1; |
---|
971 | for (iter= vars1; iter.hasItem(); iter++, index++) |
---|
972 | { |
---|
973 | if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem())) |
---|
974 | { |
---|
975 | int index2= 1; |
---|
976 | for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++, |
---|
977 | index2++) |
---|
978 | { |
---|
979 | if (index2 == index) |
---|
980 | { |
---|
981 | tmp= power (ii.getItem().factor(), ii.getItem().exp()); |
---|
982 | iter2.getItem() /= tmp; |
---|
983 | A /= tmp; |
---|
984 | CFListIterator iter3= evaluation; |
---|
985 | for (int jj= A.level(); jj > 2; jj--, iter3++) |
---|
986 | tmp= tmp (iter3.getItem(), jj); |
---|
987 | if (!tmp.inCoeffDomain()) |
---|
988 | { |
---|
989 | int index3= 1; |
---|
990 | for (iter3= biFactors; iter3.hasItem(); iter3++, index3++) |
---|
991 | { |
---|
992 | if (index3 == index2) |
---|
993 | { |
---|
994 | iter3.getItem() /= tmp; |
---|
995 | iter3.getItem() /= Lc (iter3.getItem()); |
---|
996 | break; |
---|
997 | } |
---|
998 | } |
---|
999 | } |
---|
1000 | } |
---|
1001 | } |
---|
1002 | } |
---|
1003 | } |
---|
1004 | } |
---|
1005 | } |
---|
1006 | |
---|
1007 | leadingCoeffs= leadingCoeffs2[lengthAeval2-1]; |
---|
1008 | for (int i= lengthAeval2-1; i > -1; i--) |
---|
1009 | leadingCoeffs2[i]= CFList(); |
---|
1010 | prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors, |
---|
1011 | evaluation); |
---|
1012 | Aeval= evaluateAtEval (A, evaluation, 2); |
---|
1013 | |
---|
1014 | hh= 1/Lc (Aeval.getFirst()); |
---|
1015 | |
---|
1016 | for (CFListIterator i= Aeval; i.hasItem(); i++) |
---|
1017 | i.getItem() *= hh; |
---|
1018 | |
---|
1019 | A *= hh; |
---|
1020 | |
---|
1021 | if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1]))) |
---|
1022 | { |
---|
1023 | LCheuristic= false; |
---|
1024 | A= bufA; |
---|
1025 | biFactors= bufBiFactors; |
---|
1026 | leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2; |
---|
1027 | LCmultiplier= bufLCmultiplier; |
---|
1028 | } |
---|
1029 | } |
---|
1030 | TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: "); |
---|
1031 | |
---|
1032 | tryAgainWithoutHeu: |
---|
1033 | //shifting to zero |
---|
1034 | TIMING_START (fac_shift_to_zero); |
---|
1035 | CanonicalForm denA= bCommonDen (A); |
---|
1036 | A *= denA; |
---|
1037 | A= shift2Zero (A, Aeval, evaluation); |
---|
1038 | A /= denA; |
---|
1039 | |
---|
1040 | for (iter= biFactors; iter.hasItem(); iter++) |
---|
1041 | iter.getItem()= iter.getItem () (y + evaluation.getLast(), y); |
---|
1042 | |
---|
1043 | for (int i= 0; i < lengthAeval2-1; i++) |
---|
1044 | leadingCoeffs2[i]= CFList(); |
---|
1045 | for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++) |
---|
1046 | { |
---|
1047 | iter.getItem()= shift2Zero (iter.getItem(), list, evaluation); |
---|
1048 | for (int i= A.level() - 4; i > -1; i--) |
---|
1049 | { |
---|
1050 | if (i + 1 == lengthAeval2-1) |
---|
1051 | leadingCoeffs2[i].append (iter.getItem() (0, i + 4)); |
---|
1052 | else |
---|
1053 | leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4)); |
---|
1054 | } |
---|
1055 | } |
---|
1056 | TIMING_END_AND_PRINT (fac_shift_to_zero, |
---|
1057 | "time to shift evaluation point to zero: "); |
---|
1058 | |
---|
1059 | CFArray Pi; |
---|
1060 | CFList diophant; |
---|
1061 | int* liftBounds= new int [A.level() - 1]; |
---|
1062 | int liftBoundsLength= A.level() - 1; |
---|
1063 | for (int i= 0; i < liftBoundsLength; i++) |
---|
1064 | liftBounds [i]= degree (A, i + 2) + 1; |
---|
1065 | |
---|
1066 | Aeval.removeFirst(); |
---|
1067 | bool noOneToOne= false; |
---|
1068 | |
---|
1069 | TIMING_START (fac_cleardenom); |
---|
1070 | CFList commonDenominators; |
---|
1071 | for (iter=biFactors; iter.hasItem(); iter++) |
---|
1072 | commonDenominators.append (bCommonDen (iter.getItem())); |
---|
1073 | CanonicalForm tmp1, tmp2, tmp3=1; |
---|
1074 | for (int i= 0; i < lengthAeval2; i++) |
---|
1075 | { |
---|
1076 | iter2= commonDenominators; |
---|
1077 | for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++) |
---|
1078 | { |
---|
1079 | tmp1= bCommonDen (iter.getItem()); |
---|
1080 | Off (SW_RATIONAL); |
---|
1081 | iter2.getItem()= lcm (iter2.getItem(), tmp1); |
---|
1082 | On (SW_RATIONAL); |
---|
1083 | } |
---|
1084 | } |
---|
1085 | tmp1= prod (commonDenominators); |
---|
1086 | for (iter= Aeval; iter.hasItem(); iter++) |
---|
1087 | { |
---|
1088 | tmp2= bCommonDen (iter.getItem()/denA); |
---|
1089 | Off (SW_RATIONAL); |
---|
1090 | tmp3= lcm (tmp2,tmp3); |
---|
1091 | On (SW_RATIONAL); |
---|
1092 | } |
---|
1093 | CanonicalForm multiplier; |
---|
1094 | multiplier= tmp3/tmp1; |
---|
1095 | iter2= commonDenominators; |
---|
1096 | for (iter=biFactors; iter.hasItem(); iter++, iter2++) |
---|
1097 | iter.getItem() *= iter2.getItem()*multiplier; |
---|
1098 | |
---|
1099 | for (iter= Aeval; iter.hasItem(); iter++) |
---|
1100 | iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA; |
---|
1101 | |
---|
1102 | for (int i= 0; i < lengthAeval2; i++) |
---|
1103 | { |
---|
1104 | iter2= commonDenominators; |
---|
1105 | for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++) |
---|
1106 | iter.getItem() *= iter2.getItem()*multiplier; |
---|
1107 | } |
---|
1108 | TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: "); |
---|
1109 | |
---|
1110 | TIMING_START (fac_hensel_lift); |
---|
1111 | factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant, |
---|
1112 | Pi, liftBounds, liftBoundsLength, noOneToOne); |
---|
1113 | TIMING_END_AND_PRINT (fac_hensel_lift, |
---|
1114 | "time for non monic hensel lifting over Q: "); |
---|
1115 | |
---|
1116 | if (!noOneToOne) |
---|
1117 | { |
---|
1118 | int check= factors.length(); |
---|
1119 | A= oldA; |
---|
1120 | TIMING_START (fac_recover_factors); |
---|
1121 | factors= recoverFactors (A, factors, evaluation); |
---|
1122 | TIMING_END_AND_PRINT (fac_recover_factors, |
---|
1123 | "time to recover factors over Q: "); |
---|
1124 | if (check != factors.length()) |
---|
1125 | noOneToOne= true; |
---|
1126 | else |
---|
1127 | factors= Union (factors, bufFactors); |
---|
1128 | } |
---|
1129 | if (noOneToOne) |
---|
1130 | { |
---|
1131 | if (!LCmultiplierIsConst && LCheuristic) |
---|
1132 | { |
---|
1133 | A= bufA; |
---|
1134 | biFactors= bufBiFactors; |
---|
1135 | leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2; |
---|
1136 | delete [] liftBounds; |
---|
1137 | LCheuristic= false; |
---|
1138 | goto tryAgainWithoutHeu; |
---|
1139 | //something probably went wrong in the heuristic |
---|
1140 | } |
---|
1141 | |
---|
1142 | A= shift2Zero (oldA, Aeval, evaluation); |
---|
1143 | biFactors= oldBiFactors; |
---|
1144 | for (iter= biFactors; iter.hasItem(); iter++) |
---|
1145 | iter.getItem()= iter.getItem () (y + evaluation.getLast(), y); |
---|
1146 | CanonicalForm LCA= LC (Aeval.getFirst(), 1); |
---|
1147 | CanonicalForm yToLift= power (y, lift); |
---|
1148 | CFListIterator i= biFactors; |
---|
1149 | lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1; |
---|
1150 | i++; |
---|
1151 | |
---|
1152 | for (; i.hasItem(); i++) |
---|
1153 | lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1); |
---|
1154 | |
---|
1155 | lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift); |
---|
1156 | |
---|
1157 | i= biFactors; |
---|
1158 | yToLift= power (y, lift); |
---|
1159 | CanonicalForm dummy; |
---|
1160 | for (; i.hasItem(); i++) |
---|
1161 | { |
---|
1162 | LCA= LC (i.getItem(), 1); |
---|
1163 | extgcd (LCA, yToLift, LCA, dummy); |
---|
1164 | i.getItem()= mod (i.getItem()*LCA, yToLift); |
---|
1165 | } |
---|
1166 | |
---|
1167 | liftBoundsLength= F.level() - 1; |
---|
1168 | liftBounds= liftingBounds (A, lift); |
---|
1169 | |
---|
1170 | CFList MOD; |
---|
1171 | bool earlySuccess; |
---|
1172 | CFList earlyFactors; |
---|
1173 | ExtensionInfo info= ExtensionInfo (false); |
---|
1174 | CFList liftedFactors; |
---|
1175 | TIMING_START (fac_hensel_lift); |
---|
1176 | liftedFactors= henselLiftAndEarly |
---|
1177 | (A, MOD, liftBounds, earlySuccess, earlyFactors, |
---|
1178 | Aeval, biFactors, evaluation, info); |
---|
1179 | TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); |
---|
1180 | |
---|
1181 | TIMING_START (fac_factor_recombination); |
---|
1182 | factors= factorRecombination (A, liftedFactors, MOD); |
---|
1183 | TIMING_END_AND_PRINT (fac_factor_recombination, |
---|
1184 | "time for factor recombination: "); |
---|
1185 | |
---|
1186 | if (earlySuccess) |
---|
1187 | factors= Union (factors, earlyFactors); |
---|
1188 | |
---|
1189 | for (CFListIterator i= factors; i.hasItem(); i++) |
---|
1190 | { |
---|
1191 | int kk= Aeval.getLast().level(); |
---|
1192 | for (CFListIterator j= evaluation; j.hasItem(); j++, kk--) |
---|
1193 | { |
---|
1194 | if (i.getItem().level() < kk) |
---|
1195 | continue; |
---|
1196 | i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk); |
---|
1197 | } |
---|
1198 | } |
---|
1199 | } |
---|
1200 | |
---|
1201 | if (w.level() != 1) |
---|
1202 | { |
---|
1203 | for (CFListIterator iter= factors; iter.hasItem(); iter++) |
---|
1204 | iter.getItem()= swapvar (iter.getItem(), w, y); |
---|
1205 | } |
---|
1206 | |
---|
1207 | swap (factors, 0, 0, x); |
---|
1208 | append (factors, contentAFactors); |
---|
1209 | decompress (factors, N); |
---|
1210 | if (isOn (SW_RATIONAL)) |
---|
1211 | normalize (factors); |
---|
1212 | |
---|
1213 | delete [] leadingCoeffs2; |
---|
1214 | delete [] oldAeval; |
---|
1215 | delete [] Aeval2; |
---|
1216 | delete[] liftBounds; |
---|
1217 | |
---|
1218 | return factors; |
---|
1219 | } |
---|
1220 | |
---|
1221 | #endif |
---|