Changeset 77ed181 in git for factory/facFactorize.cc


Ignore:
Timestamp:
Feb 18, 2013, 6:25:59 PM (11 years ago)
Author:
Mohamed Barakat <mohamed.barakat@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
de27d825ef8e6c2bf0bebcf1629935b1d5a3412f
Parents:
65148c4d2a607796fbd578ae2f3219965019aaae520eaa58f37075554f45501fdb328bb9c37f7f48
Message:
Merge pull request #266 from mohamed-barakat/spielwiese

created a new test: ignoring_denominators_of_coefficients.tst
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/facFactorize.cc

    r520eaa5 r77ed181  
    413413
    414414  if (w.level() != 1)
    415   {
    416     A= swapvar (A, y, w);
    417     int i= A.level();
    418     CanonicalForm evalPoint;
    419     for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
    420     {
    421       if (i == w.level())
    422       {
    423         evalPoint= iter.getItem();
    424         iter.getItem()= evaluation.getLast();
    425         evaluation.removeLast();
    426         evaluation.append (evalPoint);
    427         break;
    428       }
    429     }
    430     for (i= 0; i < lengthAeval2; i++)
    431     {
    432       if (oldAeval[i].isEmpty())
    433         continue;
    434       if (oldAeval[i].getFirst().level() == w.level())
    435       {
    436         CFArray tmp= copy (oldAeval[i]);
    437         oldAeval[i]= biFactors;
    438         for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
    439           iter.getItem()= swapvar (iter.getItem(), w, y);
    440         for (int ii= 0; ii < tmp.size(); ii++)
    441           tmp[ii]= swapvar (tmp[ii], w, y);
    442         CFArray tmp2= CFArray (tmp.size());
    443         CanonicalForm buf;
    444         for (int ii= 0; ii < tmp.size(); ii++)
    445         {
    446           buf= tmp[ii] (evaluation.getLast(),y);
    447           buf /= Lc (buf);
    448           tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
    449         }
    450         biFactors= CFList();
    451         for (int j= 0; j < tmp2.size(); j++)
    452           biFactors.append (tmp2[j]);
    453       }
    454     }
    455   }
    456 
    457   CFListIterator iter;
     415    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
     416                          uniFactors, w);
     417
    458418  CanonicalForm oldA= A;
    459419  CFList oldBiFactors= biFactors;
    460   if (!leadingCoeffs.getFirst().inCoeffDomain())
    461   {
    462     CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
    463     A *= tmp;
    464     tmp= leadingCoeffs.getFirst();
    465     iter= evaluation;
    466     for (int i= A.level(); i > 2; i--, iter++)
    467       tmp= tmp (iter.getItem(), i);
    468     if (!tmp.inCoeffDomain())
    469     {
    470       for (CFListIterator i= biFactors; i.hasItem(); i++)
    471       {
    472         i.getItem() *= tmp/LC (i.getItem(), 1);
    473         i.getItem() /= Lc (i.getItem());
    474       }
    475     }
    476   }
    477420
    478421  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
    … …  
    480423  leadingCoeffs.removeFirst();
    481424
     425  if (!LCmultiplierIsConst)
     426    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
     427
    482428  //prepare leading coefficients
    483429  CFList* leadingCoeffs2= new CFList [lengthAeval2];
    484   prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
    485                         evaluation);
    486 
    487 
    488   Aeval= evaluateAtEval (A, evaluation, 2);
    489 
    490   CanonicalForm hh= 1/Lc (Aeval.getFirst());
    491 
    492   for (iter= Aeval; iter.hasItem(); iter++)
    493     iter.getItem() *= hh;
    494 
    495   A *= hh;
    496 
    497   CFListIterator iter2;
     430  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
     431                        biFactors, evaluation);
     432
     433  CFListIterator iter;
    498434  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
    499435  bufBiFactors= biFactors;
    500436  bufA= A;
    501   CanonicalForm bufLCmultiplier= LCmultiplier;
    502   CanonicalForm testVars;
     437  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
    503438  if (!LCmultiplierIsConst)
    504439  {
    … …  
    571506      LCheuristic= true;
    572507      factors= oldFactors;
    573       CanonicalForm cont;
    574508      CFList contents, LCs;
    575       int index=1;
    576509      bool foundTrueMultiplier= false;
    577       for (iter= factors; iter.hasItem(); iter++, index++)
    578       {
    579         cont= content (iter.getItem(), 1);
    580         cont= gcd (cont , LCmultiplier);
    581         contents.append (cont);
    582         if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
    583         {
    584           foundTrueMultiplier= true;
    585           int index2= 1;
    586           for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
    587                                                                     index2++)
    588           {
    589             if (index2 == index)
    590               continue;
    591             iter2.getItem() /= LCmultiplier;
    592           }
     510      LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
     511                    contents, LCs, foundTrueMultiplier);
     512      if (foundTrueMultiplier)
     513      {
    593514          A= oldA;
    594515          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
    595516          for (int i= lengthAeval2-1; i > -1; i--)
    596517            leadingCoeffs2[i]= CFList();
    597           prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
    598                                 biFactors, evaluation );
    599           Aeval= evaluateAtEval (A, evaluation, 2);
    600 
    601           hh= 1/Lc (Aeval.getFirst());
    602 
    603           for (iter2= Aeval; iter2.hasItem(); iter2++)
    604             iter2.getItem() *= hh;
    605 
    606           A *= hh;
    607           break;
    608         }
    609         else
    610           LCs.append (LC (iter.getItem()/cont, 1));
    611       }
    612       if (!foundTrueMultiplier)
    613       {
    614         index= 1;
    615         iter2= factors;
     518          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
     519                                leadingCoeffs, biFactors, evaluation);
     520      }
     521      else
     522      {
    616523        bool foundMultiplier= false;
    617         for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
    618         {
    619           if (fdivides (iter.getItem(), LCmultiplier))
    620           {
    621             if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
    622                 !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
    623             {
    624               Variable xx= Variable (2);
    625               CanonicalForm vars;
    626               vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
    627                                         xx));
    628               for (int i= 0; i < lengthAeval2; i++)
    629               {
    630                 if (oldAeval[i].isEmpty())
    631                   continue;
    632                 xx= oldAeval[i].getFirst().mvar();
    633                 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
    634                                            xx));
    635               }
    636               if (vars.level() <= 2)
    637               {
    638                 int index2= 1;
    639                 for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
    640                      iter3.hasItem(); iter3++, index2++)
    641                 {
    642                   if (index2 == index)
    643                   {
    644                     iter3.getItem() /= LCmultiplier;
    645                     break;
    646                   }
    647                 }
    648                 A /= LCmultiplier;
    649                 foundMultiplier= true;
    650                 iter.getItem()= 1;
    651               }
    652             }
    653           }
    654         }
     524        LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
     525                      A, leadingCoeffs2, lengthAeval2, foundMultiplier);
    655526        // coming from above: divide out more LCmultiplier if possible
    656527        if (foundMultiplier)
    657528        {
    658529          foundMultiplier= false;
    659           index=1;
    660           iter2= factors;
    661           for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
    662           {
    663             if (!iter.getItem().isOne() &&
    664                 fdivides (iter.getItem(), LCmultiplier))
    665             {
    666               if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
    667               {
    668                 int index2= 1;
    669                 for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
    670                      iter2++, index2++)
    671                 {
    672                   if (index2 == index)
    673                   {
    674                     iter2.getItem() /= iter.getItem();
    675                     foundMultiplier= true;
    676                     break;
    677                   }
    678                 }
    679                 A /= iter.getItem();
    680                 LCmultiplier /= iter.getItem();
    681                 iter.getItem()= 1;
    682               }
    683               else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
    684               {
    685                 Variable xx= Variable (2);
    686                 CanonicalForm vars;
    687                 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
    688                                           xx));
    689                 for (int i= 0; i < lengthAeval2; i++)
    690                 {
    691                   if (oldAeval[i].isEmpty())
    692                     continue;
    693                   xx= oldAeval[i].getFirst().mvar();
    694                   vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
    695                                              xx));
    696                 }
    697                 if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
    698                     /myGetVars (LCmultiplier) == vars)
    699                 {
    700                   int index2= 1;
    701                   for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
    702                        iter2++, index2++)
    703                   {
    704                     if (index2 == index)
    705                     {
    706                       iter2.getItem() /= LCmultiplier;
    707                       foundMultiplier= true;
    708                       break;
    709                     }
    710                   }
    711                   A /= LCmultiplier;
    712                   iter.getItem()= 1;
    713                 }
    714               }
    715             }
    716           }
     530          LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
     531                        lengthAeval2, leadingCoeffs2, A, LCmultiplier,
     532                        foundMultiplier);
    717533        }
    718534        else
    719535        {
    720           CanonicalForm pLCs= prod (LCs);
    721           if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
    722           {
    723             A= oldA;
    724             iter2= leadingCoeffs2[lengthAeval2-1];
    725             for (iter= contents; iter.hasItem(); iter++, iter2++)
    726               iter2.getItem() /= iter.getItem();
    727             foundMultiplier= true;
    728           }
     536          LCHeuristicCheck (LCs, contents, A, oldA,
     537                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
    729538          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
    730539          {
    731             Variable xx;
    732             CFList vars1;
    733             CFFList sqrfMultiplier= sqrFree (LCmultiplier);
    734             if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
    735               sqrfMultiplier.removeFirst();
    736             sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
    737             xx= Variable (2);
    738             for (iter= oldBiFactors; iter.hasItem(); iter++)
    739               vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
    740             for (int i= 0; i < lengthAeval2; i++)
    741             {
    742               if (oldAeval[i].isEmpty())
    743                 continue;
    744               xx= oldAeval[i].getFirst().mvar();
    745               iter2= vars1;
    746               for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
    747                 iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
    748             }
    749             CanonicalForm tmp;
    750             iter2= vars1;
    751             for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
    752                                                                     iter2++)
    753             {
    754               tmp= iter.getItem()/LCmultiplier;
    755               for (int i=1; i <= tmp.level(); i++)
    756               {
    757                 if (degree(tmp,i) > 0 &&
    758                     (degree(iter2.getItem(),i) > degree (tmp,i)))
    759                   iter2.getItem() /= power (Variable (i), degree (tmp,i));
    760               }
    761             }
    762             int multi;
    763             for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
    764             {
    765               multi= 0;
    766               for (iter= vars1; iter.hasItem(); iter++)
    767               {
    768                 tmp= iter.getItem();
    769                 while (fdivides (myGetVars (ii.getItem().factor()), tmp))
    770                 {
    771                   multi++;
    772                   tmp /= myGetVars (ii.getItem().factor());
    773                 }
    774               }
    775               if (multi == ii.getItem().exp())
    776               {
    777                 index= 1;
    778                 for (iter= vars1; iter.hasItem(); iter++, index++)
    779                 {
    780                   while (fdivides (myGetVars(ii.getItem().factor()),
    781                                    iter.getItem()
    782                                   )
    783                         )
    784                   {
    785                     int index2= 1;
    786                     for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
    787                          iter2++, index2++)
    788                     {
    789                       if (index2 == index)
    790                         continue;
    791                       else
    792                       {
    793                         tmp= ii.getItem().factor();
    794                         iter2.getItem() /= tmp;
    795                         CFListIterator iter3= evaluation;
    796                         for (int jj= A.level(); jj > 2; jj--, iter3++)
    797                           tmp= tmp (iter3.getItem(), jj);
    798                         if (!tmp.inCoeffDomain())
    799                         {
    800                           int index3= 1;
    801                           for (iter3= biFactors; iter3.hasItem(); iter3++,
    802                                                                   index3++)
    803                           {
    804                             if (index3 == index2)
    805                             {
    806                               iter3.getItem() /= tmp;
    807                               iter3.getItem() /= Lc (iter3.getItem());
    808                               break;
    809                             }
    810                           }
    811                         }
    812                         A /= ii.getItem().factor();
    813                       }
    814                     }
    815                     iter.getItem() /= getVars (ii.getItem().factor());
    816                   }
    817                 }
    818               }
    819               else
    820               {
    821                 index= 1;
    822                 for (iter= vars1; iter.hasItem(); iter++, index++)
    823                 {
    824                   if (!fdivides (myGetVars (ii.getItem().factor()),
    825                                  iter.getItem()
    826                                 )
    827                      )
    828                   {
    829                     int index2= 1;
    830                     for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
    831                          iter2++, index2++)
    832                     {
    833                       if (index2 == index)
    834                       {
    835                         tmp= power (ii.getItem().factor(), ii.getItem().exp());
    836                         iter2.getItem() /= tmp;
    837                         A /= tmp;
    838                         CFListIterator iter3= evaluation;
    839                         for (int jj= A.level(); jj > 2; jj--, iter3++)
    840                           tmp= tmp (iter3.getItem(), jj);
    841                         if (!tmp.inCoeffDomain())
    842                         {
    843                           int index3= 1;
    844                           for (iter3= biFactors; iter3.hasItem(); iter3++,
    845                                                                   index3++)
    846                           {
    847                             if (index3 == index2)
    848                             {
    849                               iter3.getItem() /= tmp;
    850                               iter3.getItem() /= Lc (iter3.getItem());
    851                               break;
    852                             }
    853                           }
    854                         }
    855                       }
    856                     }
    857                   }
    858                 }
    859               }
    860             }
     540            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
     541                         lengthAeval2, evaluation, oldBiFactors);
    861542          }
    862543        }
    … …  
    866547        for (int i= lengthAeval2-1; i > -1; i--)
    867548          leadingCoeffs2[i]= CFList();
    868         prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
    869                               evaluation);
    870         Aeval= evaluateAtEval (A, evaluation, 2);
    871 
    872         hh= 1/Lc (Aeval.getFirst());
    873 
    874         for (CFListIterator i= Aeval; i.hasItem(); i++)
    875           i.getItem() *= hh;
    876 
    877         A *= hh;
     549        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
     550                              biFactors, evaluation);
    878551      }
    879552      factors= CFList();
    … …  
    898571  {
    899572    LCheuristic= true;
    900     int index;
    901     Variable xx;
    902     CFList vars1;
    903     CFFList sqrfMultiplier= sqrFree (LCmultiplier);
    904     if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
    905       sqrfMultiplier.removeFirst();
    906     sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
    907     xx= Variable (2);
    908     for (iter= oldBiFactors; iter.hasItem(); iter++)
    909       vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
    910     for (int i= 0; i < lengthAeval2; i++)
    911     {
    912       if (oldAeval[i].isEmpty())
    913         continue;
    914       xx= oldAeval[i].getFirst().mvar();
    915       iter2= vars1;
    916       for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
    917         iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
    918     }
    919     CanonicalForm tmp;
    920     iter2= vars1;
    921     for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
    922     {
    923       tmp= iter.getItem()/LCmultiplier;
    924       for (int i=1; i <= tmp.level(); i++)
    925       {
    926         if (degree(tmp,i) > 0 && (degree(iter2.getItem(),i) > degree (tmp,i)))
    927           iter2.getItem() /= power (Variable (i), degree (tmp,i));
    928       }
    929     }
    930     int multi;
    931     for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
    932     {
    933       multi= 0;
    934       for (iter= vars1; iter.hasItem(); iter++)
    935       {
    936         tmp= iter.getItem();
    937         while (fdivides (myGetVars (ii.getItem().factor()), tmp))
    938         {
    939           multi++;
    940           tmp /= myGetVars (ii.getItem().factor());
    941         }
    942       }
    943       if (multi == ii.getItem().exp())
    944       {
    945         index= 1;
    946         for (iter= vars1; iter.hasItem(); iter++, index++)
    947         {
    948           while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
    949           {
    950             int index2= 1;
    951             for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
    952                                                                       index2++)
    953             {
    954               if (index2 == index)
    955                 continue;
    956               else
    957               {
    958                 tmp= ii.getItem().factor();
    959                 iter2.getItem() /= tmp;
    960                 CFListIterator iter3= evaluation;
    961                 for (int jj= A.level(); jj > 2; jj--, iter3++)
    962                   tmp= tmp (iter3.getItem(), jj);
    963                 if (!tmp.inCoeffDomain())
    964                 {
    965                   int index3= 1;
    966                   for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
    967                   {
    968                     if (index3 == index2)
    969                     {
    970                       iter3.getItem() /= tmp;
    971                       iter3.getItem() /= Lc (iter3.getItem());
    972                       break;
    973                     }
    974                   }
    975                 }
    976                 A /= ii.getItem().factor();
    977               }
    978             }
    979             iter.getItem() /= getVars (ii.getItem().factor());
    980           }
    981         }
    982       }
    983       else
    984       {
    985         index= 1;
    986         for (iter= vars1; iter.hasItem(); iter++, index++)
    987         {
    988           if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
    989           {
    990             int index2= 1;
    991             for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
    992                                                                       index2++)
    993             {
    994               if (index2 == index)
    995               {
    996                 tmp= power (ii.getItem().factor(), ii.getItem().exp());
    997                 iter2.getItem() /= tmp;
    998                 A /= tmp;
    999                 CFListIterator iter3= evaluation;
    1000                 for (int jj= A.level(); jj > 2; jj--, iter3++)
    1001                   tmp= tmp (iter3.getItem(), jj);
    1002                 if (!tmp.inCoeffDomain())
    1003                 {
    1004                   int index3= 1;
    1005                   for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
    1006                   {
    1007                     if (index3 == index2)
    1008                     {
    1009                       iter3.getItem() /= tmp;
    1010                       iter3.getItem() /= Lc (iter3.getItem());
    1011                       break;
    1012                     }
    1013                   }
    1014                 }
    1015               }
    1016             }
    1017           }
    1018         }
    1019       }
    1020     }
     573    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
     574                 lengthAeval2, evaluation, oldBiFactors);
    1021575
    1022576    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
    1023577    for (int i= lengthAeval2-1; i > -1; i--)
    1024578      leadingCoeffs2[i]= CFList();
    1025     prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
    1026                           evaluation);
    1027     Aeval= evaluateAtEval (A, evaluation, 2);
    1028 
    1029     hh= 1/Lc (Aeval.getFirst());
    1030 
    1031     for (CFListIterator i= Aeval; i.hasItem(); i++)
    1032       i.getItem() *= hh;
    1033 
    1034     A *= hh;
     579    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
     580                          biFactors, evaluation);
    1035581
    1036582    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
    … …  
    1087633    commonDenominators.append (bCommonDen (iter.getItem()));
    1088634  CanonicalForm tmp1, tmp2, tmp3=1;
     635  CFListIterator iter2;
    1089636  for (int i= 0; i < lengthAeval2; i++)
    1090637  {
Note: See TracChangeset for help on using the changeset viewer.