Changeset 868240 in git


Ignore:
Timestamp:
May 9, 2014, 12:18:41 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
3ff2cf655541d92602d3a2216f5b7a47c5523571
Parents:
ec04e88299a064f7c80c463bcdcf43e9db165e5b
git-author:
Martin Lee <martinlee84@web.de>2014-05-09 12:18:41+02:00
git-committer:
Martin Lee <martinlee84@web.de>2014-05-12 14:35:03+02:00
Message:
chg: remove sqrf_agnorm_sub
chg: use squarefree factors of resultant instead of wasting them
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/facAlgFunc.cc

    rec04e8 r868240  
    211211// alpha is defined by the minimal polynomial Palpha
    212212// K has more than S elements (S is defined in thesis; look getDegOfExt)
    213 static void
    214 sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
    215            CFGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
    216            CanonicalForm & R)
     213static CFFList
     214sqrf_norm_sub (const CanonicalForm & f, const CanonicalForm & PPalpha,
     215               CFGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
     216               CanonicalForm & R)
    217217{
    218   Variable y=PPalpha.mvar(),vf=f.mvar();
    219   CanonicalForm temp, Palpha=PPalpha, t;
    220   int sqfreetest=0;
     218  Variable y= PPalpha.mvar(),vf= f.mvar();
     219  CanonicalForm temp, Palpha= PPalpha, t;
     220  int sqfreetest= 0;
    221221  CFFList testlist;
    222222  CFFListIterator i;
    223223
    224   myrandom.reset();   s=myrandom.item();   g=f;
     224  myrandom.reset();
     225  s= myrandom.item();
     226  g= f;
    225227  R= CanonicalForm(0);
    226228
    227229  // Norm, resultante taken with respect to y
    228   while ( !sqfreetest )
    229   {
    230     R = resultante(Palpha, g, y); R= R* bCommonDen(R);
     230  while (!sqfreetest)
     231  {
     232    R= resultante(Palpha, g, y);
     233    R= R* bCommonDen(R);
    231234    R /= content (R);
    232235    // sqfree check ; R is a polynomial in K[x]
    233     if ( getCharacteristic() == 0 )
    234     {
    235       temp= gcd(R, R.deriv(vf));
     236    if (getCharacteristic() == 0)
     237    {
     238      temp= gcd (R, R.deriv(vf));
    236239      if (degree(temp,vf) != 0 || temp == temp.genZero() )
    237240        sqfreetest= 0;
    … …  
    242245    {
    243246      Variable X;
    244       if (hasFirstAlgVar(R,X))
    245         testlist=factorize( R, X );
    246       else
    247         testlist= factorize(R);
     247      testlist= sqrFree (R);
    248248
    249249      if (testlist.getFirst().factor().inCoeffDomain())
    250250        testlist.removeFirst();
    251       sqfreetest=1;
    252       for ( i=testlist; i.hasItem(); i++)
    253       {
    254         if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0)
     251      sqfreetest= 1;
     252      for (i= testlist; i.hasItem(); i++)
     253      {
     254        if (i.getItem().exp() > 1 && degree (i.getItem().factor(), R.mvar()) > 0)
    255255        {
    256           sqfreetest=0;
     256          sqfreetest= 0;
    257257          break;
    258258        }
    259259      }
    260260    }
    261     if ( ! sqfreetest )
     261    if (!sqfreetest)
    262262    {
    263263      myrandom.next();
    264       if ( getCharacteristic() == 0 )
    265         t= CanonicalForm(mapinto(myrandom.item()));
     264      if (getCharacteristic() == 0)
     265        t= CanonicalForm (mapinto (myrandom.item()));
    266266      else
    267         t= CanonicalForm(myrandom.item());
     267        t= CanonicalForm (myrandom.item());
    268268      s= t;
    269       g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
    270     }
    271   }
     269      g= f (f.mvar() - t*Palpha.mvar(), f.mvar());
     270    }
     271  }
     272  return testlist;
    272273}
    273 static void
    274 sqrf_agnorm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
    275            AlgExtGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
    276            CanonicalForm & R)
    277 {
    278   Variable y=PPalpha.mvar(),vf=f.mvar();
    279   CanonicalForm temp, Palpha=PPalpha, t;
    280   int sqfreetest=0;
    281   CFFList testlist;
    282   CFFListIterator i;
    283 
    284   myrandom.reset();   s=myrandom.item();   g=f;
    285   R= CanonicalForm(0);
    286 
    287   // Norm, resultante taken with respect to y
    288   while ( !sqfreetest )
    289   {
    290     R = resultante(Palpha, g, y); R= R* bCommonDen(R);
    291     R /= content (R);
    292     // sqfree check ; R is a polynomial in K[x]
    293     if ( getCharacteristic() == 0 )
    294     {
    295       temp= gcd(R, R.deriv(vf));
    296       if (degree(temp,vf) != 0 || temp == temp.genZero() )
    297         sqfreetest= 0;
    298       else
    299         sqfreetest= 1;
    300     }
    301     else
    302     {
    303       Variable X;
    304       if (hasFirstAlgVar(R,X))
    305         testlist= factorize( R, X );
    306       else
    307         testlist= factorize(R);
    308       if (testlist.getFirst().factor().inCoeffDomain())
    309         testlist.removeFirst();
    310       sqfreetest=1;
    311       for ( i=testlist; i.hasItem(); i++)
    312       {
    313         if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0)
    314         {
    315           sqfreetest=0;
    316           break;
    317         }
    318       }
    319     }
    320     if ( ! sqfreetest )
    321     {
    322       myrandom.next();
    323       if ( getCharacteristic() == 0 )
    324         t= CanonicalForm(mapinto(myrandom.item()));
    325       else
    326         t= CanonicalForm(myrandom.item());
    327       s= t;
    328       g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
    329     }
    330   }
    331 }
    332 
    333 static void
     274
     275static CFFList
    334276sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha,
    335277           const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
    336278           CanonicalForm & R)
    337279{
     280  CFFList result;
    338281  if ( getCharacteristic() == 0 )
    339282  {
    340283    IntGenerator myrandom;
    341     sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
    342   }
    343   else if ( degree(Extension) > 0 ) // working over Extensions
    344   {
    345     AlgExtGenerator myrandom(Extension);
    346     sqrf_agnorm_sub(f,PPalpha, myrandom, s,g,R);
     284    result= sqrf_norm_sub (f, PPalpha, myrandom, s, g, R);
     285  }
     286  else if ( degree (Extension) > 0 ) // working over Extensions
     287  {
     288    AlgExtGenerator myrandom (Extension);
     289    result= sqrf_norm_sub (f, PPalpha, myrandom, s, g, R);
    347290  }
    348291  else
    349292  {
    350293    FFGenerator myrandom;
    351     sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
    352   }
     294    result= sqrf_norm_sub (f, PPalpha, myrandom, s, g, R);
     295  }
     296  return result;
    353297}
    354298
    … …  
    387331        On (SW_RATIONAL);
    388332      oldR= R;
    389       sqrf_norm (i.getItem(), R, Extension, s, g, R);
     333      //TODO normalize i.getItem over K(R)?
     334      (void) sqrf_norm (i.getItem(), R, Extension, s, g, R);
    390335
    391336      backSubst.insert (s);
    … …  
    474419{
    475420  bool isRat= isOn (SW_RATIONAL);
    476   CFFList L, Factorlist;
     421  CFFList L, sqrfFactors, Factorlist, tmp;
     422  CFFListIterator iter, iter2;
    477423  CanonicalForm R, Rstar, s, g, h, f= F;
    478424  CFList substlist, backSubsts;
    … …  
    492438    Factorlist= factorize (g, alpha);
    493439
    494     for (CFFListIterator i= Factorlist; i.hasItem(); i++)
    495     {
    496       h= i.getItem().factor();
     440    for (iter= Factorlist; iter.hasItem(); iter++)
     441    {
     442      h= iter.getItem().factor();
    497443      if (!h.inCoeffDomain())
    498444      {
    … …  
    501447        h= backSubst (h, backSubsts, Astar);
    502448        h= Prem (h, as);
    503         L.append (CFFactor (h, i.getItem().exp()));
     449        L.append (CFFactor (h, iter.getItem().exp()));
    504450      }
    505451    }
    … …  
    533479  }
    534480
    535   sqrf_norm (f, Rstar, vminpoly, s, g, R);
    536 
    537   Variable X;
    538   if (hasFirstAlgVar (R, X))
    539   {
    540     // factorize R over alg.extension with X
    541     Factorlist=  factorize (R, X);
     481  sqrfFactors= sqrf_norm (f, Rstar, vminpoly, s, g, R);
     482
     483  if (getCharacteristic() > 0)
     484  {
     485    if (sqrfFactors.getFirst().factor().inCoeffDomain())
     486      sqrfFactors.removeFirst();
     487
     488    Variable X;
     489    for (iter= sqrfFactors; iter.hasItem(); iter++)
     490    {
     491      if (hasFirstAlgVar (iter.getItem().factor(), X))
     492      {
     493        // factorize over alg.extension with X
     494        tmp= factorize (iter.getItem().factor(), X);
     495      }
     496      else
     497      {
     498        // factorize over k
     499        tmp= factorize (iter.getItem().factor(), true);
     500      }
     501      if (tmp.getFirst().factor().inCoeffDomain())
     502        tmp.removeFirst();
     503      for (iter2= tmp; iter2.hasItem(); iter2++)
     504        Factorlist= append (Factorlist, iter2.getItem());
     505    }
    542506  }
    543507  else
    544   {
    545     // factor R over k
    546     Factorlist = factorize (R);
    547   }
     508    Factorlist= factorize (R, true);
    548509
    549510  if (!Factorlist.getFirst().factor().inCoeffDomain())
    550511    Factorlist.insert (CFFactor (1, 1));
    551   if (Factorlist.length() == 2 && Factorlist.getLast().exp()== 1)
     512  if (Factorlist.length() == 2 && Factorlist.getLast().exp() == 1)
    552513  {
    553514    f= backSubst (f, backSubsts, Astar);
    … …  
    561522  {
    562523    g= f;
    563     for ( CFFListIterator i=Factorlist; i.hasItem(); i++)
    564     {
    565       CanonicalForm fnew=i.getItem().factor();
     524    for (iter= Factorlist; iter.hasItem(); iter++)
     525    {
     526      CanonicalForm fnew= iter.getItem().factor();
    566527      if (fnew.level() < Rstar.level()) //factor is a constant from the function field
    567528        continue;
    568529      else
    569530      {
    570         fnew= fnew (g.mvar()+s*Rstar.mvar(), g.mvar());
     531        fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
    571532        fnew= reduce (fnew, Rstar);
    572533      }
    573534
    574535      h= alg_gcd (g, fnew, Rstarlist);
    575       numinv= QuasiInverse(Rstar, alg_LC(h, algExtLevel), Rstar.mvar());
     536      numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
    576537      h *= numinv;
    577538      h= Prem (h, Rstarlist);
    … …  
    710671      if (recurse)
    711672      {
    712         ii=as;
     673        ii= as;
    713674        for (; ii.hasItem(); ii++)
    714675        {
    … …  
    821782
    822783  asnew.removeLast();
    823   for (CFListIterator i= asnew; i.hasItem(); i++)
     784  for (i= asnew; i.hasItem(); i++)
    824785    i.getItem() /= content (i.getItem());
    825786
    … …  
    854815  CFList transform;
    855816
    856   for (CFFListIterator k= tmp; k.hasItem(); k++)
     817  for (iter= tmp; iter.hasItem(); iter++)
    857818  {
    858819    transform= transBack;
    859     CanonicalForm factor= k.getItem().factor();
     820    CanonicalForm factor= iter.getItem().factor();
    860821    factor= M (factor);
    861822    transform.append (factor);
    … …  
    874835    if (expF > 0)
    875836    {
    876       int mult= tmpExp/(degree (factor)/degree (k.getItem().factor()));
    877       result.append (CFFactor (factor, k.getItem().exp()*mult));
     837      int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
     838      result.append (CFFactor (factor, iter.getItem().exp()*mult));
    878839    }
    879840    else
    880       result.append (CFFactor (factor, k.getItem().exp()));
     841      result.append (CFFactor (factor, iter.getItem().exp()));
    881842  }
    882843
Note: See TracChangeset for help on using the changeset viewer.