My Project
Loading...
Searching...
No Matches
fast_maps.h File Reference

Go to the source code of this file.

Data Structures

class  mapoly_s
 
class  macoeff_s
 
class  maideal_s
 

Typedefs

typedef class mapoly_smapoly
 
typedef class macoeff_smacoeff
 
typedef class maideal_smaideal
 

Functions

void maMonomial_Out (mapoly monomial, ring src_r, ring dest_r=NULL)
 
void maPoly_Out (mapoly mpoly, ring src_ring, ring dest_r=NULL)
 
mapoly maMonomial_Create (poly p, ring, sBucket_pt bucket=NULL)
 
void maMonomial_Destroy (mapoly monomial, ring src_r, ring dest_r=NULL)
 
mapoly maMonomial_Free (mapoly monomial, ring src_r, ring dest_r=NULL)
 
mapoly maPoly_InsertMonomial (mapoly &into, mapoly what, ring src_r)
 
mapoly maPoly_InsertMonomial (mapoly &into, poly p, ring src_r, sBucket_pt bucket=NULL)
 
void maPoly_Optimize (mapoly mpoly, ring src_r)
 
void maPoly_Eval (mapoly mpoly, ring src_r, ideal dest_id, ring dest_r, int total_cost)
 
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 &no_sort)
 
ideal maIdeal_2_Ideal (maideal ideal, ring dest_r)
 
ideal fast_map_common_subexp (const ideal map_id, const ring map_r, const ideal image_id, const ring image_r)
 

Data Structure Documentation

◆ mapoly_s

class mapoly_s

Definition at line 25 of file fast_maps.h.

Data Fields
macoeff coeff
poly dest
mapoly f1
mapoly f2
mapoly next
int ref
poly src

◆ macoeff_s

class macoeff_s

Definition at line 36 of file fast_maps.h.

Data Fields
sBucket_pt bucket
number n
macoeff next

◆ maideal_s

class maideal_s

Definition at line 44 of file fast_maps.h.

Data Fields
sBucket_pt * buckets
int n

Typedef Documentation

◆ macoeff

typedef class macoeff_s* macoeff

Definition at line 22 of file fast_maps.h.

◆ maideal

typedef class maideal_s* maideal

Definition at line 23 of file fast_maps.h.

◆ mapoly

typedef class mapoly_s* mapoly

Definition at line 21 of file fast_maps.h.

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:88
#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:497
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:712
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:105
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.

◆ maIdeal_2_Ideal()

ideal maIdeal_2_Ideal ( maideal ideal,
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
int i
Definition cfEzgcd.cc:132
CanonicalForm res
Definition facAbsFact.cc:60
#define omFreeSize(addr, size)
#define omFree(addr)
sBucket * sBucket_pt
Definition sbuckets.h:16
void sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)
Definition sbuckets.h:68
ideal idInit(int idsize, int rank)
initialise an ideal / module

◆ 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:171
static void maPoly_InsertPoly(mapoly &into, poly what, ring src_r, sBucket_pt bucket)
Definition fast_maps.cc:238
#define omAlloc0(size)
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
#define IDELEMS(i)

◆ maMap_CreateRings()

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

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:101
static int si_min(const int a, const int b)
Definition auxiliary.h:126
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:190
ring rModifyRing_Wp(ring r, int *weights)
construct Wp, C ring
Definition ring.cc:3004
ring rModifyRing_Simple(ring r, BOOLEAN ommit_degree, BOOLEAN ommit_comp, unsigned long exp_limit, BOOLEAN &simple)
Definition ring.cc:3052

◆ maMonomial_Create()

mapoly maMonomial_Create ( poly p,
ring ,
sBucket_pt bucket = NULL )

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}
int p
Definition cfModGcd.cc:4086
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)

◆ maMonomial_Destroy()

void maMonomial_Destroy ( mapoly monomial,
ring src_r,
ring dest_r = NULL )

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 assume(x)
Definition mod2.h:389
#define omFreeBin(addr, bin)
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
static void p_LmFree(poly p, ring)
Definition p_polys.h:685

◆ maMonomial_Free()

mapoly maMonomial_Free ( mapoly monomial,
ring src_r,
ring dest_r = NULL )
inline

Definition at line 67 of file fast_maps.h.

68{
69 monomial->ref--;
70 if (monomial->ref <= 0)
71 { maMonomial_Destroy(monomial, src_r, dest_r); return NULL;}
72 return monomial;
73}
void maMonomial_Destroy(mapoly monomial, ring src_r, ring dest_r=NULL)
Definition fast_maps.cc:154

◆ maMonomial_Out()

void maMonomial_Out ( mapoly monomial,
ring src_r,
ring dest_r = NULL )

◆ maPoly_Eval()

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

Definition at line 497 of file fast_maps.cc.

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

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

◆ maPoly_InsertMonomial() [2/2]

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

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 maPoly_InsertMonomial(mapoly &into, mapoly what, ring src_r)
Definition fast_maps.cc:184
mapoly maMonomial_Create(poly p, ring, sBucket_pt bucket)
Definition fast_maps.cc:137

◆ maPoly_Optimize()

void maPoly_Optimize ( mapoly mpoly,
ring src_r )

Definition at line 712 of file fast_maps.cc.

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

◆ maPoly_Out()

void maPoly_Out ( mapoly mpoly,
ring src_ring,
ring dest_r = NULL )