source: git/factory/facFactorize.cc @ a0adc3

spielwiese
Last change on this file since a0adc3 was a0adc3, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: deleted unused parameters from getLeadingCoeffs
  • Property mode set to 100644
File size: 36.7 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  {
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
1032tryAgainWithoutHeu:
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
Note: See TracBrowser for help on using the repository browser.