source: git/factory/facFactorize.cc @ 8e452c9

jengelh-datetimespielwiese
Last change on this file since 8e452c9 was 8e452c9, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: distribute content in precomputeLeadingCoeff
  • Property mode set to 100644
File size: 37.1 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 (1);
416          result= distributeContent (result, differentSecondVarLCs, length);
417          if (!result.getFirst().inCoeffDomain())
418          {
419            CFListIterator iter= result;
420            CanonicalForm tmp= iter.getItem();
421            iter++;
422            for (; iter.hasItem(); iter++)
423              iter.getItem() *= tmp;
424          }
425
426          y= Variable (1);
427          delete [] bufSqrfFactors;
428          return result;
429        }
430      }
431    }
432  }
433  if (!pass)
434  {
435    CFList result;
436    result.append (LCF);
437    for (int j= 1; j <= factors.length(); j++)
438      result.append (LCF);
439    y= Variable (1);
440    delete [] bufSqrfFactors;
441    return result;
442  }
443  else
444    factors= bufFactors;
445
446
447  bufFactors= factors;
448
449  CFMap MM, NN;
450  dummy [0]= sqrfPartF;
451  dummy [1]= 1;
452  compress (dummy, MM, NN);
453  sqrfPartF= MM (sqrfPartF);
454  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
455  for (CFListIterator iter= factors; iter.hasItem(); iter++)
456    iter.getItem()= MM (iter.getItem());
457
458  CFList evaluation2;
459  for (int i= 2; i <= varsSqrfPartF.level(); i++)
460    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
461
462  CFList interMedResult;
463  CanonicalForm oldSqrfPartF= sqrfPartF;
464  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
465  if (factors.length() > 1)
466  {
467    CanonicalForm LC1= LC (oldSqrfPartF, 1);
468    CFList leadingCoeffs;
469    for (int i= 0; i < factors.length(); i++)
470      leadingCoeffs.append (LC1);
471
472    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
473    CFList oldFactors= factors;
474    for (CFListIterator i= oldFactors; i.hasItem(); i++)
475      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
476
477    bool success= false;
478    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
479    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
480        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
481                                  oldFactors, 2, leadingCoeffs, factors))
482    {
483      interMedResult= recoverFactors (oldSqrfPartF, factors);
484      if (oldFactors.length() == interMedResult.length())
485        success= true;
486    }
487    if (!success)
488    {
489      LC1= LC (evalSqrfPartF.getFirst(), 1);
490
491      CFArray leadingCoeffs= CFArray (factors.length());
492      for (int i= 0; i < factors.length(); i++)
493        leadingCoeffs[i]= LC1;
494
495      for (CFListIterator i= factors; i.hasItem(); i++)
496        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
497      factors.insert (1);
498
499      CanonicalForm
500      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
501
502      int liftBound= degree (newSqrfPartF,2) + 1;
503
504      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
505      CFArray Pi;
506      CFList diophant;
507      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
508                            leadingCoeffs, false);
509
510      if (sqrfPartF.level() > 2)
511      {
512        int* liftBounds= new int [sqrfPartF.level() - 1];
513        liftBounds [0]= liftBound;
514        bool noOneToOne= false;
515        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
516        LC1= LC (evalSqrfPartF.getLast(), 1);
517        CFList LCs;
518        for (int i= 0; i < factors.length(); i++)
519          LCs.append (LC1);
520        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
521        for (int i= sqrfPartF.level() - 1; i > 2; i--)
522        {
523          for (CFListIterator j= LCs; j.hasItem(); j++)
524            j.getItem()= j.getItem() (0, i + 1);
525          leadingCoeffs2 [i - 3]= LCs;
526        }
527        sqrfPartF *= power (LC1, factors.length()-1);
528
529        int liftBoundsLength= sqrfPartF.level() - 1;
530        for (int i= 1; i < liftBoundsLength; i++)
531          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
532        evalSqrfPartF= evaluateAtZero (sqrfPartF);
533        evalSqrfPartF.removeFirst();
534        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
535                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
536        delete [] leadingCoeffs2;
537        delete [] liftBounds;
538      }
539      for (CFListIterator iter= factors; iter.hasItem(); iter++)
540        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
541
542      interMedResult=
543      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
544                      factors);
545    }
546  }
547  else
548  {
549    CanonicalForm contF=content (oldSqrfPartF,1);
550    factors= CFList (oldSqrfPartF/contF);
551    interMedResult= recoverFactors (oldSqrfPartF, factors);
552  }
553
554  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
555    iter.getItem()= NN (iter.getItem());
556
557  CFList result;
558  CFFListIterator k;
559  CanonicalForm tmp;
560  for (int i= 0; i < LCFFactors.length(); i++)
561  {
562    tmp= 1;
563    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
564    {
565      int pos= findItem (bufFactors, k.getItem().factor());
566      if (pos)
567        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
568    }
569    result.append (tmp);
570  }
571
572  for (CFListIterator i= result; i.hasItem(); i++)
573  {
574    F /= i.getItem();
575    if (foundDifferent)
576      i.getItem()= swapvar (i.getItem(), x, z);
577    i.getItem()= N (i.getItem());
578  }
579
580  if (foundDifferent)
581  {
582    CFList l= differentSecondVarLCs [j];
583    for (CFListIterator i= l; i.hasItem(); i++)
584      i.getItem()= swapvar (i.getItem(), y, z);
585    differentSecondVarLCs [j]= l;
586    F= swapvar (F, x, z);
587  }
588
589  result.insert (N (F));
590
591  result= distributeContent (result, differentSecondVarLCs, length);
592
593  if (!result.getFirst().inCoeffDomain())
594  {
595    CFListIterator i= result;
596    CanonicalForm tmp;
597    if (foundDifferent)
598      i.getItem()= swapvar (i.getItem(), Variable (2), y);
599
600    tmp= i.getItem();
601
602    i++;
603    for (; i.hasItem(); i++)
604    {
605      if (foundDifferent)
606        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
607      else
608        i.getItem() *= tmp;
609    }
610  }
611  else
612    y= Variable (1);
613
614  delete [] bufSqrfFactors;
615
616  return result;
617}
618
619
620CFList
621multiFactorize (const CanonicalForm& F, const Variable& v)
622{
623  if (F.inCoeffDomain())
624    return CFList (F);
625
626  // compress and find main Variable
627  CFMap N;
628  CanonicalForm A= myCompress (F, N);
629
630  //univariate case
631  if (F.isUnivariate())
632  {
633    CFList result;
634    if (v.level() != 1)
635      result= conv (factorize (F, v));
636    else
637      result= conv (factorize (F,true));
638    if (result.getFirst().inCoeffDomain())
639      result.removeFirst();
640    return result;
641  }
642
643  //bivariate case
644  if (A.level() == 2)
645  {
646    CFList buf= biFactorize (F, v);
647    return buf;
648  }
649
650  Variable x= Variable (1);
651  Variable y= Variable (2);
652
653  // remove content
654  CFList contentAi;
655  CanonicalForm lcmCont= lcmContent (A, contentAi);
656  A /= lcmCont;
657
658  // trivial after content removal
659  CFList contentAFactors;
660  if (A.inCoeffDomain())
661  {
662    for (CFListIterator i= contentAi; i.hasItem(); i++)
663    {
664      if (i.getItem().inCoeffDomain())
665        continue;
666      else
667      {
668        lcmCont /= i.getItem();
669        contentAFactors=
670        Union (multiFactorize (lcmCont, v),
671               multiFactorize (i.getItem(), v));
672        break;
673      }
674    }
675    decompress (contentAFactors, N);
676    if (isOn (SW_RATIONAL))
677      normalize (contentAFactors);
678    return contentAFactors;
679  }
680
681  // factorize content
682  contentAFactors= multiFactorize (lcmCont, v);
683
684  // univariate after content removal
685  CFList factors;
686  if (A.isUnivariate ())
687  {
688    if (v.level() != 1)
689      factors= conv (factorize (A, v));
690    else
691      factors= conv (factorize (A,true));
692    append (factors, contentAFactors);
693    decompress (factors, N);
694    return factors;
695  }
696
697  A *= bCommonDen (A);
698  // check main variable
699  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
700  int factorNums= 3;
701  CanonicalForm bivarEval;
702  CFList biFactors, bufBiFactors;
703  CanonicalForm evalPoly;
704  int lift, bufLift;
705  CFList* bufAeval2= new CFList [A.level() - 2];
706  CFList* Aeval2= new CFList [A.level() - 2];
707  int counter;
708  int differentSecondVar= 0;
709  CanonicalForm bufA;
710  // several bivariate factorizations
711  REvaluation E (2, A.level(), IntRandom (25));
712  for (int i= 0; i < factorNums; i++)
713  {
714    counter= 0;
715    bufA= A;
716    bufAeval= CFList();
717    bufEvaluation= evalPoints (bufA, bufAeval, E);
718    E.nextpoint();
719    evalPoly= 0;
720
721    bivarEval= bufEvaluation.getLast();
722
723    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
724
725    for (int j= 0; j < A.level() - 1; j++)
726    {
727      if (!bufAeval2[j].isEmpty())
728        counter++;
729    }
730
731    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
732
733    TIMING_START (fac_bi_factorize);
734    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
735    TIMING_END_AND_PRINT (fac_bi_factorize,
736                          "time for bivariate factorization: ");
737    bufBiFactors.removeFirst();
738
739    if (bufBiFactors.length() == 1)
740    {
741      factors.append (A);
742      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
743      if (isOn (SW_RATIONAL))
744        normalize (factors);
745      delete [] bufAeval2;
746      delete [] Aeval2;
747      return factors;
748    }
749
750    if (i == 0)
751    {
752      Aeval= bufAeval;
753      evaluation= bufEvaluation;
754      biFactors= bufBiFactors;
755      lift= bufLift;
756      for (int j= 0; j < A.level() - 2; j++)
757        Aeval2 [j]= bufAeval2 [j];
758      differentSecondVar= counter;
759    }
760    else
761    {
762      if (bufBiFactors.length() < biFactors.length() ||
763          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
764          counter > differentSecondVar)
765      {
766        Aeval= bufAeval;
767        evaluation= bufEvaluation;
768        biFactors= bufBiFactors;
769        lift= bufLift;
770        for (int j= 0; j < A.level() - 2; j++)
771          Aeval2 [j]= bufAeval2 [j];
772        differentSecondVar= counter;
773      }
774    }
775    int k= 0;
776    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
777      evalPoly += j.getItem()*power (x, k);
778    list.append (evalPoly);
779  }
780
781  delete [] bufAeval2;
782
783  sortList (biFactors, x);
784
785  int minFactorsLength;
786  bool irred= false;
787  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
788
789  if (irred)
790  {
791    factors.append (A);
792    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
793    if (isOn (SW_RATIONAL))
794      normalize (factors);
795    delete [] Aeval2;
796    return factors;
797  }
798
799  if (minFactorsLength == 0)
800    minFactorsLength= biFactors.length();
801  else if (biFactors.length() > minFactorsLength)
802    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
803
804  if (differentSecondVar == A.level() - 2 && getNumVars(LC(A,1)) == A.level()-1)
805  {
806    bool zeroOccured= false;
807    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
808    {
809      if (iter.getItem().isZero())
810      {
811        zeroOccured= true;
812        break;
813      }
814    }
815    if (!zeroOccured)
816    {
817      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
818                                minFactorsLength);
819      if (factors.length() == biFactors.length())
820      {
821        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
822        normalize (factors);
823        delete [] Aeval2;
824        return factors;
825      }
826      else
827        factors= CFList();
828      //TODO case where factors.length() > 0
829    }
830  }
831
832  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
833
834  sortByUniFactors (Aeval2, A.level() - 2, uniFactors, evaluation);
835
836  CFList * oldAeval= new CFList [A.level() - 2];
837  for (int i= 0; i < A.level() - 2; i++)
838    oldAeval[i]= Aeval2[i];
839
840  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
841
842  CFList biFactorsLCs;
843  for (CFListIterator i= biFactors; i.hasItem(); i++)
844    biFactorsLCs.append (LC (i.getItem(), 1));
845
846  Variable w;
847  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
848                                          evaluation, Aeval2, A.level() - 2, w);
849
850  if (w.level() != 1)
851  {
852    A= swapvar (A, y, w);
853    int i= A.level();
854    CanonicalForm evalPoint;
855    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
856    {
857      if (i == w.level())
858      {
859        evalPoint= iter.getItem();
860        iter.getItem()= evaluation.getLast();
861        evaluation.removeLast();
862        evaluation.append (evalPoint);
863        break;
864      }
865    }
866    for (i= 0; i < A.level() - 2; i++)
867    {
868      if (oldAeval[i].isEmpty())
869        continue;
870      if (oldAeval[i].getFirst().level() == w.level())
871      {
872        CFArray tmp= copy (oldAeval[i]);
873        oldAeval[i]= biFactors; 
874        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
875          iter.getItem()= swapvar (iter.getItem(), w, y);
876        for (int ii= 0; ii < tmp.size(); ii++)
877          tmp[ii]= swapvar (tmp[ii], w, y);
878        CFArray tmp2= CFArray (tmp.size());
879        CanonicalForm buf;
880        for (int ii= 0; ii < tmp.size(); ii++)
881        {
882          buf= tmp[ii] (evaluation.getLast(),y);
883          buf /= Lc (buf);
884          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
885        }
886        biFactors= CFList();
887        for (int j= 0; j < tmp2.size(); j++)
888          biFactors.append (tmp2[j]);
889      }
890    }
891  }
892
893  CFListIterator iter;
894  CanonicalForm oldA= A;
895  CFList oldBiFactors= biFactors;
896  if (!leadingCoeffs.getFirst().inCoeffDomain())
897  {
898    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
899    A *= tmp;
900    tmp= leadingCoeffs.getFirst();
901    iter= evaluation;
902    for (int i= A.level(); i > 2; i--, iter++)
903      tmp= tmp (iter.getItem(), i);
904    if (!tmp.inCoeffDomain())
905    {
906      for (CFListIterator i= biFactors; i.hasItem(); i++)
907      {
908        i.getItem() *= tmp/LC (i.getItem(), 1);
909        i.getItem() /= Lc (i.getItem());
910      }
911    }
912  }
913
914  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
915  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
916  leadingCoeffs.removeFirst();
917
918  //prepare leading coefficients
919  CFList* leadingCoeffs2= new CFList [A.level() - 2];
920  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
921                        evaluation);
922
923
924  Aeval= evaluateAtEval (A, evaluation, 2);
925
926  CanonicalForm hh= Lc (Aeval.getFirst());
927
928  for (iter= Aeval; iter.hasItem(); iter++)
929    iter.getItem() /= hh;
930
931  A /= hh;
932
933  CFListIterator iter2;
934  CFList bufLeadingCoeffs2= leadingCoeffs2[A.level()-3];
935  bufBiFactors= biFactors;
936  bufA= A;
937  CFList bufFactors= CFList();
938  bool LCheuristic= false;
939  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [A.level() - 3],
940                                factors))
941  {
942    int check= biFactors.length();
943    int * index= new int [factors.length()];
944    CFList oldFactors= factors;
945    factors= recoverFactors (A, factors, index);
946
947    if (check == factors.length())
948    {
949      if (w.level() != 1)
950      {
951        for (iter= factors; iter.hasItem(); iter++)
952          iter.getItem()= swapvar (iter.getItem(), w, y);
953      }
954
955      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
956      normalize (factors);
957      delete [] index;
958      delete [] Aeval2;
959      return factors;
960    }
961    else if (factors.length() > 0)
962    {
963      int oneCount= 0;
964      CFList l;
965      for (int i= 0; i < check; i++)
966      {
967        if (index[i] == 1)
968        {
969          iter=biFactors;
970          for (int j=1; j <= i-oneCount; j++)
971            iter++;
972          iter.remove (1);
973          for (int j= 0; j < A.level() -2; j++)
974          {
975            l= leadingCoeffs2[j];
976            iter= l;
977            for (int k=1; k <= i-oneCount; k++)
978              iter++;
979            iter.remove (1);
980            leadingCoeffs2[j]=l;
981          }
982          oneCount++;
983        }
984      }
985      bufFactors= factors;
986      factors= CFList();
987    }
988    else if (!LCmultiplier.inCoeffDomain() && factors.length() == 0)
989    {
990      LCheuristic= true;
991      factors= oldFactors;
992      CanonicalForm cont;
993      CFList contents, LCs;
994      int index=1;
995      bool foundTrueMultiplier= false;
996      for (iter= factors; iter.hasItem(); iter++, index++)
997      {
998        cont= content (iter.getItem(), 1);
999        cont= gcd (cont , LCmultiplier);
1000        contents.append (cont);
1001        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
1002        {
1003          foundTrueMultiplier= true;
1004          int index2= 1;
1005          for (iter2= leadingCoeffs2[A.level()-3]; iter2.hasItem(); iter2++,
1006                                                                    index2++)
1007          {
1008            if (index2 == index)
1009              continue;
1010            iter2.getItem() /= LCmultiplier;
1011          }
1012          A /= power (LCmultiplier, biFactors.length() -1);
1013          leadingCoeffs= leadingCoeffs2[A.level()-3];
1014          for (int i= A.level()-3; i > -1; i--)
1015            leadingCoeffs2[i]= CFList();
1016          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
1017                                biFactors, evaluation );
1018          Aeval= evaluateAtEval (A, evaluation, 2);
1019
1020          hh= Lc (Aeval.getFirst());
1021
1022          for (iter2= Aeval; iter2.hasItem(); iter2++)
1023            iter2.getItem() /= hh;
1024
1025          A /= hh;
1026          break;
1027        }
1028        else
1029          LCs.append (LC (iter.getItem()/cont, 1));
1030      }
1031      if (!foundTrueMultiplier)
1032      {
1033        index= 1;
1034        iter2= factors;
1035        bool foundMultiplier= false;
1036        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1037        {
1038          if (fdivides (iter.getItem(), LCmultiplier))
1039          {
1040            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
1041                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
1042            {
1043              int index2= 1;
1044              for (CFListIterator iter3= leadingCoeffs2[A.level()-3];
1045                   iter3.hasItem(); iter3++, index2++)
1046              {
1047                if (index2 == index)
1048                {
1049                  iter3.getItem() /= LCmultiplier;
1050                  break;
1051                }
1052              }
1053              A /= LCmultiplier;
1054              foundMultiplier= true;
1055              iter.getItem()= 1;
1056              break;
1057            }
1058          }
1059        }
1060        // coming from above: divide out more LCmultiplier if possible
1061        if (foundMultiplier)
1062        {
1063          foundMultiplier= false;
1064          index=1;
1065          iter2= factors;
1066          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1067          {
1068            if (!(iter.getItem().isOne()) &&
1069                fdivides (iter.getItem(), LCmultiplier))
1070            {
1071              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
1072              {
1073                int index2= 1;
1074                for (iter2= leadingCoeffs2[A.level()-3]; iter2.hasItem();
1075                     iter2++, index2++)
1076                {
1077                  if (index2 == index)
1078                  {
1079                    iter2.getItem() /= iter.getItem();
1080                    foundMultiplier= true;
1081                    break;
1082                  }
1083                }
1084                A /= iter.getItem();
1085                LCmultiplier /= iter.getItem();
1086                iter.getItem()= 1;
1087                break;
1088              }
1089              else //factor consists of just leading coeff
1090              {
1091                CanonicalForm vars=getVars (iter.getItem());
1092                CanonicalForm factor;
1093                Variable xx;
1094                bool oneVariableNotInCommon= false;
1095                for (int i= 0; i < A.level()-2; i++)
1096                {
1097                  if (oldAeval[i].isEmpty())
1098                    continue;
1099                  xx= oldAeval[i].getFirst().mvar();
1100                  factor= LC (getItem (oldAeval[i], index),1);
1101                  if ((factor.inCoeffDomain() && degree (vars,xx) > 0) ||
1102                      (degree (factor,xx) > 0 && degree (vars,xx) <= 0)) //scan for bivariate factors with leading coeff that does not contain variables which occur in LCmultiplier
1103                  {
1104                    oneVariableNotInCommon= true;
1105                    break;
1106                  }
1107                }
1108                if (oneVariableNotInCommon)
1109                {
1110                  int index2= 1;
1111                  for (iter2= leadingCoeffs2[A.level()-3]; iter2.hasItem();
1112                       iter2++, index2++)
1113                  {
1114                    if (index2 == index)
1115                    {
1116                      iter2.getItem() /= iter.getItem();
1117                      foundMultiplier= true;
1118                      break;
1119                    }
1120                  }
1121                  A /= iter.getItem();
1122                  LCmultiplier /= iter.getItem();
1123                  iter.getItem()= 1;
1124                  break;
1125                }
1126              }
1127            }
1128          }
1129          // wipe out the last LCmultiplier
1130          if (foundMultiplier)
1131          {
1132            index= 1;
1133            for (iter= contents; iter.hasItem(); iter++, index++)
1134            {
1135              if (!iter.getItem().isOne() &&
1136                  fdivides (LCmultiplier, iter.getItem()))
1137              {
1138                int index2= 1;
1139                for (iter2= leadingCoeffs2[A.level()-3]; iter2.hasItem();
1140                     iter2++, index2++)
1141                {
1142                  if (index2 == index)
1143                  {
1144                    iter2.getItem() /= LCmultiplier;
1145                    A /= LCmultiplier;
1146                    iter.getItem() /= LCmultiplier;
1147                  }
1148                }
1149              }
1150            }
1151          }
1152        }
1153        else
1154        {
1155          CanonicalForm pLCs= prod (LCs);
1156          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
1157          {
1158            A= oldA;
1159            iter2= leadingCoeffs2[A.level()-3];
1160            for (iter= contents; iter.hasItem(); iter++, iter2++)
1161              iter2.getItem() /= iter.getItem();
1162          }
1163        }
1164
1165        // patch everything together again
1166        leadingCoeffs= leadingCoeffs2[A.level()-3];
1167        for (int i= A.level()-3; i > -1; i--)
1168          leadingCoeffs2[i]= CFList();
1169        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1170                              evaluation);
1171        Aeval= evaluateAtEval (A, evaluation, 2);
1172
1173        hh= Lc (Aeval.getFirst());
1174
1175        for (CFListIterator i= Aeval; i.hasItem(); i++)
1176          i.getItem() /= hh;
1177
1178        A /= hh;
1179      }
1180      factors= CFList();
1181    }
1182    else
1183      factors= CFList();
1184    delete [] index;
1185  }
1186
1187tryAgainWithoutHeu:
1188  //shifting to zero
1189  A= shift2Zero (A, Aeval, evaluation);
1190
1191  for (iter= biFactors; iter.hasItem(); iter++)
1192    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1193
1194  for (int i= 0; i < A.level() - 3; i++)
1195    leadingCoeffs2[i]= CFList();
1196  for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
1197  {
1198    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
1199    for (int i= A.level() - 4; i > -1; i--)
1200    {
1201      if (i + 1 == A.level() - 3)
1202        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
1203      else
1204        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
1205    }
1206  }
1207
1208  CFArray Pi;
1209  CFList diophant;
1210  int* liftBounds= new int [A.level() - 1];
1211  int liftBoundsLength= A.level() - 1;
1212  for (int i= 0; i < liftBoundsLength; i++)
1213    liftBounds [i]= degree (A, i + 2) + 1;
1214
1215  Aeval.removeFirst();
1216  bool noOneToOne= false;
1217
1218  CFList commonDenominators;
1219  for (iter=biFactors; iter.hasItem(); iter++)
1220    commonDenominators.append (bCommonDen (iter.getItem()));
1221  CanonicalForm tmp1, tmp2, tmp3=1;
1222  for (int i= 0; i < A.level() - 2; i++)
1223  {
1224    iter2= commonDenominators;
1225    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1226    {
1227      tmp1= bCommonDen (iter.getItem());
1228      Off (SW_RATIONAL);
1229      iter2.getItem()= lcm (iter2.getItem(), tmp1);
1230      On (SW_RATIONAL);
1231    }
1232  }
1233  tmp1= prod (commonDenominators);
1234  for (iter= Aeval; iter.hasItem(); iter++)
1235  {
1236    tmp2= bCommonDen (iter.getItem());
1237    Off (SW_RATIONAL);
1238    tmp3= lcm (tmp2,tmp3);
1239    On (SW_RATIONAL);
1240  }
1241  CanonicalForm multiplier;
1242  multiplier= tmp3/tmp1;
1243  iter2= commonDenominators;
1244  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
1245    iter.getItem() *= iter2.getItem()*multiplier;
1246
1247  for (iter= Aeval; iter.hasItem(); iter++)
1248    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
1249
1250  for (int i= 0; i < A.level() - 2; i++)
1251  {
1252    iter2= commonDenominators;
1253    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1254      iter.getItem() *= iter2.getItem()*multiplier;
1255  }
1256
1257
1258  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
1259                               Pi, liftBounds, liftBoundsLength, noOneToOne);
1260
1261  if (!noOneToOne)
1262  {
1263    int check= factors.length();
1264    A= oldA;
1265    factors= recoverFactors (A, factors, evaluation);
1266    if (check != factors.length())
1267      noOneToOne= true;
1268    else
1269      factors= Union (factors, bufFactors);
1270  }
1271  if (noOneToOne)
1272  {
1273    if (!LCmultiplierIsConst && LCheuristic)
1274    {
1275      A= bufA;
1276      biFactors= bufBiFactors;
1277      leadingCoeffs2[A.level()-3]= bufLeadingCoeffs2;
1278      delete [] liftBounds;
1279      LCheuristic= false;
1280      goto tryAgainWithoutHeu;
1281      //something probably went wrong in the heuristic
1282    }
1283
1284    A= shift2Zero (oldA, Aeval, evaluation);
1285    biFactors= oldBiFactors;
1286    for (iter= biFactors; iter.hasItem(); iter++)
1287      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1288    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
1289    CanonicalForm yToLift= power (y, lift);
1290    CFListIterator i= biFactors;
1291    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
1292    i++;
1293
1294    for (; i.hasItem(); i++)
1295      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
1296
1297    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
1298
1299    i= biFactors;
1300    yToLift= power (y, lift);
1301    CanonicalForm dummy;
1302    for (; i.hasItem(); i++)
1303    {
1304      LCA= LC (i.getItem(), 1);
1305      extgcd (LCA, yToLift, LCA, dummy);
1306      i.getItem()= mod (i.getItem()*LCA, yToLift);
1307    }
1308
1309    liftBoundsLength= F.level() - 1;
1310    liftBounds= liftingBounds (A, lift);
1311
1312    CFList MOD;
1313    bool earlySuccess;
1314    CFList earlyFactors;
1315    ExtensionInfo info= ExtensionInfo (false);
1316    CFList liftedFactors;
1317    TIMING_START (fac_hensel_lift);
1318    liftedFactors= henselLiftAndEarly
1319                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1320                    Aeval, biFactors, evaluation, info);
1321    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1322
1323    TIMING_START (fac_factor_recombination);
1324    factors= factorRecombination (A, liftedFactors, MOD);
1325    TIMING_END_AND_PRINT (fac_factor_recombination,
1326                          "time for factor recombination: ");
1327
1328    if (earlySuccess)
1329      factors= Union (factors, earlyFactors);
1330
1331    for (CFListIterator i= factors; i.hasItem(); i++)
1332    {
1333      int kk= Aeval.getLast().level();
1334      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1335      {
1336        if (i.getItem().level() < kk)
1337          continue;
1338       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1339      }
1340    }
1341  }
1342
1343  if (w.level() != 1)
1344  {
1345    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1346      iter.getItem()= swapvar (iter.getItem(), w, y);
1347  }
1348
1349  swap (factors, 0, 0, x);
1350  append (factors, contentAFactors);
1351  decompress (factors, N);
1352  if (isOn (SW_RATIONAL))
1353    normalize (factors);
1354
1355  delete [] leadingCoeffs2;
1356  delete [] oldAeval;
1357  delete [] Aeval2;
1358  delete[] liftBounds;
1359
1360  return factors;
1361}
1362
1363#endif
Note: See TracBrowser for help on using the repository browser.