Macros | Functions | Variables
fast_maps.cc File Reference
#include <kernel/mod2.h>
#include <omalloc/omalloc.h>
#include <misc/options.h>
#include <polys/monomials/p_polys.h>
#include <polys/prCopy.h>
#include <kernel/ideals.h>
#include <polys/monomials/ring.h>
#include <polys/sbuckets.h>
#include <kernel/maps/fast_maps.h>

Go to the source code of this file.

Macros

#define HAVE_DEST_R   1
 
#define HAVE_SRC_R   1
 
#define HAVE_MAP_OPTIMIZE   1
 

Functions

static poly maGetMaxExpP (poly *max_map_monomials, int n_max_map_monomials, ring map_r, poly pi_m, ring pi_r)
 
static unsigned long maGetMaxExp (ideal pi_id, ring pi_r, ideal map_id, ring map_r)
 
mapoly maMonomial_Create (poly p, ring, sBucket_pt bucket)
 
void maMonomial_Destroy (mapoly mp, ring src_r, ring dest_r)
 
mapoly maPoly_InsertMonomial (mapoly &into, mapoly what, ring src_r)
 
mapoly maPoly_InsertMonomial (mapoly &into, poly p, ring src_r, sBucket_pt bucket)
 
static void maPoly_InsertPoly (mapoly &into, poly what, ring src_r, sBucket_pt bucket)
 
void maMap_CreatePolyIdeal (ideal map_id, ring map_r, ring src_r, ring dest_r, mapoly &mp, maideal &mideal)
 
void maMap_CreateRings (ideal map_id, ring map_r, ideal image_id, ring image_r, ring &src_r, ring &dest_r, BOOLEAN &simple)
 
static void maMap_KillRings (ring map_r, ring image_r, ring src_r, ring dest_r)
 
ideal maIdeal_2_Ideal (maideal m_id, ring)
 
void maPoly_GetLength (mapoly mp, int &length)
 
ideal fast_map_common_subexp (const ideal map_id, const ring map_r, const ideal image_id, const ring image_r)
 
static int maPoly_Substitute (macoeff c, poly p, ring dest_r)
 
static poly maPoly_EvalMon (poly src, ring src_r, poly *dest_id, ring dest_r)
 
void maPoly_Eval (mapoly root, ring src_r, ideal dest_id, ring dest_r, int total_cost)
 
static poly maEggT (const poly m1, const poly m2, poly &q1, poly &q2, const ring r)
 
static mapoly maFindBestggT (mapoly mp, mapoly &choice, mapoly &fp, mapoly &fq, const ring r)
 
void maPoly_Optimize (mapoly mpoly, ring src_r)
 

Variables

static omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s))
 
static omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s))
 

Macro Definition Documentation

◆ HAVE_DEST_R

#define HAVE_DEST_R   1

Definition at line 24 of file fast_maps.cc.

◆ HAVE_MAP_OPTIMIZE

#define HAVE_MAP_OPTIMIZE   1

Definition at line 28 of file fast_maps.cc.

◆ HAVE_SRC_R

#define HAVE_SRC_R   1

Definition at line 26 of file fast_maps.cc.

Function Documentation

◆ fast_map_common_subexp()

ideal fast_map_common_subexp ( const ideal  map_id,
const ring  map_r,
const ideal  image_id,
const ring  image_r 
)

Definition at line 354 of file fast_maps.cc.

355 {
356  ring src_r, dest_r;
357  ideal dest_id/*, res_id*/;
358  int length = 0;
359  BOOLEAN no_sort;
360 
361  // construct rings we work in:
362  // src_r: Wp with Weights set to length of poly in image_id
363  // dest_r: Simple ring without degree ordering and short exponents
364  maMap_CreateRings(map_id, map_r, image_id, image_r, src_r, dest_r, no_sort);
365 
366  // construct dest_id
367  if (dest_r != image_r)
368  {
369  dest_id = idrShallowCopyR(image_id, image_r, dest_r);
370  }
371  else
372  dest_id = image_id;
373 
374  // construct mpoly and mideal
375  mapoly mp;
376  maideal mideal;
377  maMap_CreatePolyIdeal(map_id, map_r, src_r, dest_r, mp, mideal);
378 
379  if (TEST_OPT_PROT)
380  {
381  maPoly_GetLength(mp, length);
382  Print("map[%ld:%d]{%d:", dest_r->bitmask, dest_r->ExpL_Size, length);
383  }
384 
385  // do the optimization step
386 #if HAVE_MAP_OPTIMIZE > 0
387  if (mp!=NULL) maPoly_Optimize(mp, src_r);
388 #endif
389  if (TEST_OPT_PROT)
390  {
391  maPoly_GetLength(mp, length);
392  Print("%d}", length);
393  }
394 
395  // do the actual evaluation
396  maPoly_Eval(mp, src_r, dest_id, dest_r, length);
397  if (TEST_OPT_PROT) PrintS(".");
398 
399  // collect the results back into an ideal
400  ideal res_dest_id = maIdeal_2_Ideal(mideal, dest_r);
401  if (TEST_OPT_PROT) PrintS(".");
402 
403  // convert result back to image_r
404  ideal res_image_id;
405  if (dest_r != image_r)
406  {
407  //if (no_sort) see Old/m134si.tst
408  // res_image_id = idrShallowCopyR_NoSort(res_dest_id, dest_r, image_r);
409  //else
410  res_image_id = idrShallowCopyR(res_dest_id, dest_r, image_r);
411  id_ShallowDelete(&res_dest_id, dest_r);
412  id_ShallowDelete(&dest_id,dest_r);
413  }
414  else
415  res_image_id = res_dest_id;
416 
417  if (TEST_OPT_PROT) PrintS(".");
418 
419  // clean-up the rings
420  maMap_KillRings(map_r, image_r, src_r, dest_r);
421 
422  if (TEST_OPT_PROT)
423  PrintLn();
424 
425  idTest(res_image_id);
426  return res_image_id;
427 }
void maPoly_Optimize(mapoly mpoly, ring src_r)
Definition: fast_maps.cc:710
void maMap_CreateRings(ideal map_id, ring map_r, ideal image_id, ring image_r, ring &src_r, ring &dest_r, BOOLEAN &simple)
Definition: fast_maps.cc:281
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
class mapoly_s * mapoly
Definition: fast_maps.h:21
#define TEST_OPT_PROT
Definition: options.h:98
void id_ShallowDelete(ideal *h, ring r)
Shallowdeletes an ideal/matrix.
ideal idrShallowCopyR(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:221
class maideal_s * maideal
Definition: fast_maps.h:23
ideal maIdeal_2_Ideal(maideal m_id, ring)
Definition: fast_maps.cc:323
void maPoly_GetLength(mapoly mp, int &length)
Definition: fast_maps.cc:338
void PrintS(const char *s)
Definition: reporter.cc:284
static void maMap_KillRings(ring map_r, ring image_r, ring src_r, ring dest_r)
Definition: fast_maps.cc:310
#define NULL
Definition: omList.c:10
void maPoly_Eval(mapoly root, ring src_r, ideal dest_id, ring dest_r, int total_cost)
Definition: fast_maps.cc:495
void maMap_CreatePolyIdeal(ideal map_id, ring map_r, ring src_r, ring dest_r, mapoly &mp, maideal &mideal)
Definition: fast_maps.cc:255
int BOOLEAN
Definition: auxiliary.h:85
#define idTest(id)
Definition: ideals.h:47

◆ maEggT()

static poly maEggT ( const poly  m1,
const poly  m2,
poly q1,
poly q2,
const ring  r 
)
static

Definition at line 586 of file fast_maps.cc.

587 {
588 
589  int i;
590  int dg = 0;
591  poly ggt = p_Init(r);
592  q1 = p_Init(r);
593  q2 = p_Init(r);
594 
595  for (i=1;i<=r->N;i++)
596  {
597  unsigned long e1 = p_GetExp(m1, i, r);
598  unsigned long e2 = p_GetExp(m2, i, r);
599  if (e1 > 0 && e2 > 0)
600  {
601  unsigned long em = (e1 > e2 ? e2 : e1);
602  dg += em;
603  p_SetExp(ggt, i, em, r);
604  p_SetExp(q1, i, e1 - em, r);
605  p_SetExp(q2, i, e2 - em, r);
606  }
607  else
608  {
609  p_SetExp(q1, i, e1, r);
610  p_SetExp(q2, i, e2, r);
611  }
612  }
613  if (dg>1)
614  {
615  p_Setm(ggt, r);
616  p_Setm(q1, r);
617  p_Setm(q2, r);
618  }
619  else
620  {
621  p_LmFree(ggt, r);
622  p_LmFree(q1, r);
623  p_LmFree(q2, r);
624  ggt = NULL;
625  }
626  return ggt;
627 }
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
const ring r
Definition: syzextra.cc:208
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
int i
Definition: cfEzgcd.cc:123
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
#define NULL
Definition: omList.c:10
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
polyrec * poly
Definition: hilb.h:10
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243

◆ maFindBestggT()

static mapoly maFindBestggT ( mapoly  mp,
mapoly choice,
mapoly fp,
mapoly fq,
const ring  r 
)
static

Definition at line 635 of file fast_maps.cc.

636 {
637  int ggt_deg = 0;
638  poly p = mp->src;
639  mapoly iter = choice;
640  poly ggT = NULL;
641  fp = NULL;
642  fq = NULL;
643  poly fp_p=NULL;
644  poly fq_p=NULL;
645  choice=NULL;
646  while ((iter != NULL) && (p_Deg(iter->src, r) > ggt_deg))
647  {
648  // maMonomial_Out(iter, r, NULL);
649  poly q1, q2, q;
650 
651  q = maEggT(p, iter->src, q1, q2,r);
652  if (q != NULL)
653  {
654  int tmp_deg;
655  assume((q1!=NULL)&&(q2!=NULL));
656  if ((tmp_deg=p_Deg(q,r)) > ggt_deg)
657  {
658  choice=iter;
659  if (ggT != NULL)
660  {
661  p_LmFree(ggT, r);
662  p_LmFree(fp_p, r);
663  p_LmFree(fq_p, r);
664  }
665  ggt_deg = tmp_deg ; /*p_Deg(q, r);*/
666  ggT = q;
667  fp_p = q1;
668  fq_p = q2;
669  }
670  else
671  {
672  p_LmFree(q, r);
673  p_LmFree(q1, r);
674  p_LmFree(q2, r);
675  }
676  }
677  iter=iter->next;
678  }
679  if(ggT!=NULL)
680  {
681  int dq =p_Totaldegree(fq_p,r);
682  if (dq!=0)
683  {
684  fq=maPoly_InsertMonomial(mp, fq_p, r, NULL);
685  fp=maPoly_InsertMonomial(mp, fp_p, r, NULL);
686  return maPoly_InsertMonomial(mp, ggT, r, NULL);
687  }
688  else
689  {
690  fq=NULL;
691  p_LmFree(fq_p, r);
692  p_LmFree(ggT, r);
693  fp=maPoly_InsertMonomial(mp, fp_p, r, NULL);
694  choice->ref++;
695  return choice;
696  }
697  }
698  else
699  {
700  return NULL;
701  }
702 }
CanonicalForm fp
Definition: cfModGcd.cc:4043
class mapoly_s * mapoly
Definition: fast_maps.h:21
return P p
Definition: myNF.cc:203
CFFListIterator iter
Definition: facAbsBiFact.cc:54
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1430
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:588
const ring r
Definition: syzextra.cc:208
static poly maEggT(const poly m1, const poly m2, poly &q1, poly &q2, const ring r)
Definition: fast_maps.cc:586
#define assume(x)
Definition: mod2.h:394
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
mapoly maPoly_InsertMonomial(mapoly &into, mapoly what, ring src_r)
Definition: fast_maps.cc:184

◆ maGetMaxExp()

static unsigned long maGetMaxExp ( ideal  pi_id,
ring  pi_r,
ideal  map_id,
ring  map_r 
)
static

Definition at line 64 of file fast_maps.cc.

65 {
66  unsigned long max=0;
67  poly* max_map_monomials = (poly*) omAlloc(IDELEMS(map_id)*sizeof(poly));
68  poly max_pi_i, max_map_i;
69 
70  int i;
71  for (i=0; i<IDELEMS(map_id); i++)
72  {
73  max_map_monomials[i] = p_GetMaxExpP(map_id->m[i], map_r);
74  }
75 
76  for (i=0; i<IDELEMS(pi_id); i++)
77  {
78  max_pi_i = p_GetMaxExpP(pi_id->m[i], pi_r);
79  max_map_i = maGetMaxExpP(max_map_monomials, IDELEMS(map_id), map_r,
80  max_pi_i, pi_r);
81  unsigned long temp = p_GetMaxExp(max_map_i, map_r);
82  if (temp > max){ max=temp; }
83 
84  p_LmFree(max_pi_i, pi_r);
85  p_LmFree(max_map_i, map_r);
86  }
87  for (i=0; i<IDELEMS(map_id); i++)
88  {
89  p_Delete(&max_map_monomials[i], map_r);
90  }
91  omFreeSize(max_map_monomials,IDELEMS(map_id)*sizeof(poly));
92 
93  return max;
94 }
static poly maGetMaxExpP(poly *max_map_monomials, int n_max_map_monomials, ring map_r, poly pi_m, ring pi_r)
Definition: fast_maps.cc:35
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
static unsigned long p_GetMaxExp(const unsigned long l, const ring r)
Definition: p_polys.h:742
#define omAlloc(size)
Definition: omAllocDecl.h:210
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
static int max(int a, int b)
Definition: fast_mult.cc:264
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
polyrec * poly
Definition: hilb.h:10
poly p_GetMaxExpP(poly p, const ring r)
return monomial r such that GetExp(r,i) is maximum of all monomials in p; coeff == 0...
Definition: p_polys.cc:1139

◆ maGetMaxExpP()

static poly maGetMaxExpP ( poly max_map_monomials,
int  n_max_map_monomials,
ring  map_r,
poly  pi_m,
ring  pi_r 
)
static

Definition at line 35 of file fast_maps.cc.

38 {
39  int n = si_min(pi_r->N, n_max_map_monomials);
40  int i, j;
41  unsigned long e_i, e_j;
42  poly m_i=NULL;
43  poly map_j = p_Init(map_r);
44 
45  for (i=1; i <= n; i++)
46  {
47  e_i = p_GetExp(pi_m, i, pi_r);
48  if (e_i==0) e_i=1;
49  m_i = max_map_monomials[i-1];
50  if (m_i != NULL && ! p_IsConstantComp(m_i, map_r))
51  {
52  for (j = 1; j<= map_r->N; j++)
53  {
54  e_j = p_GetExp(m_i, j, map_r);
55  if (e_j == 0) e_j=1;
56  p_AddExp(map_j, j, e_j*e_i, map_r);
57  }
58  }
59  }
60  return map_j;
61 }
static int si_min(const int a, const int b)
Definition: auxiliary.h:121
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
static BOOLEAN p_IsConstantComp(const poly p, const ring r)
Definition: p_polys.h:1870
#define NULL
Definition: omList.c:10
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:601
polyrec * poly
Definition: hilb.h:10
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243

◆ maIdeal_2_Ideal()

ideal maIdeal_2_Ideal ( maideal  m_id,
ring   
)

Definition at line 323 of file fast_maps.cc.

324 {
325  ideal res = idInit(m_id->n, 1);
326  int l;
327 
328  for (int i= 0; i < m_id->n; i++)
329  {
330  if (m_id->buckets[i]!=NULL)
331  sBucketDestroyAdd(m_id->buckets[i], &(res->m[i]), &l);
332  }
333  omFreeSize(m_id->buckets,m_id->n*sizeof(sBucket_pt));
334  omFree(m_id);
335  return res;
336 }
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
void sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.h:72
poly res
Definition: myNF.cc:322
#define omFree(addr)
Definition: omAllocDecl.h:261
int i
Definition: cfEzgcd.cc:123
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
#define NULL
Definition: omList.c:10
int l
Definition: cfEzgcd.cc:94

◆ maMap_CreatePolyIdeal()

void maMap_CreatePolyIdeal ( ideal  map_id,
ring  map_r,
ring  src_r,
ring  dest_r,
mapoly mp,
maideal mideal 
)

Definition at line 255 of file fast_maps.cc.

257 {
258  mideal = (maideal) omAlloc0(sizeof(maideal_s));
259  mideal->n = IDELEMS(map_id);
260  mideal->buckets = (sBucket_pt*) omAlloc0(mideal->n*sizeof(sBucket_pt));
261  int i;
262  mp = NULL;
263 
264  for (i=0; i<mideal->n; i++)
265  {
266  if (map_id->m[i] != NULL)
267  {
268  mideal->buckets[i] = sBucketCreate(dest_r);
270 #ifdef PDEBUG
271  prShallowCopyR(map_id->m[i], map_r, src_r),
272 #else
273  prShallowCopyR_NoSort(map_id->m[i], map_r, src_r),
274 #endif
275  src_r,
276  mideal->buckets[i]);
277  }
278  }
279 }
static void maPoly_InsertPoly(mapoly &into, poly what, ring src_r, sBucket_pt bucket)
Definition: fast_maps.cc:238
class maideal_s * maideal
Definition: fast_maps.h:23
poly prShallowCopyR_NoSort(poly p, ring r, ring dest_r)
Definition: prCopy.cc:113
#define PDEBUG
Definition: auxiliary.h:169
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
#define NULL
Definition: omList.c:10
poly prShallowCopyR(poly p, ring r, ring dest_r)
Definition: prCopy.cc:118
#define omAlloc0(size)
Definition: omAllocDecl.h:211

◆ maMap_CreateRings()

void maMap_CreateRings ( ideal  map_id,
ring  map_r,
ideal  image_id,
ring  image_r,
ring &  src_r,
ring &  dest_r,
BOOLEAN simple 
)

Definition at line 281 of file fast_maps.cc.

284 {
285 #if HAVE_SRC_R > 0
286  int* weights = (int*) omAlloc0(map_r->N*sizeof(int));
287  int i;
288  int n = si_min(map_r->N, IDELEMS(image_id));
289 
290  for (i=0; i<n; i++)
291  {
292  weights[i] = pLength(image_id->m[i])+1;
293  }
294  src_r = rModifyRing_Wp(map_r, weights);
295 #else
296  src_r = map_r;
297 #endif
298 
299 #if HAVE_DEST_R > 0
300  unsigned long maxExp = maGetMaxExp(map_id, map_r, image_id, image_r);
301  if (maxExp <= 1) maxExp = 2;
302  else if (maxExp > (unsigned long) image_r->bitmask)
303  maxExp = (unsigned long) image_r->bitmask;
304  dest_r = rModifyRing_Simple(image_r, TRUE, TRUE, maxExp, simple);
305 #else
306  dest_r = image_r;
307 #endif
308 }
static int si_min(const int a, const int b)
Definition: auxiliary.h:121
ring rModifyRing_Wp(ring r, int *weights)
construct Wp, C ring
Definition: ring.cc:2853
#define TRUE
Definition: auxiliary.h:98
static unsigned long maGetMaxExp(ideal pi_id, ring pi_r, ideal map_id, ring map_r)
Definition: fast_maps.cc:64
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define IDELEMS(i)
Definition: simpleideals.h:24
ring rModifyRing_Simple(ring r, BOOLEAN ommit_degree, BOOLEAN ommit_comp, unsigned long exp_limit, BOOLEAN &simple)
Definition: ring.cc:2901
#define omAlloc0(size)
Definition: omAllocDecl.h:211

◆ maMap_KillRings()

static void maMap_KillRings ( ring  map_r,
ring  image_r,
ring  src_r,
ring  dest_r 
)
static

Definition at line 310 of file fast_maps.cc.

311 {
312  if (map_r != src_r)
313  rKillModified_Wp_Ring(src_r);
314  if (image_r != dest_r)
315  rKillModifiedRing_Simple(dest_r);
316 }
void rKillModified_Wp_Ring(ring r)
Definition: ring.cc:2982
void rKillModifiedRing_Simple(ring r)
Definition: ring.cc:2966

◆ maMonomial_Create()

mapoly maMonomial_Create ( poly  p,
ring  ,
sBucket_pt  bucket 
)

Definition at line 138 of file fast_maps.cc.

139 {
141  //p_wrp(p,r_p);printf(" (%x) created\n",mp);
142  mp->src = p;
143  p->next = NULL;
144 
145  if (bucket != NULL)
146  {
147  mp->coeff = (macoeff) omAlloc0Bin(macoeffBin);
148  mp->coeff->bucket = bucket;
149  mp->coeff->n = pGetCoeff(p);
150  }
151  mp->ref = 1;
152  return mp;
153 }
class mapoly_s * mapoly
Definition: fast_maps.h:21
static omBin macoeffBin
Definition: fast_maps.cc:136
return P p
Definition: myNF.cc:203
static omBin mapolyBin
Definition: fast_maps.cc:135
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
class macoeff_s * macoeff
Definition: fast_maps.h:22
P bucket
Definition: myNF.cc:79
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define NULL
Definition: omList.c:10

◆ maMonomial_Destroy()

void maMonomial_Destroy ( mapoly  mp,
ring  src_r,
ring  dest_r 
)

Definition at line 155 of file fast_maps.cc.

156 {
157  if (mp != NULL)
158  {
159  p_LmFree(mp->src, src_r);
160  if (mp->coeff != NULL)
161  {
162  macoeff coeff, next = mp->coeff;
163  do
164  {
165  coeff = next;
166  next = coeff->next;
167  omFreeBin(coeff, macoeffBin);
168  }
169  while (next != NULL);
170  if (mp->dest != NULL)
171  {
172  assume(dest_r != NULL);
173  p_Delete(&(mp->dest), dest_r);
174  }
175  }
176  }
177  omFreeBin(mp, mapolyBin);
178 }
static omBin macoeffBin
Definition: fast_maps.cc:136
static omBin mapolyBin
Definition: fast_maps.cc:135
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
#define assume(x)
Definition: mod2.h:394
class macoeff_s * macoeff
Definition: fast_maps.h:22
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define NULL
Definition: omList.c:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
ListNode * next
Definition: janet.h:31

◆ maPoly_Eval()

void maPoly_Eval ( mapoly  root,
ring  src_r,
ideal  dest_id,
ring  dest_r,
int  total_cost 
)

Definition at line 495 of file fast_maps.cc.

496 {
497  // invert the list rooted at root:
498  if ((root!=NULL) && (root->next!=NULL))
499  {
500  mapoly q=root->next;
501  mapoly qn;
502  root->next=NULL;
503  do
504  {
505  qn=q->next;
506  q->next=root;
507  root=q;
508  q=qn;
509  }
510  while (qn !=NULL);
511  }
512 
513  total_cost /= 10;
514  int next_print_cost = total_cost;
515 
516  // the evaluation -----------------------------------------
517  mapoly p=root;
518  int cost = 0;
519 
520  while (p!=NULL)
521  {
522  // look at each mapoly: compute its value in ->dest
523  assume (p->dest==NULL);
524  {
525  if ((p->f1!=NULL)&&(p->f2!=NULL))
526  {
527  poly f1=p->f1->dest;
528  poly f2=p->f2->dest;
529  if (p->f1->ref>0) f1=p_Copy(f1,dest_r);
530  else
531  {
532  // we own p->f1->dest now (in f1)
533  p->f1->dest=NULL;
534  }
535  if (p->f2->ref>0) f2=p_Copy(f2,dest_r);
536  else
537  {
538  // we own p->f2->dest now (in f2)
539  p->f2->dest=NULL;
540  }
541  maMonomial_Free(p->f1,src_r, dest_r);
542  maMonomial_Free(p->f2,src_r, dest_r);
543  p->dest=p_Mult_q(f1,f2,dest_r);
544  } /* factors : 2 */
545  else
546  {
547  assume((p->f1==NULL) && (p->f2==NULL));
548  // no factorization provided, use the classical method:
549  p->dest=maPoly_EvalMon(p->src,src_r,dest_id->m,dest_r);
550  }
551  } /* p->dest==NULL */
552  // substitute the monomial: go through macoeff
553  p->ref -= maPoly_Substitute(p->coeff, p->dest, dest_r);
554  //printf("subst done\n");
555  if (total_cost)
556  {
558  cost++;
559  if (cost > next_print_cost)
560  {
561  PrintS("-");
562  next_print_cost += total_cost;
563  }
564  }
565 
566  mapoly pp=p;
567  p=p->next;
568  //p_wrp(pp->src, src_r);
569  if (pp->ref<=0)
570  {
571  //printf(" (%x) killed\n",pp);
572  maMonomial_Destroy(pp, src_r, dest_r);
573  }
574  //else
575  // printf(" (%x) not killed, ref=%d\n",pp,pp->ref);
576  }
577 }
class mapoly_s * mapoly
Definition: fast_maps.h:21
#define TEST_OPT_PROT
Definition: options.h:98
return P p
Definition: myNF.cc:203
static int maPoly_Substitute(macoeff c, poly p, ring dest_r)
Definition: fast_maps.cc:436
void maMonomial_Destroy(mapoly mp, ring src_r, ring dest_r)
Definition: fast_maps.cc:155
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
poly pp
Definition: myNF.cc:296
static poly maPoly_EvalMon(poly src, ring src_r, poly *dest_id, ring dest_r)
Definition: fast_maps.cc:456
#define assume(x)
Definition: mod2.h:394
void PrintS(const char *s)
Definition: reporter.cc:284
#define NULL
Definition: omList.c:10
mapoly maMonomial_Free(mapoly monomial, ring src_r, ring dest_r=NULL)
Definition: fast_maps.h:67
polyrec * poly
Definition: hilb.h:10
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020

◆ maPoly_EvalMon()

static poly maPoly_EvalMon ( poly  src,
ring  src_r,
poly dest_id,
ring  dest_r 
)
static

Definition at line 456 of file fast_maps.cc.

457 {
458  int i;
459  int e;
460  poly p=NULL;
461  poly pp;
462  BOOLEAN is_const=TRUE; // to check for zero-div in p_Mult_q
463  for(i=1;i<=src_r->N;i++)
464  {
465  e=p_GetExp(src,i,src_r);
466  if (e>0)
467  {
468  is_const=FALSE;
469  pp=dest_id[i-1];
470  if (pp==NULL)
471  {
472  p_Delete(&p,dest_r);
473  return NULL;
474  }
475  if (/*(*/ p==NULL /*)*/) /* && (e>0)*/
476  {
477  p=p_Copy(pp /*dest_id[i-1]*/,dest_r);
478  e--;
479  }
480  while (e>0)
481  {
482  p=p_Mult_q(p,p_Copy(pp /*dest_id[i-1]*/,dest_r),dest_r);
483  e--;
484  }
485  }
486  }
487  if (is_const)
488  {
489  assume(p==NULL);
490  p=p_ISet(1,dest_r);
491  }
492  return p;
493 }
#define FALSE
Definition: auxiliary.h:94
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:98
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
poly pp
Definition: myNF.cc:296
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
#define assume(x)
Definition: mod2.h:394
int i
Definition: cfEzgcd.cc:123
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
int BOOLEAN
Definition: auxiliary.h:85
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1298
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020

◆ maPoly_GetLength()

void maPoly_GetLength ( mapoly  mp,
int &  length 
)

Definition at line 338 of file fast_maps.cc.

339 {
340  length = 0;
341  while (mp != NULL)
342  {
343  length++;
344  mp = mp->next;
345  }
346 }
#define NULL
Definition: omList.c:10

◆ maPoly_InsertMonomial() [1/2]

mapoly maPoly_InsertMonomial ( mapoly into,
mapoly  what,
ring  src_r 
)

Definition at line 184 of file fast_maps.cc.

185 {
186  if (into == NULL)
187  {
188  into = what;
189  return what;
190  }
191 
192  mapoly iter = into;
193  mapoly prev = NULL;
194 
195  Top:
196  p_LmCmpAction(iter->src, what->src, src_r, goto Equal, goto Greater, goto Smaller);
197 
198  Greater:
199  if (iter->next == NULL)
200  {
201  iter->next = what;
202  return what;
203  }
204  prev = iter;
205  iter = iter->next;
206  goto Top;
207 
208  Smaller:
209  if (prev == NULL)
210  {
211  into = what;
212  what->next = iter;
213  return what;
214  }
215  prev->next = what;
216  what->next = iter;
217  return what;
218 
219  Equal:
220  iter->ref += what->ref;
221  macoeff coeff = what->coeff;
222  if (coeff != NULL)
223  {
224  while (coeff->next != NULL) coeff = coeff->next;
225  coeff->next = iter->coeff;
226  iter->coeff = what->coeff;
227  what->coeff = NULL;
228  }
229  maMonomial_Free(what, src_r);
230  return iter;
231 }
class mapoly_s * mapoly
Definition: fast_maps.h:21
static BOOLEAN Equal(number a, number b, const coeffs r)
Definition: flintcf_Q.cc:351
CFFListIterator iter
Definition: facAbsBiFact.cc:54
class macoeff_s * macoeff
Definition: fast_maps.h:22
static bool Greater(mono_type m1, mono_type m2)
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition: p_polys.h:1607
#define NULL
Definition: omList.c:10
mapoly maMonomial_Free(mapoly monomial, ring src_r, ring dest_r=NULL)
Definition: fast_maps.h:67

◆ maPoly_InsertMonomial() [2/2]

mapoly maPoly_InsertMonomial ( mapoly into,
poly  p,
ring  src_r,
sBucket_pt  bucket 
)

Definition at line 233 of file fast_maps.cc.

234 {
235  return maPoly_InsertMonomial(into, maMonomial_Create(p, src_r, bucket), src_r);
236 }
return P p
Definition: myNF.cc:203
mapoly maMonomial_Create(poly p, ring, sBucket_pt bucket)
Definition: fast_maps.cc:138
P bucket
Definition: myNF.cc:79
mapoly maPoly_InsertMonomial(mapoly &into, mapoly what, ring src_r)
Definition: fast_maps.cc:184

◆ maPoly_InsertPoly()

static void maPoly_InsertPoly ( mapoly into,
poly  what,
ring  src_r,
sBucket_pt  bucket 
)
static

Definition at line 238 of file fast_maps.cc.

239 {
240  poly next;
241 
242  while (what != NULL)
243  {
244  next = what->next;
245  maPoly_InsertMonomial(into, what, src_r, bucket);
246  what = next;
247  }
248 }
P bucket
Definition: myNF.cc:79
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
mapoly maPoly_InsertMonomial(mapoly &into, mapoly what, ring src_r)
Definition: fast_maps.cc:184
ListNode * next
Definition: janet.h:31

◆ maPoly_Optimize()

void maPoly_Optimize ( mapoly  mpoly,
ring  src_r 
)

Definition at line 710 of file fast_maps.cc.

711 {
712  assume(mpoly!=NULL && mpoly->src!=NULL);
713  mapoly iter = mpoly;
714  mapoly choice;
715  mapoly ggT=NULL;
716  mapoly fp=NULL;
717  mapoly fq=NULL;
718  while (iter->next!=NULL)
719  {
720  choice=iter->next;
721  if ( /*(*/ iter->f1==NULL /*)*/ )
722  {
723  ggT=maFindBestggT(iter, choice, fp, fq,src_r);
724  if (choice!=NULL)
725  {
726  assume(iter->f1==NULL);
727  assume(iter->f2==NULL);
728  iter->f1=fp;
729  iter->f2=ggT;
730  if (fq!=NULL)
731  {
732  ggT->ref++;
733  choice->f1=fq;
734  choice->f2=ggT;
735  }
736  }
737  else assume(ggT==NULL);
738  }
739  iter=iter->next;
740  }
741 }
static mapoly maFindBestggT(mapoly mp, mapoly &choice, mapoly &fp, mapoly &fq, const ring r)
Definition: fast_maps.cc:635
CanonicalForm fp
Definition: cfModGcd.cc:4043
class mapoly_s * mapoly
Definition: fast_maps.h:21
CFFListIterator iter
Definition: facAbsBiFact.cc:54
#define assume(x)
Definition: mod2.h:394
#define NULL
Definition: omList.c:10

◆ maPoly_Substitute()

static int maPoly_Substitute ( macoeff  c,
poly  p,
ring  dest_r 
)
static

Definition at line 436 of file fast_maps.cc.

437 {
438  // substitute the monomial: go through macoeff
439  int len;
440  BOOLEAN zero_div= (rField_is_Ring(dest_r) && !rField_is_Domain(dest_r));
441  if (!zero_div) len=pLength(p);
442  int done=0;
443  while (c!=NULL)
444  {
445  done++;
446  poly t=pp_Mult_nn(p,c->n,dest_r);
447  #ifdef HAVE_RINGS
448  if (zero_div) len=pLength(t);
449  #endif
450  sBucket_Add_p(c->bucket, t, len);
451  c=c->next;
452  }
453  return done;
454 }
return P p
Definition: myNF.cc:203
static poly pp_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:922
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:480
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:201
static unsigned pLength(poly a)
Definition: p_polys.h:189
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
#define NULL
Definition: omList.c:10
polyrec * poly
Definition: hilb.h:10
int BOOLEAN
Definition: auxiliary.h:85

Variable Documentation

◆ macoeffBin

omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s))
static

Definition at line 136 of file fast_maps.cc.

◆ mapolyBin

omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s))
static

Definition at line 135 of file fast_maps.cc.