Changeset e243418 in git


Ignore:
Timestamp:
Apr 11, 2012, 4:22:25 PM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
a9a6dcbcbc4f0be99516f14eae42b1776235ca9f
Parents:
16a0dff5411888a4f70e800b97597f593dcdfb82
git-author:
Martin Lee <martinlee84@web.de>2012-04-11 16:22:25+02:00
git-committer:
Martin Lee <martinlee84@web.de>2012-05-07 14:13:43+02:00
Message:
chg: use convex dense compression in gcd
Location:
factory
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • factory/cfNewtonPolygon.cc

    r16a0df re243418  
    598598
    599599CanonicalForm
    600 compress (const CanonicalForm& F, mat_ZZ& M, vec_ZZ& A)
     600compress (const CanonicalForm& F, mat_ZZ& M, vec_ZZ& A, bool computeMA)
    601601{
    602602  int n;
    603   int ** newtonPolyg= newtonPolygon (F, n);
    604   convexDense (newtonPolyg, n, M, A);
     603  int ** newtonPolyg;
     604  if (computeMA)
     605  {
     606    newtonPolyg= newtonPolygon (F, n);
     607    convexDense (newtonPolyg, n, M, A);
     608  }
    605609  CanonicalForm result= 0;
    606610  ZZ expX, expY;
    … …  
    679683  }
    680684
    681   for (int i= 0; i < n; i++)
    682     delete [] newtonPolyg [i];
    683   delete [] newtonPolyg;
    684 
    685   M= inv (M);
     685  if (computeMA)
     686  {
     687    for (int i= 0; i < n; i++)
     688      delete [] newtonPolyg [i];
     689    delete [] newtonPolyg;
     690    M= inv (M);
     691  }
     692
    686693  return result;
    687694}

  • factory/cfNewtonPolygon.h

    r16a0df re243418  
    8585compress (const CanonicalForm& F, ///< [in] compressed, i.e. F.level()==2,
    8686                                  ///< bivariate poly
    87           mat_ZZ& inverseM,       ///< [in,out] returns the inverse of M
    88           vec_ZZ& A               ///< [in,out] returns translation
     87          mat_ZZ& inverseM,       ///< [in,out] returns the inverse of M,
     88                                  ///< if computeMA==true, M otherwise
     89          vec_ZZ& A,              ///< [in,out] returns translation
     90          bool computeMA= true    ///< [in] whether to compute M and A
    8991         );
    9092

  • factory/cf_gcd_smallp.cc

    r16a0df re243418  
    3434#include "facHensel.h"
    3535#include "cf_iter.h"
     36#include "cfNewtonPolygon.h"
    3637
    3738// iinline helper functions:
    … …  
    598599  }
    599600
     601  int sizeNewtonPolyg;
     602  int ** newtonPolyg= NULL;
     603  mat_ZZ MM;
     604  vec_ZZ V;
     605  bool compressConvexDense= (ppA.level() == 2 && ppB.level() == 2);
     606  if (compressConvexDense)
     607  {
     608    cA= content (ppA, 1);
     609    cB= content (ppB, 1);
     610    ppA /= cA;
     611    ppB /= cB;
     612    gcdcAcB *= gcd (cA, cB);
     613    if (ppA.isUnivariate() || ppB.isUnivariate())
     614    {
     615      if (ppA.level() == ppB.level())
     616      {
     617        if (substitute > 1)
     618          return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute));
     619        else
     620          return N (gcd (ppA, ppB)*gcdcAcB);
     621      }
     622      else
     623      {
     624        if (substitute > 1)
     625          return N (reverseSubst (gcdcAcB, substitute));
     626        else
     627          return N (gcdcAcB);
     628      }
     629    }
     630
     631    newtonPolyg= newtonPolygon (ppA,ppB, sizeNewtonPolyg);
     632    convexDense (newtonPolyg, sizeNewtonPolyg, MM, V);
     633
     634    for (int i= 0; i < sizeNewtonPolyg; i++)
     635      delete [] newtonPolyg[i];
     636    delete [] newtonPolyg;
     637
     638    ppA= compress (ppA, MM, V, false);
     639    ppB= compress (ppB, MM, V, false);
     640    MM= inv (MM);
     641
     642    if (ppA.isUnivariate() && ppB.isUnivariate())
     643    {
     644      if (ppA.level() == ppB.level())
     645      {
     646        if (substitute > 1)
     647          return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB,
     648                                  substitute));
     649        else
     650          return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB);
     651      }
     652      else
     653      {
     654        if (substitute > 1)
     655          return N (reverseSubst (gcdcAcB, substitute));
     656        else
     657          return N (gcdcAcB);
     658      }
     659    }
     660  }
     661
    600662  CanonicalForm lcA, lcB;  // leading coefficients of A and B
    601663  CanonicalForm gcdlcAlcB;
    … …  
    783845          ppH /= Lc(ppH);
    784846          DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
     847          if (compressConvexDense)
     848            ppH= decompress (ppH, MM, V);
    785849          if (substitute > 1)
    786850          {
    … …  
    793857      else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    794858      {
     859        if (compressConvexDense)
     860          ppH= decompress (ppH, MM, V);
    795861        if (substitute > 1)
    796862        {
    … …  
    903969    ppA= A/cA;
    904970    ppB= B/cB;
     971  }
     972
     973  int sizeNewtonPolyg;
     974  int ** newtonPolyg= NULL;
     975  mat_ZZ MM;
     976  vec_ZZ V;
     977  bool compressConvexDense= (ppA.level() == 2 && ppB.level() == 2);
     978  if (compressConvexDense)
     979  {
     980    cA= content (ppA, 1);
     981    cB= content (ppB, 1);
     982    ppA /= cA;
     983    ppB /= cB;
     984    gcdcAcB *= gcd (cA, cB);
     985    if (ppA.isUnivariate() || ppB.isUnivariate())
     986    {
     987      if (ppA.level() == ppB.level())
     988      {
     989        if (substitute > 1)
     990          return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute));
     991        else
     992          return N (gcd (ppA, ppB)*gcdcAcB);
     993      }
     994      else
     995      {
     996        if (substitute > 1)
     997          return N (reverseSubst (gcdcAcB, substitute));
     998        else
     999          return N (gcdcAcB);
     1000      }
     1001    }
     1002
     1003    newtonPolyg= newtonPolygon (ppA,ppB, sizeNewtonPolyg);
     1004    convexDense (newtonPolyg, sizeNewtonPolyg, MM, V);
     1005
     1006    for (int i= 0; i < sizeNewtonPolyg; i++)
     1007      delete [] newtonPolyg[i];
     1008    delete [] newtonPolyg;
     1009
     1010    ppA= compress (ppA, MM, V, false);
     1011    ppB= compress (ppB, MM, V, false);
     1012    MM= inv (MM);
     1013
     1014    if (ppA.isUnivariate() && ppB.isUnivariate())
     1015    {
     1016      if (ppA.level() == ppB.level())
     1017      {
     1018        if (substitute > 1)
     1019          return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB,
     1020                                  substitute));
     1021        else
     1022          return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB);
     1023      }
     1024      else
     1025      {
     1026        if (substitute > 1)
     1027          return N (reverseSubst (gcdcAcB, substitute));
     1028        else
     1029          return N (gcdcAcB);
     1030      }
     1031    }
    9051032  }
    9061033
    … …  
    10711198          ppH= GFMapDown (ppH, k);
    10721199          DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
     1200          if (compressConvexDense)
     1201            ppH= decompress (ppH, MM, V);
    10731202          if (substitute > 1)
    10741203          {
    … …  
    10841213        if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    10851214        {
     1215          if (compressConvexDense)
     1216            ppH= decompress (ppH, MM, V);
    10861217          if (substitute > 1)
    10871218          {
    … …  
    12021333    ppA= A/cA;
    12031334    ppB= B/cB;
     1335  }
     1336
     1337  int sizeNewtonPolyg;
     1338  int ** newtonPolyg= NULL;
     1339  mat_ZZ MM;
     1340  vec_ZZ V;
     1341  bool compressConvexDense= (ppA.level() == 2 && ppB.level() == 2);
     1342  if (compressConvexDense)
     1343  {
     1344    cA= content (ppA, 1);
     1345    cB= content (ppB, 1);
     1346    ppA /= cA;
     1347    ppB /= cB;
     1348    gcdcAcB *= gcd (cA, cB);
     1349    if (ppA.isUnivariate() || ppB.isUnivariate())
     1350    {
     1351      if (ppA.level() == ppB.level())
     1352      {
     1353        if (substitute > 1)
     1354          return N (reverseSubst (gcd (ppA, ppB)*gcdcAcB, substitute));
     1355        else
     1356          return N (gcd (ppA, ppB)*gcdcAcB);
     1357      }
     1358      else
     1359      {
     1360        if (substitute > 1)
     1361          return N (reverseSubst (gcdcAcB, substitute));
     1362        else
     1363          return N (gcdcAcB);
     1364      }
     1365    }
     1366
     1367    newtonPolyg= newtonPolygon (ppA,ppB, sizeNewtonPolyg);
     1368    convexDense (newtonPolyg, sizeNewtonPolyg, MM, V);
     1369
     1370    for (int i= 0; i < sizeNewtonPolyg; i++)
     1371      delete [] newtonPolyg[i];
     1372    delete [] newtonPolyg;
     1373
     1374    ppA= compress (ppA, MM, V, false);
     1375    ppB= compress (ppB, MM, V, false);
     1376    MM= inv (MM);
     1377
     1378    if (ppA.isUnivariate() && ppB.isUnivariate())
     1379    {
     1380      if (ppA.level() == ppB.level())
     1381      {
     1382        if (substitute > 1)
     1383          return N (reverseSubst (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB,
     1384                                  substitute));
     1385        else
     1386          return N (decompress (gcd (ppA, ppB), MM, V)*gcdcAcB);
     1387      }
     1388      else
     1389      {
     1390        if (substitute > 1)
     1391          return N (reverseSubst (gcdcAcB, substitute));
     1392        else
     1393          return N (gcdcAcB);
     1394      }
     1395    }
    12041396  }
    12051397
    … …  
    14231615      if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
    14241616      {
     1617        if (compressConvexDense)
     1618          ppH= decompress (ppH, MM, V);
    14251619        if (substitute > 1)
    14261620        {
Note: See TracChangeset for help on using the changeset viewer.