source: git/factory/facFactorize.cc @ 9b4920b

spielwiese
Last change on this file since 9b4920b was 9b4920b, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: extracted LC heuristic Conflicts: factory/facFqFactorize.h
  • Property mode set to 100644
File size: 26.9 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#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
31TIMING_DEFINE_PRINT(fac_bi_factorizer)
32TIMING_DEFINE_PRINT(fac_hensel_lift)
33TIMING_DEFINE_PRINT(fac_factor_recombination)
34TIMING_DEFINE_PRINT(fac_shift_to_zero)
35TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
36TIMING_DEFINE_PRINT(fac_evaluation)
37TIMING_DEFINE_PRINT(fac_recover_factors)
38TIMING_DEFINE_PRINT(fac_preprocess_and_content)
39TIMING_DEFINE_PRINT(fac_bifactor_total)
40TIMING_DEFINE_PRINT(fac_luckswang)
41TIMING_DEFINE_PRINT(fac_lcheuristic)
42TIMING_DEFINE_PRINT(fac_cleardenom)
43TIMING_DEFINE_PRINT(fac_content)
44TIMING_DEFINE_PRINT(fac_compress)
45
46#ifdef HAVE_NTL
47CFList 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
128void
129factorizationWRTDifferentSecondVars (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
165CFList
166multiFactorize (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    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2, uniFactors, w);
416
417  CanonicalForm oldA= A;
418  CFList oldBiFactors= biFactors;
419
420  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
421  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
422  leadingCoeffs.removeFirst();
423
424  if (!LCmultiplierIsConst)
425    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
426
427  //prepare leading coefficients
428  CFList* leadingCoeffs2= new CFList [lengthAeval2];
429  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
430                        evaluation);
431
432  CFListIterator iter;
433
434  Aeval= evaluateAtEval (A, evaluation, 2);
435
436  CanonicalForm hh= 1/Lc (Aeval.getFirst());
437
438  for (iter= Aeval; iter.hasItem(); iter++)
439    iter.getItem() *= hh;
440
441  A *= hh;
442
443  CFListIterator iter2;
444  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
445  bufBiFactors= biFactors;
446  bufA= A;
447  CanonicalForm bufLCmultiplier= LCmultiplier;
448  CanonicalForm testVars;
449  if (!LCmultiplierIsConst)
450  {
451    testVars= Variable (2);
452    for (int i= 0; i < lengthAeval2; i++)
453    {
454      if (!oldAeval[i].isEmpty())
455        testVars *= oldAeval[i].getFirst().mvar();
456    }
457  }
458  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
459                       "time to precompute LC over Q: ");
460
461  TIMING_START (fac_luckswang);
462  CFList bufFactors= CFList();
463  bool LCheuristic= false;
464  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
465                                factors))
466  {
467    int check= biFactors.length();
468    int * index= new int [factors.length()];
469    CFList oldFactors= factors;
470    factors= recoverFactors (A, factors, index);
471
472    if (check == factors.length())
473    {
474      if (w.level() != 1)
475      {
476        for (iter= factors; iter.hasItem(); iter++)
477          iter.getItem()= swapvar (iter.getItem(), w, y);
478      }
479
480      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
481      normalize (factors);
482      delete [] index;
483      delete [] Aeval2;
484      TIMING_END_AND_PRINT (fac_luckswang,
485                            "time for successful LucksWang over Q: ");
486      return factors;
487    }
488    else if (factors.length() > 0)
489    {
490      int oneCount= 0;
491      CFList l;
492      for (int i= 0; i < check; i++)
493      {
494        if (index[i] == 1)
495        {
496          iter=biFactors;
497          for (int j=1; j <= i-oneCount; j++)
498            iter++;
499          iter.remove (1);
500          for (int j= 0; j < lengthAeval2; j++)
501          {
502            l= leadingCoeffs2[j];
503            iter= l;
504            for (int k=1; k <= i-oneCount; k++)
505              iter++;
506            iter.remove (1);
507            leadingCoeffs2[j]=l;
508          }
509          oneCount++;
510        }
511      }
512      bufFactors= factors;
513      factors= CFList();
514    }
515    else if (!LCmultiplierIsConst && factors.length() == 0)
516    {
517      LCheuristic= true;
518      factors= oldFactors;
519      CanonicalForm cont;
520      CFList contents, LCs;
521      int index=1;
522      bool foundTrueMultiplier= false;
523      for (iter= factors; iter.hasItem(); iter++, index++)
524      {
525        cont= content (iter.getItem(), 1);
526        cont= gcd (cont , LCmultiplier);
527        contents.append (cont);
528        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
529        {
530          foundTrueMultiplier= true;
531          int index2= 1;
532          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
533                                                                    index2++)
534          {
535            if (index2 == index)
536              continue;
537            iter2.getItem() /= LCmultiplier;
538          }
539          A= oldA;
540          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
541          for (int i= lengthAeval2-1; i > -1; i--)
542            leadingCoeffs2[i]= CFList();
543          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
544                                biFactors, evaluation );
545          Aeval= evaluateAtEval (A, evaluation, 2);
546
547          hh= 1/Lc (Aeval.getFirst());
548
549          for (iter2= Aeval; iter2.hasItem(); iter2++)
550            iter2.getItem() *= hh;
551
552          A *= hh;
553          break;
554        }
555        else
556          LCs.append (LC (iter.getItem()/cont, 1));
557      }
558      if (!foundTrueMultiplier)
559      {
560        index= 1;
561        iter2= factors;
562        bool foundMultiplier= false;
563        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
564        {
565          if (fdivides (iter.getItem(), LCmultiplier))
566          {
567            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
568                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
569            {
570              Variable xx= Variable (2);
571              CanonicalForm vars;
572              vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
573                                        xx));
574              for (int i= 0; i < lengthAeval2; i++)
575              {
576                if (oldAeval[i].isEmpty())
577                  continue;
578                xx= oldAeval[i].getFirst().mvar();
579                vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
580                                           xx));
581              }
582              if (vars.level() <= 2)
583              {
584                int index2= 1;
585                for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
586                     iter3.hasItem(); iter3++, index2++)
587                {
588                  if (index2 == index)
589                  {
590                    iter3.getItem() /= LCmultiplier;
591                    break;
592                  }
593                }
594                A /= LCmultiplier;
595                foundMultiplier= true;
596                iter.getItem()= 1;
597              }
598            }
599          }
600        }
601        // coming from above: divide out more LCmultiplier if possible
602        if (foundMultiplier)
603        {
604          foundMultiplier= false;
605          index=1;
606          iter2= factors;
607          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
608          {
609            if (!iter.getItem().isOne() &&
610                fdivides (iter.getItem(), LCmultiplier))
611            {
612              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
613              {
614                int index2= 1;
615                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
616                     iter2++, index2++)
617                {
618                  if (index2 == index)
619                  {
620                    iter2.getItem() /= iter.getItem();
621                    foundMultiplier= true;
622                    break;
623                  }
624                }
625                A /= iter.getItem();
626                LCmultiplier /= iter.getItem();
627                iter.getItem()= 1;
628              }
629              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
630              {
631                Variable xx= Variable (2);
632                CanonicalForm vars;
633                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
634                                          xx));
635                for (int i= 0; i < lengthAeval2; i++)
636                {
637                  if (oldAeval[i].isEmpty())
638                    continue;
639                  xx= oldAeval[i].getFirst().mvar();
640                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
641                                             xx));
642                }
643                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
644                    /myGetVars (LCmultiplier) == vars)
645                {
646                  int index2= 1;
647                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
648                       iter2++, index2++)
649                  {
650                    if (index2 == index)
651                    {
652                      iter2.getItem() /= LCmultiplier;
653                      foundMultiplier= true;
654                      break;
655                    }
656                  }
657                  A /= LCmultiplier;
658                  iter.getItem()= 1;
659                }
660              }
661            }
662          }
663        }
664        else
665        {
666          CanonicalForm pLCs= prod (LCs);
667          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
668          {
669            A= oldA;
670            iter2= leadingCoeffs2[lengthAeval2-1];
671            for (iter= contents; iter.hasItem(); iter++, iter2++)
672              iter2.getItem() /= iter.getItem();
673            foundMultiplier= true;
674          }
675          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
676          {
677            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
678                         lengthAeval2, evaluation, oldBiFactors);
679          }
680        }
681
682        // patch everything together again
683        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
684        for (int i= lengthAeval2-1; i > -1; i--)
685          leadingCoeffs2[i]= CFList();
686        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
687                              evaluation);
688        Aeval= evaluateAtEval (A, evaluation, 2);
689
690        hh= 1/Lc (Aeval.getFirst());
691
692        for (CFListIterator i= Aeval; i.hasItem(); i++)
693          i.getItem() *= hh;
694
695        A *= hh;
696      }
697      factors= CFList();
698      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
699      {
700        LCheuristic= false;
701        A= bufA;
702        biFactors= bufBiFactors;
703        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
704        LCmultiplier= bufLCmultiplier;
705      }
706    }
707    else
708      factors= CFList();
709    delete [] index;
710  }
711  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
712
713  TIMING_START (fac_lcheuristic);
714  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
715      && fdivides (getVars (LCmultiplier), testVars))
716  {
717    LCheuristic= true;
718    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
719                 lengthAeval2, evaluation, oldBiFactors);
720
721    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
722    for (int i= lengthAeval2-1; i > -1; i--)
723      leadingCoeffs2[i]= CFList();
724    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
725                          evaluation);
726    Aeval= evaluateAtEval (A, evaluation, 2);
727
728    hh= 1/Lc (Aeval.getFirst());
729
730    for (CFListIterator i= Aeval; i.hasItem(); i++)
731      i.getItem() *= hh;
732
733    A *= hh;
734
735    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
736    {
737      LCheuristic= false;
738      A= bufA;
739      biFactors= bufBiFactors;
740      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
741      LCmultiplier= bufLCmultiplier;
742    }
743  }
744  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
745
746tryAgainWithoutHeu:
747  //shifting to zero
748  TIMING_START (fac_shift_to_zero);
749  CanonicalForm denA= bCommonDen (A);
750  A *= denA;
751  A= shift2Zero (A, Aeval, evaluation);
752  A /= denA;
753
754  for (iter= biFactors; iter.hasItem(); iter++)
755    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
756
757  for (int i= 0; i < lengthAeval2-1; i++)
758    leadingCoeffs2[i]= CFList();
759  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
760  {
761    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
762    for (int i= A.level() - 4; i > -1; i--)
763    {
764      if (i + 1 == lengthAeval2-1)
765        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
766      else
767        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
768    }
769  }
770  TIMING_END_AND_PRINT (fac_shift_to_zero,
771                        "time to shift evaluation point to zero: ");
772
773  CFArray Pi;
774  CFList diophant;
775  int* liftBounds= new int [A.level() - 1];
776  int liftBoundsLength= A.level() - 1;
777  for (int i= 0; i < liftBoundsLength; i++)
778    liftBounds [i]= degree (A, i + 2) + 1;
779
780  Aeval.removeFirst();
781  bool noOneToOne= false;
782
783  TIMING_START (fac_cleardenom);
784  CFList commonDenominators;
785  for (iter=biFactors; iter.hasItem(); iter++)
786    commonDenominators.append (bCommonDen (iter.getItem()));
787  CanonicalForm tmp1, tmp2, tmp3=1;
788  for (int i= 0; i < lengthAeval2; i++)
789  {
790    iter2= commonDenominators;
791    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
792    {
793      tmp1= bCommonDen (iter.getItem());
794      Off (SW_RATIONAL);
795      iter2.getItem()= lcm (iter2.getItem(), tmp1);
796      On (SW_RATIONAL);
797    }
798  }
799  tmp1= prod (commonDenominators);
800  for (iter= Aeval; iter.hasItem(); iter++)
801  {
802    tmp2= bCommonDen (iter.getItem()/denA);
803    Off (SW_RATIONAL);
804    tmp3= lcm (tmp2,tmp3);
805    On (SW_RATIONAL);
806  }
807  CanonicalForm multiplier;
808  multiplier= tmp3/tmp1;
809  iter2= commonDenominators;
810  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
811    iter.getItem() *= iter2.getItem()*multiplier;
812
813  for (iter= Aeval; iter.hasItem(); iter++)
814    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
815
816  for (int i= 0; i < lengthAeval2; i++)
817  {
818    iter2= commonDenominators;
819    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
820      iter.getItem() *= iter2.getItem()*multiplier;
821  }
822  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
823
824  TIMING_START (fac_hensel_lift);
825  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
826                               Pi, liftBounds, liftBoundsLength, noOneToOne);
827  TIMING_END_AND_PRINT (fac_hensel_lift,
828                        "time for non monic hensel lifting over Q: ");
829
830  if (!noOneToOne)
831  {
832    int check= factors.length();
833    A= oldA;
834    TIMING_START (fac_recover_factors);
835    factors= recoverFactors (A, factors, evaluation);
836    TIMING_END_AND_PRINT (fac_recover_factors,
837                          "time to recover factors over Q: ");
838    if (check != factors.length())
839      noOneToOne= true;
840    else
841      factors= Union (factors, bufFactors);
842  }
843  if (noOneToOne)
844  {
845    if (!LCmultiplierIsConst && LCheuristic)
846    {
847      A= bufA;
848      biFactors= bufBiFactors;
849      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
850      delete [] liftBounds;
851      LCheuristic= false;
852      goto tryAgainWithoutHeu;
853      //something probably went wrong in the heuristic
854    }
855
856    A= shift2Zero (oldA, Aeval, evaluation);
857    biFactors= oldBiFactors;
858    for (iter= biFactors; iter.hasItem(); iter++)
859      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
860    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
861    CanonicalForm yToLift= power (y, lift);
862    CFListIterator i= biFactors;
863    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
864    i++;
865
866    for (; i.hasItem(); i++)
867      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
868
869    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
870
871    i= biFactors;
872    yToLift= power (y, lift);
873    CanonicalForm dummy;
874    for (; i.hasItem(); i++)
875    {
876      LCA= LC (i.getItem(), 1);
877      extgcd (LCA, yToLift, LCA, dummy);
878      i.getItem()= mod (i.getItem()*LCA, yToLift);
879    }
880
881    liftBoundsLength= F.level() - 1;
882    liftBounds= liftingBounds (A, lift);
883
884    CFList MOD;
885    bool earlySuccess;
886    CFList earlyFactors;
887    ExtensionInfo info= ExtensionInfo (false);
888    CFList liftedFactors;
889    TIMING_START (fac_hensel_lift);
890    liftedFactors= henselLiftAndEarly
891                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
892                    Aeval, biFactors, evaluation, info);
893    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
894
895    TIMING_START (fac_factor_recombination);
896    factors= factorRecombination (A, liftedFactors, MOD);
897    TIMING_END_AND_PRINT (fac_factor_recombination,
898                          "time for factor recombination: ");
899
900    if (earlySuccess)
901      factors= Union (factors, earlyFactors);
902
903    for (CFListIterator i= factors; i.hasItem(); i++)
904    {
905      int kk= Aeval.getLast().level();
906      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
907      {
908        if (i.getItem().level() < kk)
909          continue;
910       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
911      }
912    }
913  }
914
915  if (w.level() != 1)
916  {
917    for (CFListIterator iter= factors; iter.hasItem(); iter++)
918      iter.getItem()= swapvar (iter.getItem(), w, y);
919  }
920
921  swap (factors, 0, 0, x);
922  append (factors, contentAFactors);
923  decompress (factors, N);
924  if (isOn (SW_RATIONAL))
925    normalize (factors);
926
927  delete [] leadingCoeffs2;
928  delete [] oldAeval;
929  delete [] Aeval2;
930  delete[] liftBounds;
931
932  return factors;
933}
934
935#endif
Note: See TracBrowser for help on using the repository browser.