My Project
Loading...
Searching...
No Matches
Macros | Functions | Variables
fast_maps.cc File Reference
#include "kernel/mod2.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   0
 

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_VAR omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s))
 
STATIC_VAR omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s))
 

Macro Definition Documentation

◆ HAVE_DEST_R

#define HAVE_DEST_R   1

Definition at line 23 of file fast_maps.cc.

◆ HAVE_MAP_OPTIMIZE

#define HAVE_MAP_OPTIMIZE   0

Definition at line 27 of file fast_maps.cc.

◆ HAVE_SRC_R

#define HAVE_SRC_R   1

Definition at line 25 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 {
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 {
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, clean up mideal
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}
int BOOLEAN
Definition: auxiliary.h:87
#define Print
Definition: emacs.cc:80
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 maMap_CreatePolyIdeal(ideal map_id, ring map_r, ring src_r, ring dest_r, mapoly &mp, maideal &mideal)
Definition: fast_maps.cc:255
void maPoly_GetLength(mapoly mp, int &length)
Definition: fast_maps.cc:338
ideal maIdeal_2_Ideal(maideal m_id, ring)
Definition: fast_maps.cc:323
void maPoly_Eval(mapoly root, ring src_r, ideal dest_id, ring dest_r, int total_cost)
Definition: fast_maps.cc:499
static void maMap_KillRings(ring map_r, ring image_r, ring src_r, ring dest_r)
Definition: fast_maps.cc:310
void maPoly_Optimize(mapoly mpoly, ring src_r)
Definition: fast_maps.cc:714
class maideal_s * maideal
Definition: fast_maps.h:23
class mapoly_s * mapoly
Definition: fast_maps.h:21
#define idTest(id)
Definition: ideals.h:47
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define NULL
Definition: omList.c:12
#define TEST_OPT_PROT
Definition: options.h:104
ideal idrShallowCopyR(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:220
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
void id_ShallowDelete(ideal *h, ring r)
Shallowdeletes an ideal/matrix.

◆ maEggT()

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

Definition at line 590 of file fast_maps.cc.

591{
592
593 int i;
594 int dg = 0;
595 poly ggt = p_Init(r);
596 q1 = p_Init(r);
597 q2 = p_Init(r);
598
599 for (i=1;i<=r->N;i++)
600 {
601 unsigned long e1 = p_GetExp(m1, i, r);
602 unsigned long e2 = p_GetExp(m2, i, r);
603 if (e1 > 0 && e2 > 0)
604 {
605 unsigned long em = (e1 > e2 ? e2 : e1);
606 dg += em;
607 p_SetExp(ggt, i, em, r);
608 p_SetExp(q1, i, e1 - em, r);
609 p_SetExp(q2, i, e2 - em, r);
610 }
611 else
612 {
613 p_SetExp(q1, i, e1, r);
614 p_SetExp(q2, i, e2, r);
615 }
616 }
617 if (dg>1)
618 {
619 p_Setm(ggt, r);
620 p_Setm(q1, r);
621 p_Setm(q2, r);
622 }
623 else
624 {
625 p_LmFree(ggt, r);
626 p_LmFree(q1, r);
627 p_LmFree(q2, r);
628 ggt = NULL;
629 }
630 return ggt;
631}
int i
Definition: cfEzgcd.cc:132
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:486
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:467
static void p_LmFree(poly p, ring)
Definition: p_polys.h:681
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1318

◆ maFindBestggT()

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

Definition at line 639 of file fast_maps.cc.

640{
641 int ggt_deg = 0;
642 poly p = mp->src;
643 mapoly iter = choice;
644 poly ggT = NULL;
645 fp = NULL;
646 fq = NULL;
647 poly fp_p=NULL;
648 poly fq_p=NULL;
649 choice=NULL;
650 while ((iter != NULL) && (p_Deg(iter->src, r) > ggt_deg))
651 {
652 // maMonomial_Out(iter, r, NULL);
653 poly q1, q2, q;
654
655 q = maEggT(p, iter->src, q1, q2,r);
656 if (q != NULL)
657 {
658 int tmp_deg;
659 assume((q1!=NULL)&&(q2!=NULL));
660 if ((tmp_deg=p_Deg(q,r)) > ggt_deg)
661 {
662 choice=iter;
663 if (ggT != NULL)
664 {
665 p_LmFree(ggT, r);
666 p_LmFree(fp_p, r);
667 p_LmFree(fq_p, r);
668 }
669 ggt_deg = tmp_deg ; /*p_Deg(q, r);*/
670 ggT = q;
671 fp_p = q1;
672 fq_p = q2;
673 }
674 else
675 {
676 p_LmFree(q, r);
677 p_LmFree(q1, r);
678 p_LmFree(q2, r);
679 }
680 }
681 iter=iter->next;
682 }
683 if(ggT!=NULL)
684 {
685 int dq =p_Totaldegree(fq_p,r);
686 if (dq!=0)
687 {
688 fq=maPoly_InsertMonomial(mp, fq_p, r, NULL);
689 fp=maPoly_InsertMonomial(mp, fp_p, r, NULL);
690 return maPoly_InsertMonomial(mp, ggT, r, NULL);
691 }
692 else
693 {
694 fq=NULL;
695 p_LmFree(fq_p, r);
696 p_LmFree(ggT, r);
697 fp=maPoly_InsertMonomial(mp, fp_p, r, NULL);
698 choice->ref++;
699 return choice;
700 }
701 }
702 else
703 {
704 return NULL;
705 }
706}
int p
Definition: cfModGcd.cc:4078
CanonicalForm fp
Definition: cfModGcd.cc:4102
CFFListIterator iter
Definition: facAbsBiFact.cc:53
static poly maEggT(const poly m1, const poly m2, poly &q1, poly &q2, const ring r)
Definition: fast_maps.cc:590
mapoly maPoly_InsertMonomial(mapoly &into, mapoly what, ring src_r)
Definition: fast_maps.cc:184
#define assume(x)
Definition: mod2.h:389
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1505

◆ maGetMaxExp()

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

Definition at line 63 of file fast_maps.cc.

64{
65 unsigned long max=0;
66 poly* max_map_monomials = (poly*) omAlloc(IDELEMS(map_id)*sizeof(poly));
67 poly max_pi_i, max_map_i;
68
69 int i;
70 for (i=0; i<IDELEMS(map_id); i++)
71 {
72 max_map_monomials[i] = p_GetMaxExpP(map_id->m[i], map_r);
73 }
74
75 for (i=0; i<IDELEMS(pi_id); i++)
76 {
77 max_pi_i = p_GetMaxExpP(pi_id->m[i], pi_r);
78 max_map_i = maGetMaxExpP(max_map_monomials, IDELEMS(map_id), map_r,
79 max_pi_i, pi_r);
80 unsigned long temp = p_GetMaxExp(max_map_i, map_r);
81 if (temp > max){ max=temp; }
82
83 p_LmFree(max_pi_i, pi_r);
84 p_LmFree(max_map_i, map_r);
85 }
86 for (i=0; i<IDELEMS(map_id); i++)
87 {
88 p_LmFree(&max_map_monomials[i], map_r);
89 }
90 omFreeSize(max_map_monomials,IDELEMS(map_id)*sizeof(poly));
91
92 return max;
93}
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:34
static int max(int a, int b)
Definition: fast_mult.cc:264
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
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:1138
static unsigned long p_GetMaxExp(const unsigned long l, const ring r)
Definition: p_polys.h:779
#define IDELEMS(i)
Definition: simpleideals.h:23

◆ 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 34 of file fast_maps.cc.

37{
38 int n = si_min(pi_r->N, n_max_map_monomials);
39 int i, j;
40 unsigned long e_i, e_j;
41 poly m_i=NULL;
42 poly map_j = p_Init(map_r);
43
44 for (i=1; i <= n; i++)
45 {
46 e_i = p_GetExp(pi_m, i, pi_r);
47 if (e_i==0) e_i=1;
48 m_i = max_map_monomials[i-1];
49 if (m_i != NULL && ! p_IsConstantComp(m_i, map_r))
50 {
51 for (j = 1; j<= map_r->N; j++)
52 {
53 e_j = p_GetExp(m_i, j, map_r);
54 if (e_j == 0) e_j=1;
55 p_AddExp(map_j, j, e_j*e_i, map_r);
56 }
57 }
58 }
59 return map_j;
60}
static int si_min(const int a, const int b)
Definition: auxiliary.h:125
int j
Definition: facHensel.cc:110
static BOOLEAN p_IsConstantComp(const poly p, const ring r)
like the respective p_LmIs* routines, except that p might be empty
Definition: p_polys.h:1956
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:604

◆ maIdeal_2_Ideal()

ideal maIdeal_2_Ideal ( maideal  m_id,
ring  dest_r 
)

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}
int l
Definition: cfEzgcd.cc:100
CanonicalForm res
Definition: facAbsFact.cc:60
#define omFree(addr)
Definition: omAllocDecl.h:261
void sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.h:68
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35

◆ 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}
#define PDEBUG
Definition: auxiliary.h:170
static void maPoly_InsertPoly(mapoly &into, poly what, ring src_r, sBucket_pt bucket)
Definition: fast_maps.cc:238
#define omAlloc0(size)
Definition: omAllocDecl.h:211
poly prShallowCopyR(poly p, ring r, ring dest_r)
Definition: prCopy.cc:117
poly prShallowCopyR_NoSort(poly p, ring r, ring dest_r)
Definition: prCopy.cc:112
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96

◆ 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}
#define TRUE
Definition: auxiliary.h:100
static unsigned long maGetMaxExp(ideal pi_id, ring pi_r, ideal map_id, ring map_r)
Definition: fast_maps.cc:63
static int pLength(poly a)
Definition: p_polys.h:188
ring rModifyRing_Wp(ring r, int *weights)
construct Wp, C ring
Definition: ring.cc:2945
ring rModifyRing_Simple(ring r, BOOLEAN ommit_degree, BOOLEAN ommit_comp, unsigned long exp_limit, BOOLEAN &simple)
Definition: ring.cc:2993

◆ 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)
314 if (image_r != dest_r)
315 rKillModifiedRing(dest_r);
316}
void rKillModifiedRing(ring r)
Definition: ring.cc:3059
void rKillModified_Wp_Ring(ring r)
Definition: ring.cc:3069

◆ maMonomial_Create()

mapoly maMonomial_Create ( poly  p,
ring  ,
sBucket_pt  bucket 
)

Definition at line 137 of file fast_maps.cc.

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

◆ maMonomial_Destroy()

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

Definition at line 154 of file fast_maps.cc.

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

◆ maPoly_Eval()

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

Definition at line 499 of file fast_maps.cc.

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

◆ 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; // for constant src
463 for(i=1;i<=src_r->N;i++)
464 {
465 e=p_GetExp(src,i,src_r);
466 if (e>0)
467 {
468 pp=dest_id[i-1];
469 if (pp==NULL)
470 {
471 p_Delete(&p,dest_r);
472 return NULL;
473 }
474 if (p==NULL)
475 {
476 if (!is_const) // possible only when the coefficient ring is not a field
477 {
478 return NULL;
479 }
480 p=p_Copy(pp /*dest_id[i-1]*/,dest_r);
481 e--;
482 }
483 while (e>0)
484 {
485 p=p_Mult_q(p,p_Copy(pp /*dest_id[i-1]*/,dest_r),dest_r);
486 e--;
487 }
488 is_const=FALSE;
489 }
490 }
491 if (is_const)
492 {
493 assume(p==NULL);
494 p=p_ISet(1,dest_r);
495 }
496 return p;
497}
#define FALSE
Definition: auxiliary.h:96
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1297

◆ 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}

◆ 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}
static BOOLEAN Equal(number a, number b, const coeffs)
Definition: flintcf_Q.cc:324
static bool Greater(mono_type m1, mono_type m2)
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition: p_polys.h:1717

◆ 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}
mapoly maMonomial_Create(poly p, ring, sBucket_pt bucket)
Definition: fast_maps.cc:137

◆ 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}

◆ maPoly_Optimize()

void maPoly_Optimize ( mapoly  mpoly,
ring  src_r 
)

Definition at line 714 of file fast_maps.cc.

715{
716 assume(mpoly!=NULL && mpoly->src!=NULL);
717 mapoly iter = mpoly;
718 mapoly choice;
719 mapoly ggT=NULL;
720 mapoly fp=NULL;
721 mapoly fq=NULL;
722 while (iter->next!=NULL)
723 {
724 choice=iter->next;
725 if ( /*(*/ iter->f1==NULL /*)*/ )
726 {
727 ggT=maFindBestggT(iter, choice, fp, fq,src_r);
728 if (choice!=NULL)
729 {
730 assume(iter->f1==NULL);
731 assume(iter->f2==NULL);
732 iter->f1=fp;
733 iter->f2=ggT;
734 if (fq!=NULL)
735 {
736 ggT->ref++;
737 choice->f1=fq;
738 choice->f2=ggT;
739 }
740 }
741 else assume(ggT==NULL);
742 }
743 iter=iter->next;
744 }
745}
static mapoly maFindBestggT(mapoly mp, mapoly &choice, mapoly &fp, mapoly &fq, const ring r)
Definition: fast_maps.cc:639

◆ 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}
#define __pp_Mult_nn(p, n, r)
Definition: p_polys.h:1000
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:487
#define rField_is_Ring(R)
Definition: ring.h:485
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:203

Variable Documentation

◆ macoeffBin

STATIC_VAR omBin macoeffBin = omGetSpecBin(sizeof(macoeff_s))

Definition at line 135 of file fast_maps.cc.

◆ mapolyBin

STATIC_VAR omBin mapolyBin = omGetSpecBin(sizeof(mapoly_s))

Definition at line 134 of file fast_maps.cc.