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

jengelh-datetimespielwiese
Last change on this file since 9dacf3f was 9dacf3f, checked in by Martin Lee <martinlee84@…>, 10 years ago
fix: more fixes to precomputeLeadingCoeff
  • Property mode set to 100644
File size: 28.0 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  CanonicalForm deriv_x, gcd_deriv;
43  CFListIterator iter;
44  do
45  {
46    eval.insert (F);
47    bool bad= false;
48    for (int i= E.max(); i >= E.min(); i--)
49    {
50      eval.insert (eval.getFirst()( E [i], i));
51      result.append (E[i]);
52      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
53      {
54        result= CFList();
55        eval= CFList();
56        bad= true;
57        break;
58      }
59    }
60
61    if (bad)
62    {
63      E.nextpoint();
64      continue;
65    }
66
67    if (degree (eval.getFirst()) != degree (F, 1))
68    {
69      result= CFList();
70      eval= CFList();
71      E.nextpoint();
72      continue;
73    }
74
75    deriv_x= deriv (eval.getFirst(), x);
76    gcd_deriv= gcd (eval.getFirst(), deriv_x);
77    if (degree (gcd_deriv) > 0)
78    {
79      result= CFList();
80      eval= CFList();
81      E.nextpoint();
82      continue;
83    }
84    iter= eval;
85    iter++;
86    CanonicalForm contentx= content (iter.getItem(), x);
87    if (degree (contentx) > 0)
88    {
89      result= CFList();
90      eval= CFList();
91      E.nextpoint();
92      continue;
93    }
94    found= true;
95  }
96  while (!found);
97
98  if (!eval.isEmpty())
99    eval.removeFirst();
100  return result;
101}
102
103void
104factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
105                                     int& minFactorsLength, bool& irred,
106                                     const Variable& w)
107{
108  Variable x= Variable (1);
109  minFactorsLength= 0;
110  irred= false;
111  Variable v;
112  CFList factors;
113  CanonicalForm LCA= LC (A,1);
114  if (!LCA.inCoeffDomain())
115  {
116    for (int j= 0; j < A.level() - 2; j++)
117    {
118      if (!Aeval[j].isEmpty() && (degree (LCA, j+3) > 0))
119      {
120        v= Variable (Aeval[j].getFirst().level());
121
122        factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
123
124        if (factors.getFirst().inCoeffDomain())
125          factors.removeFirst();
126
127        if (minFactorsLength == 0)
128          minFactorsLength= factors.length();
129        else
130          minFactorsLength= tmin (minFactorsLength, factors.length());
131
132        if (factors.length() == 1)
133        {
134          irred= true;
135          return;
136        }
137        sortList (factors, x);
138        Aeval [j]= factors;
139      }
140      else if (!Aeval[j].isEmpty())
141      {
142        Aeval[j]=CFList();
143      }
144    }
145  }
146  else
147  {
148    for (int j= 0; j < A.level() - 2; j++)
149      Aeval[j]= CFList();
150  }
151}
152
153int
154testFactors (const CanonicalForm& G, const CFList& uniFactors,
155             CanonicalForm& sqrfPartF, CFList& factors,
156             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
157             const CFArray& evalPoint)
158{
159  CanonicalForm tmp;
160  CFListIterator j;
161  for (CFListIterator i= uniFactors; i.hasItem(); i++)
162  {
163    tmp= i.getItem();
164    if (i.hasItem())
165      i++;
166    else
167      break;
168    for (j= i; j.hasItem(); j++)
169    {
170      if (tmp == j.getItem())
171        return 0;
172    }
173  }
174
175  CanonicalForm F= G;
176  CFFList sqrfFactorization= sqrFree (F);
177
178  sqrfPartF= 1;
179  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
180    sqrfPartF *= i.getItem().factor();
181
182  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
183
184  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
185
186  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
187    return 0;
188
189  CFFList sqrfFactors;
190  CFList tmp2;
191  int k= 0;
192  factors= uniFactors;
193  CFFListIterator iter;
194  for (CFListIterator i= factors; i.hasItem(); i++, k++)
195  {
196    tmp= 1;
197    sqrfFactors= sqrFree (i.getItem());
198
199    for (iter= sqrfFactors; iter.hasItem(); iter++)
200    {
201      tmp2.append (iter.getItem().factor());
202      tmp *= iter.getItem().factor();
203    }
204    i.getItem()= tmp/Lc(tmp);
205    bufSqrfFactors [k]= sqrfFactors;
206  }
207
208  for (int i= 0; i < factors.length() - 1; i++)
209  {
210    for (int k= i + 1; k < factors.length(); k++)
211    {
212      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
213    }
214  }
215
216  factors= CFList();
217  for (int i= 0; i < uniFactors.length(); i++)
218  {
219    if (i == 0)
220    {
221      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
222      {
223        if (iter.getItem().factor().inCoeffDomain())
224          continue;
225        iter.getItem()= CFFactor (iter.getItem().factor()/
226                                  Lc (iter.getItem().factor()),
227                                  iter.getItem().exp());
228        factors.append (iter.getItem().factor());
229      }
230    }
231    else
232    {
233      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
234      {
235        if (iter.getItem().factor().inCoeffDomain())
236          continue;
237        iter.getItem()= CFFactor (iter.getItem().factor()/
238                               Lc (iter.getItem().factor()),
239                               iter.getItem().exp());
240        if (!find (factors, iter.getItem().factor()))
241          factors.append (iter.getItem().factor());
242      }
243    }
244  }
245
246  test= prod (factors);
247  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
248  if (test/Lc (test) != tmp/Lc (tmp))
249    return 0;
250  else
251    return 1;
252}
253
254CFList
255precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
256                        const CFList& evaluation,CFList*& differentSecondVarLCs,
257                        int length, Variable& y
258                       )
259{
260  y= Variable (1);
261  if (LCF.inCoeffDomain())
262  {
263    CFList result;
264    for (int i= 1; i <= LCFFactors.length() + 1; i++)
265      result.append (1);
266    return result;
267  }
268
269  CFMap N, M;
270  CFArray dummy= CFArray (2);
271  dummy [0]= LCF;
272  dummy [1]= Variable (2);
273  compress (dummy, M, N);
274  CanonicalForm F= M (LCF);
275  if (LCF.isUnivariate())
276  {
277    CFList result;
278    int LCFLevel= LCF.level();
279    bool found= false;
280    if (LCFLevel == 2)
281    {
282    //bivariate leading coefficients are already the true leading coefficients
283      result= LCFFactors;
284      found= true;
285    }
286    else
287    {
288      CFListIterator j;
289      for (int i= 0; i < length; i++)
290      {
291        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
292        {
293          if (j.getItem().level() == LCFLevel)
294          {
295            found= true;
296            break;
297          }
298        }
299        if (found)
300        {
301          result= differentSecondVarLCs [i];
302          break;
303        }
304      }
305      if (!found)
306        result= LCFFactors;
307    }
308    if (found)
309      result.insert (Lc (LCF));
310    else
311      result.append (LCF);
312    return result;
313  }
314
315  CFList factors= LCFFactors;
316
317  for (CFListIterator i= factors; i.hasItem(); i++)
318    i.getItem()= M (i.getItem());
319
320  CanonicalForm sqrfPartF;
321  CFFList * bufSqrfFactors= new CFFList [factors.length()];
322  CFList evalSqrfPartF, bufFactors;
323  CFArray evalPoint= CFArray (evaluation.length() - 1);
324  CFArray buf= CFArray (evaluation.length());
325  CFArray swap= CFArray (evaluation.length());
326  CFListIterator iter= evaluation;
327  CanonicalForm vars=getVars (LCF)*Variable (2);
328  for (int i= evaluation.length() +1; i > 1; i--, iter++)
329  {
330    buf[i-2]=iter.getItem();
331    if (degree (vars, i) > 0)
332      swap[M(Variable (i)).level()-1]=buf[i-2];
333  }
334  buf= swap;
335  for (int i= 0; i < evaluation.length() - 1; i++)
336    evalPoint[i]= buf[i+1];
337
338  //TODO sqrfPartF einmal berechnen nicht stÀndig
339  int pass= testFactors (F, factors, sqrfPartF,
340                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
341
342  bool foundDifferent= false;
343  Variable z;
344  Variable x= y;
345  int j= 0;
346  if (!pass)
347  {
348    int lev= 0;
349    CanonicalForm bufF;
350    CFList bufBufFactors;
351    for (int i= 0; i < length; i++)
352    {
353      if (!differentSecondVarLCs [i].isEmpty())
354      {
355        bool allConstant= true;
356        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
357        {
358          if (!iter.getItem().inCoeffDomain())
359          {
360            allConstant= false;
361            y= Variable (iter.getItem().level());
362            lev= M(y).level();
363          }
364        }
365        if (allConstant)
366          continue;
367
368        bufFactors= differentSecondVarLCs [i];
369        for (iter= bufFactors; iter.hasItem(); iter++)
370          iter.getItem()= swapvar (iter.getItem(), x, y);
371        bufF= F;
372        z= Variable (lev);
373        bufF= swapvar (bufF, x, z);
374        bufBufFactors= bufFactors;
375        evalPoint= CFArray (evaluation.length() - 1);
376        for (int k= 0; k < evaluation.length()-1; k++)
377        {
378          if (N (Variable (k+1)).level() != y.level())
379            evalPoint[k]= buf[k+1];
380          else
381            evalPoint[k]= buf[0];
382        }
383        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
384                           bufSqrfFactors, evalSqrfPartF, evalPoint);
385        if (pass)
386        {
387          foundDifferent= true;
388          F= bufF;
389          CFList l= factors;
390          for (iter= l; iter.hasItem(); iter++)
391            iter.getItem()= swapvar (iter.getItem(), x, y);
392          differentSecondVarLCs [i]= l;
393          j= i;
394          break;
395        }
396        if (!pass && i == length - 1)
397        {
398          CFList result;
399          result.append (LCF);
400          for (int j= 1; j <= factors.length(); j++)
401            result.append (LCF);
402          y= Variable (1);
403          delete [] bufSqrfFactors;
404          return result;
405        }
406      }
407    }
408  }
409  if (!pass)
410  {
411    CFList result;
412    result.append (LCF);
413    for (int j= 1; j <= factors.length(); j++)
414      result.append (LCF);
415    y= Variable (1);
416    delete [] bufSqrfFactors;
417    return result;
418  }
419  else
420    factors= bufFactors;
421
422
423  bufFactors= factors;
424  CFList evaluation2;
425  for (int i= 0; i < F.level()-1; i++)
426    evaluation2.insert (evalPoint[i]);
427
428  CFList interMedResult;
429  CanonicalForm oldSqrfPartF= sqrfPartF;
430  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
431  if (factors.length() > 1)
432  {
433    CanonicalForm LC1= LC (oldSqrfPartF, 1);
434    CFList leadingCoeffs;
435    for (int i= 0; i < factors.length(); i++)
436      leadingCoeffs.append (LC1);
437
438    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
439    CFList oldFactors= factors;
440    for (CFListIterator i= oldFactors; i.hasItem(); i++)
441      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
442
443    bool success= false;
444    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
445    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
446        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
447                                  oldFactors, 2, leadingCoeffs, factors))
448    {
449      interMedResult= recoverFactors (oldSqrfPartF, factors);
450      if (oldFactors.length() == interMedResult.length())
451        success= true;
452    }
453    if (!success)
454    {
455      LC1= LC (evalSqrfPartF.getFirst(), 1);
456
457      CFArray leadingCoeffs= CFArray (factors.length());
458      for (int i= 0; i < factors.length(); i++)
459        leadingCoeffs[i]= LC1;
460
461      for (CFListIterator i= factors; i.hasItem(); i++)
462        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
463      factors.insert (1);
464
465      CanonicalForm
466      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
467
468      int liftBound= degree (newSqrfPartF,2) + 1;
469
470      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
471      CFArray Pi;
472      CFList diophant;
473      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
474                            leadingCoeffs, false);
475
476      if (sqrfPartF.level() > 2)
477      {
478        int* liftBounds= new int [sqrfPartF.level() - 1];
479        liftBounds [0]= liftBound;
480        bool noOneToOne= false;
481        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
482        LC1= LC (evalSqrfPartF.getLast(), 1);
483        CFList LCs;
484        for (int i= 0; i < factors.length(); i++)
485          LCs.append (LC1);
486        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
487        for (int i= sqrfPartF.level() - 1; i > 2; i--)
488        {
489          for (CFListIterator j= LCs; j.hasItem(); j++)
490            j.getItem()= j.getItem() (0, i + 1);
491          leadingCoeffs2 [i - 3]= LCs;
492        }
493        sqrfPartF *= power (LC1, factors.length()-1);
494
495        int liftBoundsLength= sqrfPartF.level() - 1;
496        for (int i= 1; i < liftBoundsLength; i++)
497          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
498        evalSqrfPartF= evaluateAtZero (sqrfPartF);
499        evalSqrfPartF.removeFirst();
500        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
501                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
502        delete [] leadingCoeffs2;
503        delete [] liftBounds;
504      }
505      for (CFListIterator iter= factors; iter.hasItem(); iter++)
506        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
507
508      interMedResult=
509      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
510                      factors);
511    }
512  }
513  else
514  {
515    CanonicalForm contF=content (oldSqrfPartF,1);
516    factors= CFList (oldSqrfPartF/contF);
517    interMedResult= recoverFactors (oldSqrfPartF, factors);
518  }
519
520  CFList result;
521  CFFListIterator k;
522  CanonicalForm tmp;
523  for (int i= 0; i < LCFFactors.length(); i++)
524  {
525    tmp= 1;
526    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
527    {
528      int pos= findItem (bufFactors, k.getItem().factor());
529      if (pos)
530        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
531    }
532    result.append (tmp);
533  }
534
535  for (CFListIterator i= result; i.hasItem(); i++)
536  {
537    F /= i.getItem();
538    if (foundDifferent)
539      i.getItem()= swapvar (i.getItem(), x, z);
540    i.getItem()= N (i.getItem());
541  }
542
543  if (foundDifferent)
544  {
545    CFList l= differentSecondVarLCs [j];
546    for (CFListIterator i= l; i.hasItem(); i++)
547      i.getItem()= swapvar (i.getItem(), y, z);
548    differentSecondVarLCs [j]= l;
549    F= swapvar (F, x, z);
550  }
551
552  result.insert (N (F));
553
554  result= distributeContent (result, differentSecondVarLCs, length);
555
556  if (!result.getFirst().inCoeffDomain())
557  {
558    CFListIterator i= result;
559    CanonicalForm tmp;
560    if (foundDifferent)
561      i.getItem()= swapvar (i.getItem(), Variable (2), y);
562
563    tmp= i.getItem();
564
565    i++;
566    for (; i.hasItem(); i++)
567    {
568      if (foundDifferent)
569        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
570      else
571        i.getItem() *= tmp;
572    }
573  }
574  else
575    y= Variable (1);
576
577  delete [] bufSqrfFactors;
578
579  return result;
580}
581
582
583CFList
584multiFactorize (const CanonicalForm& F, const Variable& v)
585{
586  if (F.inCoeffDomain())
587    return CFList (F);
588
589  // compress and find main Variable
590  CFMap N;
591  CanonicalForm A= myCompress (F, N);
592
593  //univariate case
594  if (F.isUnivariate())
595  {
596    CFList result;
597    if (v.level() != 1)
598      result= conv (factorize (F, v));
599    else
600      result= conv (factorize (F,true));
601    if (result.getFirst().inCoeffDomain())
602      result.removeFirst();
603    return result;
604  }
605
606  //bivariate case
607  if (A.level() == 2)
608  {
609    CFList buf= biFactorize (F, v);
610    return buf;
611  }
612
613  Variable x= Variable (1);
614  Variable y= Variable (2);
615
616  // remove content
617  CFList contentAi;
618  CanonicalForm lcmCont= lcmContent (A, contentAi);
619  A /= lcmCont;
620
621  // trivial after content removal
622  CFList contentAFactors;
623  if (A.inCoeffDomain())
624  {
625    for (CFListIterator i= contentAi; i.hasItem(); i++)
626    {
627      if (i.getItem().inCoeffDomain())
628        continue;
629      else
630      {
631        lcmCont /= i.getItem();
632        contentAFactors=
633        Union (multiFactorize (lcmCont, v),
634               multiFactorize (i.getItem(), v));
635        break;
636      }
637    }
638    decompress (contentAFactors, N);
639    if (isOn (SW_RATIONAL))
640      normalize (contentAFactors);
641    return contentAFactors;
642  }
643
644  // factorize content
645  contentAFactors= multiFactorize (lcmCont, v);
646
647  // univariate after content removal
648  CFList factors;
649  if (A.isUnivariate ())
650  {
651    if (v.level() != 1)
652      factors= conv (factorize (A, v));
653    else
654      factors= conv (factorize (A,true));
655    append (factors, contentAFactors);
656    decompress (factors, N);
657    return factors;
658  }
659
660  A *= bCommonDen (A);
661  // check main variable
662  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
663  int factorNums= 3;
664  CanonicalForm bivarEval;
665  CFList biFactors, bufBiFactors;
666  CanonicalForm evalPoly;
667  int lift, bufLift;
668  CFList* bufAeval2= new CFList [A.level() - 2];
669  CFList* Aeval2= new CFList [A.level() - 2];
670  int counter;
671  int differentSecondVar= 0;
672  CanonicalForm bufA;
673  // several bivariate factorizations
674  REvaluation E (2, A.level(), IntRandom (25));
675  for (int i= 0; i < factorNums; i++)
676  {
677    counter= 0;
678    bufA= A;
679    bufAeval= CFList();
680    bufEvaluation= evalPoints (bufA, bufAeval, E);
681    E.nextpoint();
682    evalPoly= 0;
683
684    bivarEval= bufEvaluation.getLast();
685
686    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
687
688    for (int j= 0; j < A.level() - 1; j++)
689    {
690      if (!bufAeval2[j].isEmpty())
691        counter++;
692    }
693
694    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
695
696    TIMING_START (fac_bi_factorize);
697    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
698    TIMING_END_AND_PRINT (fac_bi_factorize,
699                          "time for bivariate factorization: ");
700    bufBiFactors.removeFirst();
701
702    if (bufBiFactors.length() == 1)
703    {
704      factors.append (A);
705      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
706      if (isOn (SW_RATIONAL))
707        normalize (factors);
708      delete [] bufAeval2;
709      delete [] Aeval2;
710      return factors;
711    }
712
713    if (i == 0)
714    {
715      Aeval= bufAeval;
716      evaluation= bufEvaluation;
717      biFactors= bufBiFactors;
718      lift= bufLift;
719      for (int j= 0; j < A.level() - 2; j++)
720        Aeval2 [j]= bufAeval2 [j];
721      differentSecondVar= counter;
722    }
723    else
724    {
725      if (bufBiFactors.length() < biFactors.length() ||
726          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
727          counter > differentSecondVar)
728      {
729        Aeval= bufAeval;
730        evaluation= bufEvaluation;
731        biFactors= bufBiFactors;
732        lift= bufLift;
733        for (int j= 0; j < A.level() - 2; j++)
734          Aeval2 [j]= bufAeval2 [j];
735        differentSecondVar= counter;
736      }
737    }
738    int k= 0;
739    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
740      evalPoly += j.getItem()*power (x, k);
741    list.append (evalPoly);
742  }
743
744  delete [] bufAeval2;
745
746  sortList (biFactors, x);
747
748  int minFactorsLength;
749  bool irred= false;
750  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
751
752  if (irred)
753  {
754    factors.append (A);
755    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
756    if (isOn (SW_RATIONAL))
757      normalize (factors);
758    delete [] Aeval2;
759    return factors;
760  }
761
762  if (minFactorsLength == 0)
763    minFactorsLength= biFactors.length();
764  else if (biFactors.length() > minFactorsLength)
765    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
766
767  if (differentSecondVar == A.level() - 2 && getNumVars(LC(A,1)) == A.level()-1)
768  {
769    bool zeroOccured= false;
770    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
771    {
772      if (iter.getItem().isZero())
773      {
774        zeroOccured= true;
775        break;
776      }
777    }
778    if (!zeroOccured)
779    {
780      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
781                                minFactorsLength);
782      if (factors.length() == biFactors.length())
783      {
784        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
785        normalize (factors);
786        delete [] Aeval2;
787        return factors;
788      }
789      else
790        factors= CFList();
791      //TODO case where factors.length() > 0
792    }
793  }
794
795  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
796
797  sortByUniFactors (Aeval2, A.level() - 2, uniFactors, evaluation);
798
799  CFList * oldAeval= new CFList [A.level() - 2];
800  for (int i= 0; i < A.level() - 2; i++)
801    oldAeval[i]= Aeval2[i];
802
803  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
804
805  CFList biFactorsLCs;
806  for (CFListIterator i= biFactors; i.hasItem(); i++)
807    biFactorsLCs.append (LC (i.getItem(), 1));
808
809  Variable w;
810  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
811                                          evaluation, Aeval2, A.level() - 2, w);
812
813  if (w.level() != 1)
814  {
815    A= swapvar (A, y, w);
816    int i= A.level();
817    CanonicalForm evalPoint;
818    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
819    {
820      if (i == w.level())
821      {
822        evalPoint= iter.getItem();
823        iter.getItem()= evaluation.getLast();
824        evaluation.removeLast();
825        evaluation.append (evalPoint);
826        break;
827      }
828    }
829    for (i= 0; i < A.level() - 2; i++)
830    {
831      if (oldAeval[i].isEmpty())
832        continue;
833      if (oldAeval[i].getFirst().level() == w.level())
834      {
835        CFArray tmp= copy (oldAeval[i]);
836        for (int ii= 0; ii < tmp.size(); ii++)
837          tmp[ii]= swapvar (tmp[ii], w, y);
838        CFArray tmp2= CFArray (tmp.size());
839        CanonicalForm buf;
840        for (int ii= 0; ii < tmp.size(); ii++)
841        {
842          buf= tmp[ii] (evaluation.getLast(),y);
843          buf /= Lc (buf);
844          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
845        }
846        biFactors= CFList();
847        for (int j= 0; j < tmp2.size(); j++)
848          biFactors.append (tmp2[j]);
849      }
850    }
851  }
852
853  CFListIterator iter;
854  CanonicalForm oldA= A;
855  CFList oldBiFactors= biFactors;
856  if (!leadingCoeffs.getFirst().inCoeffDomain())
857  {
858    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
859    A *= tmp;
860    tmp= leadingCoeffs.getFirst();
861    iter= evaluation;
862    for (int i= A.level(); i > 2; i--, iter++)
863      tmp= tmp (iter.getItem(), i);
864    if (!tmp.inCoeffDomain())
865    {
866      for (CFListIterator i= biFactors; i.hasItem(); i++)
867      {
868        i.getItem() *= tmp/LC (i.getItem(), 1);
869        i.getItem() /= Lc (i.getItem());
870      }
871    }
872  }
873
874  leadingCoeffs.removeFirst();
875
876  //prepare leading coefficients
877  CFList* leadingCoeffs2= new CFList [A.level() - 2];
878  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
879                        evaluation);
880
881
882  Aeval= evaluateAtEval (A, evaluation, 2);
883
884  CanonicalForm hh= Lc (Aeval.getFirst());
885
886  for (CFListIterator i= Aeval; i.hasItem(); i++)
887    i.getItem() /= hh;
888
889  A /= hh;
890
891  if (size (A)/getNumVars (A) < 500 &&
892      LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [A.level() - 3],
893                                factors))
894  {
895    int check= factors.length();
896    factors= recoverFactors (A, factors);
897
898    if (check == factors.length())
899    {
900
901      if (w.level() != 1)
902      {
903        for (CFListIterator iter= factors; iter.hasItem(); iter++)
904          iter.getItem()= swapvar (iter.getItem(), w, y);
905      }
906
907      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
908      normalize (factors);
909      delete [] Aeval2;
910      return factors;
911    }
912    else
913      factors= CFList();
914  }
915
916
917  //shifting to zero
918  A= shift2Zero (A, Aeval, evaluation);
919
920  for (iter= biFactors; iter.hasItem(); iter++)
921    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
922
923  for (int i= 0; i < A.level() - 2; i++)
924  {
925    if (i != A.level() - 3)
926      leadingCoeffs2[i]= CFList();
927  }
928  for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
929  {
930    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
931    for (int i= A.level() - 4; i > -1; i--)
932    {
933      if (i + 1 == A.level() - 3)
934        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
935      else
936        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
937    }
938  }
939
940  CFArray Pi;
941  CFList diophant;
942  int* liftBounds= new int [A.level() - 1];
943  int liftBoundsLength= A.level() - 1;
944  for (int i= 0; i < liftBoundsLength; i++)
945    liftBounds [i]= degree (A, i + 2) + 1;
946
947  Aeval.removeFirst();
948  bool noOneToOne= false;
949
950  CFList commonDenominators;
951  for (CFListIterator iter=biFactors; iter.hasItem(); iter++)
952    commonDenominators.append (bCommonDen (iter.getItem()));
953  CanonicalForm tmp1, tmp2, tmp3=1;
954  CFListIterator iter1, iter2;
955  for (int i= 0; i < A.level() - 2; i++)
956  {
957    iter2= commonDenominators;
958    for (iter1= leadingCoeffs2[i]; iter1.hasItem(); iter1++, iter2++)
959    {
960      tmp1= bCommonDen (iter1.getItem());
961      Off (SW_RATIONAL);
962      iter2.getItem()= lcm (iter2.getItem(), tmp1);
963      On (SW_RATIONAL);
964    }
965  }
966  tmp1= prod (commonDenominators);
967  for (iter1= Aeval; iter1.hasItem(); iter1++)
968  {
969    tmp2= bCommonDen (iter1.getItem());
970    Off (SW_RATIONAL);
971    tmp3= lcm (tmp2,tmp3);
972    On (SW_RATIONAL);
973  }
974  CanonicalForm multiplier;
975  multiplier= tmp3/tmp1;
976  iter2= commonDenominators;
977  for (iter1=biFactors; iter1.hasItem(); iter1++, iter2++)
978    iter1.getItem() *= iter2.getItem()*multiplier;
979
980  for (iter1= Aeval; iter1.hasItem(); iter1++)
981    iter1.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
982
983  for (int i= 0; i < A.level() - 2; i++)
984  {
985    iter2= commonDenominators;
986    for (iter1= leadingCoeffs2[i]; iter1.hasItem(); iter1++, iter2++)
987      iter1.getItem() *= iter2.getItem()*multiplier;
988  }
989
990
991  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
992                               Pi, liftBounds, liftBoundsLength, noOneToOne);
993
994  if (!noOneToOne)
995  {
996    int check= factors.length();
997    A= oldA;
998    factors= recoverFactors (A, factors, evaluation);
999    if (check != factors.length())
1000      noOneToOne= true;
1001  }
1002  if (noOneToOne)
1003  {
1004    A= shift2Zero (oldA, Aeval, evaluation);
1005    biFactors= oldBiFactors;
1006    for (iter= biFactors; iter.hasItem(); iter++)
1007      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1008    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
1009    CanonicalForm yToLift= power (y, lift);
1010    CFListIterator i= biFactors;
1011    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
1012    i++;
1013
1014    for (; i.hasItem(); i++)
1015      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
1016
1017    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
1018
1019    i= biFactors;
1020    yToLift= power (y, lift);
1021    CanonicalForm dummy;
1022    for (; i.hasItem(); i++)
1023    {
1024      LCA= LC (i.getItem(), 1);
1025      extgcd (LCA, yToLift, LCA, dummy);
1026      i.getItem()= mod (i.getItem()*LCA, yToLift);
1027    }
1028
1029    liftBoundsLength= F.level() - 1;
1030    liftBounds= liftingBounds (A, lift);
1031
1032    CFList MOD;
1033    bool earlySuccess;
1034    CFList earlyFactors;
1035    ExtensionInfo info= ExtensionInfo (false);
1036    CFList liftedFactors;
1037    TIMING_START (fac_hensel_lift);
1038    liftedFactors= henselLiftAndEarly
1039                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1040                    Aeval, biFactors, evaluation, info);
1041    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1042
1043    TIMING_START (fac_factor_recombination);
1044    factors= factorRecombination (A, liftedFactors, MOD);
1045    TIMING_END_AND_PRINT (fac_factor_recombination,
1046                          "time for factor recombination: ");
1047
1048    if (earlySuccess)
1049      factors= Union (factors, earlyFactors);
1050
1051    for (CFListIterator i= factors; i.hasItem(); i++)
1052    {
1053      int kk= Aeval.getLast().level();
1054      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1055      {
1056        if (i.getItem().level() < kk)
1057          continue;
1058       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1059      }
1060    }
1061  }
1062
1063  if (w.level() != 1)
1064  {
1065    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1066      iter.getItem()= swapvar (iter.getItem(), w, y);
1067  }
1068
1069  swap (factors, 0, 0, x);
1070  append (factors, contentAFactors);
1071  decompress (factors, N);
1072  if (isOn (SW_RATIONAL))
1073    normalize (factors);
1074
1075  delete [] leadingCoeffs2;
1076  delete [] oldAeval;
1077  delete [] Aeval2;
1078  delete[] liftBounds;
1079
1080  return factors;
1081}
1082
1083#endif
Note: See TracBrowser for help on using the repository browser.