Changeset 1a3011e in git


Ignore:
Timestamp:
Feb 1, 2012, 4:21:14 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
69c8820d335e5e0a8ddcbf89ce82547457c3ec66
Parents:
09609a2f4751f0b3b3d459d710552a967e51d5d6
git-author:
Martin Lee <martinlee84@web.de>2012-02-01 16:21:14+01:00
git-committer:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-02-10 14:16:44+01:00
Message:
chg: avoid double checking of factors during henselLiftAndEarly
chg: lower liftBound in bivariate factorization
Location:
factory
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • factory/facBivar.cc

    r09609a r1a3011e  
    364364  A= A (y + evaluation, y);
    365365
    366   int liftBound= degree (A, y) + 1 + degree (LC(A, x));
     366  int liftBound= degree (A, y) + 1;
    367367
    368368  ExtensionInfo dummy= ExtensionInfo (false);

  • factory/facFqBivar.cc

    r09609a r1a3011e  
    620620}
    621621
    622 CFList
    623 earlyFactorDetection (CanonicalForm& F, CFList& factors,int& adaptedLiftBound,
     622void
     623earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
     624                      factors, int& adaptedLiftBound, int*& factorsFoundIndex,
    624625                      DegreePattern& degs, bool& success, int deg)
    625626{
    626627  DegreePattern bufDegs1= degs;
    627628  DegreePattern bufDegs2;
    628   CFList result;
    629629  CFList T= factors;
    630630  CanonicalForm buf= F;
    … …  
    634634  CanonicalForm M= power (F.mvar(), deg);
    635635  adaptedLiftBound= 0;
    636   int d= degree (F);
    637   for (CFListIterator i= factors; i.hasItem(); i++)
    638   {
    639     if (!bufDegs1.find (degree (i.getItem(), 1)))
     636  int d= degree (F), l= 0;
     637  for (CFListIterator i= factors; i.hasItem(); i++, l++)
     638  {
     639    if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
    640640      continue;
    641641    else
    … …  
    645645      if (fdivides (g, buf, quot))
    646646      {
    647         result.append (g);
     647        reconstructedFactors.append (g);
     648        factorsFoundIndex[l]= 1;
    648649        buf= quot;
    649650        d -= degree (g);
    … …  
    657658        if (bufDegs1.getLength() <= 1)
    658659        {
    659           result.append (buf);
     660          reconstructedFactors.append (buf);
    660661          break;
    661662        }
    … …  
    666667  if (adaptedLiftBound < deg)
    667668  {
     669    success= true;
    668670    factors= T;
    669671    degs= bufDegs1;
    670672    F= buf;
    671     success= true;
    672673  }
    673674  if (bufDegs1.getLength() <= 1)
    674675    degs= bufDegs1;
    675   return result;
    676676}
    677677
    678 CFList
    679 extEarlyFactorDetection (CanonicalForm& F, CFList& factors,
    680                          int& adaptedLiftBound, DegreePattern& degs,
    681                          bool& success, const ExtensionInfo& info,
    682                          const CanonicalForm& eval, int deg)
     678void
     679extEarlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
     680                         factors,int& adaptedLiftBound, int*& factorsFoundIndex,
     681                         DegreePattern& degs, bool& success, const
     682                         ExtensionInfo& info, const CanonicalForm& eval, int deg
     683                        )
    683684{
    684685  Variable alpha= info.getAlpha();
    … …  
    696697  adaptedLiftBound= 0;
    697698  bool trueFactor= false;
    698   int d= degree (F);
     699  int d= degree (F), l= 0;
    699700  CFList source, dest;
    700701  int degMipoBeta= 1;
    … …  
    702703    degMipoBeta= degree (getMipo (beta));
    703704  CanonicalForm quot;
    704   for (CFListIterator i= factors; i.hasItem(); i++)
    705   {
    706     if (!bufDegs1.find (degree (i.getItem(), 1)))
     705  for (CFListIterator i= factors; i.hasItem(); i++, l++)
     706  {
     707    if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
    707708      continue;
    708709    else
    … …  
    719720          if (degree (buf2, alpha) < degMipoBeta)
    720721          {
    721             appendTestMapDown (result, buf2, info, source, dest);
     722            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
     723            factorsFoundIndex[l]= 1;
    722724            buf= quot;
    723725            d -= degree (g);
    … …  
    730732          if (!isInExtension (buf2, gamma, k, delta, source, dest))
    731733          {
    732             appendTestMapDown (result, buf2, info, source, dest);
     734            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
     735            factorsFoundIndex[l]= 1;
    733736            buf= quot;
    734737            d -= degree (g);
    … …  
    750753            buf= buf (y - eval, y);
    751754            buf /= Lc (buf);
    752             appendMapDown (result, buf, info, source, dest);
     755            appendMapDown (reconstructedFactors, buf, info, source, dest);
    753756            break;
    754757          }
    … …  
    767770  if (bufDegs1.getLength() <= 1)
    768771    degs= bufDegs1;
    769 
    770   return result;
    771772}
    772773
    … …  
    826827}
    827828
     829void
     830deleteFactors (const CFList& L, CFList& factors, const CanonicalForm& eval, bool
     831               extension)
     832{
     833  int index;
     834  CanonicalForm tmp1, tmp2;
     835  CFListIterator j;
     836  Variable y= Variable (2);
     837  for (CFListIterator i= L; i.hasItem(); i++)
     838  {
     839    index= 1;
     840    if (extension)
     841      tmp1= mod (i.getItem(), y-eval);
     842    else
     843      tmp1= mod (i.getItem(), y);
     844    tmp1 /= Lc (tmp1);
     845    for (j= factors; j.hasItem(); j++, index++)
     846    {
     847      tmp2= mod (j.getItem(), y);
     848      tmp2 /= Lc (tmp2);
     849      if (tmp1 == tmp2)
     850      {
     851        index++;
     852        j.remove(index);
     853        break;
     854      }
     855    }
     856  }
     857}
     858
    828859CFList
    829860henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
    … …  
    853884  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
    854885  int dummy;
     886  int * factorsFoundIndex= new int [uniFactors.length()];
     887  for (int i= 0; i < uniFactors.length(); i++)
     888    factorsFoundIndex [i]= 0;
     889
    855890  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
    856891    henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
    … …  
    859894    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
    860895    if (!extension)
    861       earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    862                      degs, earlySuccess, smallFactorDeg);
     896      earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     897                            factorsFoundIndex, degs, earlySuccess,
     898                            smallFactorDeg);
    863899    else
    864       earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    865                      newLiftBound, degs, earlySuccess, info, eval,
    866                      smallFactorDeg);
     900      extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     901                               factorsFoundIndex, degs, earlySuccess, info,
     902                               eval, smallFactorDeg);
    867903    if (degs.getLength() > 1 && !earlySuccess &&
    868904        smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
    … …  
    874910                            liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M);
    875911        if (!extension)
    876           earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    877                         degs, earlySuccess, liftPre[sizeOfLiftPre-1] + 1);
     912          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     913                                factorsFoundIndex, degs, earlySuccess,
     914                                liftPre[sizeOfLiftPre-1] + 1);
    878915        else
    879           earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    880                         newLiftBound, degs, earlySuccess, info, eval,
    881                         liftPre[sizeOfLiftPre-1] + 1);
     916          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     917                                   factorsFoundIndex, degs, earlySuccess, info,
     918                                   eval, liftPre[sizeOfLiftPre-1] + 1);
    882919      }
    883920    }
    … …  
    894931                            liftPre[i-1] + 1, Pi, diophant, M);
    895932        if (!extension)
    896           earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    897                         degs, earlySuccess, liftPre[i-1] + 1);
     933          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     934                                factorsFoundIndex, degs, earlySuccess,
     935                                liftPre[i-1] + 1);
    898936        else
    899           earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    900                         newLiftBound, degs, earlySuccess, info, eval,
    901                         liftPre[i-1] + 1);
     937          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     938                                   factorsFoundIndex, degs, earlySuccess, info,
     939                                   eval, liftPre[i-1] + 1);
    902940      }
    903941      else
    … …  
    916954    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
    917955    if (!extension)
    918       earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    919                      degs, earlySuccess, smallFactorDeg);
     956      earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     957                            factorsFoundIndex, degs, earlySuccess,
     958                            smallFactorDeg);
    920959    else
    921       earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    922                      newLiftBound, degs, earlySuccess, info, eval,
    923                      smallFactorDeg);
     960      extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     961                               factorsFoundIndex, degs, earlySuccess, info,
     962                               eval, smallFactorDeg);
    924963    int i= 1;
    925964    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
    … …  
    932971                          dummy, Pi, diophant, M);
    933972      if (!extension)
    934         earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    935                       degs, earlySuccess, dummy);
     973        earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     974                              factorsFoundIndex, degs, earlySuccess, dummy);
    936975      else
    937         earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    938                       newLiftBound, degs, earlySuccess, info, eval,
    939                       dummy);
     976        extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     977                                 factorsFoundIndex, degs, earlySuccess, info,
     978                                 eval, dummy);
    940979    }
    941980    while (degs.getLength() > 1 && !earlySuccess && i < 4)
    … …  
    948987                            dummy, Pi, diophant, M);
    949988        if (!extension)
    950           earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
    951                         degs, earlySuccess, dummy);
     989          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     990                                factorsFoundIndex, degs, earlySuccess, dummy);
    952991        else
    953           earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
    954                         newLiftBound, degs, earlySuccess, info, eval,
    955                         dummy);
     992          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
     993                                   factorsFoundIndex, degs, earlySuccess, info,
     994                                   eval, dummy);
    956995      }
    957996      else
    … …  
    9661005  }
    9671006
    968   if (!earlySuccess)
    969     liftBound= degree (A,y) + 1;
    970 
     1007  delete [] factorsFoundIndex;
    9711008  delete [] liftPre;
    9721009
    … …  
    41994236  int adaptedLiftBound;
    42004237  success= false;
    4201   CFList earlyFactors= earlyFactorDetection (F, bufUniFactors, adaptedLiftBound,
    4202                                              degs, success, smallFactorDeg
    4203                                             );
     4238  int * factorsFoundIndex= new int [uniFactors.length()];
     4239  for (int i= 0; i < uniFactors.length(); i++)
     4240    factorsFoundIndex [i]= 0;
     4241  CFList earlyFactors;
     4242  earlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
     4243                        factorsFoundIndex, degs, success, smallFactorDeg);
     4244  delete [] factorsFoundIndex;
    42044245  if (degs.getLength() == 1)
    42054246  {
    … …  
    42494290  int adaptedLiftBound;
    42504291  success= false;
    4251   CFList earlyFactors= extEarlyFactorDetection (F, bufUniFactors,
    4252                                                 adaptedLiftBound, degs, success,
    4253                                                 info, evaluation, smallFactorDeg
    4254                                                );
     4292  int * factorsFoundIndex= new int [uniFactors.length()];
     4293  for (int i= 0; i < uniFactors.length(); i++)
     4294    factorsFoundIndex [i]= 0;
     4295  CFList earlyFactors;
     4296  extEarlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
     4297                           factorsFoundIndex, degs, success, info, evaluation,
     4298                           smallFactorDeg);
     4299  delete [] factorsFoundIndex;
    42554300  if (degs.getLength() == 1)
    42564301  {
    … …  
    56995744  A= A (y + evaluation, y);
    57005745
    5701   int liftBound= degree (A, y) + 1 + degree (LC(A, x));
     5746  int liftBound= degree (A, y) + 1;
    57025747
    57035748  int boundsLength;

  • factory/facFqBivar.h

    r09609a r1a3011e  
    678678/// degree pattern are updated.
    679679///
    680 /// @return @a earlyFactorDetection returns a list of factors of F (possibly in-
    681 ///         complete), in case of success. Otherwise an empty list.
    682680/// @sa factorRecombination(), extEarlyFactorDetection()
    683 CFList
     681void
    684682earlyFactorDetection (
     683           CFList& reconstructedFactors, ///< [in,out] list of reconstructed
     684                                         ///< factors
    685685           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
    686686                                   ///< poly divided by detected factors in case
    … …  
    690690                                   ///< without detected factors
    691691           int& adaptedLiftBound,  ///< [in,out] adapted lift bound
     692           int*& factorsFoundIndex,///< [in,out] factors already considered
    692693           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
    693694                                   ///< whenever we find a factor
    … …  
    700701/// degree pattern are updated.
    701702///
    702 /// @return @a extEarlyFactorDetection returns a list of factors of F (possibly
    703 ///         incomplete), whose shift to zero is reversed, in case of success.
    704 ///         Otherwise an empty list.
    705703/// @sa factorRecombination(), earlyFactorDetection()
    706 CFList
     704void
    707705extEarlyFactorDetection (
     706        CFList& reconstructedFactors, ///< [in,out] list of reconstructed
     707                                      ///< factors
    708708        CanonicalForm& F,          ///< [in,out] poly to be factored, returns
    709709                                   ///< poly divided by detected factors in case
    … …  
    713713                                   ///< without detected factors
    714714        int& adaptedLiftBound,     ///< [in,out] adapted lift bound
     715        int*& factorsFoundIndex,   ///< [in,out] factors already considered
    715716        DegreePattern& degs,       ///< [in,out] degree pattern, is updated
    716717                                   ///< whenever we find a factor
Note: See TracChangeset for help on using the changeset viewer.