Changeset 7a4e77 in git


Ignore:
Timestamp:
Dec 1, 2013, 8:00:29 PM (9 years ago)
Author:
Yue Ren <ren@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '5bec8f88c9ee2573d328cf7c3aff2bcb301d2395')
Children:
528fa78d82d2bc9d49f41d3dbb87afea0e1697e2
Parents:
fa167e9991d970432d089c5d6b7094886d1ffbb7
git-author:
Yue Ren <ren@mathematik.uni-kl.de>2013-12-01 20:00:29+01:00
git-committer:
Yue Ren <ren@mathematik.uni-kl.de>2015-02-06 13:47:02+01:00
Message:
new: reduceInitially(poly &h, const poly g)
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • Singular/dyn_modules/gfanlib/tropical.cc

    rfa167e r7a4e77  
    972972  // p->iiAddCproc("","divideByGcd",FALSE,divideByGcd);
    973973  p->iiAddCproc("","pReduce",FALSE,pReduce);
     974  p->iiAddCproc("","reduceInitially0",FALSE,reduceInitially0);
     975  p->iiAddCproc("","reduceInitially1",FALSE,reduceInitially1);
    974976#endif //NDEBUG
    975977  // p->iiAddCproc("","initialReduction",FALSE,initialReduction);
  • dyn_modules/callgfanlib/initialReduction.cc

    rfa167e r7a4e77  
    6767}
    6868
     69
    6970#ifndef NDEBUG
    7071BOOLEAN pReduce(leftv res, leftv args)
     
    7778    Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
    7879    g = (poly) u->CopyD();
    79     pReduce(g,p);
     80    (void) pReduce(g,p);
    8081    p_Delete(&g,currRing);
    8182    omUpdateInfo();
    8283    Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
    8384    g = (poly) u->CopyD();
    84     pReduce(g,p);
     85    (void) pReduce(g,p);
    8586    n_Delete(&p,currRing->cf);
    8687    res->rtyp = POLY_CMD;
     
    9394
    9495
    95 
     96/***
     97 * Returns, if it exists, a pointer to the first term in g
     98 * that is divisible by (the leading monomial of) m or, if it does not exist, the NULL pointer
     99 * If g is homogeneous in x with the same degree as m,
     100 * then it returns the first term with the same monomial in x as m,
     101 * if the t-degree of the term is higher than the t-degree of m, or NULL otherwise.
     102 **/
     103static inline poly firstTermDivisibleBy(const poly g, const poly m)
     104{
     105  poly gCache = NULL;
     106  for (gCache=g; gCache; pIter(gCache))
     107    if (p_LeadmonomDivisibleBy(m,gCache,currRing)) break;
     108  return gCache;
     109}
     110
     111
     112/***
     113 * reduces h initially with respect to g,
     114 * returns NULL if h was initially reduced in the first place. if reductions have taken place,
     115 * returns a pointer to a term from which onwards changes have taken place.
     116 * assumes that h and g are in pReduced form and homogeneous in x of the same degree
     117 **/
     118poly reduceInitially(poly &h, const poly g)
     119{
     120  poly hCache=h;
     121  if (p_LeadmonomDivisibleBy(g,hCache,currRing))
     122  {
     123    number gAlpha = p_GetCoeff(g,currRing);
     124    poly hAlphaT = p_Init(currRing);
     125    p_SetCoeff(hAlphaT,n_Copy(p_GetCoeff(hCache,currRing),currRing->cf),currRing);
     126    p_SetExp(hAlphaT,1,p_GetExp(hCache,1,currRing)-p_GetExp(g,1,currRing),currRing);
     127    for (int i=2; i<=currRing->N; i++)
     128      p_SetExp(hAlphaT,i,0,currRing);
     129    p_Setm(hAlphaT,currRing); pTest(hAlphaT);
     130    h = p_Add_q(p_Mult_nn(h,gAlpha,currRing),
     131                p_Neg(p_Mult_q(p_Copy(g,currRing),hAlphaT,currRing),currRing),
     132                currRing);
     133    pTest(h);
     134    return(h);
     135  }
     136  for (; pNext(hCache); pIter(hCache))
     137    if (p_LeadmonomDivisibleBy(g,pNext(hCache),currRing)) break;
     138  if (pNext(hCache))
     139  {
     140    number gAlpha = p_GetCoeff(g,currRing);
     141    poly hAlphaT = p_Init(currRing);
     142    p_SetCoeff(hAlphaT,n_Copy(p_GetCoeff(pNext(hCache),currRing),currRing->cf),currRing);
     143    p_SetExp(hAlphaT,1,p_GetExp(pNext(hCache),1,currRing)-p_GetExp(g,1,currRing),currRing);
     144    for (int i=2; i<=currRing->N; i++)
     145      p_SetExp(hAlphaT,i,0,currRing);
     146    p_Setm(hAlphaT,currRing); pTest(hAlphaT);
     147    h = p_Add_q(p_Mult_nn(h,gAlpha,currRing),
     148                p_Neg(p_Mult_q(p_Copy(g,currRing),hAlphaT,currRing),currRing),
     149                currRing);
     150    pTest(h);
     151  }
     152  return pNext(hCache);
     153}
     154
     155
     156#ifndef NDEBUG
     157BOOLEAN reduceInitially0(leftv res, leftv args)
     158{
     159  leftv u = args;
     160  if ((u != NULL) && (u->Typ() == POLY_CMD))
     161  {
     162    leftv v = u->next;
     163    if ((v != NULL) && (v->Typ() == POLY_CMD))
     164    {
     165      poly g,h;
     166      omUpdateInfo();
     167      Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
     168      h = (poly) u->CopyD();
     169      g = (poly) v->CopyD();
     170      (void)reduceInitially(h,g);
     171      p_Delete(&h,currRing);
     172      p_Delete(&g,currRing);
     173      omUpdateInfo();
     174      Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
     175      h = (poly) u->CopyD();
     176      g = (poly) v->CopyD();
     177      (void)reduceInitially(h,g);
     178      p_Delete(&g,currRing);
     179      res->rtyp = POLY_CMD;
     180      res->data = (char*) h;
     181      return FALSE;
     182    }
     183  }
     184  return TRUE;
     185}
     186#endif //NDEBUG
     187
     188
     189static inline void sortByLeadmonom(ideal I)
     190{
     191  poly cache; int i, n=IDELEMS(I), newn;
     192  do
     193  {
     194    newn=0;
     195    for (i=1; i<n; i++)
     196    {
     197      if (pLmCmp(I->m[i-1],I->m[i])<0)
     198      {
     199        cache=I->m[i-1];
     200        I->m[i-1]=I->m[i];
     201        I->m[i]=cache;
     202        newn = i;
     203      }
     204    }
     205    n=newn;
     206  } while(n);
     207}
     208
     209
     210/***
     211 * reduces I initially with respect to itself and with respect to p-t.
     212 * assumes that I is generated by elements which are homogeneous in x of the same degree.
     213 **/
     214bool reduceInitially(ideal I, const number p)
     215{
     216  sortByLeadmonom(I); int i,j;
     217  for (i=1; i<IDELEMS(I); i++)
     218    if (pReduce(I->m[i],p)) return true;
     219
     220  /***
     221   * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
     222   **/
     223  poly cache = NULL;
     224  for (i=0; i<IDELEMS(I)-1; i++)
     225  {
     226    for (j=i+1; j<IDELEMS(I); j++)
     227    {
     228      cache = reduceInitially(I->m[j], I->m[i]);
     229      if (cache)
     230      {
     231        if(pReduce(cache,p)) return true;
     232        cache = NULL;
     233      }
     234    }
     235  }
     236
     237  /***
     238   * the second pass. removing terms divisible by lt(g_j) out of g_i for i<j
     239   **/
     240  for (i=0; i<IDELEMS(I)-1; i++)
     241  {
     242    for (j=i+1; j<IDELEMS(I); j++)
     243    {
     244      cache = reduceInitially(I->m[i], I->m[j]);
     245      if (cache)
     246      {
     247        if (pReduce(cache,p)) return true;
     248        cache = NULL;
     249      }
     250    }
     251  }
     252  return false;
     253}
     254
     255
     256#ifndef NDEBUG
     257BOOLEAN reduceInitially1(leftv res, leftv args)
     258{
     259  leftv u = args;
     260  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
     261  {
     262    leftv v = u->next;
     263    if ((v != NULL) && (v->Typ() == NUMBER_CMD))
     264    {
     265      ideal I = (ideal) u->CopyD();
     266      number p = (number) v->CopyD();
     267      omUpdateInfo();
     268      Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
     269      (void) reduceInitially(I,p);
     270      omUpdateInfo();
     271      Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
     272      n_Delete(&p,currRing->cf);
     273      res->rtyp = IDEAL_CMD;
     274      res->data = (char*) I;
     275      return FALSE;
     276    }
     277  }
     278  return TRUE;
     279}
     280#endif //NDEBUG
  • dyn_modules/callgfanlib/initialReduction.h

    rfa167e r7a4e77  
    66#ifndef N_DEBUG
    77BOOLEAN pReduce(leftv res, leftv args);
     8BOOLEAN reduceInitially0(leftv res, leftv args);
     9BOOLEAN reduceInitially1(leftv res, leftv args);
    810#endif
    911
Note: See TracChangeset for help on using the changeset viewer.