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_s *	mapoly
typedef class macoeff_s *	macoeff
typedef class maideal_s *	maideal

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.

{
  ring src_r, dest_r;
  ideal dest_id/*, res_id*/;
  int length = 0;
  BOOLEAN no_sort;
 
  // construct rings we work in:
  // src_r: Wp with Weights set to length of poly in image_id
  // dest_r: Simple ring without degree ordering and short exponents
  maMap_CreateRings(map_id, map_r, image_id, image_r, src_r, dest_r, no_sort);
 
  // construct dest_id
  if (dest_r != image_r)
  {
    dest_id = idrShallowCopyR(image_id, image_r, dest_r);
  }
  else
    dest_id = image_id;
 
  // construct mpoly and mideal
  mapoly mp;
  maideal mideal;
  maMap_CreatePolyIdeal(map_id, map_r, src_r, dest_r, mp, mideal);
 
  if (TEST_OPT_PROT)
  {
    maPoly_GetLength(mp, length);
    Print("map[%ld:%d]{%d:", dest_r->bitmask, dest_r->ExpL_Size, length);
  }
 
  // do the optimization step
#if HAVE_MAP_OPTIMIZE > 0
  if (mp!=NULL) maPoly_Optimize(mp, src_r);
#endif
  if (TEST_OPT_PROT)
  {
    maPoly_GetLength(mp, length);
    Print("%d}", length);
  }
 
  // do the actual evaluation
  maPoly_Eval(mp, src_r, dest_id, dest_r, length);
  if (TEST_OPT_PROT) PrintS(".");
 
  // collect the results back into an ideal, clean up mideal
  ideal res_dest_id = maIdeal_2_Ideal(mideal, dest_r);
  if (TEST_OPT_PROT) PrintS(".");
 
  // convert result back to image_r
  ideal res_image_id;
  if (dest_r != image_r)
  {
    //if (no_sort) see Old/m134si.tst
    //  res_image_id = idrShallowCopyR_NoSort(res_dest_id, dest_r, image_r);
    //else
      res_image_id = idrShallowCopyR(res_dest_id, dest_r, image_r);
    id_ShallowDelete(&res_dest_id, dest_r);
    id_ShallowDelete(&dest_id,dest_r);
  }
  else
    res_image_id = res_dest_id;
 
  if (TEST_OPT_PROT) PrintS(".");
 
  // clean-up the rings
  maMap_KillRings(map_r, image_r, src_r, dest_r);
 
  if (TEST_OPT_PROT)
    PrintLn();
 
  idTest(res_image_id);
  return res_image_id;
}

maIdeal_2_Ideal()

ideal maIdeal_2_Ideal	(	maideal	ideal,
		ring	dest_r
	)

Definition at line 323 of file fast_maps.cc.

{
  ideal res = idInit(m_id->n, 1);
  int l;
 
  for (int i= 0; i < m_id->n; i++)
  {
    if (m_id->buckets[i]!=NULL)
      sBucketDestroyAdd(m_id->buckets[i], &(res->m[i]), &l);
  }
  omFreeSize(m_id->buckets,m_id->n*sizeof(sBucket_pt));
  omFree(m_id);
  return res;
}

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.

{
  mideal = (maideal) omAlloc0(sizeof(maideal_s));
  mideal->n = IDELEMS(map_id);
  mideal->buckets = (sBucket_pt*) omAlloc0(mideal->n*sizeof(sBucket_pt));
  int i;
  mp = NULL;
 
  for (i=0; i<mideal->n; i++)
  {
    if (map_id->m[i] != NULL)
    {
      mideal->buckets[i] = sBucketCreate(dest_r);
      maPoly_InsertPoly(mp,
#ifdef PDEBUG
                        prShallowCopyR(map_id->m[i], map_r, src_r),
#else
                        prShallowCopyR_NoSort(map_id->m[i], map_r, src_r),
#endif
                        src_r,
                        mideal->buckets[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.

{
#if HAVE_SRC_R > 0
  int* weights = (int*) omAlloc0(map_r->N*sizeof(int));
  int i;
  int n = si_min(map_r->N, IDELEMS(image_id));
 
  for (i=0; i<n; i++)
  {
    weights[i] = pLength(image_id->m[i])+1;
  }
  src_r = rModifyRing_Wp(map_r, weights);
#else
  src_r = map_r;
#endif
 
#if HAVE_DEST_R > 0
  unsigned long maxExp = maGetMaxExp(map_id, map_r, image_id, image_r);
  if (maxExp <=  1) maxExp = 2;
  else if (maxExp > (unsigned long) image_r->bitmask)
    maxExp = (unsigned long) image_r->bitmask;
  dest_r = rModifyRing_Simple(image_r, TRUE, TRUE, maxExp,  simple);
#else
  dest_r = image_r;
#endif
}

maMonomial_Create()

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

Definition at line 137 of file fast_maps.cc.

{
  mapoly mp = (mapoly) omAlloc0Bin(mapolyBin);
  //p_wrp(p,r_p);printf(" (%x) created\n",mp);
  mp->src = p;
  p->next = NULL;
 
  if (bucket != NULL)
  {
    mp->coeff = (macoeff) omAlloc0Bin(macoeffBin);
    mp->coeff->bucket = bucket;
    mp->coeff->n = pGetCoeff(p);
  }
  mp->ref = 1;
  return mp;
}

maMonomial_Destroy()

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

Definition at line 154 of file fast_maps.cc.

{
  if (mp != NULL)
  {
    p_LmFree(mp->src, src_r);
    if (mp->coeff != NULL)
    {
      macoeff coeff, next = mp->coeff;
      do
      {
        coeff = next;
        next = coeff->next;
        omFreeBin(coeff, macoeffBin);
      }
      while (next != NULL);
      mp->coeff=NULL;
    }
    if (mp->dest != NULL)
    {
      assume(dest_r != NULL);
      p_Delete(&(mp->dest), dest_r);
    }
  }
  omFreeBin(mp, mapolyBin);
}

maMonomial_Free()

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

inline

Definition at line 67 of file fast_maps.h.

{
  monomial->ref--;
  if (monomial->ref <= 0)
  { maMonomial_Destroy(monomial, src_r, dest_r); return NULL;}
  return monomial;
}

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

{
  // invert the list rooted at root:
  if ((root!=NULL) && (root->next!=NULL))
  {
    mapoly q=root->next;
    mapoly qn;
    root->next=NULL;
    do
    {
      qn=q->next;
      q->next=root;
      root=q;
      q=qn;
    }
    while (qn !=NULL);
  }
 
  total_cost /= 10;
  int next_print_cost = total_cost;
 
  // the evaluation -----------------------------------------
  mapoly p=root;
  int cost = 0;
 
  while (p!=NULL)
  {
    // look at each mapoly: compute its value in ->dest
    assume (p->dest==NULL);
    {
      if ((p->f1!=NULL)&&(p->f2!=NULL))
      {
        poly f1=p->f1->dest;
        poly f2=p->f2->dest;
        if (p->f1->ref>0) f1=p_Copy(f1,dest_r);
        else
        {
          // we own p->f1->dest now (in f1)
          p->f1->dest=NULL;
        }
        if (p->f2->ref>0) f2=p_Copy(f2,dest_r);
        else
        {
          // we own p->f2->dest now (in f2)
          p->f2->dest=NULL;
        }
        maMonomial_Free(p->f1,src_r, dest_r);
        maMonomial_Free(p->f2,src_r, dest_r);
        p->dest=p_Mult_q(f1,f2,dest_r);
      } /* factors : 2 */
      else
      {
        assume((p->f1==NULL) && (p->f2==NULL));
        // no factorization provided, use the classical method:
        p->dest=maPoly_EvalMon(p->src,src_r,dest_id->m,dest_r);
      }
    } /* p->dest==NULL */
    // substitute the monomial: go through macoeff
    p->ref -= maPoly_Substitute(p->coeff, p->dest, dest_r);
    //printf("subst done\n");
    if (total_cost)
    {
      assume(TEST_OPT_PROT);
      cost++;
      if (cost > next_print_cost)
      {
        PrintS("-");
        next_print_cost += total_cost;
      }
    }
 
    mapoly pp=p;
    p=p->next;
    //p_wrp(pp->src, src_r);
    if (pp->ref<=0)
    {
      //printf(" (%x) killed\n",pp);
      maMonomial_Destroy(pp, src_r, dest_r);
    }
    //else
    //  printf(" (%x) not killed, ref=%d\n",pp,pp->ref);
  }
}

maPoly_InsertMonomial() [1/2]

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

Definition at line 184 of file fast_maps.cc.

{
  if (into == NULL)
  {
    into = what;
    return what;
  }
 
  mapoly iter = into;
  mapoly prev = NULL;
 
  Top:
  p_LmCmpAction(iter->src, what->src, src_r, goto Equal, goto Greater, goto Smaller);
 
  Greater:
  if (iter->next == NULL)
  {
    iter->next = what;
    return what;
  }
  prev = iter;
  iter = iter->next;
  goto Top;
 
  Smaller:
  if (prev == NULL)
  {
    into = what;
    what->next = iter;
    return what;
  }
  prev->next = what;
  what->next = iter;
  return what;
 
  Equal:
  iter->ref += what->ref;
  macoeff coeff = what->coeff;
  if (coeff != NULL)
  {
    while (coeff->next != NULL) coeff = coeff->next;
    coeff->next = iter->coeff;
    iter->coeff = what->coeff;
    what->coeff = NULL;
  }
  maMonomial_Free(what, src_r);
  return iter;
}

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.

{
  return maPoly_InsertMonomial(into, maMonomial_Create(p, src_r, bucket), src_r);
}

maPoly_Optimize()

void maPoly_Optimize	(	mapoly	mpoly,
		ring	src_r
	)

Definition at line 714 of file fast_maps.cc.

{
  assume(mpoly!=NULL && mpoly->src!=NULL);
  mapoly iter = mpoly;
  mapoly choice;
  mapoly ggT=NULL;
  mapoly fp=NULL;
  mapoly fq=NULL;
  while (iter->next!=NULL)
  {
    choice=iter->next;
    if ( /*(*/ iter->f1==NULL /*)*/ )
    {
      ggT=maFindBestggT(iter, choice, fp, fq,src_r);
      if (choice!=NULL)
      {
        assume(iter->f1==NULL);
        assume(iter->f2==NULL);
        iter->f1=fp;
        iter->f2=ggT;
        if (fq!=NULL)
        {
          ggT->ref++;
          choice->f1=fq;
          choice->f2=ggT;
        }
      }
      else assume(ggT==NULL);
    }
    iter=iter->next;
  }
}

maPoly_Out()

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