Changeset 8de151 in git for libfac


Ignore:
Timestamp:
May 21, 2007, 6:41:29 PM (17 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
Children:
7f466305807b49579ddcb444085d45b360472e5a
Parents:
aef8bb403e723cf3c64015379df7cbc448fbb3b3
Message:
*hannes: Factorize2


git-svn-id: file:///usr/local/Singular/svn/trunk@10053 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
libfac
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • libfac/factor.h

    raef8bb r8de151  
    1919CFFList Factorize( const CanonicalForm & F, int is_SqrFree=0 ) ;
    2020CFFList Factorize( const CanonicalForm & F, const CanonicalForm & mipo, int is_SqrFree=0 ) ;
    21 CFFList Factorize2(const CanonicalForm & F, const CanonicalForm & minpoly );
     21CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly );
    2222CFFList newfactoras( const CanonicalForm & f, const CFList & as, int success);
    2323CFFList factorize2 ( const CanonicalForm & f,
  • libfac/factor/Factor.cc

    raef8bb r8de151  
    11/* Copyright 1996 Michael Messollen. All rights reserved. */
    22///////////////////////////////////////////////////////////////////////////////
    3 static char * rcsid = "$Id: Factor.cc,v 1.25 2007-05-15 15:50:42 Singular Exp $ ";
     3static char * rcsid = "$Id: Factor.cc,v 1.26 2007-05-21 16:40:12 Singular Exp $ ";
    44static 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.";
    55///////////////////////////////////////////////////////////////////////////////
     
    613613///////////////////////////////////////////////////////////////
    614614CFFList
    615 Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar){
     615Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar)
     616{
    616617  CanonicalForm f,lt,ff,ffuni;
    617618  Variable Extension=alpha.mvar();
     
    626627  // INTERRUPTHANDLER
    627628
    628   if ( F.isUnivariate() ){ // could have lost one Variable elsewhere
    629     if ( degree(Extension) == 0 ){
     629  if ( F.isUnivariate() ) // could have lost one Variable elsewhere
     630  {
     631    if ( degree(Extension) == 0 )
     632    {
    630633      TIMING_START(evaluate_time);
    631634      Outputlist = factorize(F,1); // poly is sqr-free
     
    633636      return Outputlist;
    634637    }
    635     else{
     638    else
     639    {
    636640      if (Extension.level()<0)
    637641      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
     
    794798
    795799    TIMING_START(hensel_time);
    796     Outputlist = MultiHensel(ff,UnivariateFactorlist,Substitutionlist);
     800    Outputlist = MultiHensel(ff,UnivariateFactorlist,Substitutionlist, alpha);
    797801    DEBOUTLN(CERR, "Outputlist after MultiHensel: ", Outputlist);
    798802    TIMING_END(hensel_time);
     
    993997//           * ensuring poly is sqrfree (n.y.i.)             //
    994998///////////////////////////////////////////////////////////////
    995 CFFList Factorize2(const CanonicalForm & F, const CanonicalForm & minpoly )
     999CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly )
    9961000{
    9971001  CFFList iF=Factorize(F);
     
    10041008    d = i.getItem().exp();
    10051009    fac = i.getItem().factor();
    1006     G = Factorize( fac, minpoly);
     1010    if (fdivides(F,fac))
     1011    {
     1012      if ((getNumVars(fac)==0)||(fac.degree()<=1))
     1013      {
     1014#ifndef NOSTREAMIO
     1015#ifndef NDEBUG
     1016        printf("append trivial factor\n");
     1017#endif
     1018#endif
     1019        H.append( CFFactor( fac, d));
     1020        do {F/=fac; d--; } while (d>0);
     1021      }
     1022      else
     1023      {
     1024        G = Factorize( fac, minpoly);
     1025        for ( k = G; k.hasItem(); ++k )
     1026        {
     1027          fac = k.getItem().factor();
     1028          int dd = k.getItem().exp();
     1029          if ((!fac.isZero())&& fdivides(F,fac))
     1030          {
     1031#ifndef NOSTREAMIO
     1032#ifndef NDEBUG
     1033            out_cf("factor:",fac,"\n");
     1034#endif
     1035#endif
     1036            H.append( CFFactor( fac , d*dd ) );
     1037            do {F/=fac; d--; } while (d>0);
     1038          }
     1039        }
     1040      }
     1041    }
     1042  }
     1043  if (getNumVars(F)>0)
     1044  {
     1045#ifndef NOSTREAMIO
     1046#ifndef NDEBUG
     1047        out_cf("retry:",F,"\n");
     1048#endif
     1049#endif
     1050    G = Factorize(F, minpoly);
    10071051    for ( k = G; k.hasItem(); ++k )
    10081052    {
    10091053      fac = k.getItem().factor();
    10101054      int dd = k.getItem().exp();
    1011       H.append( CFFactor( fac , d*dd ) );
    1012     }
     1055      if ((!fac.isZero())&& fdivides(F,fac))
     1056      {
     1057#ifndef NOSTREAMIO
     1058#ifndef NDEBUG
     1059        out_cf("factor:",fac,"\n");
     1060#endif
     1061#endif
     1062        H.append( CFFactor( fac , d*dd ) );
     1063        do {F/=fac; d--; } while (d>0);
     1064      }
     1065    }
     1066  }
     1067  if (getNumVars(F)>0)
     1068  {
     1069#ifndef NOSTREAMIO
     1070#ifndef NDEBUG
     1071        out_cf("rest:",fac,"\n");
     1072#endif
     1073#endif
     1074    H.append( CFFactor(F,1) );
    10131075  }
    10141076  //Outputlist = newfactoras( F, as, 1);
     1077  if(isOn(SW_USE_NTL_SORT)) H.sort(cmpCF);
    10151078  return H;
    10161079}
     
    11181181      Outputlist.append( CFFactor(g,1) ) ;
    11191182    else// a real polynomial
     1183    {
    11201184      if ( g.isUnivariate() )
    11211185      {
     
    11491213          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
    11501214      }
     1215    }
    11511216  }
    11521217  g=1; unit=1;
     
    11951260/*
    11961261$Log: not supported by cvs2svn $
     1262Revision 1.25  2007/05/15 15:50:42  Singular
     1263*hannes: Factorize2
     1264
    11971265Revision 1.24  2007/05/15 14:46:48  Singular
    11981266*hannes: factorize in Zp(a)[x...]
  • libfac/factor/MVMultiHensel.cc

    raef8bb r8de151  
    22///////////////////////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // static char * rcsid = "$Id: MVMultiHensel.cc,v 1.10 2007-05-15 14:46:49 Singular Exp $";
     4// static char * rcsid = "$Id: MVMultiHensel.cc,v 1.11 2007-05-21 16:40:12 Singular Exp $";
    55///////////////////////////////////////////////////////////////////////////////
    66// FACTORY - Includes
     
    118118///////////////////////////////////////////////////////////////
    119119static DiophantForm
    120 diophant( int levelU , const CanonicalForm & F1 , const CanonicalForm & F2 , int i , RememberArray & A, RememberArray & B )
     120diophant( int levelU , const CanonicalForm & F1 , const CanonicalForm & F2 ,
     121          int i , RememberArray & A, RememberArray & B,
     122          const CanonicalForm &alpha )
    121123{
    122124  DiophantForm Retvalue;
     
    136138  }
    137139
     140#if 0
    138141  // Degrees ok? degree(F1,mainvar) + degree(F2,mainvar) <= i ?
    139142  if ( (degree(F1,levelU) + degree(F2,levelU) ) <= i )
     
    154157    return Retvalue;
    155158  }
     159#endif
    156160
    157161  if ( i == 0 )
     
    161165    if ( ! r.isOne() )
    162166    {
     167      if (r.degree()<1) // some constant != 1 ?
     168      {
     169        Retvalue.One=s/r;Retvalue.Two=t/r;
     170        return Retvalue;
     171      }
     172      else if (alpha!=0)
     173      {
     174        Variable Alpha=alpha.mvar();
     175        if (r.mvar()==Alpha)   // from field extension ?
     176        {
     177          Variable X=rootOf(alpha);
     178          r=replacevar(r,Alpha,X);
     179          s=replacevar(s,Alpha,X);
     180          t=replacevar(t,Alpha,X);
     181          s/=r;
     182          t/=r;
     183          s=replacevar(s,X,Alpha);
     184          t=replacevar(t,X,Alpha);
     185          Retvalue.One=s; Retvalue.Two=t;
     186          return Retvalue;
     187        }
     188      }
    163189#ifdef HAVE_SINGULAR_ERROR
    164190      WerrorS("libfac: diophant ERROR: F1 and F2 are not relatively prime! ");
    165       //out_cf("F1:",F1,"\n");
    166       //out_cf("F2:",F2,"\n");
     191#ifndef NOSTREAMIO
     192      out_cf("F1:",F1,"\n");
     193      out_cf("F2:",F2,"\n");
     194      out_cf("gcd:",r,"\n");
     195#endif
    167196#else
    168197#ifndef NOSTREAMIO
     
    173202#endif
    174203#endif
    175       Retvalue.One=F1;Retvalue.Two=F2;
     204      Retvalue.One=s/r;Retvalue.Two=t/r;
    176205      return Retvalue;
    177206    }
     
    180209  else
    181210  { // recursively call diophant
    182     Retvalue=diophant(levelU,F1,F2,i-1,A,B);
     211    Retvalue=diophant(levelU,F1,F2,i-1,A,B,alpha);
    183212    Retvalue.One *= x; // createVar(levelU,1);
    184213    Retvalue.Two *= x; // createVar(levelU,1);
     
    221250make_delta( int levelU, const CanonicalForm & W,
    222251            const CanonicalForm & F1, const CanonicalForm & F2,
    223             RememberArray & A, RememberArray & B){
     252            RememberArray & A, RememberArray & B,
     253            const CanonicalForm &alpha)
     254{
    224255  CanonicalForm Retvalue;
    225256  DiophantForm intermediate;
     
    228259  DEBOUTLN(CERR, "  degree(W,levelU)= ", degree(W,levelU) );
    229260
    230   if ( levelU == level(W) ){ // same level, good
    231     for ( CFIterator i=W; i.hasTerms(); i++){
    232       intermediate=diophant(levelU,F1,F2,i.exp(),A,B);
     261  if ( levelU == level(W) ) // same level, good
     262  {
     263    for ( CFIterator i=W; i.hasTerms(); i++)
     264    {
     265      intermediate=diophant(levelU,F1,F2,i.exp(),A,B,alpha);
    233266      Retvalue += intermediate.One * i.coeff();
    234267    }
    235268  }
    236   else{ // level(W) < levelU ; i.e. degree(w,levelU) == 0
    237     intermediate=diophant(levelU,F1,F2,0,A,B);
     269  else // level(W) < levelU ; i.e. degree(w,levelU) == 0
     270  {
     271    intermediate=diophant(levelU,F1,F2,0,A,B,alpha);
    238272    Retvalue = W * intermediate.One;
    239273  }
     
    245279make_square( int levelU, const CanonicalForm & W,
    246280             const CanonicalForm & F1, const CanonicalForm & F2,
    247              RememberArray & A, RememberArray & B){
     281             RememberArray & A, RememberArray & B,const CanonicalForm &alpha)
     282{
    248283  CanonicalForm Retvalue;
    249284  DiophantForm intermediate;
     
    254289  if ( levelU == level(W) ){ // same level, good
    255290    for ( CFIterator i=W; i.hasTerms(); i++){
    256       intermediate=diophant(levelU,F1,F2,i.exp(),A,B);
     291      intermediate=diophant(levelU,F1,F2,i.exp(),A,B,alpha);
    257292      Retvalue += i.coeff() * intermediate.Two;
    258293    }
    259294  }
    260295  else{ // level(W) < levelU ; i.e. degree(w,levelU) == 0
    261     intermediate=diophant(levelU,F1,F2,0,A,B);
     296    intermediate=diophant(levelU,F1,F2,0,A,B,alpha);
    262297    Retvalue = W * intermediate.Two;
    263298  }
     
    277312static DiophantForm
    278313mvhensel( const CanonicalForm & U , const CanonicalForm & F ,
    279           const CanonicalForm & G , const SFormList & Substitutionlist){
     314          const CanonicalForm & G , const SFormList & Substitutionlist,
     315          const CanonicalForm &alpha)
     316{
    280317  CanonicalForm V,Fk=F,Gk=G,Rk,W,D,S;
    281318  int  levelU=level(U), degU=subvardegree(U,levelU); // degree(U,{x_1,..,x_(level(U)-1)})
     
    297334       << "          Rk= " << Rk << "\n";
    298335#endif
    299   for ( int k=2; k<=degU+1; k++){//2; k++){//degU+1; k++){
     336  for ( int k=2; k<=degU+1; k++)
     337  {
    300338    W = mod_power(Rk,k,levelU);
    301339#ifdef HENSELDEBUG2
     
    303341    CERR << "mvhensel: W= " << W << "\n";
    304342#endif
    305     D = make_delta(levelU,W,F,G,A,B);
     343    D = make_delta(levelU,W,F,G,A,B,alpha);
    306344#ifdef HENSELDEBUG2
    307345    CERR << "mvhensel: D= " << D << "\n";
    308346#endif
    309     S = make_square(levelU,W,F,G,A,B);
     347    S = make_square(levelU,W,F,G,A,B,alpha);
    310348#ifdef HENSELDEBUG2
    311349    CERR << "mvhensel: S= " << S << "\n";
     
    339377CFFList
    340378multihensel( const CanonicalForm & mF, const CFFList & Factorlist,
    341              const SFormList & Substitutionlist){
     379             const SFormList & Substitutionlist,
     380             const CanonicalForm &alpha)
     381{
    342382  CFFList Returnlist,factorlist=Factorlist;
    343383  DiophantForm intermediat;
     
    355395      intermediat= mvhensel(mF, factorlist.getFirst().factor(),
    356396                            Factorlist.getLast().factor(),
    357                             Substitutionlist);
     397                            Substitutionlist,alpha);
    358398      Returnlist.append(CFFactor(intermediat.One,1));
    359399      Returnlist.append(CFFactor(intermediat.Two,1));
     
    371411           << "  " << factorlist << "\n";
    372412#endif
    373       intermediat= mvhensel(mF,Pl,Pr,Substitutionlist);
     413      intermediat= mvhensel(mF,Pl,Pr,Substitutionlist,alpha);
    374414      Returnlist.append(CFFactor(intermediat.One,1));
    375       Returnlist=Union( multihensel(intermediat.Two,factorlist,Substitutionlist), Returnlist);
    376     }
    377   }
    378 
     415      Returnlist=Union( multihensel(intermediat.Two,factorlist,Substitutionlist,alpha),
     416                        Returnlist);
     417    }
     418  }
    379419  return Returnlist;
    380420}
     
    389429CFFList
    390430MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist,
    391              const SFormList & Substitutionlist){
     431             const SFormList & Substitutionlist, const CanonicalForm &alpha)
     432{
    392433  CFFList Returnlist,Retlistinter,factorlist=Factorlist,Ll;
    393434  CFFListIterator i;
     
    401442  DEBOUTLN(CERR,"  ", h);
    402443
    403   if ( n == 1 ) {
     444  if ( n == 1 )
     445  {
    404446    Returnlist.append(CFFactor(mF,1));
    405447  }
    406   else {
    407     if ( n == 2 ){
     448  else
     449  {
     450    if ( n == 2 )
     451    {
    408452      intermediat= mvhensel(mF, factorlist.getFirst().factor(),
    409453                            Factorlist.getLast().factor(),
    410                             Substitutionlist);
     454                            Substitutionlist,alpha);
    411455      Returnlist.append(CFFactor(intermediat.One,1));
    412456      Returnlist.append(CFFactor(intermediat.Two,1));
    413457    }
    414     else { // more then two factors
    415       for ( k=1 ; k<=h; k++){
     458    else  // more then two factors
     459    {
     460      for ( k=1 ; k<=h; k++)
     461      {
    416462        Ll.append(factorlist.getFirst());
    417463        factorlist.removeFirst();
     
    428474        Pr *= i.getItem().factor();
    429475      DEBOUTLN(CERR, "MultiHensel: Pr= ", Pr);
    430       intermediat = mvhensel(mF,Pl,Pr,Substitutionlist);
     476      intermediat = mvhensel(mF,Pl,Pr,Substitutionlist,alpha);
    431477      // divison test for intermediat.One and intermediat.Two ?
    432478      CanonicalForm a,b;
     
    437483        Retlistinter.append(CFFactor(intermediat.Two,1)  );
    438484
    439       Ll = MultiHensel(intermediat.One, Ll, Substitutionlist);
    440       Returnlist = MultiHensel(intermediat.Two, factorlist, Substitutionlist);
     485      Ll = MultiHensel(intermediat.One, Ll, Substitutionlist,alpha);
     486      Returnlist = MultiHensel(intermediat.Two, factorlist, Substitutionlist,alpha);
    441487      Returnlist = Union(Returnlist,Ll);
    442488
     
    450496/*
    451497$Log: not supported by cvs2svn $
     498Revision 1.10  2007/05/15 14:46:49  Singular
     499*hannes: factorize in Zp(a)[x...]
     500
    452501Revision 1.9  2006/05/16 14:46:49  Singular
    453502*hannes: gcc 4.1 fixes
  • libfac/factor/MVMultiHensel.h

    raef8bb r8de151  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // $Id: MVMultiHensel.h,v 1.3 1997-09-12 07:19:48 Singular Exp $
     4// $Id: MVMultiHensel.h,v 1.4 2007-05-21 16:40:12 Singular Exp $
    55/////////////////////////////////////////////////////////////
    66#ifndef MULTIHENSEL_H
    77#define MULTIHENSEL_H
    88// recursive version:
    9 CFFList multihensel( const CanonicalForm & mF, const CFFList & Factorlist, const SFormList & Substitutionlist);
     9CFFList multihensel( const CanonicalForm & mF, const CFFList & Factorlist,
     10                     const SFormList & Substitutionlist,
     11                     const CanonicalForm &alpha);
    1012// this is the real one (quasiparallel):
    11 CFFList MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist, const SFormList & Substitutionlist);
     13CFFList MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist,
     14                     const SFormList & Substitutionlist,
     15                     const CanonicalForm &alpha);
    1216
    1317#endif /* MULTIHENSEL_H */
     
    1620/*
    1721$Log: not supported by cvs2svn $
     22Revision 1.3  1997/09/12 07:19:48  Singular
     23* hannes/michael: libfac-0.3.0
     24
    1825Revision 1.2  1997/04/25 22:31:40  michael
    1926Version for libfac-0.2.1
Note: See TracChangeset for help on using the changeset viewer.