Changeset 36ef97a in git


Ignore:
Timestamp:
Feb 28, 2013, 12:27:27 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '5a0dde71de01068fad5736a17555c993ecbbf495')
Children:
f224fda57b6b8846990a1284ec08a294e5b2f0f7
Parents:
160ec65155bebf896fb6d52bbe233c0c557a8c0e
git-author:
Martin Lee <martinlee84@web.de>2013-02-28 12:27:27+01:00
git-committer:
Martin Lee <martinlee84@web.de>2013-05-02 11:42:35+02:00
Message:
chg: added absolute irreducibility test
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • Singular/extra.cc

    r160ec6 r36ef97a  
    37073707        {
    37083708          CanonicalForm F= convSingPFactoryP((poly)(h->Data()));
    3709           CFList factors= absFactorize (F);
     3709          CFFList factors= absFactorize (F);
    37103710          res->rtyp= INT_CMD;
    37113711          res->data= (void*) 1;
  • factory/cfNewtonPolygon.cc

    r160ec6 r36ef97a  
    857857bool irreducibilityTest (const CanonicalForm& F)
    858858{
     859  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     860  ASSERT (getCharacteristic() == 0, "expected polynomial over integers or rationals");
     861
    859862  int sizeOfNewtonPolygon;
    860863  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     
    872875        if (isRat)
    873876          Off (SW_RATIONAL);
    874         CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
     877        CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
    875878        tmp= gcd (tmp, newtonPolyg[1][0]);
    876879        tmp= gcd (tmp, newtonPolyg[1][1]);
     
    891894  return false;
    892895}
     896
     897bool absIrredTest (const CanonicalForm& F)
     898{
     899  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     900  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     901
     902  int sizeOfNewtonPolygon;
     903  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     904  bool isRat= isOn (SW_RATIONAL);
     905  if (isRat)
     906    Off (SW_RATIONAL);
     907  int p=getCharacteristic();
     908  int d=1;
     909  char bufGFName='Z';
     910  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
     911  if (GF)
     912  {
     913    d= getGFDegree();
     914    bufGFName=gf_name;
     915  }
     916
     917  setCharacteristic(0);
     918
     919  CanonicalForm g= gcd (newtonPolyg[0][0], newtonPolyg[0][1]); //maybe it's better to use plain intgcd
     920
     921  int i= 1;
     922  while (!g.isOne() && i < sizeOfNewtonPolygon)
     923  {
     924    g= gcd (g, newtonPolyg[i][0]);
     925    g= gcd (g, newtonPolyg[i][1]);
     926    i++;
     927  }
     928
     929  bool result= g.isOne();
     930
     931  if (GF)
     932    setCharacteristic (p, d, bufGFName);
     933  else
     934    setCharacteristic(p);
     935
     936  if (isRat)
     937    On (SW_RATIONAL);
     938
     939  return result;
     940}
     941
  • factory/cfNewtonPolygon.h

    r160ec6 r36ef97a  
    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//TODO add modular test from "Modular Las Vegas Algorithms
     87// for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo
     88
    7689#ifdef HAVE_NTL
    7790/// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization
  • factory/facFqBivarUtil.cc

    r160ec6 r36ef97a  
    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++)
Note: See TracChangeset for help on using the changeset viewer.