ppinitialReduction.h File Reference

#include "kernel/structs.h"
#include "tropicalStrategy.h"

Go to the source code of this file.

Typedefs
typedef std::pair< int, int >	mark
typedef std::vector< std::pair< int, int > >	marks

Functions
bool	isOrderingLocalInT (const ring r)
void	pReduce (ideal &I, const number p, const ring r)
void	pReduceInhomogeneous (poly &g, const number p, const ring r)
bool	ppreduceInitially (ideal I, const ring r, const number p)
	reduces I initially with respect to itself. More...

Typedef Documentation

mark

typedef std::pair<int,int> mark

Definition at line 7 of file ppinitialReduction.h.

marks

typedef std::vector<std::pair<int,int> > marks

Definition at line 8 of file ppinitialReduction.h.

Function Documentation

isOrderingLocalInT()

bool isOrderingLocalInT

(

const ring

r

)

Definition at line 8 of file ppinitialReduction.cc.

{
  poly one = p_One(r);
  poly t = p_One(r);
  p_SetExp(t,1,1,r);
  p_Setm(t,r);
  int s = p_LmCmp(one,t,r);
  p_Delete(&one,r);
  p_Delete(&t,r);
  return (s==1);
}

ppreduceInitially()

bool ppreduceInitially	(	ideal	I,
		const ring	r,
		const number	p
	)

reduces I initially with respect to itself.

assumes that the generators of I are homogeneous in x and that p-t is in I.

sorts Hi according to degree in t in descending order (lowest first, highest last)

Definition at line 597 of file ppinitialReduction.cc.

{
  assume(!n_IsUnit(p,r->cf));
 
  /***
   * Step 1: split up I into components of same degree in x
   *  the lowest component should only contain p-t
   **/
  std::map<long,ideal> H; int n = IDELEMS(I);
  for (int i=0; i<n; i++)
  {
    if(I->m[i]!=NULL)
    {
      I->m[i] = p_Cleardenom(I->m[i],r);
      long d = 0;
      for (int j=2; j<=r->N; j++)
        d += p_GetExp(I->m[i],j,r);
      std::map<long,ideal>::iterator it = H.find(d);
      if (it != H.end())
        idInsertPoly(it->second,I->m[i]);
      else
      {
        std::pair<long,ideal> Hd(d,idInit(1));
        Hd.second->m[0] = I->m[i];
        H.insert(Hd);
      }
    }
  }
 
  std::map<long,ideal>::iterator it=H.begin();
  ideal Hi = it->second;
  idShallowDelete(&Hi);
  it++;
  Hi = it->second;
 
  /***
   * Step 2: reduce each component initially with respect to itself
   *  and all lower components
   **/
  if (ppreduceInitially(Hi,p,r)) return true;
  idSkipZeroes(Hi);
  id_Test(Hi,r);
  id_Test(I,r);
 
  ideal G = idInit(n); int m=0;
  ideal GG = (ideal) omAllocBin(sip_sideal_bin);
  GG->nrows = 1; GG->rank = 1; GG->m=NULL;
 
  for (it++; it!=H.end(); it++)
  {
    int l=IDELEMS(Hi); int k=l; poly cache;
    /**
     * sorts Hi according to degree in t in descending order
     * (lowest first, highest last)
     */
    do
    {
      int j=0;
      for (int i=1; i<k; i++)
      {
        if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
        {
          cache=Hi->m[i-1];
          Hi->m[i-1]=Hi->m[i];
          Hi->m[i]=cache;
          j = i;
        }
      }
      k=j;
    } while(k);
    int kG=n-m, kH=0;
    for (int i=n-m-l; i<n; i++)
    {
      if (kG==n)
      {
        memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
        break;
      }
      if (kH==l)
        break;
      if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
        G->m[i] = G->m[kG++];
      else
        G->m[i] = Hi->m[kH++];
    }
    m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
    id_Test(it->second,r);
    id_Test(GG,r);
    if (ppreduceInitially(it->second,p,GG,r)) return true;
    id_Test(it->second,r);
    id_Test(GG,r);
    idShallowDelete(&Hi); Hi = it->second;
  }
  idShallowDelete(&Hi);
 
  ptNormalize(I,p,r);
  omFreeBin((ADDRESS)GG, sip_sideal_bin);
  idShallowDelete(&G);
  return false;
}

pReduce()

void pReduce	(	ideal &	I,
		const number	p,
		const ring	r
	)

Definition at line 261 of file ppinitialReduction.cc.

{
  int k = IDELEMS(I);
  for (int i=0; i<k; i++)
  {
    if (I->m[i]!=NULL)
    {
      number c = p_GetCoeff(I->m[i],r);
      if (!n_DivBy(p,c,r->cf))
        pReduce(I->m[i],p,r);
    }
  }
}

pReduceInhomogeneous()

void pReduceInhomogeneous	(	poly &	g,
		const number	p,
		const ring	r
	)

Definition at line 132 of file ppinitialReduction.cc.

{
  if (g==NULL)
    return;
  p_Test(g,r);
 
  poly toBeChecked = pNext(g);
  pNext(g) = NULL; poly gEnd = g;
  poly gCache;
 
  number coeff, pPower; int power; poly subst;
  while(toBeChecked)
  {
    for (gCache = g; gCache; pIter(gCache))
      if (p_xLeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
    if (gCache)
    {
      n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
      coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
      p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
      n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
      toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
    }
    else
    {
      if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
      {
        power=1;
        coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
        while (n_DivBy(coeff,p,r->cf))
        {
          power++;
          number coeff0 = n_Div(coeff,p,r->cf);
          n_Delete(&coeff,r->cf);
          coeff = coeff0;
          coeff0 = NULL;
          if (power<1)
          {
            WerrorS("pReduce: overflow in exponent");
            throw 0;
          }
        }
        subst=p_LmInit(toBeChecked,r);
        p_AddExp(subst,1,power,r);
        p_SetCoeff(subst,coeff,r);
        p_Setm(subst,r); p_Test(subst,r);
        toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
        toBeChecked=p_Add_q(toBeChecked,subst,r);
        p_Test(toBeChecked,r);
      }
      else
      {
        pNext(gEnd)=toBeChecked;
        pIter(gEnd); pIter(toBeChecked);
        pNext(gEnd)=NULL;
        p_Test(g,r);
      }
    }
  }
  p_Test(g,r);
  divideByCommonGcd(g,r);
  return;
}