witness.h File Reference

#include "polys/monomials/monomials.h"
#include "polys/simpleideals.h"

Go to the source code of this file.

Functions
matrix	divisionDiscardingRemainder (const poly f, const ideal G, const ring r)
	Computes a division discarding remainder of f with respect to G. More...
matrix	divisionDiscardingRemainder (const ideal F, const ideal G, const ring r)
	Computes a division discarding remainder of F with respect to G. More...
poly	witness (const poly m, const ideal I, const ideal inI, const ring r)
	Let w be the uppermost weight vector in the matrix defining the ordering on r. More...
ideal	witness (const ideal inI, const ideal J, const ring r)
	Computes witnesses in J for inI Given inI={h1,...,hl} and J={g1,...,gk} two sets of polynomials in r, returns a set I={f1,...,fl} of <g1,...,gk> such that in_w(fj)=hj for all j=1,...,l, where w denotes the uppoermost weight vector in the matrix defining the ordering on r. More...

Function Documentation

divisionDiscardingRemainder() [1/2]

matrix divisionDiscardingRemainder	(	const ideal	F,
		const ideal	G,
		const ring	r
	)

Computes a division discarding remainder of F with respect to G.

Given F={f1,...,fl} and G={g1,...,gk} two sets of polynomials in r, returns a matrix Q=(qij) i=1,..,k j=1,...,l over r such that fj = q1j*g1+...+qkj*gk+sj is a determinate division with remainder sj for all j=1,...,l.

Definition at line 21 of file witness.cc.

{
  ring origin = currRing;
  if (origin != r) rChangeCurrRing(r);
  ideal R; matrix U;
  ideal m = idLift(G,F,&R,FALSE,FALSE,TRUE,&U);
  matrix Q = id_Module2formatedMatrix(m,IDELEMS(G),IDELEMS(F),currRing);
  id_Delete(&R,r);
  mp_Delete(&U,r);
  if (origin != r) rChangeCurrRing(origin);
  return Q;
}

divisionDiscardingRemainder() [2/2]

matrix divisionDiscardingRemainder	(	const poly	f,
		const ideal	G,
		const ring	r
	)

Computes a division discarding remainder of f with respect to G.

Given f a polynomial and G={g1,...,gk} a set of polynomials in r, returns a matrix Q=(q1,...,qk) over r such that f = q1*g1+...+qk*gk+s is a determinate division with remainder s.

Definition at line 9 of file witness.cc.

{
  ring origin = currRing;
  if (origin != r) rChangeCurrRing(r);
  ideal F = idInit(1); F->m[0]=f;
  ideal m = idLift(G,F);
  F->m[0]=NULL; id_Delete(&F, currRing);
  matrix Q = id_Module2formatedMatrix(m,IDELEMS(G),1,currRing);
  if (origin != r) rChangeCurrRing(origin);
  return Q;
}

witness() [1/2]

ideal witness	(	const ideal	inI,
		const ideal	J,
		const ring	r
	)

Computes witnesses in J for inI Given inI={h1,...,hl} and J={g1,...,gk} two sets of polynomials in r, returns a set I={f1,...,fl} of <g1,...,gk> such that in_w(fj)=hj for all j=1,...,l, where w denotes the uppoermost weight vector in the matrix defining the ordering on r.

Assumes that hj is an element of <in_w(g1),...,in_w(gk)>

Definition at line 52 of file witness.cc.

{
  ring origin = currRing;
  if (origin!=r)
    rChangeCurrRing(r);
  ideal NFinI = kNF(J,r->qideal,inI);
  if (origin!=r)
    rChangeCurrRing(origin);
 
  int k = IDELEMS(inI);
  ideal I = idInit(k);
  for (int i=0; i<k; i++)
  {
    I->m[i] = p_Add_q(p_Copy(inI->m[i],r),p_Neg(NFinI->m[i],r),r);
    NFinI->m[i] = NULL;
  }
 
  assume(areIdealsEqual(I,r,J,r));
 
  return I;
}

witness() [2/2]

poly witness	(	const poly	m,
		const ideal	I,
		const ideal	inI,
		const ring	r
	)

Let w be the uppermost weight vector in the matrix defining the ordering on r.

Let I be a Groebner basis of an ideal in r, inI its initial form with respect w. Given an w-homogeneous element m of inI, computes a witness g of m in I, i.e. g in I such that in_w(g)=m.

Definition at line 34 of file witness.cc.

{
  assume(IDELEMS(I)==IDELEMS(inI));
  matrix Q = divisionDiscardingRemainder(m,inI,r);
 
  int k = IDELEMS(I);
  poly f = p_Mult_q(p_Copy(I->m[0],r),Q->m[0],r);
  Q->m[0] = NULL;
  for (int i=1; i<k; i++)
  {
    f = p_Add_q(f,p_Mult_q(p_Copy(I->m[i],r),Q->m[i],r),r);
    Q->m[i] = NULL;
  }
  mp_Delete(&Q,r);
 
  return f;
}