source: git/factory/facFactorize.cc @ a0efc8

spielwiese
Last change on this file since a0efc8 was a0efc8, checked in by Hans Schoenemann <hannes@…>, 3 years ago
comments: multivariate Factroization over Qa, w/o NTL
  • Property mode set to 100644
File size: 23.5 KB
Line 
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
14#include "config.h"
15
16
17#include "cf_assert.h"
18#include "debug.h"
19#include "timing.h"
20
21#include "cf_algorithm.h"
22#include "facFqFactorizeUtil.h"
23#include "facFactorize.h"
24#include "facFqFactorize.h"
25#include "cf_random.h"
26#include "facHensel.h"
27#include "cf_map_ext.h"
28#include "cf_reval.h"
29#include "facSparseHensel.h"
30#include "cfUnivarGcd.h"
31
32TIMING_DEFINE_PRINT(fac_bi_factorizer)
33TIMING_DEFINE_PRINT(fac_hensel_lift)
34TIMING_DEFINE_PRINT(fac_factor_recombination)
35TIMING_DEFINE_PRINT(fac_shift_to_zero)
36TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
37TIMING_DEFINE_PRINT(fac_evaluation)
38TIMING_DEFINE_PRINT(fac_recover_factors)
39TIMING_DEFINE_PRINT(fac_preprocess_and_content)
40TIMING_DEFINE_PRINT(fac_bifactor_total)
41TIMING_DEFINE_PRINT(fac_luckswang)
42TIMING_DEFINE_PRINT(fac_lcheuristic)
43TIMING_DEFINE_PRINT(fac_cleardenom)
44TIMING_DEFINE_PRINT(fac_content)
45TIMING_DEFINE_PRINT(fac_compress)
46
47CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
48{
49  CFList result;
50  Variable x= Variable (1);
51
52  CanonicalForm LCF=LC (F,x);
53  CFList LCFeval;
54
55  bool found= false;
56  bool allZero= true;
57  bool foundZero= false;
58  CanonicalForm deriv_x, gcd_deriv;
59  CFListIterator iter;
60  do
61  {
62    eval.insert (F);
63    LCFeval.insert (LCF);
64    bool bad= false;
65    for (int i= E.max(); i >= E.min(); i--)
66    {
67      eval.insert (eval.getFirst()( E [i], i));
68      LCFeval.insert (LCFeval.getFirst() (E [i], i));
69      result.append (E[i]);
70      if (!E[i].isZero())
71        allZero= false;
72      else
73        foundZero= true;
74      if (!allZero && foundZero)
75      {
76        result= CFList();
77        eval= CFList();
78        LCFeval= CFList();
79        bad= true;
80        foundZero= false;
81        break;
82      }
83      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
84      {
85        result= CFList();
86        eval= CFList();
87        LCFeval= CFList();
88        bad= true;
89        break;
90      }
91      if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
92      {
93        result= CFList();
94        eval= CFList();
95        LCFeval= CFList();
96        bad= true;
97        break;
98      }
99    }
100
101    if (bad)
102    {
103      E.nextpoint();
104      continue;
105    }
106
107    if (degree (eval.getFirst()) != degree (F, 1))
108    {
109      result= CFList();
110      eval= CFList();
111      LCFeval= CFList();
112      E.nextpoint();
113      continue;
114    }
115
116    deriv_x= deriv (eval.getFirst(), x);
117    gcd_deriv= gcd (eval.getFirst(), deriv_x);
118    if (degree (gcd_deriv) > 0)
119    {
120      result= CFList();
121      eval= CFList();
122      LCFeval= CFList();
123      E.nextpoint();
124      continue;
125    }
126    iter= eval;
127    iter++;
128    CanonicalForm contentx= content (iter.getItem(), x);
129    if (degree (contentx) > 0)
130    {
131      result= CFList();
132      eval= CFList();
133      LCFeval= CFList();
134      E.nextpoint();
135      continue;
136    }
137    contentx= content (iter.getItem());
138    if (degree (contentx) > 0)
139    {
140      result= CFList();
141      eval= CFList();
142      LCFeval= CFList();
143      E.nextpoint();
144      continue;
145    }
146    found= true;
147  }
148  while (!found);
149
150  if (!eval.isEmpty())
151    eval.removeFirst();
152  return result;
153}
154
155
156#ifdef HAVE_NTL // ratBiSqrfFactorize
157void
158factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
159                                     int& minFactorsLength, bool& irred,
160                                     const Variable& w)
161{
162  Variable x= Variable (1);
163  minFactorsLength= 0;
164  irred= false;
165  Variable v;
166  CFList factors;
167  CanonicalForm LCA= LC (A,1);
168  for (int j= 0; j < A.level() - 2; j++)
169  {
170    if (!Aeval[j].isEmpty())
171    {
172      v= Variable (Aeval[j].getFirst().level());
173
174      factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
175      if (factors.getFirst().inCoeffDomain())
176        factors.removeFirst();
177
178      if (minFactorsLength == 0)
179        minFactorsLength= factors.length();
180      else
181        minFactorsLength= tmin (minFactorsLength, factors.length());
182
183      if (factors.length() == 1)
184      {
185        irred= true;
186        return;
187      }
188      sortList (factors, x);
189      Aeval [j]= factors;
190    }
191  }
192}
193#endif
194
195#ifdef HAVE_NTL // precomputeLeadingCoeff,
196// henselLiftAndEarly, nonMonicHenselLift
197CFList
198multiFactorize (const CanonicalForm& F, const Variable& v)
199{
200  if (F.inCoeffDomain())
201    return CFList (F);
202
203  TIMING_START (fac_preprocess_and_content);
204  // compress and find main Variable
205  CFMap N;
206  TIMING_START (fac_compress)
207  CanonicalForm A= myCompress (F, N);
208  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
209
210  //univariate case
211  if (F.isUnivariate())
212  {
213    CFList result;
214    if (v.level() != 1)
215      result= conv (factorize (F, v));
216    else
217      result= conv (factorize (F,true));
218    if (result.getFirst().inCoeffDomain())
219      result.removeFirst();
220    return result;
221  }
222
223  //bivariate case
224  if (A.level() == 2)
225  {
226    CFList buf= ratBiSqrfFactorize (F, v);
227    if (buf.getFirst().inCoeffDomain())
228      buf.removeFirst();
229    return buf;
230  }
231
232  Variable x= Variable (1);
233  Variable y= Variable (2);
234
235  // remove content
236  TIMING_START (fac_content);
237  CFList contentAi;
238  CanonicalForm lcmCont= lcmContent (A, contentAi);
239  A /= lcmCont;
240  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
241
242  // trivial after content removal
243  CFList contentAFactors;
244  if (A.inCoeffDomain())
245  {
246    for (CFListIterator i= contentAi; i.hasItem(); i++)
247    {
248      if (i.getItem().inCoeffDomain())
249        continue;
250      else
251      {
252        lcmCont /= i.getItem();
253        contentAFactors=
254        Union (multiFactorize (lcmCont, v),
255               multiFactorize (i.getItem(), v));
256        break;
257      }
258    }
259    decompress (contentAFactors, N);
260    if (isOn (SW_RATIONAL))
261      normalize (contentAFactors);
262    return contentAFactors;
263  }
264
265  // factorize content
266  TIMING_START (fac_content);
267  contentAFactors= multiFactorize (lcmCont, v);
268  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
269
270  // univariate after content removal
271  CFList factors;
272  if (A.isUnivariate ())
273  {
274    if (v.level() != 1)
275      factors= conv (factorize (A, v));
276    else
277      factors= conv (factorize (A,true));
278    append (factors, contentAFactors);
279    decompress (factors, N);
280    return factors;
281  }
282
283  A *= bCommonDen (A);
284  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
285  int factorNums= 2;
286  //p is irreducible. But factorize does not recognizes this. However, if you
287  //change factorNums to 2 at line 281 in facFactorize.cc it will. That change
288  //might impair performance in some cases since you do twice as many
289  //bivariate factorizations as before. Otherwise you need to change
290  //precomputeLeadingCoeff to detect these cases and trigger more bivariate
291  // factorizations.
292  // (http://www.singular.uni-kl.de:8002/trac/ticket/666)
293  CFList biFactors, bufBiFactors;
294  CanonicalForm evalPoly;
295  int lift, bufLift, lengthAeval2= A.level()-2;
296  CFList* bufAeval2= new CFList [lengthAeval2];
297  CFList* Aeval2= new CFList [lengthAeval2];
298  int counter;
299  int differentSecondVar= 0;
300  CanonicalForm bufA;
301  TIMING_END_AND_PRINT (fac_preprocess_and_content,
302                       "time to preprocess poly and extract content over Q: ");
303
304  // several bivariate factorizations
305  TIMING_START (fac_bifactor_total);
306  REvaluation E (2, A.level(), IntRandom (25));
307  for (int i= 0; i < factorNums; i++)
308  {
309    counter= 0;
310    bufA= A;
311    bufAeval= CFList();
312    TIMING_START (fac_evaluation);
313    bufEvaluation= evalPoints (bufA, bufAeval, E);
314    TIMING_END_AND_PRINT (fac_evaluation,
315                          "time to find evaluation point over Q: ");
316    E.nextpoint();
317    evalPoly= 0;
318
319    TIMING_START (fac_evaluation);
320    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
321    TIMING_END_AND_PRINT (fac_evaluation,
322                          "time to eval wrt diff second vars over Q: ");
323
324    for (int j= 0; j < lengthAeval2; j++)
325    {
326      if (!bufAeval2[j].isEmpty())
327        counter++;
328    }
329
330    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
331
332    TIMING_START (fac_bi_factorizer);
333    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
334    TIMING_END_AND_PRINT (fac_bi_factorizer,
335                          "time for bivariate factorization: ");
336    bufBiFactors.removeFirst();
337
338    if (bufBiFactors.length() == 1)
339    {
340      factors.append (A);
341      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
342      if (isOn (SW_RATIONAL))
343        normalize (factors);
344      delete [] bufAeval2;
345      delete [] Aeval2;
346      return factors;
347    }
348
349    if (i == 0)
350    {
351      Aeval= bufAeval;
352      evaluation= bufEvaluation;
353      biFactors= bufBiFactors;
354      lift= bufLift;
355      for (int j= 0; j < lengthAeval2; j++)
356        Aeval2 [j]= bufAeval2 [j];
357      differentSecondVar= counter;
358    }
359    else
360    {
361      if (bufBiFactors.length() < biFactors.length() ||
362          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
363          counter > differentSecondVar)
364      {
365        Aeval= bufAeval;
366        evaluation= bufEvaluation;
367        biFactors= bufBiFactors;
368        lift= bufLift;
369        for (int j= 0; j < lengthAeval2; j++)
370          Aeval2 [j]= bufAeval2 [j];
371        differentSecondVar= counter;
372      }
373    }
374    int k= 0;
375    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
376      evalPoly += j.getItem()*power (x, k);
377    list.append (evalPoly);
378  }
379
380  delete [] bufAeval2;
381
382  sortList (biFactors, x);
383
384  int minFactorsLength;
385  bool irred= false;
386  TIMING_START (fac_bi_factorizer);
387  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
388  TIMING_END_AND_PRINT (fac_bi_factorizer,
389             "time for bivariate factorization wrt diff second vars over Q: ");
390
391  TIMING_END_AND_PRINT (fac_bifactor_total,
392                        "total time for eval and bivar factors over Q: ");
393  if (irred)
394  {
395    factors.append (A);
396    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
397    if (isOn (SW_RATIONAL))
398      normalize (factors);
399    delete [] Aeval2;
400    return factors;
401  }
402
403  if (minFactorsLength == 0)
404    minFactorsLength= biFactors.length();
405  else if (biFactors.length() > minFactorsLength)
406    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
407  minFactorsLength= tmin (minFactorsLength, biFactors.length());
408
409  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
410
411  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
412
413  minFactorsLength= tmin (minFactorsLength, biFactors.length());
414
415  if (minFactorsLength == 1)
416  {
417    factors.append (A);
418    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
419    if (isOn (SW_RATIONAL))
420      normalize (factors);
421    delete [] Aeval2;
422    return factors;
423  }
424
425  if (differentSecondVar == lengthAeval2)
426  {
427    bool zeroOccured= false;
428    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
429    {
430      if (iter.getItem().isZero())
431      {
432        zeroOccured= true;
433        break;
434      }
435    }
436    if (!zeroOccured)
437    {
438      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
439                                minFactorsLength);
440      if (factors.length() == biFactors.length())
441      {
442        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
443        normalize (factors);
444        delete [] Aeval2;
445        return factors;
446      }
447      else
448        factors= CFList();
449      //TODO case where factors.length() > 0
450    }
451  }
452
453  CFList * oldAeval= new CFList [lengthAeval2];
454  for (int i= 0; i < lengthAeval2; i++)
455    oldAeval[i]= Aeval2[i];
456
457  getLeadingCoeffs (A, Aeval2);
458
459  CFList biFactorsLCs;
460  for (CFListIterator i= biFactors; i.hasItem(); i++)
461    biFactorsLCs.append (LC (i.getItem(), 1));
462
463  Variable w;
464  TIMING_START (fac_precompute_leadcoeff);
465  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
466                                          evaluation, Aeval2, lengthAeval2, w);
467
468  if (w.level() != 1)
469    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
470                          uniFactors, w);
471
472  CanonicalForm oldA= A;
473  CFList oldBiFactors= biFactors;
474
475  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
476  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
477  leadingCoeffs.removeFirst();
478
479  if (!LCmultiplierIsConst)
480    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
481
482  //prepare leading coefficients
483  CFList* leadingCoeffs2= new CFList [lengthAeval2];
484  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
485                        biFactors, evaluation);
486
487  CFListIterator iter;
488  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
489  bufBiFactors= biFactors;
490  bufA= A;
491  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
492  if (!LCmultiplierIsConst)
493  {
494    testVars= Variable (2);
495    for (int i= 0; i < lengthAeval2; i++)
496    {
497      if (!oldAeval[i].isEmpty())
498        testVars *= oldAeval[i].getFirst().mvar();
499    }
500  }
501  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
502                       "time to precompute LC over Q: ");
503
504  TIMING_START (fac_luckswang);
505  CFList bufFactors= CFList();
506  bool LCheuristic= false;
507  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
508                                factors))
509  {
510    int check= biFactors.length();
511    int * index= new int [factors.length()];
512    CFList oldFactors= factors;
513    factors= recoverFactors (A, factors, index);
514
515    if (check == factors.length())
516    {
517      if (w.level() != 1)
518      {
519        for (iter= factors; iter.hasItem(); iter++)
520          iter.getItem()= swapvar (iter.getItem(), w, y);
521      }
522
523      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
524      normalize (factors);
525      delete [] index;
526      delete [] Aeval2;
527      TIMING_END_AND_PRINT (fac_luckswang,
528                            "time for successful LucksWang over Q: ");
529      return factors;
530    }
531    else if (factors.length() > 0)
532    {
533      int oneCount= 0;
534      CFList l;
535      for (int i= 0; i < check; i++)
536      {
537        if (index[i] == 1)
538        {
539          iter=biFactors;
540          for (int j=1; j <= i-oneCount; j++)
541            iter++;
542          iter.remove (1);
543          for (int j= 0; j < lengthAeval2; j++)
544          {
545            l= leadingCoeffs2[j];
546            iter= l;
547            for (int k=1; k <= i-oneCount; k++)
548              iter++;
549            iter.remove (1);
550            leadingCoeffs2[j]=l;
551          }
552          oneCount++;
553        }
554      }
555      bufFactors= factors;
556      factors= CFList();
557    }
558    else if (!LCmultiplierIsConst && factors.length() == 0)
559    {
560      LCheuristic= true;
561      factors= oldFactors;
562      CFList contents, LCs;
563      bool foundTrueMultiplier= false;
564      LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
565                    contents, LCs, foundTrueMultiplier);
566      if (foundTrueMultiplier)
567      {
568          A= oldA;
569          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
570          for (int i= lengthAeval2-1; i > -1; i--)
571            leadingCoeffs2[i]= CFList();
572          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
573                                leadingCoeffs, biFactors, evaluation);
574      }
575      else
576      {
577        bool foundMultiplier= false;
578        LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
579                      A, leadingCoeffs2, lengthAeval2, foundMultiplier);
580        // coming from above: divide out more LCmultiplier if possible
581        if (foundMultiplier)
582        {
583          foundMultiplier= false;
584          LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
585                        lengthAeval2, leadingCoeffs2, A, LCmultiplier,
586                        foundMultiplier);
587        }
588        else
589        {
590          LCHeuristicCheck (LCs, contents, A, oldA,
591                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
592          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
593          {
594            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
595                         lengthAeval2, evaluation, oldBiFactors);
596          }
597        }
598
599        // patch everything together again
600        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
601        for (int i= lengthAeval2-1; i > -1; i--)
602          leadingCoeffs2[i]= CFList();
603        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
604                              biFactors, evaluation);
605      }
606      factors= CFList();
607      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
608      {
609        LCheuristic= false;
610        A= bufA;
611        biFactors= bufBiFactors;
612        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
613        LCmultiplier= bufLCmultiplier;
614      }
615    }
616    else
617      factors= CFList();
618    delete [] index;
619  }
620  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
621
622  TIMING_START (fac_lcheuristic);
623  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
624      && fdivides (getVars (LCmultiplier), testVars))
625  {
626    LCheuristic= true;
627    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
628                 lengthAeval2, evaluation, oldBiFactors);
629
630    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
631    for (int i= lengthAeval2-1; i > -1; i--)
632      leadingCoeffs2[i]= CFList();
633    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
634                          biFactors, evaluation);
635
636    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
637    {
638      LCheuristic= false;
639      A= bufA;
640      biFactors= bufBiFactors;
641      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
642      LCmultiplier= bufLCmultiplier;
643    }
644  }
645  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
646
647tryAgainWithoutHeu:
648  //shifting to zero
649  TIMING_START (fac_shift_to_zero);
650  CanonicalForm denA= bCommonDen (A);
651  A *= denA;
652  A= shift2Zero (A, Aeval, evaluation);
653  A /= denA;
654
655  for (iter= biFactors; iter.hasItem(); iter++)
656    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
657
658  for (int i= 0; i < lengthAeval2-1; i++)
659    leadingCoeffs2[i]= CFList();
660  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
661  {
662    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
663    for (int i= A.level() - 4; i > -1; i--)
664    {
665      if (i + 1 == lengthAeval2-1)
666        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
667      else
668        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
669    }
670  }
671  TIMING_END_AND_PRINT (fac_shift_to_zero,
672                        "time to shift evaluation point to zero: ");
673
674  CFArray Pi;
675  CFList diophant;
676  int* liftBounds= new int [A.level() - 1];
677  int liftBoundsLength= A.level() - 1;
678  for (int i= 0; i < liftBoundsLength; i++)
679    liftBounds [i]= degree (A, i + 2) + 1;
680
681  Aeval.removeFirst();
682  bool noOneToOne= false;
683
684  TIMING_START (fac_cleardenom);
685  CFList commonDenominators;
686  for (iter=biFactors; iter.hasItem(); iter++)
687    commonDenominators.append (bCommonDen (iter.getItem()));
688  CanonicalForm tmp1, tmp2, tmp3=1;
689  CFListIterator iter2;
690  for (int i= 0; i < lengthAeval2; i++)
691  {
692    iter2= commonDenominators;
693    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
694    {
695      tmp1= bCommonDen (iter.getItem());
696      Off (SW_RATIONAL);
697      iter2.getItem()= lcm (iter2.getItem(), tmp1);
698      On (SW_RATIONAL);
699    }
700  }
701  tmp1= prod (commonDenominators);
702  for (iter= Aeval; iter.hasItem(); iter++)
703  {
704    tmp2= bCommonDen (iter.getItem()/denA);
705    Off (SW_RATIONAL);
706    tmp3= lcm (tmp2,tmp3);
707    On (SW_RATIONAL);
708  }
709  CanonicalForm multiplier;
710  multiplier= tmp3/tmp1;
711  iter2= commonDenominators;
712  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
713    iter.getItem() *= iter2.getItem()*multiplier;
714
715  for (iter= Aeval; iter.hasItem(); iter++)
716    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
717
718  for (int i= 0; i < lengthAeval2; i++)
719  {
720    iter2= commonDenominators;
721    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
722      iter.getItem() *= iter2.getItem()*multiplier;
723  }
724  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
725
726  TIMING_START (fac_hensel_lift);
727  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
728                               Pi, liftBounds, liftBoundsLength, noOneToOne);
729  TIMING_END_AND_PRINT (fac_hensel_lift,
730                        "time for non monic hensel lifting over Q: ");
731
732  if (!noOneToOne)
733  {
734    int check= factors.length();
735    A= oldA;
736    TIMING_START (fac_recover_factors);
737    factors= recoverFactors (A, factors, evaluation);
738    TIMING_END_AND_PRINT (fac_recover_factors,
739                          "time to recover factors over Q: ");
740    if (check != factors.length())
741      noOneToOne= true;
742    else
743      factors= Union (factors, bufFactors);
744  }
745  if (noOneToOne)
746  {
747    if (!LCmultiplierIsConst && LCheuristic)
748    {
749      A= bufA;
750      biFactors= bufBiFactors;
751      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
752      delete [] liftBounds;
753      LCheuristic= false;
754      goto tryAgainWithoutHeu;
755      //something probably went wrong in the heuristic
756    }
757
758    A= shift2Zero (oldA, Aeval, evaluation);
759    biFactors= oldBiFactors;
760    for (iter= biFactors; iter.hasItem(); iter++)
761      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
762    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
763    CanonicalForm yToLift= power (y, lift);
764    CFListIterator i= biFactors;
765    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
766    i++;
767
768    for (; i.hasItem(); i++)
769      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
770
771    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
772
773    i= biFactors;
774    yToLift= power (y, lift);
775    CanonicalForm dummy;
776    for (; i.hasItem(); i++)
777    {
778      LCA= LC (i.getItem(), 1);
779      extgcd (LCA, yToLift, LCA, dummy);
780      i.getItem()= mod (i.getItem()*LCA, yToLift);
781    }
782
783    liftBoundsLength= F.level() - 1;
784    liftBounds= liftingBounds (A, lift);
785
786    CFList MOD;
787    bool earlySuccess;
788    CFList earlyFactors;
789    ExtensionInfo info= ExtensionInfo (false);
790    CFList liftedFactors;
791    TIMING_START (fac_hensel_lift);
792    liftedFactors= henselLiftAndEarly
793                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
794                    Aeval, biFactors, evaluation, info);
795    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
796
797    TIMING_START (fac_factor_recombination);
798    factors= factorRecombination (A, liftedFactors, MOD);
799    TIMING_END_AND_PRINT (fac_factor_recombination,
800                          "time for factor recombination: ");
801
802    if (earlySuccess)
803      factors= Union (factors, earlyFactors);
804
805    for (CFListIterator i= factors; i.hasItem(); i++)
806    {
807      int kk= Aeval.getLast().level();
808      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
809      {
810        if (i.getItem().level() < kk)
811          continue;
812       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
813      }
814    }
815  }
816
817  if (w.level() != 1)
818  {
819    for (CFListIterator iter= factors; iter.hasItem(); iter++)
820      iter.getItem()= swapvar (iter.getItem(), w, y);
821  }
822
823  append (factors, contentAFactors);
824  decompress (factors, N);
825  if (isOn (SW_RATIONAL))
826    normalize (factors);
827
828  delete [] leadingCoeffs2;
829  delete [] oldAeval;
830  delete [] Aeval2;
831  delete[] liftBounds;
832
833  return factors;
834}
835#endif
Note: See TracBrowser for help on using the repository browser.