source: git/libfac/factor/Factor.cc @ aadd442

spielwiese
Last change on this file since aadd442 was aadd442, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes: SqrFreeTest -> isSqrFree git-svn-id: file:///usr/local/Singular/svn/trunk@10524 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 46.4 KB
Line 
1/* Copyright 1996 Michael Messollen. All rights reserved. */
2///////////////////////////////////////////////////////////////////////////////
3static char * rcsid = "$Id: Factor.cc,v 1.40 2008-01-25 14:19:40 Singular Exp $ ";
4static char * errmsg = "\nYou found a bug!\nPlease inform (Michael Messollen) michael@math.uni-sb.de \nPlease include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you.";
5///////////////////////////////////////////////////////////////////////////////
6// FACTORY - Includes
7#include <factory.h>
8#ifndef NOSTREAMIO
9#ifdef HAVE_IOSTREAM
10#include <iostream>
11#define CERR std::cerr
12#define CIN std::cin
13#elif defined(HAVE_IOSTREAM_H)
14#include <iostream.h>
15#define CERR cerr
16#define CIN cin
17#endif
18#endif
19// Factor - Includes
20#include "tmpl_inst.h"
21#include "SqrFree.h"
22#include "helpstuff.h"
23#include "MVMultiHensel.h"
24#include "Truefactor.h"
25#include "homogfactor.h"
26#include "interrupt.h"
27// some CC's need this:
28#include "Factor.h"
29
30#include "alg_factor.h"
31void out_cf(char *s1,const CanonicalForm &f,char *s2);
32void out_cff(CFFList &L);
33
34
35#ifdef SINGULAR
36#define HAVE_SINGULAR_ERROR
37#endif
38
39#ifdef HAVE_SINGULAR_ERROR
40   extern "C" { void WerrorS(char *); }
41   extern "C" { void WarnS(const char *); }
42#endif
43
44#ifdef FACTORDEBUG
45#  define DEBUGOUTPUT
46#else
47#  undef DEBUGOUTPUT
48#endif
49
50#include "debug.h"
51#include "timing.h"
52TIMING_DEFINE_PRINT(factorize_time);
53TIMING_DEFINE_PRINT(sqrfree_time);
54TIMING_DEFINE_PRINT(discr_time);
55TIMING_DEFINE_PRINT(evaluate_time);
56TIMING_DEFINE_PRINT(hensel_time);
57TIMING_DEFINE_PRINT(truefactor_time);
58
59/*
60* a wrapper for factorize over algebraic extensions:
61* does a sanity check and, if nec., a conversion
62* before calling factorize(f,alpha)
63* ( in factorize, alpha.level() must be < 0 )
64*/
65CFFList factorize2 ( const CanonicalForm & f,
66                     const Variable & alpha, const CanonicalForm & mipo )
67{
68  if (alpha.level() <0)
69  {
70    if (f.isUnivariate())
71      return factorize(f,alpha);
72    else
73    {
74      return Factorize(f,mipo);
75    }
76  }
77  else
78  {
79    bool repl=(f.mvar() != alpha);
80    //out_cf("f2 - factor:",f,"\n");
81    //out_cf("f2 - ext:",alpha,"\n");
82    //out_cf("f2 - mipo:",mipo,"\n");
83    Variable X=rootOf(mipo);
84    CanonicalForm F=f;
85    if (repl) F=replacevar(f,alpha,X);
86    //out_cf("call - factor:",F,"\n");
87    //out_cf("call - ext:",X,"\n");
88    //out_cf("call - mipo:",getMipo(X,'A'),"\n");
89    CFFList L=factorize(F,X);
90    CFFListIterator i=L;
91    if (repl)
92    {
93      CFFList Outputlist;
94      for(;i.hasItem(); i++ )
95      {
96        Outputlist.append(CFFactor(
97        replacevar(i.getItem().factor(),X,alpha),
98        i.getItem().exp()));
99      }
100      return Outputlist;
101    }
102    else return L;
103  }
104}
105///////////////////////////////////////////////////////////////
106// Choose a main variable if the user didn`t wish a          //
107// special one. Returns level of main variable.              //
108///////////////////////////////////////////////////////////////
109static int
110choose_main_variable( const CanonicalForm & f, int Mainvar=0){
111  CanonicalForm remlc, newlc;
112  int n= level(f), mainvar= Mainvar;
113
114  if (mainvar != 0) return mainvar ; // We force use of the wished mainvar
115  remlc= LC(f,n); mainvar = n;
116  if ( totaldegree(remlc)==0 ){ remlc=f.genOne() ; }
117  DEBOUTLN(CERR, "remlc= " , remlc);
118  for ( int i=n-1; i>=1; i-- )
119  {
120    newlc= LC(f,i);
121    if ( totaldegree(newlc)==0 ){ newlc=f.genOne() ; }
122    DEBOUTLN(CERR, "newlc= " , newlc);
123    if ( (remlc.isOne()) && (newlc.isOne()) ){ // take care of the degrees
124      if ( degree(f,i) < degree(f,mainvar) ){
125        remlc= newlc;
126        mainvar= i;
127      }
128    }
129    else  if ( (! remlc.isOne() ) && ( newlc.isOne() ) ){
130      remlc= newlc;
131      mainvar= i;
132    }
133  }
134  return mainvar;
135}
136
137///////////////////////////////////////////////////////////////
138// Check if the derivative is nonzero for oldmainvar.        //
139// Returns the level of the choosen main variable.           //
140///////////////////////////////////////////////////////////////
141static int
142necessary_condition( const CanonicalForm & F, int oldmainvar){
143  CanonicalForm g;
144  int n=level(F);
145
146  g= swapvar(F,oldmainvar,n);
147  g= g.deriv();
148  if ( g.isZero() )
149  {
150    for ( int i=n; i>=1; i-- )
151    {
152      g= swapvar(F,i,n);
153      g= g.deriv();
154      if ( ! g.isZero() ) return i;
155    }
156  }
157  return oldmainvar;
158}
159
160///////////////////////////////////////////////////////////////
161// Make F monic. Return monic polynomial.                    //
162///////////////////////////////////////////////////////////////
163static CanonicalForm
164make_monic( const CanonicalForm & F, const CanonicalForm & lt)
165{
166  CanonicalForm intermediatpoly,f;
167  Variable x(level(F));
168
169  if ( degree(lt) == 0 ) f= 1/lt * F ;
170  else
171  {
172    intermediatpoly= power(lt,degree(F)-1);
173    for ( int i=0; i<=degree(F); i++ )
174      if ( ! F[i].isZero())
175        f+= (F[i] * intermediatpoly*power(x,i))/power(lt,i);
176  }
177  return f;
178}
179
180///////////////////////////////////////////////////////////////
181// Decide whether num/denum (num,denum both from the         //
182// FiniteFielddomain)  lies in the RationalDomain.           //
183// If false, return num/denum else return the zero poly from //
184// the FiniteFielddomain.                                    //
185///////////////////////////////////////////////////////////////
186static CanonicalForm
187is_rational( const CanonicalForm & num, const CanonicalForm & denum ){
188  CanonicalForm a, b;
189  int retvalue;
190
191  retvalue= mydivremt(num,denum,a,b);
192  if ( retvalue && b == num.genZero() ) // num/denum from FFdomain
193    return a;
194  else // num/denum is rational
195    return num.genZero();
196}
197
198///////////////////////////////////////////////////////////////
199// lt_is_product returns 1 iff lt is a product, 0 iff lt is  //
200// a sum.                                                    //
201///////////////////////////////////////////////////////////////
202static int
203lt_is_product( const CanonicalForm & lt ){
204  CFList result;
205
206  result= get_Terms(lt);
207  if ( result.length() > 1 ) return 0;
208  else return 1;
209}
210
211///////////////////////////////////////////////////////////////
212// Reverse the make_monic transformation.                    //
213// Return the list of factors.                               //
214///////////////////////////////////////////////////////////////
215static CFFList
216not_monic( const CFFList & TheList, const CanonicalForm & ltt, const CanonicalForm & F, int levelF)
217{
218  CFFList Returnlist,IntermediateList;
219  CFFListIterator i;
220  CanonicalForm intermediate,lt= ltt,savelc;
221  CanonicalForm numerator,denumerator,test,a,b;
222  Variable x(level(F));
223  int test1;
224
225  if ( lt.isOne() ) return TheList; // the poly was already monic
226  if ( TheList.length() <= 1 ) // only one factor to substitute back
227  {
228    if ( totaldegree(lt) == 0 ) // lt is type numeric
229      Returnlist.append( CFFactor(lt*TheList.getFirst().factor(),
230                                  TheList.getFirst().exp()) );
231    else
232    {
233      intermediate = F(x*lt, levelF)/power(lt,degree(F,levelF)-1);
234      Returnlist.append(CFFactor(intermediate,TheList.getFirst().exp()));
235    }
236  }
237  else // more then one factor
238  {
239    IntermediateList= TheList;
240    if ( totaldegree(lt) == 0 ){ // lt is type numeric;(SqrFree-use, see above)
241      Returnlist.append( CFFactor(lt*IntermediateList.getFirst().factor()
242                                  , IntermediateList.getFirst().exp()) );
243      IntermediateList.removeFirst();
244      Returnlist= Union(Returnlist,IntermediateList);
245    }
246    else // lt is a) a product or b) a sum of terms
247    {
248      if ( lt_is_product(lt) ) // case a)
249      {
250        DEBOUTLN(CERR, "lt_is_product: ", lt);
251        savelc= content(lt) ; // can we simplify to savelc= lc(lt); ?
252        while ( getNumVars(savelc) != 0 )
253          savelc= content(savelc);
254        for ( i=TheList; i.hasItem();i++ )
255        {
256          numerator= i.getItem().factor();
257          numerator= numerator(x*lt,levelF); // x <- x*lt
258          denumerator= power(lt,degree(F,levelF)-1); // == lt^(1-degree(F,x)
259          while (numerator.genZero() == is_rational(numerator, denumerator))
260            numerator*= lt;
261          intermediate= is_rational(numerator,denumerator);
262
263          Returnlist.append( CFFactor(lc(content(intermediate))*intermediate/content(intermediate), i.getItem().exp() ) );
264        }
265        // Now we add a test. If product(factors)/F is a multiple of
266        // savelc, we have to add 1/multiplicity to the factors
267        IntermediateList= Returnlist;
268        intermediate= 1;
269        for ( CFFListIterator j=IntermediateList; j.hasItem(); j++)
270          intermediate*= j.getItem().factor();
271        test1= mydivremt( intermediate,F,a,b);
272        if ( test1 && b == intermediate.genZero() ) // Yupp!
273        {
274          IntermediateList.append(CFFactor(1/a,1));
275          Returnlist= IntermediateList;
276        }
277        else { Returnlist= IntermediateList; }
278      }
279      else // case b)
280      {
281        DEBOUTLN(CERR, "lt_is_sum: ", lt);
282        CanonicalForm save_denumerator= 1;
283        for ( i=TheList; i.hasItem(); i++ )
284        {
285          numerator= i.getItem().factor();
286          numerator= numerator(x*lt,levelF); // x <- x*lt
287          denumerator= power(lt,degree(numerator,levelF)); // == lt^(-degree(numerator,x)
288          test= content(numerator,x);
289          test1= mydivremt(denumerator,test,a,b);
290          if ( test1 && b == numerator.genZero() ) // Yupp!
291          {
292            save_denumerator*= a;
293            Returnlist.append(CFFactor(numerator/test ,1));
294          }
295          else
296          {
297#ifdef HAVE_SINGULAR_ERROR
298            WerrorS("libfac: ERROR: not_monic1: case lt is a sum.");
299#else
300#ifndef NOSTREAMIO
301            CERR << "libfac: ERROR: not_monic1: case lt is a sum.\n"
302                 << rcsid << errmsg << "\n";
303#endif
304#endif
305          }
306        }
307        // Now we add a test if we did the right thing:
308        // save_denumerator should be a multiple of the leading coeff
309        test1= mydivremt(save_denumerator,lt,a,b);
310        if ( test1 && b == save_denumerator.genZero() ) // Yupp!
311          // We have to multiply one of the factors with
312          // the multiplicity of the save_denumerator <-> lc
313          // the following will do what we want
314          Returnlist= UnionCFFL( CFFList(CFFactor(1/a,1)),Returnlist) ;
315        else
316        {
317#ifdef HAVE_SINGULAR_ERROR
318          WerrorS("libfac: ERROR: not_monic2: case lt is a sum.");
319#else
320#ifndef NOSTREAMIO
321          CERR << "libfac: ERROR: not_monic2: case lt is a sum.\n"
322               << rcsid << errmsg << "\n";
323#endif
324#endif
325        }
326      }
327    }
328  }
329  DEBOUTLN(CERR,"Returnlist: ", Returnlist);
330  return Returnlist;
331}
332
333///////////////////////////////////////////////////////////////
334// Substitute the (Variable,Value)-Pair(s) from Substitution-//
335// list into the polynomial F. Returns the resulting poly.   //
336///////////////////////////////////////////////////////////////
337static CanonicalForm
338substitutePoly( const CanonicalForm & F, const SFormList & Substitutionlist){
339  CanonicalForm f= F;
340
341  for ( SFormListIterator i=Substitutionlist; i.hasItem(); i++ )
342    f= f(i.getItem().exp(),level(i.getItem().factor()));
343  return f;
344}
345
346///////////////////////////////////////////////////////////////
347// Find specialization values for the poly F. Returns 0 if   //
348// procedure failed, 1 otherwise. On success Substitutionlist//
349// holds (Variable,Value)-pairs. On failure we only have a   //
350// partitial list.                                           //
351///////////////////////////////////////////////////////////////
352//      *** This is the version with extensions ***          //
353///////////////////////////////////////////////////////////////
354
355///////////////////////////////////////////////////////////////
356// is CF g ok?                                               //
357///////////////////////////////////////////////////////////////
358static int
359various_tests( const CanonicalForm & g, int deg, int vars_left)
360{
361  CFMap m;
362
363  if ( degree(g) == deg ) // degrees match
364    if ( level(compress(g,m)) == (vars_left) ) // exactly one variable less
365      if ( isSqrFree(g) ) // poly is sqrfree
366        if ( gcd(g,g.deriv()).isOne() ) // Discriminante != 0
367           return 1;
368  return 0;
369}
370
371///////////////////////////////////////////////////////////////
372// specialize one variable over the given field.             //
373///////////////////////////////////////////////////////////////
374// substitutes in poly f of degree deg with former
375// former_nr_of_variables variables the variable nr_of_variable ;
376// this is done in the field of Char getCharacteristic() and
377// Extension given by Extgenerator.
378///////////////////////////////////////////////////////////////
379static int
380specialize_variable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
381                     int former_nr_of_variables, CFGenerator & Extgenerator ){
382  CanonicalForm g;
383  Variable x(nr_of_variable);
384
385  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
386  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
387    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
388    g= f( Extgenerator.item(), x );
389    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
390    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
391      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
392      f= g;
393      return 1;
394    }
395  }
396  return 0;
397}
398static int
399specialize_agvariable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
400                     int former_nr_of_variables, AlgExtGenerator & Extgenerator ){
401  CanonicalForm g;
402  Variable x(nr_of_variable);
403
404  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
405  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
406    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
407    g= f( Extgenerator.item(), x );
408    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
409    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
410      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
411      f= g;
412      return 1;
413    }
414  }
415  return 0;
416}
417
418///////////////////////////////////////////////////////////////
419// generate a minpoly of degree degree_of_Extension in the   //
420// field getCharacteristik()^Extension.                      //
421///////////////////////////////////////////////////////////////
422CanonicalForm
423generate_mipo( int degree_of_Extension , const Variable & Extension ){
424  FFRandom gen;
425  if ( degree(Extension) > 0 ) GFRandom gen;
426  else {
427    if ( degree(Extension) == 0 ) FFRandom gen;
428    else {
429#ifdef HAVE_SINGULAR_ERROR
430    WerrorS("libfac: evaluate: Extension not inFF() or inGF() !");
431#else
432#ifndef NOSTREAMIO
433    CERR << "libfac: evaluate: " << Extension << " not inFF() or inGF() !"
434         << "\n";
435#endif
436#endif
437    FFRandom gen;
438    }
439  }
440  return find_irreducible( degree_of_Extension, gen, Variable(1) );
441}
442
443///////////////////////////////////////////////////////////////
444// Try to find a specialization for f over the field of char //
445// f.getCharacteristic() and (possible) extension defined by //
446// the variable Extension .                                  //
447// Returns 1 iff specialisation was found, 0 otherwise.      //
448// If 0 is returned there are variables left to substitute.  //
449// We check if Substitutionlist.length() > 0, i.e. we        //
450// previously tried to find specialization values for some   //
451// values. We take them and work with the resulting poly.    //
452///////////////////////////////////////////////////////////////
453static int
454try_specializePoly(const CanonicalForm & f, const Variable & Extension, int deg, SFormList & Substitutionlist, int ii,int j)
455{
456  int ok,i= ii;
457  CanonicalForm ff= f;
458
459  if ( Substitutionlist.length() > 0 ){ // we formerly tried to specialize
460    ff= substitutePoly(f,Substitutionlist); // substitute found values
461    i= Substitutionlist.length() + 1;
462  }
463
464  if ( degree(Extension) > 0 )
465  { // working over Extensions
466    DEBOUTLN(CERR, "try_specializePoly: working over Extensions: ", Extension);
467    if (Extension.level() > 0)
468    {
469    //  AlgExtGenerator g(Extension,minpoly );
470    //  for ( int k=i ; k<j ; k++ ) // try to find specialization for all
471    //  {                           // variables (# = k ) beginning with the
472    //                             // starting value i
473    //    ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
474    //    if ( ! ok ) return 0; // we failed
475    //  }
476      #ifndef NDEBUG
477        //printf("libfac: try_specializePoly: extension level >0\n");
478      #endif
479      return 0; // we failed
480    }
481    else
482    {
483      AlgExtGenerator g(Extension);
484      for ( int k=i ; k<j ; k++ ) // try to find specialization for all
485      {                           // variables (# = k ) beginning with the
486                                 // starting value i
487        ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
488        if ( ! ok ) return 0; // we failed
489      }
490    }
491  }
492  else{ // working over the ground-field
493    FFGenerator g;
494    DEBOUTMSG(CERR, "try_specializePoly: working over the ground-field.");
495    for ( int k=i ; k<j ; k++ ){
496      ok= specialize_variable( ff, deg, Substitutionlist, k, j, g );
497      if ( ! ok ) return 0; // we failed
498    }
499  }
500  return 1;
501}
502
503static int
504specializePoly(const CanonicalForm & f, Variable & Extension, int deg, SFormList & Substitutionlist, int i,int j){
505  Variable minpoly= Extension;
506  int ok,extended= degree(Extension), working_over_extension;
507
508  // Remember if we are working over an extension-field
509  if ( extended >= 2 )    { working_over_extension = 1; }
510  else                    { working_over_extension = 0; extended = 1; }
511  // First try:
512  ok = try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
513  while ( ! ok ){ // we have to extend!
514    extended+= 1;
515    if ( ! working_over_extension ){
516      minpoly= rootOf(generate_mipo( extended,Extension ));
517      Extension= minpoly;
518      ok= try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
519    }
520    else {
521#ifdef HAVE_SINGULAR_ERROR
522      WerrorS("libfac: spezializePoly ERROR: Working over given extension-field not yet implemented!");
523#else
524#ifndef NOSTREAMIO
525      CERR << "libfac: spezializePoly ERROR: Working over given extension-field not yet implemented!\n"
526           << rcsid << errmsg << "\n";
527#endif
528#endif
529      return 0;
530    }
531  }
532  return 1;
533}
534
535
536// This is a procedure to play with: lot's of parameters!
537// returns: 0  iff no success (possibly because Extension isn't great enough
538//          >0 iff g (univariate) splits into n factors;
539// if n>0 BestEvaluationpoint contains the choice of values for the variables
540//
541// tries to find at least maxtries evaluation points
542// if g factored sametries into the same number of poly's the procedure stops
543// if we tried failtries evaluations not found valid, we stop. Perhaps
544// Extension isn't big enough!
545static int
546evaluate( int maxtries, int sametries, int failtries, const CanonicalForm &f , const Variable & Extension, const CanonicalForm &mipo, SFormList & BestEvaluationpoint, CFFList & BestFactorisation ){
547  int minfactors=degree(f),degf=degree(f),n=level(f.mvar())-1;
548  SFormList minEvaluation;
549  CFFList minFactorisation;
550  int samefactors=0, failedfactor=0, tried=0;
551  FFRandom gen;
552  CFFList unilist;
553
554  if ( degree(Extension) >0 ) GFRandom gen;
555  else { if ( degree(Extension) == 0 ) FFRandom gen;
556  else {
557#ifdef HAVE_SINGULAR_ERROR
558    WerrorS("libfac: evaluate: Extension not inFF() or inGF() !");
559#else
560#ifndef NOSTREAMIO
561    CERR << "libfac: evaluate: " << Extension << " not inFF() or inGF() !"
562         << "\n";
563#endif
564#endif
565    FFRandom gen; }}
566  REvaluation k(1,n,gen);
567  k.nextpoint();
568  for ( int i=1; i<=maxtries ; i++){
569    // k.nextpoint();
570    SFormList Substitutionlist;
571    for ( int j=1; j<=n; j++ )
572     Substitutionlist.insert(SForm(Variable(j),k[j]));
573    k.nextpoint();
574    CanonicalForm g=substitutePoly(f,Substitutionlist);
575    if ( various_tests(g, degf,1) ){ // found a valid point
576      failedfactor = 0; tried += 1;
577      if ( degree(Extension) == 0   )
578        unilist = factorize(g,1); // poly is sqr-free!
579      else
580      {
581        unilist = factorize2(g,Extension,mipo);
582      }
583      if (unilist.length() <= minfactors )
584      {
585        minfactors=unilist.length();
586        minEvaluation=Substitutionlist;
587        minFactorisation=unilist;
588      }
589      else samefactors +=1;
590
591      if (unilist.length() == 1 ) // wow! we found f is irreducible!
592      {
593        BestEvaluationpoint=minEvaluation;
594        BestFactorisation=minFactorisation;
595        return 1;
596      }
597
598      if ( samefactors >= sametries ) // now we stop ( maybe polynomial *has*
599                                      // minfactors factors? )
600      {
601        BestEvaluationpoint=minEvaluation;
602        BestFactorisation=minFactorisation;
603        return minfactors;
604      }
605
606    }
607    else
608      failedfactor += 1;
609
610    if ( failedfactor >= failtries ) // now we stop ( perhaps Extension isn't
611                                     // big enough )
612    {
613      if ( tried == 0 )
614        return 0;
615      else
616      {
617        BestEvaluationpoint=minEvaluation;
618        BestFactorisation=minFactorisation;
619        return minfactors;
620      }
621    }
622  }
623  BestEvaluationpoint=minEvaluation;
624  BestFactorisation=minFactorisation;
625  return minfactors;
626}
627
628#ifdef EXPERIMENTAL
629static int
630find_evaluation(int maxtries, int sametries, int failtries, const CanonicalForm &f , const Variable & Extension, SFormList & BestEvaluationpoint, CFFList & BestFactorisation ){
631  int success;
632
633  success=evaluate( maxtries, sametries, failtries, f , Extension, BestEvaluationpoint, BestFactorisation );
634  return success;
635}
636#endif
637
638///////////////////////////////////////////////////////////////
639// A factorization routine for a sqrfree polynomial.         //
640// Returns the list of factors.                              //
641///////////////////////////////////////////////////////////////
642CFFList
643Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar)
644{
645  CanonicalForm f,lt,ff,ffuni;
646  Variable Extension=alpha.mvar();
647  CFFList Outputlist,UnivariateFactorlist,Outputlist2;
648  SFormList Substitutionlist, Evaluationpoint;
649  CFFactor copy;
650  int mainvar=Mainvar,success,oldmainvar;
651  CFMap m;
652
653  // INTERRUPTHANDLER
654  if ( interrupt_handle() ) return CFFList() ;
655  // INTERRUPTHANDLER
656
657  if ( F.isUnivariate() ) // could have lost one Variable elsewhere
658  {
659    if ( degree(Extension) == 0 )
660    {
661      TIMING_START(evaluate_time);
662      Outputlist = factorize(F,1); // poly is sqr-free
663      TIMING_END(evaluate_time);
664      return Outputlist;
665    }
666    else
667    {
668      if (Extension.level()<0)
669      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
670               degree(getMipo(Extension,'x')) );
671      else
672      DEBOUTLN(CERR, "Univ. Factorization over extension of level ??",
673                Extension.level());
674      TIMING_START(evaluate_time);
675     #if 1
676     Outputlist = factorize2(F,Extension,alpha);
677     #else
678      Variable X;
679      CanonicalForm mipo=getMipo(Extension,X);
680      CFList as(mipo);
681      Outputlist = newfactoras( F, as, 1);
682     #endif
683      TIMING_END(evaluate_time);
684      return Outputlist;
685    }
686  }
687
688  if ( Mainvar ) oldmainvar=Mainvar; else oldmainvar=level(F);
689  // First choose a main variable; this may be revisted in the next step
690  mainvar = choose_main_variable(F);
691  // Let`s look if @f/@mainvar is nonzero
692  mainvar = necessary_condition(F,mainvar);
693  // Now we have definetly choosen a main variable
694  // swap poly such that the mainvar has highest level
695  f=swapvar(F,mainvar,level(F));
696
697  // INTERRUPTHANDLER
698  if ( interrupt_handle() ) return CFFList() ;
699  // INTERRUPTHANDLER
700
701  if ( oldmainvar != mainvar ){
702    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped poly ", F);
703    DEBOUT(CERR, " in ", f); DEBOUTNL(CERR);
704    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped  ", oldmainvar );
705    DEBOUT(CERR, " <-- ", mainvar ); DEBOUT(CERR, "  Mainvar= ", f.mvar());
706    DEBOUTNL(CERR);
707    ff = f.deriv();
708    TIMING_START(discr_time);
709    ffuni = gcd(f,ff);
710    TIMING_END(discr_time);
711    if ( !(ffuni.isOne()) ){ //discriminante nonzero: split poly
712      DEBOUTLN(CERR,"Nontrivial GCD of f= ", f);
713      DEBOUTLN(CERR,"             and @f= ", ff);
714      DEBOUTLN(CERR,"          GCD(f,@f)= ", ffuni);
715      ff=f/ffuni;
716      CFFList Outputlist_a, Outputlist_b;
717      Outputlist_a = Factorized(ff,alpha);
718      DEBOUTLN(CERR, "Outputlist_a = ", Outputlist_a);
719      Outputlist_b = Factorized(ffuni,alpha);
720      DEBOUTLN(CERR, "Outputlist_b = ", Outputlist_b);
721      Outputlist = UnionCFFL(Outputlist_a, Outputlist_b);
722      // have to back-swapvar the factors....
723      for ( CFFListIterator i=Outputlist; i.hasItem(); i++ ){
724        copy=i.getItem();
725        Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
726      }
727      DEBOUTLN(CERR, "Outputlist2 (a+b swapped) (to return) = ", Outputlist2);
728      return Outputlist2;
729    }
730  }
731
732  // Check special cases
733  for ( int i=1; i<=level(F); i++)
734  {
735    if ( degree(f,Variable(i) ) == 1 ) 
736    //test trivial case; only true iff F is primitiv w.r.t every variable; else check (if F=ax+b) gcd(a,b)=1 ?
737    {
738      DEBOUTLN(CERR, "Trivial case: ", F);
739      Outputlist.append(CFFactor(F,1));
740      return Outputlist;
741    }
742  }
743
744  // Look at the leading term:
745  lt = LC(f);
746  DEBOUTLN(CERR, "Leading term: ", lt);
747  //if ( lt != f.genOne() )
748  if ( !lt.isOne() )
749  {
750    // make the polynomial monic in the main variable
751    ff = make_monic(f,lt); ffuni = ff;
752    DEBOUTLN(CERR, "make_monic returned: ", ff);
753  }
754  else{ ff= f; ffuni= ff; }
755
756  TIMING_START(evaluate_time);
757  success=evaluate(min(10,max(degree(ff), 5)), min(degree(ff),3), min(degree(ff),3), ff, Extension, alpha, Substitutionlist,UnivariateFactorlist);
758  DEBOUTLN(CERR,  "Returned from evaluate: success: ", success);
759  for ( SFormListIterator ii=Substitutionlist; ii.hasItem(); ii++ )
760  {
761    DEBOUTLN(CERR, "Substituting ", ii.getItem().factor());
762    DEBOUTLN(CERR, "       with value: ", ii.getItem().exp());
763  }
764
765  if ( success==0 ) // evalute wasn't successfull
766  {
767    success= specializePoly(ffuni,Extension,degree(ff),Substitutionlist,1,getNumVars(compress(ff,m)));
768    DEBOUTLN(CERR,  "Returned from specializePoly: success: ", success);
769    if (success == 0 ) // No spezialisation could be found
770    {
771#ifdef HAVE_SINGULAR_ERROR
772      WarnS("libfac: Factorize: ERROR: Not able to find a valid specialization!");
773#else
774#ifndef NOSTREAMIO
775      CERR << "libfac: Factorize: ERROR: Not able to find a valid specialization!\n"
776           << rcsid << errmsg << "\n";
777#else
778       ;
779#endif
780#endif
781      Outputlist.append(CFFactor(F,1));
782      return Outputlist;
783    }
784
785    // INTERRUPTHANDLER
786    if ( interrupt_handle() ) return CFFList() ;
787    // INTERRUPTHANDLER
788
789    ffuni = substitutePoly(ff,Substitutionlist);
790    // We now have an univariat poly; factorize that
791    if ( degree(Extension) == 0   )
792    {
793      DEBOUTMSG(CERR, "Univ. Factorization over the ground field");
794      UnivariateFactorlist = factorize(ffuni,1); // univ. poly is sqr-free!
795    }
796    else
797    {
798      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
799               degree(getMipo(Extension,'x')) );
800     #if 1
801      UnivariateFactorlist = factorize2(ffuni,Extension,alpha);
802     #else
803      Variable X;
804      CanonicalForm mipo=getMipo(Extension,X);
805      CFList as(mipo);
806      UnivariateFactorlist = newfactoras( ffuni, as, 1);
807     #endif
808    }
809  }
810  else
811  {
812    ffuni = substitutePoly(ff,Substitutionlist);
813  }
814    TIMING_END(evaluate_time);
815  if (UnivariateFactorlist.length() == 1)
816  { // poly is irreduzibel
817    DEBOUTLN(CERR, "Univ. poly is irreduzible: ", UnivariateFactorlist);
818    Outputlist.append(CFFactor(F,1));
819    return Outputlist;
820  }
821  else
822  { // we have factors
823    DEBOUTSL(CERR);
824    DEBOUT(CERR, "Univariate poly has " , UnivariateFactorlist.length());
825    DEBOUT(CERR, " factors:  ", ffuni);
826    DEBOUT(CERR, " = ", UnivariateFactorlist); DEBOUTNL(CERR);
827
828    // INTERRUPTHANDLER
829    if ( interrupt_handle() ) return CFFList() ;
830    // INTERRUPTHANDLER
831
832    TIMING_START(hensel_time);
833    Outputlist = MultiHensel(ff,UnivariateFactorlist,Substitutionlist, alpha);
834    DEBOUTLN(CERR, "Outputlist after MultiHensel: ", Outputlist);
835    TIMING_END(hensel_time);
836
837    // INTERRUPTHANDLER
838    if ( interrupt_handle() ) return CFFList() ;
839    // INTERRUPTHANDLER
840
841    TIMING_START(truefactor_time);
842    Outputlist = Truefactors(ff, level(ff), Substitutionlist, Outputlist);
843    DEBOUTLN(CERR, "Outputlist after Truefactors: ", Outputlist);
844    TIMING_END(truefactor_time);
845
846    // INTERRUPTHANDLER
847    if ( interrupt_handle() ) return CFFList() ;
848    // INTERRUPTHANDLER
849
850    //if ( lt != f.genOne() )
851    if ( !lt.isOne() )
852    {
853      Outputlist = not_monic(Outputlist,lt,ff,level(ff));
854      DEBOUTLN(CERR, "not_monic returned: ", Outputlist);
855    }
856
857    // have to back-swapvar the factors....
858    for ( CFFListIterator i=Outputlist; i.hasItem(); i++ )
859    {
860      copy=i.getItem();
861      Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
862    }
863
864    return Outputlist2;
865  }
866}
867
868// for debuggig:
869int cmpCF( const CFFactor & f, const CFFactor & g );
870
871///////////////////////////////////////////////////////////////
872// The user front-end for a uni/multivariate factorization   //
873// routine. F needs not to be SqrFree.                       //
874// Option of * choosing a  main variable (n.y.i.)            //
875//           * choosing an algebraic extension (n.y.u.)      //
876//           * ensuring poly is sqrfree (n.y.i.)             //
877// use Factorize(F,alpha,is_SqrFree) if not over Zp[x]/Q[x]  //
878///////////////////////////////////////////////////////////////
879int find_mvar(const CanonicalForm &f);
880CFFList Factorize(const CanonicalForm & F, int is_SqrFree )
881{
882  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
883  ListIterator<CFFactor> i,j;
884  CanonicalForm g=1,unit=1,r=1;
885  Variable minpoly; // dummy
886  int exp;
887  CFMap m;
888
889  // INTERRUPTHANDLER
890  if ( interrupt_handle() ) return CFFList() ;
891  // INTERRUPTHANDLER
892
893  DEBINCLEVEL(CERR, "Factorize");
894  DEBOUTMSG(CERR, rcsid);
895  DEBOUTLN(CERR, "Called with F= ", F);
896  if ( getCharacteristic() == 0 )
897  { // char == 0
898    TIMING_START(factorize_time);
899    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
900    Outputlist= factorize(F);
901    // Factorization in char=0 doesn't sometimes return at least two elements!!!
902    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
903      Outputlist.insert(CFFactor(1,1));
904    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
905    TIMING_END(factorize_time);
906    DEBDECLEVEL(CERR, "Factorize");
907    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
908    return Outputlist;
909  }
910  TIMING_START(factorize_time);
911  // search an "optimal" main variavble
912  int mv=F.level();
913  if (mv != LEVELBASE && ! F.isUnivariate() )
914  {
915     mv=find_mvar(F);
916     if (mv!=F.level())
917     {
918       swapvar(F,Variable(mv),F.mvar());
919     }
920  }
921
922  ///////
923  // Maybe it`s better to add a sqrfree-test before?
924  // (If gcd is fast...)
925  ///////
926  //  if ( ! isSqrFree(F) ){
927  if ( ! is_SqrFree )
928  {
929    TIMING_START(sqrfree_time);
930    SqrFreeList = sqrFree(F,0,false) ; // first sqrfree the polynomial
931    // Ex.: char=p   f= x^p*(y+1);
932    // InternalSqrFree(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
933    TIMING_END(sqrfree_time);
934
935    // INTERRUPTHANDLER
936    if ( interrupt_handle() ) return CFFList() ;
937    // INTERRUPTHANDLER
938
939  }
940  else
941    SqrFreeList.append(CFFactor(F,1));
942  DEBOUTLN(CERR, "SqrFreeList= ", SqrFreeList);
943  for ( i=SqrFreeList; i.hasItem(); i++ )
944  {
945    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
946    // We need a compress on each list item ! Maybe we have less variables!
947    g =compress(i.getItem().factor(),m);
948    exp = i.getItem().exp();
949    if ( getNumVars(g) ==0 ) // a constant; Exp==1
950      Outputlist.append( CFFactor(g,1) ) ;
951    else// a real polynomial
952      if ( g.isUnivariate() )
953      {
954        Intermediatelist=factorize(g,1); // poly is sqr-free!
955        for ( j=Intermediatelist; j.hasItem(); j++ )
956          //Normally j.getItem().exp() should be 1
957          Outputlist.append( CFFactor( m(j.getItem().factor()),exp*j.getItem().exp()));
958      }
959      else
960      { // multivariate polynomial
961        if ( g.isHomogeneous() )
962        {
963          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
964          // Now we can substitute one variable to 1, factorize and then
965          // look on the resulting factors and their monomials for
966          // backsubstitution of the substituted variable.
967          Intermediatelist = HomogFactor(g, minpoly, 0);
968        }
969        else // not homogeneous
970          Intermediatelist = Factorized(g, minpoly, 0);
971
972        // INTERRUPTHANDLER
973        if ( interrupt_handle() ) return CFFList() ;
974        // INTERRUPTHANDLER
975
976        for ( j=Intermediatelist; j.hasItem(); j++ )
977          //Normally j.getItem().exp() should be 1
978          Outputlist= appendCFFL( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
979      }
980  }
981  g=1; unit=1;
982  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
983  for ( i=Outputlist; i.hasItem(); i++ )
984    if ( level(i.getItem().factor()) > 0 )
985    {
986      unit = lc(i.getItem().factor());
987      if ( getNumVars(unit) == 0 )
988      { // a constant; possibly 1
989        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
990        g *=power(i.getItem().factor()/unit,i.getItem().exp());
991      }
992      else
993      {
994        Outputlist2.append(i.getItem());
995        g *=power(i.getItem().factor(),i.getItem().exp());
996      }
997    }
998
999  r=F/g;
1000  Outputlist2.insert(CFFactor(r,1));
1001
1002  if ((mv!=F.level()) && (! F.isUnivariate() ))
1003  {
1004    CFFListIterator J=Outputlist2;
1005    for ( ; J.hasItem(); J++)
1006    {
1007      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1008    }
1009    swapvar(F,Variable(mv),F.mvar());
1010  }
1011
1012  DEBDECLEVEL(CERR, "Factorize");
1013  TIMING_END(factorize_time);
1014
1015  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1016  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1017  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1018  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1019  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1020  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1021
1022  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1023
1024  return Outputlist2;
1025}
1026
1027///////////////////////////////////////////////////////////////
1028// The user front-end for a uni/multivariate factorization   //
1029// routine. F needs not to be SqrFree.                       //
1030// Option of * choosing a  main variable (n.y.i.)            //
1031//           * choosing an algebraic extension (n.y.u.)      //
1032//           * ensuring poly is sqrfree (n.y.i.)             //
1033///////////////////////////////////////////////////////////////
1034static bool fdivides2(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &minpoly)
1035{
1036  if (minpoly!=0)
1037  {
1038  #if 0
1039    Variable Alpha=minpoly.mvar();
1040    Variable X=rootOf(minpoly);
1041    CanonicalForm rF=replacevar(F,Alpha,X);
1042    CanonicalForm rG=replacevar(G,Alpha,X);
1043    return fdivides(rF,rG);;
1044  #else
1045    if (degree(F,F.mvar()) > degree(G,F.mvar())) return false;
1046    return true;
1047    //CanonicalForm a,b;
1048    //mydivrem(G,F,a,b);
1049    //if (b.isZero()) return true;
1050    //else return false;
1051  #endif
1052  }
1053  else
1054   return fdivides(F,G);
1055}
1056CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly )
1057{
1058#ifndef NDEBUG
1059  //printf("start Factorize2(int_flag=%d)\n",libfac_interruptflag);
1060#endif
1061  CFFList G,H;
1062  CanonicalForm fac;
1063  int d,e;
1064  ListIterator<CFFactor> i,k;
1065  libfac_interruptflag=0;
1066  CFFList iF=Factorize(F,minpoly);
1067  if ((libfac_interruptflag==0)||(iF.isEmpty()))
1068    H=iF;
1069  else
1070  {
1071#ifndef NDEBUG
1072    //printf("variant 2(int_flag=%d)\n",libfac_interruptflag);
1073#endif
1074    libfac_interruptflag=0;
1075    iF=Factorize(F);
1076    if (libfac_interruptflag==0)
1077    {
1078      i = iF;
1079      while( i.hasItem())
1080      {
1081        d = i.getItem().exp();
1082        fac = i.getItem().factor();
1083        if (fdivides(fac,F))
1084        {
1085          if ((getNumVars(fac)==0)||(fac.degree()<=1))
1086          {
1087#ifndef NOSTREAMIO
1088#ifndef NDEBUG
1089            //printf("append trivial factor\n");
1090#endif
1091#endif
1092            H.append( CFFactor( fac, d));
1093            do {F/=fac; d--; } while (d>0);
1094          }
1095          else
1096          {
1097            G = Factorize( fac, minpoly);
1098            if (libfac_interruptflag!=0)
1099            {
1100              libfac_interruptflag=0;
1101              k = G;
1102              while( k.hasItem())
1103              {
1104                fac = k.getItem().factor();
1105                int dd = k.getItem().exp()*d;
1106                e=0;
1107                while ((!fac.isZero())&& fdivides2(fac,F,minpoly) && (dd>0))
1108                {
1109#ifndef NOSTREAMIO
1110#ifndef NDEBUG
1111                  //out_cf("factor:",fac,"\n");
1112#endif
1113#endif
1114                  e++;dd--;
1115                  F/=fac;
1116                }
1117                if (e>0) H.append( CFFactor( fac , e ) );
1118                ++k;
1119              }
1120            }
1121          }
1122        }
1123        ++i;
1124      }
1125    }
1126  }
1127  //Outputlist = newfactoras( F, as, 1);
1128  if((isOn(SW_USE_NTL_SORT))&&(!H.isEmpty())) H.sort(cmpCF);
1129#ifndef NDEBUG
1130  //printf("end Factorize2(%d)\n",libfac_interruptflag);
1131#endif
1132  return H;
1133}
1134
1135CFFList
1136Factorize(const CanonicalForm & F, const CanonicalForm & minpoly, int is_SqrFree )
1137{
1138  //out_cf("Factorize: F=",F,"\n");
1139  //out_cf("           minpoly:",minpoly,"\n");
1140  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
1141  ListIterator<CFFactor> i,j;
1142  CanonicalForm g=1,unit=1,r=1;
1143  //Variable minpoly; // reserved (-> Factorisation over algebraic Extensions)
1144  int exp;
1145  CFMap m;
1146
1147  // INTERRUPTHANDLER
1148  if ( interrupt_handle() ) return CFFList() ;
1149  // INTERRUPTHANDLER
1150
1151  DEBINCLEVEL(CERR, "Factorize");
1152  DEBOUTMSG(CERR, rcsid);
1153  DEBOUTLN(CERR, "Called with F= ", F);
1154  if ( getCharacteristic() == 0 )
1155  { // char == 0
1156    TIMING_START(factorize_time);
1157    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
1158    #if 0
1159    // SHOULD: Outputlist= factorize(F,minpoly);
1160    Outputlist= factorize(F);
1161    #else
1162    if (minpoly!=0)
1163    {
1164      if ( F.isHomogeneous() )
1165      {
1166        DEBOUTLN(CERR, "Poly is homogeneous! : ", F);
1167        // Now we can substitute one variable to 1, factorize and then
1168        // look on the resulting factors and their monomials for
1169        // backsubstitution of the substituted variable.
1170        Outputlist=HomogFactor(F, minpoly, 0);
1171      }
1172      else
1173      {
1174        CFList as(minpoly);
1175        CFFList sqF=sqrFree(F,0,false); // sqrFreeZ
1176        CFFList G,H;
1177        CanonicalForm fac;
1178        int d;
1179        ListIterator<CFFactor> i,k;
1180        for ( i = sqF; i.hasItem(); ++i )
1181        {
1182          d = i.getItem().exp();
1183          fac = i.getItem().factor();
1184          G = newfactoras( fac, as, 1);
1185          for ( k = G; k.hasItem(); ++k )
1186          {
1187            fac = k.getItem().factor();
1188            int dd = k.getItem().exp();
1189            H.append( CFFactor( fac , d*dd ) );
1190          }
1191        }
1192        //Outputlist = newfactoras( F, as, 1);
1193        Outputlist = H;
1194      }
1195    }
1196    else
1197      Outputlist=factorize(F);
1198    #endif
1199    // Factorization in char=0 doesn't sometimes return at least two elements!!!
1200    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
1201      Outputlist.insert(CFFactor(1,1));
1202    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
1203    TIMING_END(factorize_time);
1204    DEBDECLEVEL(CERR, "Factorize");
1205    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1206    //out_cff(Outputlist);
1207    return Outputlist;
1208  }
1209  TIMING_START(factorize_time);
1210  // search an "optimal" main variavble
1211  int mv=F.level();
1212  if (mv != LEVELBASE && ! F.isUnivariate() )
1213  {
1214     mv=find_mvar(F);
1215     if (mv!=F.level())
1216     {
1217       swapvar(F,Variable(mv),F.mvar());
1218     }
1219  }
1220
1221  ///////
1222  // Maybe it`s better to add a sqrfree-test before?
1223  // (If gcd is fast...)
1224  ///////
1225  //  if ( ! isSqrFree(F) ){
1226  if ( ! is_SqrFree )
1227  {
1228    TIMING_START(sqrfree_time);
1229    SqrFreeList = sqrFree(F, minpoly) ; // first sqrfree the polynomial
1230    // Ex.: char=p   f= x^p*(y+1);
1231    // InternalSqrFree(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
1232    TIMING_END(sqrfree_time);
1233
1234    // INTERRUPTHANDLER
1235    if ( interrupt_handle() ) return CFFList() ;
1236    // INTERRUPTHANDLER
1237
1238  }
1239  else
1240    SqrFreeList.append(CFFactor(F,1));
1241  DEBOUTLN(CERR, "SqrFreeList= ", SqrFreeList);
1242  for ( i=SqrFreeList; i.hasItem(); i++ )
1243  {
1244    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
1245    // We need a compress on each list item ! Maybe we have less variables!
1246    g =compress(i.getItem().factor(),m);
1247    exp = i.getItem().exp();
1248    if ( getNumVars(g) ==0 ) // a constant; Exp==1
1249      Outputlist.append( CFFactor(g,1) ) ;
1250    else// a real polynomial
1251    {
1252      if ( g.isUnivariate() )
1253      {
1254        Variable alpha=rootOf(minpoly);
1255        Intermediatelist=factorize2(g,alpha,minpoly); // poly is sqr-free!
1256        for ( j=Intermediatelist; j.hasItem(); j++ )
1257          //Normally j.getItem().exp() should be 1
1258          Outputlist.append(
1259           CFFactor( m(replacevar(j.getItem().factor(),alpha,minpoly.mvar())),
1260             exp*j.getItem().exp()));
1261      }
1262      else // multivariate polynomial
1263      {
1264        if ( g.isHomogeneous() )
1265        {
1266          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
1267          // Now we can substitute one variable to 1, factorize and then
1268          // look on the resulting factors and their monomials for
1269          // backsubstitution of the substituted variable.
1270          Intermediatelist = HomogFactor(g, minpoly, 0);
1271        }
1272        else // not homogeneous
1273          Intermediatelist = Factorized(g, minpoly, 0);
1274
1275        // INTERRUPTHANDLER
1276        if ( interrupt_handle() ) return CFFList() ;
1277        // INTERRUPTHANDLER
1278
1279        for ( j=Intermediatelist; j.hasItem(); j++ )
1280          //Normally j.getItem().exp() should be 1
1281          Outputlist= appendCFFL( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
1282      }
1283    }
1284  }
1285  g=1; unit=1;
1286  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
1287  for ( i=Outputlist; i.hasItem(); i++ )
1288    if ( level(i.getItem().factor()) > 0 ){
1289      unit = lc(i.getItem().factor());
1290      if ( getNumVars(unit) == 0 ){ // a constant; possibly 1
1291        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
1292        g *=power(i.getItem().factor()/unit,i.getItem().exp());
1293      }
1294      else{
1295        Outputlist2.append(i.getItem());
1296        g *=power(i.getItem().factor(),i.getItem().exp());
1297      }
1298    }
1299
1300  r=F/g;
1301  Outputlist2.insert(CFFactor(r,1));
1302
1303  if ((mv!=F.level()) && (! F.isUnivariate() ))
1304  {
1305    CFFListIterator J=Outputlist2;
1306    for ( ; J.hasItem(); J++)
1307    {
1308      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1309    }
1310    swapvar(F,Variable(mv),F.mvar());
1311  }
1312
1313  DEBDECLEVEL(CERR, "Factorize");
1314  TIMING_END(factorize_time);
1315
1316  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1317  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1318  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1319  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1320  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1321  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1322
1323  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1324
1325  //out_cff(Outputlist2);
1326  return Outputlist2;
1327}
1328
1329/*
1330$Log: not supported by cvs2svn $
1331Revision 1.39  2008/01/22 09:51:37  Singular
1332*hannes: sqrFree/InternalSqrFree -> factory
1333
1334Revision 1.38  2008/01/07 13:34:56  Singular
1335*hannes: omse optiomzations(isOne)
1336
1337Revision 1.37  2007/10/25 14:45:41  Singular
1338*hannes: homgfactor for alg.ext of Q
1339
1340Revision 1.36  2007/10/15 18:03:11  Singular
1341*hannes: // debug stuff
1342
1343Revision 1.35  2007/06/14 14:16:35  Singular
1344*hannes: Factorize2 etc.
1345
1346Revision 1.34  2007/06/02 10:21:57  Singular
1347*hannes: fdivides2 again
1348
1349Revision 1.33  2007/05/25 16:02:01  Singular
1350*hannes: removed diophant_error, format
1351
1352Revision 1.32  2007/05/25 12:59:05  Singular
1353*hannes: fdivides2
1354
1355Revision 1.31  2007/05/22 14:49:52  Singular
1356*hannes: format
1357
1358Revision 1.30  2007/05/22 14:30:53  Singular
1359*hannes: diophant_error
1360
1361Revision 1.29  2007/05/22 13:18:57  Singular
1362*hannes: Factorize2: div test, sort etc.
1363
1364Revision 1.28  2007/05/21 17:56:55  Singular
1365*hannes: fixed exp.
1366
1367Revision 1.27  2007/05/21 16:50:56  Singular
1368*hannes: fix fdivide test
1369
1370Revision 1.26  2007/05/21 16:40:12  Singular
1371*hannes: Factorize2
1372
1373Revision 1.25  2007/05/15 15:50:42  Singular
1374*hannes: Factorize2
1375
1376Revision 1.24  2007/05/15 14:46:48  Singular
1377*hannes: factorize in Zp(a)[x...]
1378
1379Revision 1.23  2006/05/16 14:46:49  Singular
1380*hannes: gcc 4.1 fixes
1381
1382Revision 1.22  2006/04/28 13:46:29  Singular
1383*hannes: better tests for 0, 1
1384
1385Revision 1.21  2005/12/12 18:02:03  Singular
1386*hannes: use sorting option in Factorize
1387
1388Revision 1.20  2005/12/05 15:47:32  Singular
1389*hannes: is_homogeneous -> factory: isHomogeneous
1390
1391Revision 1.19  2005/10/17 13:18:44  Singular
1392*hannes: apply sqrFree before newfactoras (Factorize in Q(a))
1393
1394Revision 1.18  2005/10/17 13:17:39  Singular
1395*hannes: aplly sqrFree before newfactoras (Factorize in Q(a))
1396
1397Revision 1.17  2004/12/10 10:15:06  Singular
1398*pohl: AlgExtGenerator etc.
1399
1400Revision 1.16  2003/05/28 11:52:52  Singular
1401*pfister/hannes: newfactoras, alg_gcd, divide (see bug_33)
1402
1403Revision 1.15  2003/02/14 15:51:15  Singular
1404* hannes: bugfix
1405          could not factorize x2+xy+y2 in Fp(a)[x,y], a2+a+1=0
1406          (factorize2 does nor sanity checks)
1407
1408Revision 1.14  2002/08/19 11:11:32  Singular
1409* hannes/pfister: alg_gcd etc.
1410
1411Revision 1.13  2002/07/30 17:06:47  Singular
1412*hannes: uuh - factorize in Q(a)[x] is missing, use Q[a][x].
1413
1414Revision 1.12  2002/07/30 15:10:22  Singular
1415*hannes: added Factorize for alg. ext.
1416
1417Revision 1.11  2001/08/22 14:21:16  Singular
1418*hannes: added search for main var to Factorize
1419
1420Revision 1.10  2001/08/08 14:26:55  Singular
1421*hannes: Dan's HAVE_SINGULAR_ERROR
1422
1423Revision 1.9  2001/08/08 11:59:12  Singular
1424*hannes: Dan's NOSTREAMIO changes
1425
1426Revision 1.8  2001/08/06 08:32:54  Singular
1427* hannes: code cleanup
1428
1429Revision 1.7  2001/06/21 14:57:05  Singular
1430*hannes/GP: Factorize, newfactoras, ...
1431
1432Revision 1.6  2001/06/18 08:44:41  pfister
1433* hannes/GP/michael: factory debug, Factorize
1434
1435Revision 1.5  1999/06/15 12:54:55  Singular
1436* hannes: debug fixes for Singular-interface
1437
1438Revision 1.4  1997/11/18 16:39:04  Singular
1439* hannes: moved WerrorS from C++ to C
1440     (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc)
1441
1442Revision 1.3  1997/09/12 07:19:46  Singular
1443* hannes/michael: libfac-0.3.0
1444
1445Revision 1.6  1997/04/25 22:18:40  michael
1446changed lc == 1 to lc == unit in choose_mainvar
1447changed cerr and cout messages for use with Singular
1448Version for libfac-0.2.1
1449
1450Revision 1.5  1997/01/17 05:04:03  michael
1451* added support for homogenous polynomials
1452* exported functions to homogfactor.cc
1453
1454*/
Note: See TracBrowser for help on using the repository browser.