ratgring.cc File Reference

#include "kernel/mod2.h"
#include "kernel/GBEngine/ratgring.h"
#include "polys/nc/nc.h"
#include "polys/monomials/ring.h"
#include "kernel/polys.h"
#include "coeffs/numbers.h"
#include "kernel/ideals.h"
#include "polys/matpol.h"
#include "polys/kbuckets.h"
#include "kernel/GBEngine/kstd1.h"
#include "polys/sbuckets.h"
#include "polys/prCopy.h"
#include "polys/operations/p_Mult_q.h"
#include "polys/clapsing.h"
#include "misc/options.h"

Go to the source code of this file.

Functions
void	pLcmRat (poly a, poly b, poly m, int rat_shift)
poly	p_HeadRat (poly p, int ishift, ring r)
void	p_ExpVectorDiffRat (poly pr, poly p1, poly p2, int ishift, ring r)
ideal	ncGCD2 (poly p, poly q, const ring r)
ideal	ncGCD (poly p, poly q, const ring r)
poly	nc_rat_CreateSpoly (poly pp1, poly pp2, int ishift, const ring r)
poly	nc_rat_ReduceSpolyNew (const poly p1, poly p2, int ishift, const ring r)
BOOLEAN	p_DivisibleByRat (poly a, poly b, int ishift, const ring r)
int	redRat (poly *h, poly *reducer, int *red_length, int rl, int ishift, ring r)
BOOLEAN	p_LmIsConstantRat (const poly p, const ring r)
BOOLEAN	p_LmIsConstantCompRat (const poly p, const ring r)

Function Documentation

nc_rat_CreateSpoly()

poly nc_rat_CreateSpoly	(	poly	pp1,
		poly	pp2,
		int	ishift,
		const ring	r
	)

Definition at line 340 of file ratgring.cc.

{
 
  poly p1 = p_Copy(pp1,r);
  poly p2 = p_Copy(pp2,r);
 
  const long lCompP1 = p_GetComp(p1,r);
  const long lCompP2 = p_GetComp(p2,r);
 
  if ((lCompP1!=lCompP2) && (lCompP1!=0) && (lCompP2!=0))
  {
#ifdef PDEBUG
    WerrorS("nc_rat_CreateSpoly: different non-zero components!");
#endif
    return(NULL);
  }
 
  if ( (p_LmIsConstantRat(p1,r)) || (p_LmIsConstantRat(p2,r)) )
  {
    p_Delete(&p1,r);
    p_Delete(&p2,r);
    return( NULL );
  }
 
 
/* note: prod. crit does not apply! */
  poly pL=pOne();
  poly m1=pOne();
  poly m2=pOne();
  int is = ishift; /* TODO */
  pLcmRat(p1,p2,pL,is);
  p_Setm(pL,r);
#ifdef PDEBUG
  p_Test(pL,r);
#endif
  poly pr1 = p_GetExp_k_n(p1,1,ishift,r); /* rat D-exp of p1 */
  poly pr2 = p_GetExp_k_n(p2,1,ishift,r); /* rat D-exp of p2 */
  p_ExpVectorDiff(m1,pL,pr1,r); /* purely in D part by construction */
  p_ExpVectorDiff(m2,pL,pr2,r); /* purely in D part by construction */
  p_Delete(&pr1,r);
  p_Delete(&pr2,r);
  p_Delete(&pL,r);
#ifdef PDEBUG
  p_Test(m1,r);
  PrintS("d^{gamma-alpha} = "); p_wrp(m1,r); PrintLn();
  p_Test(m2,r);
  PrintS("d^{gamma-beta} = "); p_wrp(m2,r); PrintLn();
#endif
 
  poly HF = NULL;
  HF = p_HeadRat(p1,is,r); // lm_D(f)
  HF  = nc_mm_Mult_p(m1, HF, r); // // d^{gamma-alpha} lm_D(f)
  poly C  = p_GetCoeffRat(HF,  is, r); // c = lc_D(h_f) in the paper
 
  poly HG = NULL;
  HG = p_HeadRat(p2,is,r); // lm_D(g)
  HG  = nc_mm_Mult_p(m2, HG, r); // // d^{gamma-beta} lm_D(g)
  poly K  = p_GetCoeffRat(HG,  is, r); // k = lc_D(h_g) in the paper
 
#ifdef PDEBUG
  PrintS("f: "); p_wrp(p1,r); PrintS("\n");
  PrintS("c: "); p_wrp(C,r); PrintS("\n");
  PrintS("g: "); p_wrp(p2,r); PrintS("\n");
  PrintS("k: "); p_wrp(K,r); PrintS("\n");
#endif
 
  ideal ncsyz = ncGCD(C,K,r);
  poly KK = ncsyz->m[0]; ncsyz->m[0]=NULL; //p_Copy(ncsyz->m[0],r); // k'
  poly CC = ncsyz->m[1]; ncsyz->m[1]= NULL; //p_Copy(ncsyz->m[1],r); // c'
  id_Delete(&ncsyz,r);
 
  p_LmDeleteAndNextRat(&p1, is, r); // t_f
  p_LmDeleteAndNextRat(&HF, is, r); // r_f = h_f - lt_D(h_f)
 
  p_LmDeleteAndNextRat(&p2, is, r); // t_g
  p_LmDeleteAndNextRat(&HG, is, r); // r_g = h_g - lt_D(h_g)
 
 
#ifdef PDEBUG
  PrintS(" t_f: "); p_wrp(p1,r); PrintS("\n");
  PrintS(" t_g: "); p_wrp(p2,r); PrintS("\n");
  PrintS(" r_f: "); p_wrp(HF,r); PrintS("\n");
  PrintS(" r_g: "); p_wrp(HG,r); PrintS("\n");
  PrintS(" c': "); p_wrp(CC,r); PrintS("\n");
  PrintS(" k': "); p_wrp(KK,r); PrintS("\n");
 
#endif
 
  // k'(r_f + d^{gamma-alpha} t_f)
 
  p1 = p_Mult_q(m1, p1, r); // p1 = d^{gamma-alpha} t_f
  p1 = p_Add_q(p1,HF,r); // p1 = r_f + d^{gamma-alpha} t_f
  p1 = p_Mult_q(KK,p1,r); // p1 = k'(r_f + d^{gamma-alpha} t_f)
 
  // c'(r_f + d^{gamma-beta} t_g)
 
  p2 = p_Mult_q(m2, p2, r); // p2 = d^{gamma-beta} t_g
  p2 = p_Add_q(p2,HG,r); // p2 = r_g + d^{gamma-beta} t_g
  p2 = p_Mult_q(CC,p2,r); // p2 = c'(r_g + d^{gamma-beta} t_g)
 
#ifdef PDEBUG
  p_Test(p1,r);
  p_Test(p2,r);
  PrintS(" k'(r_f + d^{gamma-alpha} t_f): "); p_wrp(p1,r);
  PrintS(" c'(r_g + d^{gamma-beta} t_g): "); p_wrp(p2,r);
#endif
 
  poly out = p_Add_q(p1,p2,r); // delete p1, p2; // the sum
 
#ifdef PDEBUG
  p_Test(out,r);
#endif
 
  //  if ( out!=NULL ) pCleardenom(out); // postponed to enterS
  return(out);
}

nc_rat_ReduceSpolyNew()

poly nc_rat_ReduceSpolyNew	(	const poly	p1,
		poly	p2,
		int	ishift,
		const ring	r
	)

Definition at line 465 of file ratgring.cc.

{
  const long lCompP1 = p_GetComp(p1,r);
  const long lCompP2 = p_GetComp(p2,r);
 
  if ((lCompP1!=lCompP2) && (lCompP1!=0) && (lCompP2!=0))
  {
#ifdef PDEBUG
    WerrorS("nc_rat_ReduceSpolyNew: different non-zero components!");
#endif
    return(NULL);
  }
 
  if (p_LmIsConstantRat(p1,r))
  {
    return( NULL );
  }
 
 
  int is = ishift; /* TODO */
 
  poly m = pOne();
  p_ExpVectorDiffRat(m, p2, p1, ishift, r); // includes X and D parts
  //p_Setm(m,r);
  //  m = p_GetExp_k_n(m,1,ishift,r); /* rat D-exp of m */
#ifdef PDEBUG
  p_Test(m,r);
  PrintS("d^alpha = "); p_wrp(m,r); PrintLn();
#endif
 
  /* pSetComp(m,r)=0? */
  poly HH = NULL;
  poly H  = NULL;
  HH = p_HeadRat(p1,is,r); //p_Copy(p_HeadRat(p1,is,r),r); // lm_D(g)
//  H  = r->nc->p_Procs.mm_Mult_p(m, p_Copy(HH, r), r); // d^alpha lm_D(g)
  H  = nc_mm_Mult_p(m, HH, r); // d^alpha lm_D(g) == h_g in the paper
 
  poly K  = p_GetCoeffRat(H,  is, r); //p_Copy( p_GetCoeffRat(H,  is, r), r); // k in the paper
  poly P  = p_GetCoeffRat(p2, is, r); //p_Copy( p_GetCoeffRat(p2, is, r), r); // lc_D(p_2) == lc_D(f)
 
#ifdef PDEBUG
  PrintS("k: "); p_wrp(K,r); PrintS("\n");
  PrintS("p: "); p_wrp(P,r); PrintS("\n");
  PrintS("f: "); p_wrp(p2,r); PrintS("\n");
  PrintS("g: "); p_wrp(p1,r); PrintS("\n");
#endif
  // alt:
  poly out = p_Copy(p1,r);
  p_LmDeleteAndNextRat(&out, is, r); // out == t_g
 
  ideal ncsyz = ncGCD(P,K,r);
  poly KK = ncsyz->m[0]; ncsyz->m[0]=NULL; //p_Copy(ncsyz->m[0],r); // k'
  poly PP = ncsyz->m[1]; ncsyz->m[1]= NULL; //p_Copy(ncsyz->m[1],r); // p'
 
#ifdef PDEBUG
  PrintS("t_g: "); p_wrp(out,r);
  PrintS("k': "); p_wrp(KK,r); PrintS("\n");
  PrintS("p': "); p_wrp(PP,r); PrintS("\n");
#endif
  id_Delete(&ncsyz,r);
  p_LmDeleteAndNextRat(&p2, is, r); // t_f
  p_LmDeleteAndNextRat(&H, is, r); // r_g = h_g - lt_D(h_g)
 
#ifdef PDEBUG
  PrintS(" t_f: "); p_wrp(p2,r);
  PrintS(" r_g: "); p_wrp(H,r);
#endif
 
  p2 = p_Mult_q(KK, p2, r); // p2 = k' t_f
 
#ifdef PDEBUG
  p_Test(p2,r);
  PrintS(" k' t_f: "); p_wrp(p2,r);
#endif
 
//  out = r->nc->p_Procs.mm_Mult_p(m, out, r); // d^alpha t_g
  out = nc_mm_Mult_p(m, out, r); // d^alpha t_g
  p_Delete(&m,r);
 
#ifdef PDEBUG
  PrintS(" d^a t_g: "); p_wrp(out,r);
  PrintS(" end reduction\n");
#endif
 
  out = p_Add_q(H, out, r); // r_g + d^a t_g
 
#ifdef PDEBUG
  p_Test(out,r);
#endif
  out = p_Mult_q(PP, out, r); // p' (r_g + d^a t_g)
  out = p_Add_q(p2,out,r); // delete out, p2; // the sum
 
#ifdef PDEBUG
  p_Test(out,r);
#endif
 
  //  if ( out!=NULL ) pCleardenom(out); // postponed to enterS
  return(out);
}

ncGCD()

ideal ncGCD	(	poly	p,
		poly	q,
		const ring	r
	)

Definition at line 160 of file ratgring.cc.

{
  // destroys p and q
  // assume: p,q are in the comm. ring
  // to be used in the coeff business
#ifdef PDEBUG
  PrintS(" GCD_start:");
#endif
  poly g = singclap_gcd(p_Copy(p,r),p_Copy(q,r), r);
#ifdef PDEBUG
  p_wrp(g,r);
  PrintS(" GCD_end;\n");
#endif
  poly u = singclap_pdivide(q, g, r); //q/g
  poly v = singclap_pdivide(p, g, r); //p/g
  v = p_Neg(v,r);
  p_Delete(&p,r);
  p_Delete(&q,r);
  ideal h = idInit(2,1);
  h->m[0] = u; // p_Copy(u,r);
  h->m[1] = v; // p_Copy(v,r);
  return(h);
}

ncGCD2()

ideal ncGCD2	(	poly	p,
		poly	q,
		const ring	r
	)

Definition at line 112 of file ratgring.cc.

{
  // todo: must destroy p,q
  intvec *w = NULL;
  ideal h = idInit(2,1);
  h->m[0] = p_Copy(p,r);
  h->m[1] = p_Copy(q,r);
#ifdef PDEBUG
  PrintS("running syzygy comp. for nc_GCD:\n");
#endif
  ideal sh = idSyzygies(h, testHomog, &w);
#ifdef PDEBUG
  PrintS("done syzygy comp. for nc_GCD\n");
#endif
  /* in comm case, there is only 1 syzygy */
  /*   singclap_gcd(); */
  poly K, K1, K2;
  K  = sh->m[0]; /* take just the first element - to be enhanced later */
  K1 = pTakeOutComp(&K, 1); // 1st component is taken out from K
//  pShift(&K,-2); // 2nd component to 0th comp.
  K2 = pTakeOutComp(&K, 1);
//  K2 = K;
 
  PrintS("syz1: "); p_wrp(K1,r);
  PrintS("syz2: "); p_wrp(K2,r);
 
  /* checking signs before multiplying */
  number ck1 = p_GetCoeff(K1,r);
  number ck2 = p_GetCoeff(K2,r);
  BOOLEAN bck1, bck2;
  bck1 = n_GreaterZero(ck1,r);
  bck2 = n_GreaterZero(ck2,r);
  /* K1 <0, K2 <0 (-K1,-K2)    */
//   if ( !(bck1 && bck2) ) /* - , - */
//   {
//     K1 = p_Neg(K1,r);
//     K2 = p_Neg(K2,r);
//   }
  id_Delete(&h,r);
  h = idInit(2,1);
  h->m[0] = p_Copy(K1,r);
  h->m[1] = p_Copy(K2,r);
  id_Delete(&sh,r);
  return(h);
}

p_DivisibleByRat()

BOOLEAN p_DivisibleByRat	(	poly	a,
		poly	b,
		int	ishift,
		const ring	r
	)

Definition at line 569 of file ratgring.cc.

{
#ifdef PDEBUG
  PrintS("invoke p_DivByRat with a = ");
  p_wrp(p_Head(a,r),r);
  PrintS(" and b= ");
  p_wrp(p_Head(b,r),r);
  PrintLn();
#endif
  int i;
  for(i=r->N; i>ishift; i--)
  {
#ifdef PDEBUG
    Print("i=%d,",i);
#endif
    if (p_GetExp(a,i,r) > p_GetExp(b,i,r)) return FALSE;
  }
  return ((p_GetComp(a,r)==p_GetComp(b,r)) || (p_GetComp(a,r)==0));
}

p_ExpVectorDiffRat()

void p_ExpVectorDiffRat	(	poly	pr,
		poly	p1,
		poly	p2,
		int	ishift,
		ring	r
	)

Definition at line 81 of file ratgring.cc.

{
  p_LmCheckPolyRing1(p1, r);
  p_LmCheckPolyRing1(p2, r);
  p_LmCheckPolyRing1(pr, r);
  int i;
  poly t=pr;
  int e1,e2;
  for (i=ishift+1; i<=r->N; i++)
  {
    e1 = p_GetExp(p1, i, r);
    e2 = p_GetExp(p2, i, r);
    //    pAssume1(p_GetExp(p1, i, r) >= p_GetExp(p2, i, r));
    if (e1 < e2)
    {
#ifdef PDEBUG
      PrintS("negative ExpVectorDiff\n");
#endif
      p_Delete(&t,r);
      break;
    }
    else
    {
      p_SetExp(t,i, e1-e2,r);
    }
  }
  p_Setm(t,r);
}

p_HeadRat()

poly p_HeadRat	(	poly	p,
		int	ishift,
		ring	r
	)

Definition at line 64 of file ratgring.cc.

{
  poly q   = pNext(p);
  if (q == NULL) return p;
  poly res = p_Head(p,r);
  const long cmp = p_GetComp(p, r);
  while ( (q!=NULL) && (p_Comp_k_n(p, q, ishift+1, r)) && (p_GetComp(q, r) == cmp) )
  {
    res = p_Add_q(res,p_Head(q,r),r);
    q   = pNext(q);
  }
  p_SetCompP(res,cmp,r);
  return res;
}

p_LmIsConstantCompRat()

BOOLEAN p_LmIsConstantCompRat	(	const poly	p,
		const ring	r
	)

Definition at line 651 of file ratgring.cc.

{
  int i = r->real_var_end;
 
  while ( (p_GetExp(p,i,r)==0) && (i>=r->real_var_start))
  {
    i--;
  }
  return ( i+1 == r->real_var_start );
}

p_LmIsConstantRat()

BOOLEAN p_LmIsConstantRat	(	const poly	p,
		const ring	r
	)

Definition at line 642 of file ratgring.cc.

{
  if (p_LmIsConstantCompRat(p, r))
    return (p_GetComp(p, r) == 0);
  return FALSE;
}

pLcmRat()

void pLcmRat	(	poly	a,
		poly	b,
		poly	m,
		int	rat_shift
	)

Definition at line 30 of file ratgring.cc.

{
  /* rat_shift is the last exp one should count with */
  int i;
  for (i=(currRing->N); i>=rat_shift; i--)
  {
    pSetExp(m,i, si_max( pGetExp(a,i), pGetExp(b,i)));
  }
  pSetComp(m, si_max(pGetComp(a), pGetComp(b)));
  /* Don't do a pSetm here, otherwise hres/lres chockes */
}

redRat()

int redRat	(	poly *	h,
		poly *	reducer,
		int *	red_length,
		int	rl,
		int	ishift,
		ring	r
	)

Definition at line 593 of file ratgring.cc.

{
  if ((*h)==NULL) return 0;
 
  int j,i,l;
 
  loop
  {
    j=rl;l=MAX_INT_VAL;
    for(i=rl-1;i>=0;i--)
    {
      //      Print("test %d, l=%d (curr=%d, l=%d\n",i,red_length[i],j,l);
      if ((l>red_length[i]) && (p_DivisibleByRat(reducer[i],*h,ishift,r)))
      {
        j=i; l=red_length[i];
        //        PrintS(" yes\n");
      }
      //      else PrintS(" no\n");
    }
    if (j >=rl)
    {
      return 1; // not reducible
    }
 
    if (TEST_OPT_DEBUG)
    {
      PrintS("reduce ");
      p_wrp(*h,r);
      PrintS(" with ");
      p_wrp(reducer[j],r);
    }
    poly hh=nc_rat_ReduceSpolyNew(reducer[j], *h, ishift, r);
    //    p_Delete(h,r);
    *h=hh;
    if (TEST_OPT_DEBUG)
    {
      PrintS(" to ");
      p_wrp(*h,r);
      PrintLn();
    }
    if ((*h)==NULL)
    {
      return 0;
    }
  }
}