source: git/factory/facFactorize.cc @ fcd296

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