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

spielwiese
Last change on this file since e89e56 was e89e56, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes: fact.tst git-svn-id: file:///usr/local/Singular/svn/trunk@10621 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 46.5 KB
Line 
1/* Copyright 1996 Michael Messollen. All rights reserved. */
2///////////////////////////////////////////////////////////////////////////////
3static char * rcsid = "$Id: Factor.cc,v 1.42 2008-03-17 17:44:16 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= myUnion( 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 ( SqrFreeTest(g,1) ) // 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 = myUnion(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 ( ! SqrFreeTest(F) ){
927  if ( ! is_SqrFree )
928  {
929    TIMING_START(sqrfree_time);
930    SqrFreeList = SqrFreeMV(F) ; // first sqrfree the polynomial
931    // don't use sqrFree(F), factory's internal sqrFree for multiv.
932    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
933    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
934    TIMING_END(sqrfree_time);
935
936    // INTERRUPTHANDLER
937    if ( interrupt_handle() ) return CFFList() ;
938    // INTERRUPTHANDLER
939
940  }
941  else
942    SqrFreeList.append(CFFactor(F,1));
943  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
944  for ( i=SqrFreeList; i.hasItem(); i++ )
945  {
946    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
947    // We need a compress on each list item ! Maybe we have less variables!
948    g =compress(i.getItem().factor(),m);
949    exp = i.getItem().exp();
950    if ( getNumVars(g) ==0 ) // a constant; Exp==1
951      Outputlist.append( CFFactor(g,1) ) ;
952    else// a real polynomial
953      if ( g.isUnivariate() )
954      {
955        Intermediatelist=factorize(g,1); // poly is sqr-free!
956        for ( j=Intermediatelist; j.hasItem(); j++ )
957          //Normally j.getItem().exp() should be 1
958          Outputlist.append( CFFactor( m(j.getItem().factor()),exp*j.getItem().exp()));
959      }
960      else
961      { // multivariate polynomial
962        if ( g.isHomogeneous() )
963        {
964          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
965          // Now we can substitute one variable to 1, factorize and then
966          // look on the resulting factors and their monomials for
967          // backsubstitution of the substituted variable.
968          Intermediatelist = HomogFactor(g, minpoly, 0);
969        }
970        else // not homogeneous
971          Intermediatelist = Factorized(g, minpoly, 0);
972
973        // INTERRUPTHANDLER
974        if ( interrupt_handle() ) return CFFList() ;
975        // INTERRUPTHANDLER
976
977        for ( j=Intermediatelist; j.hasItem(); j++ )
978          //Normally j.getItem().exp() should be 1
979          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
980      }
981  }
982  g=1; unit=1;
983  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
984  for ( i=Outputlist; i.hasItem(); i++ )
985    if ( level(i.getItem().factor()) > 0 )
986    {
987      unit = lc(i.getItem().factor());
988      if ( getNumVars(unit) == 0 )
989      { // a constant; possibly 1
990        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
991        g *=power(i.getItem().factor()/unit,i.getItem().exp());
992      }
993      else
994      {
995        Outputlist2.append(i.getItem());
996        g *=power(i.getItem().factor(),i.getItem().exp());
997      }
998    }
999
1000  r=F/g;
1001  Outputlist2.insert(CFFactor(r,1));
1002
1003  if ((mv!=F.level()) && (! F.isUnivariate() ))
1004  {
1005    CFFListIterator J=Outputlist2;
1006    for ( ; J.hasItem(); J++)
1007    {
1008      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1009    }
1010    swapvar(F,Variable(mv),F.mvar());
1011  }
1012
1013  DEBDECLEVEL(CERR, "Factorize");
1014  TIMING_END(factorize_time);
1015
1016  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1017  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1018  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1019  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1020  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1021  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1022
1023  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1024
1025  return Outputlist2;
1026}
1027
1028///////////////////////////////////////////////////////////////
1029// The user front-end for a uni/multivariate factorization   //
1030// routine. F needs not to be SqrFree.                       //
1031// Option of * choosing a  main variable (n.y.i.)            //
1032//           * choosing an algebraic extension (n.y.u.)      //
1033//           * ensuring poly is sqrfree (n.y.i.)             //
1034///////////////////////////////////////////////////////////////
1035static bool fdivides2(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &minpoly)
1036{
1037  if (minpoly!=0)
1038  {
1039  #if 0
1040    Variable Alpha=minpoly.mvar();
1041    Variable X=rootOf(minpoly);
1042    CanonicalForm rF=replacevar(F,Alpha,X);
1043    CanonicalForm rG=replacevar(G,Alpha,X);
1044    return fdivides(rF,rG);;
1045  #else
1046    if (degree(F,F.mvar()) > degree(G,F.mvar())) return false;
1047    return true;
1048    //CanonicalForm a,b;
1049    //mydivrem(G,F,a,b);
1050    //if (b.isZero()) return true;
1051    //else return false;
1052  #endif
1053  }
1054  else
1055   return fdivides(F,G);
1056}
1057CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly )
1058{
1059#ifndef NDEBUG
1060  //printf("start Factorize2(int_flag=%d)\n",libfac_interruptflag);
1061#endif
1062  CFFList G,H;
1063  CanonicalForm fac;
1064  int d,e;
1065  ListIterator<CFFactor> i,k;
1066  libfac_interruptflag=0;
1067  CFFList iF=Factorize(F,minpoly);
1068  if ((libfac_interruptflag==0)&&(!iF.isEmpty()))
1069    H=iF;
1070  else
1071  {
1072#ifndef NDEBUG
1073    //printf("variant 2(int_flag=%d)\n",libfac_interruptflag);
1074#endif
1075    libfac_interruptflag=0;
1076    iF=Factorize(F);
1077    if (libfac_interruptflag==0)
1078    {
1079      i = iF;
1080      while( i.hasItem())
1081      {
1082        d = i.getItem().exp();
1083        fac = i.getItem().factor();
1084        if (fdivides(fac,F))
1085        {
1086          if ((getNumVars(fac)==0)||(fac.degree()<=1))
1087          {
1088#ifndef NOSTREAMIO
1089#ifndef NDEBUG
1090            //printf("append trivial factor\n");
1091#endif
1092#endif
1093            H.append( CFFactor( fac, d));
1094            do {F/=fac; d--; } while (d>0);
1095          }
1096          else
1097          {
1098            G = Factorize( fac, minpoly);
1099            if (libfac_interruptflag!=0)
1100            {
1101              libfac_interruptflag=0;
1102              k = G;
1103              while( k.hasItem())
1104              {
1105                fac = k.getItem().factor();
1106                int dd = k.getItem().exp()*d;
1107                e=0;
1108                while ((!fac.isZero())&& fdivides2(fac,F,minpoly) && (dd>0))
1109                {
1110#ifndef NOSTREAMIO
1111#ifndef NDEBUG
1112                  //out_cf("factor:",fac,"\n");
1113#endif
1114#endif
1115                  e++;dd--;
1116                  F/=fac;
1117                }
1118                if (e>0) H.append( CFFactor( fac , e ) );
1119                ++k;
1120              }
1121            }
1122          }
1123        }
1124        ++i;
1125      }
1126    }
1127  }
1128  //Outputlist = newfactoras( F, as, 1);
1129  if((isOn(SW_USE_NTL_SORT))&&(!H.isEmpty())) H.sort(cmpCF);
1130#ifndef NDEBUG
1131  //printf("end Factorize2(%d)\n",libfac_interruptflag);
1132#endif
1133  return H;
1134}
1135
1136CFFList
1137Factorize(const CanonicalForm & F, const CanonicalForm & minpoly, int is_SqrFree )
1138{
1139  //out_cf("Factorize: F=",F,"\n");
1140  //out_cf("           minpoly:",minpoly,"\n");
1141  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
1142  ListIterator<CFFactor> i,j;
1143  CanonicalForm g=1,unit=1,r=1;
1144  //Variable minpoly; // reserved (-> Factorisation over algebraic Extensions)
1145  int exp;
1146  CFMap m;
1147
1148  // INTERRUPTHANDLER
1149  if ( interrupt_handle() ) return CFFList() ;
1150  // INTERRUPTHANDLER
1151
1152  DEBINCLEVEL(CERR, "Factorize");
1153  DEBOUTMSG(CERR, rcsid);
1154  DEBOUTLN(CERR, "Called with F= ", F);
1155  if ( getCharacteristic() == 0 )
1156  { // char == 0
1157    TIMING_START(factorize_time);
1158    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
1159    #if 0
1160    // SHOULD: Outputlist= factorize(F,minpoly);
1161    Outputlist= factorize(F);
1162    #else
1163    if (minpoly!=0)
1164    {
1165      if ( F.isHomogeneous() )
1166      {
1167        DEBOUTLN(CERR, "Poly is homogeneous! : ", F);
1168        // Now we can substitute one variable to 1, factorize and then
1169        // look on the resulting factors and their monomials for
1170        // backsubstitution of the substituted variable.
1171        Outputlist=HomogFactor(F, minpoly, 0);
1172      }
1173      else
1174      {
1175        CFList as(minpoly);
1176        CFFList sqF=sqrFree(F); // sqrFreeZ
1177        CFFList G,H;
1178        CanonicalForm fac;
1179        int d;
1180        ListIterator<CFFactor> i,k;
1181        for ( i = sqF; i.hasItem(); ++i )
1182        {
1183          d = i.getItem().exp();
1184          fac = i.getItem().factor();
1185          G = newfactoras( fac, as, 1);
1186          for ( k = G; k.hasItem(); ++k )
1187          {
1188            fac = k.getItem().factor();
1189            int dd = k.getItem().exp();
1190            H.append( CFFactor( fac , d*dd ) );
1191          }
1192        }
1193        //Outputlist = newfactoras( F, as, 1);
1194        Outputlist = H;
1195      }
1196    }
1197    else
1198      Outputlist=factorize(F);
1199    #endif
1200    // Factorization in char=0 doesn't sometimes return at least two elements!!!
1201    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
1202      Outputlist.insert(CFFactor(1,1));
1203    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
1204    TIMING_END(factorize_time);
1205    DEBDECLEVEL(CERR, "Factorize");
1206    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1207    //out_cff(Outputlist);
1208    return Outputlist;
1209  }
1210  TIMING_START(factorize_time);
1211  // search an "optimal" main variavble
1212  int mv=F.level();
1213  if (mv != LEVELBASE && ! F.isUnivariate() )
1214  {
1215     mv=find_mvar(F);
1216     if (mv!=F.level())
1217     {
1218       swapvar(F,Variable(mv),F.mvar());
1219     }
1220  }
1221
1222  ///////
1223  // Maybe it`s better to add a sqrfree-test before?
1224  // (If gcd is fast...)
1225  ///////
1226  //  if ( ! SqrFreeTest(F) ){
1227  if ( ! is_SqrFree )
1228  {
1229    TIMING_START(sqrfree_time);
1230    SqrFreeList = SqrFreeMV(F, minpoly) ; // first sqrfree the polynomial
1231    // don't use sqrFree(F), factory's internal sqrFree for multiv.
1232    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
1233    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
1234    TIMING_END(sqrfree_time);
1235
1236    // INTERRUPTHANDLER
1237    if ( interrupt_handle() ) return CFFList() ;
1238    // INTERRUPTHANDLER
1239
1240  }
1241  else
1242    SqrFreeList.append(CFFactor(F,1));
1243  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
1244  for ( i=SqrFreeList; i.hasItem(); i++ )
1245  {
1246    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
1247    // We need a compress on each list item ! Maybe we have less variables!
1248    g =compress(i.getItem().factor(),m);
1249    exp = i.getItem().exp();
1250    if ( getNumVars(g) ==0 ) // a constant; Exp==1
1251      Outputlist.append( CFFactor(g,1) ) ;
1252    else// a real polynomial
1253    {
1254      if ( g.isUnivariate() )
1255      {
1256        Variable alpha=rootOf(minpoly);
1257        Intermediatelist=factorize2(g,alpha,minpoly); // poly is sqr-free!
1258        for ( j=Intermediatelist; j.hasItem(); j++ )
1259          //Normally j.getItem().exp() should be 1
1260          Outputlist.append(
1261           CFFactor( m(replacevar(j.getItem().factor(),alpha,minpoly.mvar())),
1262             exp*j.getItem().exp()));
1263      }
1264      else // multivariate polynomial
1265      {
1266        if ( g.isHomogeneous() )
1267        {
1268          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
1269          // Now we can substitute one variable to 1, factorize and then
1270          // look on the resulting factors and their monomials for
1271          // backsubstitution of the substituted variable.
1272          Intermediatelist = HomogFactor(g, minpoly, 0);
1273        }
1274        else // not homogeneous
1275          Intermediatelist = Factorized(g, minpoly, 0);
1276
1277        // INTERRUPTHANDLER
1278        if ( interrupt_handle() ) return CFFList() ;
1279        // INTERRUPTHANDLER
1280
1281        for ( j=Intermediatelist; j.hasItem(); j++ )
1282          //Normally j.getItem().exp() should be 1
1283          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
1284      }
1285    }
1286  }
1287  g=1; unit=1;
1288  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
1289  for ( i=Outputlist; i.hasItem(); i++ )
1290    if ( level(i.getItem().factor()) > 0 ){
1291      unit = lc(i.getItem().factor());
1292      if ( getNumVars(unit) == 0 ){ // a constant; possibly 1
1293        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
1294        g *=power(i.getItem().factor()/unit,i.getItem().exp());
1295      }
1296      else{
1297        Outputlist2.append(i.getItem());
1298        g *=power(i.getItem().factor(),i.getItem().exp());
1299      }
1300    }
1301
1302  r=F/g;
1303  Outputlist2.insert(CFFactor(r,1));
1304
1305  if ((mv!=F.level()) && (! F.isUnivariate() ))
1306  {
1307    CFFListIterator J=Outputlist2;
1308    for ( ; J.hasItem(); J++)
1309    {
1310      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1311    }
1312    swapvar(F,Variable(mv),F.mvar());
1313  }
1314
1315  DEBDECLEVEL(CERR, "Factorize");
1316  TIMING_END(factorize_time);
1317
1318  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1319  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1320  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1321  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1322  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1323  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1324
1325  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1326
1327  //out_cff(Outputlist2);
1328  return Outputlist2;
1329}
1330
1331/*
1332$Log: not supported by cvs2svn $
1333Revision 1.38  2008/01/07 13:34:56  Singular
1334*hannes: omse optiomzations(isOne)
1335
1336Revision 1.37  2007/10/25 14:45:41  Singular
1337*hannes: homgfactor for alg.ext of Q
1338
1339Revision 1.36  2007/10/15 18:03:11  Singular
1340*hannes: // debug stuff
1341
1342Revision 1.35  2007/06/14 14:16:35  Singular
1343*hannes: Factorize2 etc.
1344
1345Revision 1.34  2007/06/02 10:21:57  Singular
1346*hannes: fdivides2 again
1347
1348Revision 1.33  2007/05/25 16:02:01  Singular
1349*hannes: removed diophant_error, format
1350
1351Revision 1.32  2007/05/25 12:59:05  Singular
1352*hannes: fdivides2
1353
1354Revision 1.31  2007/05/22 14:49:52  Singular
1355*hannes: format
1356
1357Revision 1.30  2007/05/22 14:30:53  Singular
1358*hannes: diophant_error
1359
1360Revision 1.29  2007/05/22 13:18:57  Singular
1361*hannes: Factorize2: div test, sort etc.
1362
1363Revision 1.28  2007/05/21 17:56:55  Singular
1364*hannes: fixed exp.
1365
1366Revision 1.27  2007/05/21 16:50:56  Singular
1367*hannes: fix fdivide test
1368
1369Revision 1.26  2007/05/21 16:40:12  Singular
1370*hannes: Factorize2
1371
1372Revision 1.25  2007/05/15 15:50:42  Singular
1373*hannes: Factorize2
1374
1375Revision 1.24  2007/05/15 14:46:48  Singular
1376*hannes: factorize in Zp(a)[x...]
1377
1378Revision 1.23  2006/05/16 14:46:49  Singular
1379*hannes: gcc 4.1 fixes
1380
1381Revision 1.22  2006/04/28 13:46:29  Singular
1382*hannes: better tests for 0, 1
1383
1384Revision 1.21  2005/12/12 18:02:03  Singular
1385*hannes: use sorting option in Factorize
1386
1387Revision 1.20  2005/12/05 15:47:32  Singular
1388*hannes: is_homogeneous -> factory: isHomogeneous
1389
1390Revision 1.19  2005/10/17 13:18:44  Singular
1391*hannes: apply sqrFree before newfactoras (Factorize in Q(a))
1392
1393Revision 1.18  2005/10/17 13:17:39  Singular
1394*hannes: aplly sqrFree before newfactoras (Factorize in Q(a))
1395
1396Revision 1.17  2004/12/10 10:15:06  Singular
1397*pohl: AlgExtGenerator etc.
1398
1399Revision 1.16  2003/05/28 11:52:52  Singular
1400*pfister/hannes: newfactoras, alg_gcd, divide (see bug_33)
1401
1402Revision 1.15  2003/02/14 15:51:15  Singular
1403* hannes: bugfix
1404          could not factorize x2+xy+y2 in Fp(a)[x,y], a2+a+1=0
1405          (factorize2 does nor sanity checks)
1406
1407Revision 1.14  2002/08/19 11:11:32  Singular
1408* hannes/pfister: alg_gcd etc.
1409
1410Revision 1.13  2002/07/30 17:06:47  Singular
1411*hannes: uuh - factorize in Q(a)[x] is missing, use Q[a][x].
1412
1413Revision 1.12  2002/07/30 15:10:22  Singular
1414*hannes: added Factorize for alg. ext.
1415
1416Revision 1.11  2001/08/22 14:21:16  Singular
1417*hannes: added search for main var to Factorize
1418
1419Revision 1.10  2001/08/08 14:26:55  Singular
1420*hannes: Dan's HAVE_SINGULAR_ERROR
1421
1422Revision 1.9  2001/08/08 11:59:12  Singular
1423*hannes: Dan's NOSTREAMIO changes
1424
1425Revision 1.8  2001/08/06 08:32:54  Singular
1426* hannes: code cleanup
1427
1428Revision 1.7  2001/06/21 14:57:05  Singular
1429*hannes/GP: Factorize, newfactoras, ...
1430
1431Revision 1.6  2001/06/18 08:44:41  pfister
1432* hannes/GP/michael: factory debug, Factorize
1433
1434Revision 1.5  1999/06/15 12:54:55  Singular
1435* hannes: debug fixes for Singular-interface
1436
1437Revision 1.4  1997/11/18 16:39:04  Singular
1438* hannes: moved WerrorS from C++ to C
1439     (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc)
1440
1441Revision 1.3  1997/09/12 07:19:46  Singular
1442* hannes/michael: libfac-0.3.0
1443
1444Revision 1.6  1997/04/25 22:18:40  michael
1445changed lc == 1 to lc == unit in choose_mainvar
1446changed cerr and cout messages for use with Singular
1447Version for libfac-0.2.1
1448
1449Revision 1.5  1997/01/17 05:04:03  michael
1450* added support for homogenous polynomials
1451* exported functions to homogfactor.cc
1452
1453*/
Note: See TracBrowser for help on using the repository browser.