Changeset 11bcf16 in git


Ignore:
Timestamp:
Jan 19, 2002, 11:58:42 AM (22 years ago)
Author:
Olaf Bachmann <obachman@…>
Branches:
(u'spielwiese', 'd1b01e9d51ade4b46b745d3bada5c5f3696be3a8')
Children:
a9256747eae039136ca8aa9de4dabf605eb86355
Parents:
d0441d3c847efa2ea3d91182675a497f18c54425
Message:
clean up


git-svn-id: file:///usr/local/Singular/svn/trunk@5731 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/fast_maps.cc

    rd0441d r11bcf16  
    77 *  Author:  obachman (Olaf Bachmann)
    88 *  Created: 02/01
    9  *  Version: $Id: fast_maps.cc,v 1.4 2002-01-19 10:15:06 Singular Exp $
     9 *  Version: $Id: fast_maps.cc,v 1.5 2002-01-19 10:58:42 obachman Exp $
    1010 *******************************************************************/
    1111#include "mod2.h"
    … …  
    1616#include "ring.h"
    1717#include "febase.h"
     18#include "fast_maps.h"
     19
     20/*******************************************************************************
     21**
     22*F  debugging stuff
     23*/
     24void maMonomial_Out(mapoly monomial, ring src_r, ring dest_r = NULL)
     25{
     26  p_wrp(monomial->src, src_r);
     27  printf(" ref:%d", monomial->ref);
     28  if (dest_r != NULL)
     29  {
     30    printf(" dest:");
     31    p_wrp(monomial->dest, dest_r);
     32  }
     33  printf("\n");
     34  fflush(stdout);
     35}
     36
     37void maPoly_Out(mapoly mpoly, ring src_r, ring dest_r = NULL)
     38{
     39  while (mpoly != NULL)
     40  {
     41    maMonomial_Out(mpoly, src_r, dest_r);
     42    mpoly = mpoly->next;
     43  }
     44}
     45
     46
     47/*******************************************************************************
     48**
     49*F  mapolyCreate  . . . . . . . . . . . . . . .  Creates mapoly
     50*/
     51static omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s));
     52static omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s));
     53
     54mapoly maMonomial_Create(poly p, ring r_p, sBucket_pt bucket = NULL)
     55{
     56  mapoly mp = (mapoly) omAlloc0Bin(mapolyBin);
     57  mp->src = p;
     58  p->next = NULL;
     59
     60  if (bucket != NULL)
     61  {
     62    mp->coeff = (macoeff) omAlloc0Bin(macoeffBin);
     63    mp->coeff->bucket = bucket;
     64    mp->coeff->n = pGetCoeff(p);
     65  }
     66  mp->ref = 1;
     67  return mp;
     68}
     69
     70void maMonomial_Destroy(mapoly mp, ring src_r, ring dest_r = NULL)
     71{
     72  if (mp != NULL)
     73  {
     74    p_LmFree(mp->src, src_r);
     75    if (mp->coeff != NULL)
     76    {
     77      macoeff coeff, next = mp->coeff;
     78      do
     79      {
     80        coeff = next;
     81        next = coeff->next;
     82        omFreeBin(coeff, macoeffBin);
     83      }
     84      while (next != NULL);
     85      if (mp->dest != NULL)
     86      {
     87        assume(dest_r != NULL);
     88        p_Delete(&(mp->dest), dest_r);
     89      }
     90      omFreeBin(mp, mapolyBin);
     91    }
     92  }
     93}
     94
     95/*******************************************************************************
     96**
     97*F  maPoly_InsertMonomial . . . . . . . . .insertion of a monomial into mapoly
     98*/
     99mapoly maPoly_InsertMonomial(mapoly into, mapoly what, ring src_r)
     100{
     101  if (into == NULL)
     102  {
     103    into = what;
     104    return what;
     105  }
     106 
     107  mapoly iter = into;
     108  mapoly prev = NULL;
     109 
     110  Top:
     111  p_LmCmpAction(iter->src, what->src, src_r, goto Greater, goto Smaller, goto Equal);
     112 
     113  Greater:
     114  prev = iter;
     115  iter = iter->next;
     116  if (iter == NULL) goto Smaller;
     117  goto Top;
     118 
     119  Smaller:
     120  what->next = iter;
     121  if (prev != NULL)
     122    prev->next = what;
     123  return what;
     124 
     125  Equal:
     126  iter->ref += what->ref;
     127  macoeff coeff = what->coeff;
     128  if (coeff != NULL)
     129  {
     130    while (coeff->next != NULL) coeff = coeff->next;
     131    coeff->next = iter->coeff;
     132    iter->coeff = what->coeff;
     133  }
     134  p_LmFree(what->src, src_r);
     135  omFreeBinAddr(what);
     136  return iter;
     137}
     138
     139mapoly maPoly_InsertMonomial(mapoly into, poly p, ring src_r, sBucket_pt bucket = NULL)
     140{
     141  return maPoly_InsertMonomial(into, maMonomial_Create(p, src_r, bucket), src_r);
     142}
     143
     144static mapoly maPoly_InsertPoly(mapoly into, poly what, ring src_r, sBucket_pt bucket)
     145{
     146  poly next;
     147 
     148  while (what != NULL)
     149  {
     150    next = what->next;
     151    into = maPoly_InsertMonomial(into, what, src_r, bucket);
     152    what = next;
     153  }
     154  return into;
     155}
     156
     157static void maMap_InitMpoly(ideal map_id, ring map_r, ring src_r, ring dest_r,
     158                       mapoly &mp, maideal &mideal)
     159{
     160  mideal = (maideal) omAlloc0(sizeof(maideal_s));
     161  mideal->n = IDELEMS(map_id);
     162  mideal->buckets = (sBucket_pt*) omAlloc0(mideal->n*sizeof(sBucket_pt));
     163  int i;
     164  mp = NULL;
     165 
     166  for (i=0; i<mideal->n; i++)
     167  {
     168    if (map_id->m[i] != NULL)
     169    {
     170      mideal->buckets[i] = sBucketCreate(dest_r);
     171      maPoly_InsertMonomial(mp,
     172                            prShallowCopyR_NoSort(map_id->m[i], map_r, src_r),
     173                            src_r,                     
     174                            mideal->buckets[i]);
     175    }
     176  }
     177}
     178
     179#if 0
    18180
    19181/*******************************************************************************
    … …  
    51213}
    52214
    53 // returns maximal exponent if map_id is applied to pi_id
    54 static Exponent_t maGetMaxExp(ideal map_id, ring map_r, ideal pi_id, ring pi_r)
    55 {
    56   Exponent_t max=0;
     215// returns maximal monomial if map_id is applied to pi_id
     216static poly maGetMaxExpP(ideal map_id, ring map_r, ideal pi_id, ring pi_r)
     217{
    57218  poly* max_map_monomials = (poly*) omAlloc(IDELEMS(map_id)*sizeof(poly));
    58219  poly max_pi_i, max_map_i;
     220  poly max_map = p_Init(map_r);
    59221 
    60222  int i, j;
    … …  
    69231    max_map_i = maGetMaxExpP(max_map_monomials, IDELEMS(map_id), map_r,
    70232                              max_pi_i, pi_r);
    71     Exponent_t temp = p_GetMaxExp(max_map_i, map_r);
    72     if (temp> max){
    73       max=temp;
    74     }
    75 
     233    // get maximum
     234    for (j = 1; j<= map_r->N; j++)
     235    {
     236      if (p_GetExp(max_map, j, map_r) < p_GetExp(max_map_i, j, map_r))
     237        p_SetExp(max_map, j, p_GetExp(max_map_i, j, map_r), map_r);
     238    }
    76239    p_LmFree(max_pi_i, pi_r);
    77240    p_LmFree(max_map_i, map_r);
    78241  }
     242  return max_map;
     243}
     244
     245// returns maximal exponent if map_id is applied to pi_id
     246static Exponent_t maGetMaxExp(ideal map_id, ring map_r, ideal pi_id, ring pi_r)
     247{
     248  poly p = maGetMaxExpP(map_id, map_r, pi_id, pi_r);
     249  Exponent_t max = p_GetMaxExp(p, map_r);
     250  p_LmFree(p, map_r);
    79251  return max;
    80252}
    81 
    82253
    83254// construct ring/map ideal  in/with which we perform computations
    … …  
    175346}
    176347
    177 /*******************************************************************************
    178 **
    179 *S  mapoly, macoeff . . . . . . . . . . . . definition of structs/classes
    180 */
    181 class macoeff_s;
    182 class mapoly_s;
    183 class maideal_s;
    184 typedef class mapoly_s*  mapoly;
    185 typedef class macoeff_s* macoeff;
    186 typedef class maideal_s* maideal;
    187 
    188 class mapoly_s
    189 {
    190 public:
    191   mapoly    next;
    192   int       factors;    // -1: not set, 0: constant, 1, 2, 3
    193   poly      src;        // monomial from WeightedRing
    194   poly      dest;       // poly in CompRing
    195   mapoly    f1, f2;     // if f1 != NULL && f2 != NULL then dest = f1*f2
    196   int       ref;        // use to catch last usage to save last copy
    197   macoeff   coeff;      // list of coeffs to use
    198 };
    199 
    200 class macoeff_s
    201 {
    202 public:
    203   macoeff       next;
    204   number        n;
    205   sBucket_pt    bucket;
    206 };
    207 
    208 class maideal_s
    209 {
    210 public:
    211   int n;
    212   sBucket_pt* buckets;
    213 };
    214 /*******************************************************************************
    215 **
    216 *F  mapolyCreate  . . . . . . . . . . . . . . .  Creates mapoly
    217 */
    218 static omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s));
    219 static omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s));
    220 mapoly mapolyCreate(poly p, sBucket_pt bucket)
    221 {
    222   long cost, factors;
    223   maGetCostFactors(p, r_p, cost, factors);
    224 
    225   // factors < 0, i.e. monomial maps to zero
    226   if (factors < 0)
    227     return NULL;
    228 
    229   if (cost
    230   mapoly mp = (mapoly) omAlloc0Bin(mapolyBin);
    231   mp->src = p;
    232   maGetCostFactors(src, mp->cost, mp->factors);
    233   if (mp->factors == -1)
    234   {
    235    
    236  
    237   if (bucket != NULL)
    238   {
    239     mp->coeff = (macoeff) omAlloc0Bin(macoeffBin);
    240     mp->coeff->bucket = bucket;
    241     mp->coeff->n = pGetCoeff(p);
    242   }
    243   else
    244   {
    245     what->ref = 1;
    246   }
    247   return mp;
    248 }
    249 
    250 /*******************************************************************************
    251 **
    252 *F  mapInsert . . . . . . . . . . . . . . .insertion of monomial/poly into mpoly
    253 */
    254 static int maGetFactors(poly p, ring r)
    255 {
    256   int fac = 0;
    257  
    258   for (i=1; i<=r->N;i++)
    259   {
    260     fac += p_GetExp(p, i, r);
    261     if (fac >= 3)
    262       return fac;
    263   }
    264 }
    265 
    266 static mapoly mapInsertMonomial(mapoly &into, mapoly what, ring w_r)
    267 {
    268   if (into == NULL)
    269   {
    270     into = what;
    271     return what;
    272   }
    273  
    274   mapoly iter = into;
    275   mapoly prev = NULL;
    276  
    277   Top:
    278   p_LmCmpAction(iter->src, what->src, w_r,goto Greater, goto Equal, goto Smaller);
    279  
    280   Greater:
    281   prev = iter;
    282   iter = iter->next;
    283   if (iter == NULL) goto Smaller;
    284   goto Top;
    285  
    286   Smaller:
    287   what->next = iter;
    288   if (what->factors == -1)
    289     what->factors = maGetFactors(what->src, w_r);
    290   if (prev != NULL)
    291     prev->next = what;
    292   return what;
    293  
    294   Equal:
    295   iter->ref += what->ref;
    296   macoeff coeff = what->coeff;
    297   if (coeff != NULL)
    298   {
    299     while (coeff->next != NULL) coeff = coeff->next;
    300     coeff->next = iter->coeff;
    301     iter->coeff = what->coeff;
    302   }
    303   p_LmFree(what->src, w_r);
    304   omFreeBinAddr(what);
    305   return iter;
    306 }
    307 
    308 static mapoly mapInsertMonomial(mapoly &into, poly what, ring w_r,
    309                                 sBucket_pt bucket)
    310 {
    311   return mapInsertMonomial(into, mapolyCreate(what, bucket), w_r);
    312 }
    313 
    314 static mapoly mapInsertPoly(mapoly &into, poly what, ring w_r, sBucket_pt bucket)
    315 {
    316   poly next;
    317  
    318   while (what != NULL)
    319   {
    320     next = what->next;
    321     into = mapInsertMonomial(into, what, w_r, bucket);
    322     what = next;
    323   }
    324   return into;
    325 }
    326 
    327 /*******************************************************************************
    328 **
    329 *F  maMap_2_maPoly  . . . . . . . . . . . construnct maideal and mapoly from map
    330 */
    331 static void maMap_2_maPoly(ideal theMap, ring map_r, ring weight_r, ring comp_r,
     348
     349
     350
     351
     352static void maMap_2_maPoly(ideal source_id, ring source_r, ring weight_r, ring comp_r,
    332353                           mapoly &mp, maideal &mideal)
    333354{
    334355  mideal = (maideal) omAlloc0(sizeof(maideal_s));
    335   mideal->n = IDELEMS(theMap);
     356  mideal->n = IDELEMS(source_id);
    336357  mideal->buckets = (sBucket_pt*) omAlloc0(mideal->n*sizeof(sBucket_pt));
    337358  int i;
    … …  
    340361  for (i=0; i<mideal->n; i++)
    341362  {
    342     if (theMap->m[i] != NULL)
     363    if (source_id->m[i] != NULL)
    343364    {
    344365      mideal->buckets[i] = sBucketCreate(comp_r);
    345366      mapInsertPoly(mp,
    346                     prShallowCopyR_NoSort(theMap->m[i], map_r, weight_r),
     367                    prShallowCopyR_NoSort(source_id->m[i], source_r, weight_r),
    347368                    weight_r,                     
    348369                    mideal->buckets[i]);
    349370    }
    350   }
    351 }
     371    maPoly_Out(mp, source_r);
     372  }
     373}
     374
     375
     376
     377
    352378
    353379static mapoly maFindBestggT(mapoly mp, mapoly in, poly ggT, poly fp, poly fq)
    … …  
    363389  {
    364390    poly q1, q2, q;
    365     q = maEggT(p, in->src, q1, q2);
     391//    q = maEggT(p, in->src, q1, q2);
    366392    if (q != NULL)
    367393    {
    … …  
    429455  return res;
    430456}
    431    
    432    
    433 #if 0
    434457/*******************************************************************************
    435458**
    … …  
    466489  return id;
    467490}
     491
    468492#endif
    469493
    470 
     494void map_main(ideal map_id, ring map_r, ideal image_id, ring image_r)
     495{
     496 
     497}
     498
     499   
     500   
     501                   
     502 
     503   
     504
     505
     506
     507
     508
     509
     510
     511
     512 
     513 
     514 
     515 
     516
     517 
     518     
Note: See TracChangeset for help on using the changeset viewer.