Changeset 2391e4 in git


Ignore:
Timestamp:
May 3, 2013, 8:56:15 PM (11 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '45e267b9942dec9429fe249ce3e5e44ab80a6a3a')
Children:
a8f51f2cbfd5e70ab9d6ada456b3c4f409b753bd
Parents:
552d26572655f537d219086f12ab104e239f7db2ed95e6148ac6926aac6e83629cf4545c5c95a7a7
Message:
Merge pull request #326 from mmklee/factory_absfact_sw

Factory absfact sw
Files:
7 added
18 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/absfact.lib

    r552d26 r2391e4  
    2626PROCEDURES:
    2727  absFactorize();        absolute factorization of poly
     28  absBiFactorize();      absolute factorization of bivariate poly
    2829";
    2930
     
    609610}
    610611
     612////////////////////////////////////////////////////////////////////////////////
     613proc absBiFactorize(poly p, list #)
     614"USAGE:  absBiFactorize(p [,s]);   p poly, s string
     615ASSUME: coefficient field is the field of rational numbers or a
     616        transcendental extension thereof
     617RETURN: ring @code{R} which is obtained from the current basering
     618        by adding a new parameter (if a string @code{s} is given as a
     619        second input, the new parameter gets this string as name). The ring
     620        @code{R} comes with a list @code{absolute_factors} with the
     621        following entries:
     622@format
     623    absolute_factors[1]: ideal   (the absolute factors)
     624    absolute_factors[2]: intvec  (the multiplicities)
     625    absolute_factors[3]: ideal   (the minimal polynomials)
     626    absolute_factors[4]: int     (total number of nontriv. absolute factors)
     627@end format
     628        The entry @code{absolute_factors[1][1]} is a constant, the
     629        entry @code{absolute_factors[3][1]} is the parameter added to the
     630        current ring.@*
     631        Each of the remaining entries @code{absolute_factors[1][j]} stands for
     632        a class of conjugated absolute factors. The corresponding entry
     633        @code{absolute_factors[3][j]} is the minimal polynomial of the
     634        field extension over which the factor is minimally defined (its degree
     635        is the number of conjugates in the class). If the entry
     636        @code{absolute_factors[3][j]} coincides with @code{absolute_factors[3][1]},
     637        no field extension was necessary for the @code{j}th (class of)
     638        absolute factor(s).
     639NOTE:   The input polynomial p is assumed to be bivariate or to contain one para-
     640        meter and one variable. All factors are presented denominator- and
     641        content-free. The constant factor (first entry) is chosen such that the
     642        product of all (!) the (denominator- and content-free) absolute factors
     643        of @code{p} equals @code{p / absolute_factors[1][1]}.
     644SEE ALSO: factorize, absPrimdecGTZ, absFactorize
     645EXAMPLE: example absBiFactorize; shows an example
     646"
     647{
     648  int dblevel = printlevel - voice + 2;
     649  dbprint(dblevel,"Entering absfact.lib::absBiFactorize with ",p);
     650  def MP = basering;
     651  int i;
     652  if (char(MP) != 0)
     653  {
     654    ERROR("// absfact.lib::absBiFactorize is only implemented for "+
     655          "characteristic 0");
     656  }
     657  if(minpoly!=0)
     658  {
     659    ERROR("// absfact.lib::absBiFactorize is not implemented for algebraic "
     660          +"extensions");
     661  }
     662
     663  int n = nvars(MP);
     664  int pa=npars(MP);
     665  list lMP= ringlist(MP);
     666  intvec vv,vk;
     667  for(i=1;i<=n;i++){vv[i]=1;}
     668  vk=vv,1;
     669
     670  //if the basering has parameters, add the parameters to the variables
     671  //takes care about coefficients and possible denominators
     672  if(pa>0)
     673  {
     674    poly qh=cleardenom(p);
     675    if (p==0)
     676    {
     677      number cok=0;
     678    }
     679    else
     680    {
     681      number cok=leadcoef(p)/leadcoef(qh);
     682    }
     683    p=qh;
     684    string sp;
     685    for(i=1;i<=npars(basering);i++)
     686    {
     687      sp=string(par(i));
     688      sp=sp[2..size(sp)-1];
     689      lMP[2][n+i]=sp;
     690      vv=vv,1;
     691    }
     692    lMP[1]=0;
     693    n=n+npars(MP);
     694  }
     695
     696  // MPz is obtained by adding the new variable @z to MP
     697  // ordering is wp(1...1)
     698  // All the above subroutines work in MPz
     699  string newvar;
     700  if(size(#)>0)
     701  {
     702    if(typeof(#[1])=="string")
     703    {
     704      newvar=#[1];
     705    }
     706    else
     707    {
     708      newvar = "a";
     709    }
     710  }
     711  else
     712  {
     713    newvar = "a";
     714  }
     715  if (newvar=="a")
     716  {
     717    if(belongTo(newvar, lMP[2])||defined(a)){newvar = "b";}
     718    if(belongTo(newvar, lMP[2])||defined(b)){newvar = "c";}
     719    if(belongTo(newvar, lMP[2])||defined(c)){newvar = "@c";}
     720    while(belongTo(newvar, lMP[2]))
     721    {
     722       newvar = "@" + newvar;
     723    }
     724  }
     725
     726  // create ring with extra parameter `newvar` for output:
     727  setring(MP);
     728  list Lout=ringlist(MP);
     729  if(!pa)
     730  {
     731    list Lpar=list(char(MP),list(newvar),list(list("lp",intvec(1))),ideal(0));
     732  }
     733  else
     734  {
     735    list Lpar=Lout[1];
     736    Lpar[2][size(Lpar[2])+1]=newvar;
     737    vv=Lpar[3][1][2];
     738    vv=vv,1;
     739    Lpar[3][1][2]=vv;
     740  }
     741  Lout[1]=Lpar;
     742  def MPo=ring(Lout);
     743  setring(MPo);
     744
     745  poly p=imap(MP,p);
     746
     747  if (size (variables (p)) > 2)
     748  {
     749    ERROR("// absfact.lib::absBiFactorize is not implemented for polynomials "
     750          +"with more than 2 variables");
     751  }
     752
     753  // special treatment in the homogeneous case, dropping one variable
     754  // by substituting the first variable by 1
     755  int ho=homog(p);
     756  if(ho)
     757  {
     758    int dh=deg(p);
     759    p=subst(p,var(1),1);
     760    int di=deg(p);
     761  }
     762
     763  list tmpf=system ("absBiFact", p);
     764
     765  // the homogeneous case, homogenizing the result
     766  // the new variable has to have degree 0
     767  // need to change the ring
     768  if(ho)
     769  {
     770    list ll=ringlist(MPo);
     771    vv[size(vv)]=0;
     772    ll[3][1][2]=vv;
     773    def MPhelp=ring(ll);
     774    setring(MPhelp);
     775    list tmpf=imap(MPo,tmpf);
     776    for(i=2;i<=size(tmpf[1]);i++)
     777    {
     778      tmpf[1][i]=homog(tmpf[1][i],var(1));
     779    }
     780    if(dh>di)
     781    {
     782      tmpf[1][size(tmpf[1])+1]=var(1);
     783      tmpf[2][size(tmpf[2])+1]=dh-di;
     784      tmpf[3][size(tmpf[3])+1]=par(npars(MPo));
     785      tmpf[4]= tmpf[4]+dh-di;
     786    }
     787    setring(MPo);
     788    tmpf=imap(MPhelp,tmpf);
     789  }
     790
     791  if (pa)
     792  {
     793    number cok=imap(MP,cok);
     794    tmpf[1][1]=cok*tmpf[1][1];
     795  }
     796
     797  // if we want the output as string
     798  if(size(#)>0)
     799  {
     800    if(typeof(#[1])=="int")
     801    {
     802      if(#[1]==77)
     803      {  // undocumented feature for Gerhard's absPrimdecGTZ
     804        if (size(tmpf[1])<2){ list abs_fac = list(var(n+1),poly(1)); }
     805        else
     806        {
     807          list abs_fac= tmpf[3][2];
     808          abs_fac= abs_fac, tmpf[1][2];
     809          for (i= 3; i <= size(tmpf[1]); i++)
     810          {
     811            abs_fac=abs_fac,tmpf[3][i];
     812            abs_fac=abs_fac,tmpf[1][i];
     813          }
     814        }
     815        abs_fac=abs_fac,newvar;
     816        return(string(abs_fac));
     817      }
     818    }
     819  }
     820
     821  list absolute_factors= tmpf;
     822  export absolute_factors;
     823  setring(MP);
     824
     825  dbprint( printlevel-voice+3,"
     826// 'absBiFactorize' created a ring, in which a list absolute_factors (the
     827// absolute factors) is stored.
     828// To access the list of absolute factors, type (if the name S was assigned
     829// to the return value):
     830        setring(S); absolute_factors; ");
     831  return(MPo);
     832}
     833example
     834{
     835  "EXAMPLE:"; echo = 2;
     836  ring R = (0), (x,y), lp;
     837  poly p = (-7*x^2 + 2*x*y^2 + 6*x + y^4 + 14*y^2 + 47)*(5x2+y2)^3*(x-y)^4;
     838  def S = absBiFactorize(p) ;
     839  setring(S);
     840  absolute_factors;
     841}
     842
     843
    611844/*
    612845  ring r=0,(x,t),dp;
  • Singular/LIB/primdec.lib

    red95e6 r2391e4  
    37693769    I=interred(I+F);option(set,save);return(I);
    37703770   }
     3771   I=simplify(I,1);
    37713772
    37723773   for(i=1;i<=n;i++)             //consider all polynomials over
     
    44444445        if(check==0) // H==I => U is a primary decomposition
    44454446        {
    4446           option(set,save);
     4447          option(set,save);
    44474448          return(U);
    44484449        }
  • Singular/extra.cc

    r552d26 r2391e4  
    36833683      }
    36843684      else
     3685  /*================= absBiFact ======================*/
     3686      if (strcmp(sys_cmd, "absBiFact") == 0)
     3687      {
     3688        if (h!=NULL)
     3689        {
     3690          res->rtyp=LIST_CMD;
     3691          if (h->Typ()==POLY_CMD)
     3692          {
     3693            intvec *v=NULL;
     3694            ideal mipos= NULL;
     3695            int n= 0;
     3696            ideal f=singclap_absBiFactorize((poly)(h->Data()), mipos, &v, n, currRing);
     3697            if (f==NULL) return TRUE;
     3698            ivTest(v);
     3699            lists l=(lists)omAllocBin(slists_bin);
     3700            l->Init(4);
     3701            l->m[0].rtyp=IDEAL_CMD;
     3702            l->m[0].data=(void *)f;
     3703            l->m[1].rtyp=INTVEC_CMD;
     3704            l->m[1].data=(void *)v;
     3705            l->m[2].rtyp=IDEAL_CMD;
     3706            l->m[2].data=(void*) mipos;
     3707            l->m[3].rtyp=INT_CMD;
     3708            l->m[3].data=(void*) (long) n;
     3709            res->data=(void *)l;
     3710            return FALSE;
     3711          }
     3712          else return TRUE;
     3713        }
     3714        else return TRUE;
     3715      }
     3716      else
    36853717      #endif
    36863718  /*================= probIrredTest ======================*/
  • Singular/subexpr.cc

    red95e6 r2391e4  
    10661066        return  ((idhdl)h->data.ustring)->data.ustring;
    10671067      }
    1068       case VECHO:      return (void *)si_echo;
    1069       case VPRINTLEVEL:return (void *)printlevel;
    1070       case VCOLMAX:    return (void *)colmax;
    1071       case VTIMER:     return (void *)getTimer();
    1072       case VRTIMER:    return (void *)getRTimer();
    1073       case VOICE:      return (void *)(myynest+1);
    1074       case VMAXDEG:    return (void *)Kstd1_deg;
    1075       case VMAXMULT:   return (void *)Kstd1_mu;
    1076       case TRACE:      return (void *)traceit;
    1077       case VSHORTOUT:  return (void *)(currRing != NULL ? currRing->ShortOut : 0);
     1068      case VECHO:      return (void *)(long)si_echo;
     1069      case VPRINTLEVEL:return (void *)(long)printlevel;
     1070      case VCOLMAX:    return (void *)(long)colmax;
     1071      case VTIMER:     return (void *)(long)getTimer();
     1072      case VRTIMER:    return (void *)(long)getRTimer();
     1073      case VOICE:      return (void *)(long)(myynest+1);
     1074      case VMAXDEG:    return (void *)(long)Kstd1_deg;
     1075      case VMAXMULT:   return (void *)(long)Kstd1_mu;
     1076      case TRACE:      return (void *)(long)traceit;
     1077      case VSHORTOUT:  return (void *)(long)(currRing != NULL ? currRing->ShortOut : 0);
    10781078      case VMINPOLY:
    10791079        if ( (currRing != NULL)  && nCoeff_is_algExt(currRing->cf) && !nCoeff_is_GF(currRing->cf))
  • Tst/Short.lst

    r552d26 r2391e4  
     1Short/absbifact.tst
    12Short/alexpoly.tst
    23Short/algebralib.tst
  • Tst/Short/ok_s.lst

    r552d26 r2391e4  
    11;; Test which should pass shifted exponents
     2absbifact
    23abusalem
    34alexpoly
  • factory/Makefile.am

    r552d26 r2391e4  
    6262                DegreePattern.cc \
    6363                ExtensionInfo.cc \
     64                facAbsFact.cc \
    6465                facAlgExt.cc \
    6566                facBivar.cc \
     
    144145                DegreePattern.h \
    145146                ExtensionInfo.h \
     147                facAbsFact.h \
    146148                facAlgExt.h \
    147149                facBivar.h \
     
    248250
    249251templatesrc =   templates/ftmpl_array.cc \
     252                templates/ftmpl_afactor.cc \
    250253                templates/ftmpl_factor.cc \
    251254                templates/ftmpl_functions.h \
  • factory/canonicalform.h

    r552d26 r2391e4  
    2323#include <factory/templates/ftmpl_list.h>
    2424#include <factory/templates/ftmpl_array.h>
     25#include <factory/templates/ftmpl_afactor.h>
    2526#include <factory/templates/ftmpl_factor.h>
    2627#include <factory/templates/ftmpl_matrix.h>
     
    360361
    361362//{{{ type definitions
     363typedef AFactor<CanonicalForm> CFAFactor;
     364typedef List <CFAFactor> CFAFList;
     365typedef ListIterator<CFAFactor> CFAFListIterator;
    362366typedef Factor<CanonicalForm> CFFactor;
    363367typedef List<CFFactor> CFFList;
  • factory/cfNewtonPolygon.cc

    r552d26 r2391e4  
    1313
    1414#include "config.h"
     15
     16#include "cf_assert.h"
     17
    1518#include <stdlib.h>
    1619
     
    1821#include "cf_iter.h"
    1922#include "cf_algorithm.h"
     23#include "cf_primes.h"
     24#include "cf_reval.h"
     25#include "cf_factory.h"
     26#include "gfops.h"
    2027#include "cfNewtonPolygon.h"
    2128#include "templates/ftmpl_functions.h"
     
    857864bool irreducibilityTest (const CanonicalForm& F)
    858865{
     866  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     867  ASSERT (getCharacteristic() == 0, "expected polynomial over integers or rationals");
     868
    859869  int sizeOfNewtonPolygon;
    860870  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     
    872882        if (isRat)
    873883          Off (SW_RATIONAL);
    874         CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
     884        CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
    875885        tmp= gcd (tmp, newtonPolyg[1][0]);
    876886        tmp= gcd (tmp, newtonPolyg[1][1]);
     
    891901  return false;
    892902}
     903
     904bool absIrredTest (const CanonicalForm& F)
     905{
     906  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     907  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     908
     909  int sizeOfNewtonPolygon;
     910  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     911  bool isRat= isOn (SW_RATIONAL);
     912  if (isRat)
     913    Off (SW_RATIONAL);
     914  int p=getCharacteristic();
     915  int d=1;
     916  char bufGFName='Z';
     917  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
     918  if (GF)
     919  {
     920    d= getGFDegree();
     921    bufGFName=gf_name;
     922  }
     923
     924  setCharacteristic(0);
     925
     926  CanonicalForm g= gcd (newtonPolyg[0][0], newtonPolyg[0][1]); //maybe it's better to use plain intgcd
     927
     928  int i= 1;
     929  while (!g.isOne() && i < sizeOfNewtonPolygon)
     930  {
     931    g= gcd (g, newtonPolyg[i][0]);
     932    g= gcd (g, newtonPolyg[i][1]);
     933    i++;
     934  }
     935
     936  bool result= g.isOne();
     937
     938  if (GF)
     939    setCharacteristic (p, d, bufGFName);
     940  else
     941    setCharacteristic(p);
     942
     943  if (isRat)
     944    On (SW_RATIONAL);
     945
     946  for (int i= 0; i < sizeOfNewtonPolygon; i++)
     947    delete [] newtonPolyg[i];
     948
     949  delete [] newtonPolyg;
     950
     951  return result;
     952}
     953
     954bool modularIrredTest (const CanonicalForm& F)
     955{
     956  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     957  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     958
     959  bool isRat= isOn (SW_RATIONAL);
     960  if (isRat)
     961    Off (SW_RATIONAL);
     962
     963  if (isRat)
     964    ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
     965
     966  CanonicalForm Fp, N= maxNorm (F);
     967  int tdeg= totaldegree (F);
     968
     969  int i= 0;
     970  //TODO: maybe it's better to choose the characteristic as large as possible
     971  //      as factorization over large finite field will be faster
     972  //TODO: handle those cases where our factory primes are not enough
     973  //TODO: factorize coefficients corresponding to the vertices of the Newton
     974  //      polygon and only try the obtained factors
     975  if (N < cf_getSmallPrime (cf_getNumSmallPrimes()-1))
     976  {
     977    while (i < cf_getNumSmallPrimes() && N > cf_getSmallPrime(i))
     978    {
     979      setCharacteristic (cf_getSmallPrime (i));
     980      Fp= F.mapinto();
     981      i++;
     982      if (totaldegree (Fp) == tdeg)
     983      {
     984        if (absIrredTest (Fp))
     985        {
     986          CFFList factors= factorize (Fp);
     987          if (factors.length() == 2 && factors.getLast().exp() == 1)
     988          {
     989            if (isRat)
     990              On (SW_RATIONAL);
     991            setCharacteristic (0);
     992            return true;
     993          }
     994        }
     995      }
     996      setCharacteristic (0);
     997    }
     998  }
     999  else
     1000  {
     1001    while (i < cf_getNumPrimes() && N > cf_getPrime (i))
     1002    {
     1003      setCharacteristic (cf_getPrime (i));
     1004      Fp= F.mapinto();
     1005      i++;
     1006      if (totaldegree (Fp) == tdeg)
     1007      {
     1008        if (absIrredTest (Fp))
     1009        {
     1010          CFFList factors= factorize (Fp);
     1011          if (factors.length() == 2 && factors.getLast().exp() == 1)
     1012          {
     1013            if (isRat)
     1014              On (SW_RATIONAL);
     1015            setCharacteristic (0);
     1016            return true;
     1017          }
     1018        }
     1019      }
     1020      setCharacteristic (0);
     1021    }
     1022  }
     1023
     1024  if (isRat)
     1025    On (SW_RATIONAL);
     1026
     1027  return false;
     1028}
     1029
     1030bool
     1031modularIrredTestWithShift (const CanonicalForm& F)
     1032{
     1033  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     1034  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     1035
     1036  bool isRat= isOn (SW_RATIONAL);
     1037  if (isRat)
     1038    Off (SW_RATIONAL);
     1039
     1040  if (isRat)
     1041    ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
     1042
     1043  Variable x= Variable (1);
     1044  Variable y= Variable (2);
     1045  CanonicalForm Fp;
     1046  int tdeg= totaldegree (F);
     1047
     1048  REvaluation E;
     1049
     1050  setCharacteristic (2);
     1051  Fp= F.mapinto();
     1052
     1053  E= REvaluation (1,2, FFRandom());
     1054
     1055  E.nextpoint();
     1056
     1057  Fp= Fp (x+E[1], x);
     1058  Fp= Fp (y+E[2], y);
     1059
     1060  if (tdeg == totaldegree (Fp))
     1061  {
     1062    if (absIrredTest (Fp))
     1063    {
     1064      CFFList factors= factorize (Fp);
     1065      if (factors.length() == 2 && factors.getLast().exp() == 1)
     1066      {
     1067        if (isRat)
     1068          On (SW_RATIONAL);
     1069        setCharacteristic (0);
     1070        return true;
     1071      }
     1072    }
     1073  }
     1074
     1075  E.nextpoint();
     1076
     1077  Fp= Fp (x+E[1], x);
     1078  Fp= Fp (y+E[2], y);
     1079
     1080  if (tdeg == totaldegree (Fp))
     1081  {
     1082    if (absIrredTest (Fp))
     1083    {
     1084      CFFList factors= factorize (Fp);
     1085      if (factors.length() == 2 && factors.getLast().exp() == 1)
     1086      {
     1087        if (isRat)
     1088          On (SW_RATIONAL);
     1089        setCharacteristic (0);
     1090        return true;
     1091      }
     1092    }
     1093  }
     1094
     1095  int i= 0;
     1096  while (cf_getSmallPrime (i) < 102)
     1097  {
     1098    setCharacteristic (cf_getSmallPrime (i));
     1099    i++;
     1100    E= REvaluation (1, 2, FFRandom());
     1101
     1102    for (int j= 0; j < 3; j++)
     1103    {
     1104      Fp= F.mapinto();
     1105      E.nextpoint();
     1106      Fp= Fp (x+E[1], x);
     1107      Fp= Fp (y+E[2], y);
     1108
     1109      if (tdeg == totaldegree (Fp))
     1110      {
     1111        if (absIrredTest (Fp))
     1112        {
     1113          CFFList factors= factorize (Fp);
     1114          if (factors.length() == 2 && factors.getLast().exp() == 1)
     1115          {
     1116            if (isRat)
     1117              On (SW_RATIONAL);
     1118            setCharacteristic (0);
     1119            return true;
     1120          }
     1121        }
     1122      }
     1123    }
     1124  }
     1125
     1126  setCharacteristic (0);
     1127  if (isRat)
     1128    On (SW_RATIONAL);
     1129
     1130  return false;
     1131}
     1132
     1133
  • factory/cfNewtonPolygon.h

    r552d26 r2391e4  
    7474                   );
    7575
     76/// absolute irreducibility test as described in "Modular Las Vegas Algorithms
     77/// for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo
     78///
     79/// @return true if F satisfies condition (C) from the above paper and thus
     80/// is absolutely irreducible, false otherwise
     81bool
     82absIrredTest (const CanonicalForm& F ///< [in] a bivariate polynomial
     83                                     ///< irreducible over ground field
     84             );
     85
     86/// modular absolute irreducibility test as described in "Modular Las Vegas
     87/// Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze,
     88/// A. Galligo
     89///
     90/// @return true if F is absolutely irreducible, false otherwise
     91bool
     92modularIrredTest (const CanonicalForm& F ///< [in] a bivariate polynomial
     93                                         ///< irreducible over Z
     94                 );
     95
     96/// modular absolute irreducibility test with shift as described in "Modular Las
     97/// Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone,
     98/// G. Cheze, A. Galligo
     99///
     100/// @return true if F is absolutely irreducible, false otherwise
     101bool
     102modularIrredTestWithShift (const CanonicalForm& F ///< [in] a bivariate polynomial
     103                                                  ///< irreducible over Z
     104                          );
     105
     106
    76107#ifdef HAVE_NTL
    77108/// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization
  • factory/facBivar.h

    r552d26 r2391e4  
    5151  CFMap N;
    5252  CanonicalForm F= compress (G, N);
    53   CanonicalForm contentX= content (F, 1);
     53  CanonicalForm contentX= content (F, 1); //erwarte hier primitiven input: primitiv ÃŒber Z bzw. Z[a]
    5454  CanonicalForm contentY= content (F, 2);
    5555  F /= (contentX*contentY);
  • factory/facFqBivarUtil.cc

    r552d26 r2391e4  
    680680{
    681681  n= degree (F, 1);
     682  int* result= new int [n];
     683  int sizeOfNewtonPolygon;
     684  int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     685
     686  isIrreducible= false;
     687  if (sizeOfNewtonPolygon == 3)
     688  {
     689    bool check1=
     690        (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
     691    if (check1)
     692    {
     693      bool check2=
     694        (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
     695      if (check2)
     696      {
     697        int p=getCharacteristic();
     698        int d=1;
     699        char bufGFName='Z';
     700        bool GF= (CFFactory::gettype()==GaloisFieldDomain);
     701        if (GF)
     702        {
     703          d= getGFDegree();
     704          bufGFName=gf_name;
     705        }
     706        setCharacteristic(0);
     707        CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);  // maybe it's better to use plain intgcd
     708        tmp= gcd (tmp, newtonPolyg[1][0]);
     709        tmp= gcd (tmp, newtonPolyg[1][1]);
     710        tmp= gcd (tmp, newtonPolyg[2][0]);
     711        tmp= gcd (tmp, newtonPolyg[2][1]);
     712        isIrreducible= (tmp==1);
     713        if (GF)
     714          setCharacteristic (p, d, bufGFName);
     715        else
     716          setCharacteristic(p);
     717      }
     718    }
     719  }
     720
     721  int minX, minY, maxX, maxY;
     722  minX= newtonPolyg [0] [0];
     723  minY= newtonPolyg [0] [1];
     724  maxX= minX;
     725  maxY= minY;
     726  for (int i= 1; i < sizeOfNewtonPolygon; i++)
     727  {
     728    if (minX > newtonPolyg [i] [0])
     729      minX= newtonPolyg [i] [0];
     730    if (maxX < newtonPolyg [i] [0])
     731      maxX= newtonPolyg [i] [0];
     732    if (minY > newtonPolyg [i] [1])
     733      minY= newtonPolyg [i] [1];
     734    if (maxY < newtonPolyg [i] [1])
     735      maxY= newtonPolyg [i] [1];
     736  }
     737
     738  int k= maxX;
     739  for (int i= 0; i < n; i++)
     740  {
     741    if (i + 1 > maxY || i + 1 < minY)
     742    {
     743      result [i]= 0;
     744      continue;
     745    }
     746    int* point= new int [2];
     747    point [0]= k;
     748    point [1]= i + 1;
     749    while (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
     750    {
     751      k--;
     752      point [0]= k;
     753    }
     754    result [i]= k;
     755    k= maxX;
     756    delete [] point;
     757  }
     758
     759  return result;
     760}
     761
     762int *
     763computeBoundsWrtDiffMainvar (const CanonicalForm& F, int& n,
     764                             bool& isIrreducible)
     765{
     766  n= degree (F, 2);
    682767  int* result= new int [n];
    683768  int sizeOfNewtonPolygon;
     
    736821  }
    737822
    738   int k= maxX;
    739   for (int i= 0; i < n; i++)
    740   {
    741     if (i + 1 > maxY || i + 1 < minY)
    742     {
    743       result [i]= 0;
    744       continue;
    745     }
    746     int* point= new int [2];
    747     point [0]= k;
    748     point [1]= i + 1;
    749     while (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
    750     {
    751       k--;
    752       point [0]= k;
    753     }
    754     result [i]= k;
    755     k= maxX;
    756     delete [] point;
    757   }
    758 
    759   return result;
    760 }
    761 
    762 int *
    763 computeBoundsWrtDiffMainvar (const CanonicalForm& F, int& n,
    764                              bool& isIrreducible)
    765 {
    766   n= degree (F, 2);
    767   int* result= new int [n];
    768   int sizeOfNewtonPolygon;
    769   int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
    770 
    771   isIrreducible= false;
    772   if (sizeOfNewtonPolygon == 3)
    773   {
    774     bool check1=
    775         (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
    776     if (check1)
    777     {
    778       bool check2=
    779         (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
    780       if (check2)
    781       {
    782         int p=getCharacteristic();
    783         int d=1;
    784         char bufGFName='Z';
    785         bool GF= (CFFactory::gettype()==GaloisFieldDomain);
    786         if (GF)
    787         {
    788           d= getGFDegree();
    789           bufGFName=gf_name;
    790         }
    791         setCharacteristic(0);
    792         CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
    793         tmp= gcd (tmp, newtonPolyg[1][0]);
    794         tmp= gcd (tmp, newtonPolyg[1][1]);
    795         tmp= gcd (tmp, newtonPolyg[2][0]);
    796         tmp= gcd (tmp, newtonPolyg[2][1]);
    797         isIrreducible= (tmp==1);
    798         if (GF)
    799           setCharacteristic (p, d, bufGFName);
    800         else
    801           setCharacteristic(p);
    802       }
    803     }
    804   }
    805 
    806   int minX, minY, maxX, maxY;
    807   minX= newtonPolyg [0] [0];
    808   minY= newtonPolyg [0] [1];
    809   maxX= minX;
    810   maxY= minY;
    811   for (int i= 1; i < sizeOfNewtonPolygon; i++)
    812   {
    813     if (minX > newtonPolyg [i] [0])
    814       minX= newtonPolyg [i] [0];
    815     if (maxX < newtonPolyg [i] [0])
    816       maxX= newtonPolyg [i] [0];
    817     if (minY > newtonPolyg [i] [1])
    818       minY= newtonPolyg [i] [1];
    819     if (maxY < newtonPolyg [i] [1])
    820       maxY= newtonPolyg [i] [1];
    821   }
    822 
    823823  int k= maxY;
    824824  for (int i= 0; i < n; i++)
  • factory/factory.template

    r552d26 r2391e4  
    3838
    3939#include <factory/templates/ftmpl_array.h>
     40#include <factory/templates/ftmpl_afactor.h>
    4041#include <factory/templates/ftmpl_factor.h>
    4142#include <factory/templates/ftmpl_list.h>
     
    105106#include "facIrredTest.h"
    106107
     108/*MAKEHEADER PUBLIC ONLY*/
     109#include "facAbsFact.h"
     110
    107111#endif /* ! INCL_FACTORY_H */
  • factory/ftmpl_inst.cc

    r552d26 r2391e4  
    2323
    2424#include "templates/ftmpl_array.cc"
     25#include "templates/ftmpl_afactor.cc"
    2526#include "templates/ftmpl_factor.cc"
    2627#include "templates/ftmpl_list.cc"
     
    3435template class ListItem<CFFactor>;
    3536template class ListIterator<CFFactor>;
     37template class AFactor<CanonicalForm>;
     38template class List<CFAFactor>;
     39template class ListItem<CFAFactor>;
     40template class ListIterator<CFAFactor>;
    3641template class List<CanonicalForm>;
    3742template class ListItem<CanonicalForm>;
     
    7782
    7883template int operator == ( const Factor<CanonicalForm> &, const Factor<CanonicalForm> & );
     84template int operator == ( const AFactor<CanonicalForm> &, const AFactor<CanonicalForm> & );
    7985
    8086template List<CFFactor> Union ( const List<CFFactor> &, const List<CFFactor> & );
     87template List<CFAFactor> Union ( const List<CFAFactor> &, const List<CFAFactor> & );
    8188
    8289#if ! defined(WINNT) || defined(__GNUC__)
  • factory/include/factory/Makefile.am

    r552d26 r2391e4  
    22
    33templateincl =  templates/ftmpl_array.h \
     4                templates/ftmpl_afactor.h \
    45                templates/ftmpl_factor.h \
    56                templates/ftmpl_list.h \
  • libpolys/polys/clapconv.cc

    r552d26 r2391e4  
    319319  {
    320320    n_Normalize(p_GetCoeff(p, r), r->cf);
    321     CanonicalForm term=convSingPFactoryP(NUM(p_GetCoeff(p, r)),r->cf->extRing);
    322 
    323     if ((DEN(p_GetCoeff(p,r))!=NULL)
    324     && (!errorreported))
    325     {
     321
     322    // test if denominator is constant
     323    if (!p_IsConstantPoly(DEN (p_GetCoeff (p,r)),r) && !errorreported)
    326324      WerrorS("conversion error: denominator!= 1");
     325
     326    CanonicalForm term=convSingPFactoryP(NUM (p_GetCoeff(p, r)),r->cf->extRing);
     327
     328    // if denominator is not NULL it should be a constant at this point
     329    if (DEN (p_GetCoeff(p,r)) != NULL)
     330    {
     331      CanonicalForm den= convSingPFactoryP(DEN (p_GetCoeff(p, r)),r->cf->extRing);
     332      if (rChar (r) == 0)
     333        On (SW_RATIONAL);
     334      term /= den;
    327335    }
    328336
  • libpolys/polys/clapsing.cc

    r552d26 r2391e4  
    10251025  return res;
    10261026}
     1027#ifdef HAVE_NTL
     1028ideal singclap_absBiFactorize ( poly f, ideal & mipos, intvec ** exps, int & numFactors, const ring r)
     1029{
     1030  p_Test(f, r);
     1031
     1032  ideal res=NULL;
     1033
     1034  int offs = rPar(r);
     1035  if (f==NULL)
     1036  {
     1037    res= idInit (1, 1);
     1038    mipos= idInit (1, 1);
     1039    mipos->m[0]= convFactoryPSingTrP (Variable (offs), r); //overkill
     1040    (*exps)=new intvec (1);
     1041    (**exps)[0]= 1;
     1042    numFactors= 0;
     1043    return res;
     1044  }
     1045  CanonicalForm F( convSingTrPFactoryP( f, r) );
     1046
     1047  if (getNumVars (F) > 2)
     1048  {
     1049    WerrorS( feNotImplemented );
     1050    return res;
     1051  }
     1052  CFAFList absFactors= absFactorize (F);
     1053
     1054  int n= absFactors.length();
     1055  *exps=new intvec (n);
     1056
     1057  res= idInit (n, 1);
     1058
     1059  mipos= idInit (n, 1);
     1060
     1061  Variable x= Variable (offs);
     1062  Variable alpha;
     1063  int i= 0;
     1064  numFactors= 0;
     1065  int count;
     1066  CFAFListIterator iter= absFactors;
     1067  CanonicalForm lead= iter.getItem().factor();
     1068  if (iter.getItem().factor().inCoeffDomain())
     1069  {
     1070    i++;
     1071    iter++;
     1072  }
     1073  bool isRat= isOn (SW_RATIONAL);
     1074  if (!isRat)
     1075    On (SW_RATIONAL);
     1076  for (; iter.hasItem(); iter++, i++)
     1077  {
     1078    (**exps)[i]= iter.getItem().exp();
     1079    alpha= iter.getItem().minpoly().mvar();
     1080    if (iter.getItem().minpoly().isOne())
     1081      lead /= power (bCommonDen (iter.getItem().factor()), iter.getItem().exp());
     1082    else
     1083      lead /= power (power (bCommonDen (iter.getItem().factor()), degree (iter.getItem().minpoly())), iter.getItem().exp());
     1084    res->m[i]= convFactoryPSingTrP (replacevar (iter.getItem().factor()*bCommonDen (iter.getItem().factor()), alpha, x), r);
     1085    if (iter.getItem().minpoly().isOne())
     1086    {
     1087      count= iter.getItem().exp();
     1088      mipos->m[i]= convFactoryPSingTrP (x,r);
     1089    }
     1090    else
     1091    {
     1092      count= iter.getItem().exp()*degree (iter.getItem().minpoly());
     1093      mipos->m[i]= convFactoryPSingTrP (replacevar (iter.getItem().minpoly(), alpha, x), r);
     1094    }
     1095    numFactors += count;
     1096  }
     1097  if (!isRat)
     1098    Off (SW_RATIONAL);
     1099
     1100  (**exps)[0]= 1;
     1101  res->m[0]= convFactoryPSingTrP (lead, r);
     1102  mipos->m[0]= convFactoryPSingTrP (x, r);
     1103  return res;
     1104}
     1105#endif
    10271106ideal singclap_sqrfree ( poly f, intvec ** v , int with_exps, const ring r)
    10281107{
  • libpolys/polys/clapsing.h

    r552d26 r2391e4  
    5151matrix singntl_LLL(matrix A, const ring r);
    5252intvec* singntl_LLL(intvec* A, const ring r);
     53ideal singclap_absBiFactorize ( poly f, ideal & mipos, intvec ** exps, int & n, const ring r);
    5354#endif
    5455#endif
Note: See TracChangeset for help on using the changeset viewer.