weight.cc File Reference

#include <misc/auxiliary.h>
#include <omalloc/omalloc.h>
#include <misc/options.h>
#include <misc/intvec.h>
#include <polys/monomials/ring.h>
#include <polys/monomials/p_polys.h>
#include <polys/weight.h>
#include <math.h>

Go to the source code of this file.

Functions
double	wFunctionalMora (int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
double	wFunctionalBuch (int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
void	wAdd (int *A, int mons, int kn, int xx, int rvar)
void	wNorm (int *degw, int *lpol, int npol, double *rel)
void	wFirstSearch (int *A, int *x, int mons, int *lpol, int npol, double *rel, double *fopt, double wNsqr, int rvar)
void	wSecondSearch (int *A, int *x, int *lpol, int npol, int mons, double *rel, double *fk, double wNsqr, int rvar)
void	wGcd (int *x, int n)
static void	wDimensions (poly *s, int sl, int *lpol, int *npol, int *mons)
static void	wInit (poly *s, int sl, int mons, int *A, const ring R)
void	wCall (poly *s, int sl, int *x, double wNsqr, const ring R)
void	kEcartWeights (poly *s, int sl, short *eweight, const ring R)
short *	iv2array (intvec *iv, const ring R)
long	totaldegreeWecart (poly p, ring r)
long	totaldegreeWecart_IV (poly p, ring r, const short *w)
long	maxdegreeWecart (poly p, int *l, ring r)

Variables
double(*	wFunctional )(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)

Function Documentation

short* iv2array	(	intvec *	iv,
		const ring	R
	)

Definition at line 208 of file weight.cc.

{
  short *s=(short *)omAlloc0((rVar(R)+1)*sizeof(short));
  int len=0;
  if(iv!=NULL)
    len=si_min(iv->length(),rVar(R)); // usually: rVar(R)==length()
  int i;
  //for(i=pVariables;i>len;i--) s[i]=1;
  for(i=len;i>0;i--)               s[i]=(*iv)[i-1];
  return s;
}

void kEcartWeights	(	poly *	s,
		int	sl,
		short *	eweight,
		const ring	R
	)

Definition at line 190 of file weight.cc.

{
  int  n, i;
  int  *x;

  *eweight = 0;
  n = rVar(R);
  if (rHasLocalOrMixedOrdering(R))
    wFunctional = wFunctionalMora;
  else
    wFunctional = wFunctionalBuch;
  x = (int * )omAlloc(2 * (n + 1) * sizeof(int));
  wCall(s, sl, x, (double)2.0 / (double)n, R);
  for (i = n; i!=0; i--)
    eweight[i] = x[i + n + 1];
  omFreeSize((ADDRESS)x, 2 * (n + 1) * sizeof(int));
}

long maxdegreeWecart	(	poly	p,
		int *	l,
		ring	r
	)

Definition at line 255 of file weight.cc.

{
  short k=p_GetComp(p, r);
  int ll=1;
  long t,max;

  max=totaldegreeWecart(p, r);
  pIter(p);
  while ((p!=NULL) && (p_GetComp(p, r)==k))
  {
    t=totaldegreeWecart(p, r);
    if (t>max) max=t;
    ll++;
    pIter(p);
  }
  *l=ll;
  return max;
}

long totaldegreeWecart	(	poly	p,
		ring	r
	)

Definition at line 225 of file weight.cc.

{
  int i;
  long j =0;

  for (i=rVar(r); i>0; i--)
    j += (int)(p_GetExp(p,i,r) * ecartWeights[i]);
  return  j;
}

long totaldegreeWecart_IV	(	poly	p,
		ring	r,
		const short *	w
	)

Definition at line 239 of file weight.cc.

{
  int i;
  long j =0;

  for (i=rVar(r); i>0; i--)
    j += (long)((int)(p_GetExp(p,i,r) * w[i]));
  return  j;
}

void wAdd	(	int *	A,
		int	mons,
		int	kn,
		int	xx,
		int	rvar
	)

Definition at line 136 of file weight0.c.

{
  int  i, *B, *ex;

  B = A + ((kn - 1) * mons);
  ex = A + (rvar * mons);
  i = mons;
  if (xx == 1)
  {
    for (/* i=mons */; i!=0 ; i--)
      *ex++ += *B++;
  }
  else
  {
    for (/* i=mons */; i!=0 ; i--)
      *ex++ += (*B++) * xx;
  }
}

void wCall	(	poly *	s,
		int	sl,
		int *	x,
		double	wNsqr,
		const ring	R
	)

Definition at line 116 of file weight.cc.

{
  int  n, q, npol, mons, i;
  int  *A, *xopt, *lpol, *degw;
  double  f1, fx, eps, *rel;
  void *adr;

  n = rVar(R);
  lpol = (int * )omAlloc((sl + 1) * sizeof(int));
  wDimensions(s, sl, lpol, &npol, &mons);
  xopt = x + (n + 1);
  for (i = n; i!=0; i--)
    xopt[i] = 1;
  if (mons==0)
  {
    omFreeSize((ADDRESS)lpol, (sl + 1) * sizeof(int));
    return;
  }
  adr = (void * )omAllocAligned(npol * sizeof(double));
  rel = (double*)adr;
  q = (n + 1) * mons * sizeof(int);
  A = (int * )omAlloc(q);
  wInit(s, sl, mons, A, R);
  degw = A + (n * mons);
  memset(degw, 0, mons * sizeof(int));
  for (i = n; i!=0; i--)
    wAdd(A, mons, i, 1, rVar(R));
  wNorm(degw, lpol, npol, rel);
  f1 = (*wFunctional)(degw, lpol, npol, rel, (double)1.0, wNsqr);
  if (TEST_OPT_PROT) Print("// %e\n",f1);
  eps = f1;
  fx = (double)2.0 * eps;
  memset(x, 0, (n + 1) * sizeof(int));
  wFirstSearch(A, x, mons, lpol, npol, rel, &fx, wNsqr, rVar(R));
  if (TEST_OPT_PROT) Print("// %e\n",fx);
  memcpy(x + 1, xopt + 1, n * sizeof(int));
  memset(degw, 0, mons * sizeof(int));
  for (i = n; i!=0; i--)
  {
    x[i] *= 16;
    wAdd(A, mons, i, x[i], rVar(R));
  }
  wSecondSearch(A, x, lpol, npol, mons, rel, &fx, wNsqr, rVar(R));
  if (TEST_OPT_PROT) Print("// %e\n",fx);
  if (fx >= eps)
  {
    for (i = n; i!=0; i--)
      xopt[i] = 1;
  }
  else
  {
    wGcd(xopt, n);
//    if (BTEST1(22))
//    {
//      f1 = fx + (double)0.1 * (f1 - fx);
//      wSimple(x, n);
//      memset(degw, 0, mons * sizeof(int));
//      for (i = n; i!=0; i--)
//        wAdd(A, mons, i, x[i], rVar(R));
//      eps = wPrWeight(x, n);
//      fx = (*wFunctional)(degw, lpol, npol, rel, eps);
//      if (fx < f1)
//      {
//        if (TEST_OPT_PROT) Print("// %e\n",fx);
//        memcpy(xopt + 1, x + 1, n * sizeof(int));
//      }
//    }
  }
  omFreeSize((ADDRESS)A, q);
  omFreeSize((ADDRESS)lpol, (sl + 1) * sizeof(int));
  omFreeSize((ADDRESS)adr, npol * sizeof(double));
}

static void wDimensions ( poly *  s, int  sl, int *  lpol, int *  npol, int *  mons  )

static

Definition at line 42 of file weight.cc.

{
  int  i, i1, j, k;
  poly p, q;

  i1 = j = 0;
  for (i = 0; i <= sl; i++)
  {
    p = s[i];
    if (p!=NULL)
    {
      k = 1;
      q = pNext(p);
      while (q!=NULL)
      {
        k++;
        q = pNext(q);
      }
      if (k > 1)
      {
        lpol[i1++] = k;
        j += k;
      }
    }
  }
  *npol = i1;
  *mons = j;
}

void wFirstSearch	(	int *	A,
		int *	x,
		int	mons,
		int *	lpol,
		int	npol,
		double *	rel,
		double *	fopt,
		double	wNsqr,
		int	rvar
	)

Definition at line 156 of file weight0.c.

{
  int  a0, a, n, xn, t, xx, y1;
  int  *y, *degw, *xopt;
  double  fy, fmax, wx;
  double *pr;
  void *adr;

  fy = *fopt;
  n = rvar;
  xn = n + 6 + (21 / n);
  a0 = n * sizeof(double);
  a = n * sizeof(int);
  y = (int * )omAlloc((long)a);
  adr = (void * )omAllocAligned((long)a0);
  pr = adr;
  *pr = (double)1.0;
  *y = 0;
  degw = A + (n * mons);
  xopt = x + (n + 2);
  t = 1;
  loop
  {
    while (t < n)
    {
      xx = x[t] + 1;
      wx = pr[t-1] * (double)xx;
      y1 = y[t-1] + xx;
      if ((y1 + n - t) <= xn)
      {
        pr[t] = wx;
        y[t] = y1;
        x[t] = xx;
        if (xx > 1)
          wAdd(A, mons, t, 1, rvar);
        t++;
      }
      else
      {
        xx = x[t] - 1;
        x[t] = 0;
        if (xx!=0)
          wSub(A, mons, t, xx, rvar);
        t--;
        if (t==0)
        {
          *fopt = fy;
          omFreeSize((ADDRESS)y, (long)a);
          omFreeSize((ADDRESS)adr, (long)a0);
          return;
        }
      }
    }
    xx = xn - y[t-1];
    wx = pr[t-1] * (double)xx;
    x[t] = xx;
    xx--;
    if (xx!=0)
      wAdd(A, mons, t, xx, rvar);
    fmax = (*wFunctional)(degw, lpol, npol, rel, wx,wNsqr);
    if (xx!=0)
      wSub(A, mons, t, xx, rvar);
    if (fmax < fy)
    {
      fy = fmax;
      memcpy(xopt, x + 1, a);
    }
    t--;
  } /* end loop */
}

double wFunctionalBuch	(	int *	degw,
		int *	lpol,
		int	npol,
		double *	rel,
		double	wx,
		double	wNsqr
	)

Definition at line 82 of file weight0.c.

{
  int  i, j, ecl, ecu, ec;
  int  *ex;
  double gfmax, ghom, pfmax;
  double *r;

  ex = degw;
  r = rel;
  gfmax = (double)0.0;
  ghom = (double)1.0;
  for (i = 0; i < npol; i++)
  {
    ecu = ecl = *ex++;
    for (j = lpol[i] - 1; j!=0 ; j--)
    {
      ec = *ex++;
      if (ec < ecl)
        ecl = ec;
      else if (ec > ecu)
        ecu = ec;
    }
    pfmax = (double)ecl / (double)ecu;
    if (pfmax < ghom)
      ghom = pfmax;
    gfmax += (double)(ecu * ecu) * (*r++);
  }
  if (ghom > (double)0.5)
    gfmax *= ((double)1.0 - (ghom * ghom)) / (double)0.75;
  return gfmax / pow(wx, wNsqr);
}

double wFunctionalMora	(	int *	degw,
		int *	lpol,
		int	npol,
		double *	rel,
		double	wx,
		double	wNsqr
	)

Definition at line 38 of file weight0.c.

{
  int  i, j, e1, ecu, ecl, ec;
  int  *ex;
  double gfmax, gecart, ghom, pfmax;
  double *r;

  ex = degw;
  r = rel;
  gfmax = (double)0.0;
  gecart = (double)0.4 + (double)npol;
  ghom = (double)1.0;
  for (i = 0; i < npol; i++)
  {
    ecl = ecu = e1 = *ex++;
    for (j = lpol[i] - 1; j!=0; j--)
    {
      ec = *ex++;
      if (ec > ecu)
        ecu = ec;
      else if (ec < ecl)
        ecl = ec;
    }
    pfmax = (double)ecl / (double)ecu;
    if (pfmax < ghom)
      ghom = pfmax;
    pfmax = (double)e1 / (double)ecu;
    if (pfmax > (double)0.5)
      gecart -= (pfmax * pfmax);
    else
      gecart -= (double)0.25;
    ecu = 2 * ecu - ecl;
    gfmax += (double)(ecu * ecu) * (*r++);
  }
  if (ghom > (double)0.8)
  {
    ghom *= (double)5.0;
    gecart *= ((double)5.0 - ghom);
  }
  return (gfmax * gecart) / pow(wx, wNsqr);
}

void wGcd	(	int *	x,
		int	n
	)

Definition at line 356 of file weight0.c.

{
  int i, b, a, h;

  i = n;
  b = x[i];
  loop
  {
    i--;
    if (i==0)
      break;
    a = x[i];
    if (a < b)
    {
      h = a;
      a = b;
      b = h;
    }
    do
    {
      h = a % b;
      a = b;
      b = h;
    }
    while (b!=0);
    b = a;
    if (b == 1)
      return;
  }
  for (i = n; i!=0 ; i--)
    x[i] /= b;
}

static void wInit ( poly *  s, int  sl, int  mons, int *  A, const ring  R  )

static

Definition at line 72 of file weight.cc.

{
  int  n, a, i, j, *B, *C;
  poly p, q;
  int *pl;

  B = A;
  n = rVar(R);
  a = (n + 1) * sizeof(int);
  pl = (int *)omAlloc(a);
  for (i = 0; i <= sl; i++)
  {
    p = s[i];
    if (p!=NULL)
    {
      q = pNext(p);
      if (q!=NULL)
      {
        C = B;
        B++;
        p_GetExpV(p, pl,R);
        for (j = 0; j < n; j++)
        {
          *C = pl[j+1];
          C += mons;
        }
      }
      while (q!=NULL)
      {
        C = B;
        B++;
        p_GetExpV(q, pl,R);
        for (j = 0; j < n; j++)
        {
          *C = pl[j+1];
          C += mons;
        }
        pIter(q);
      }
    }
  }
  omFreeSize((ADDRESS)pl, a);
}

void wNorm	(	int *	degw,
		int *	lpol,
		int	npol,
		double *	rel
	)

Definition at line 467 of file weight0.c.

{
  int  i, j, ecu, ec;
  int  *ex;
  double *r;

  ex = degw;
  r = rel;
  for (i = 0; i < npol; i++)
  {
    ecu = *ex++;
    for (j = lpol[i] - 1; j!=0 ; j--)
    {
      ec = *ex++;
      if (ec > ecu)
        ecu = ec;
    }
    *r = (double)1.0 / (double)(ecu * ecu);
    r++;
  }
}

void wSecondSearch	(	int *	A,
		int *	x,
		int *	lpol,
		int	npol,
		int	mons,
		double *	rel,
		double *	fk,
		double	wNsqr,
		int	rvar
	)

Definition at line 299 of file weight0.c.

{
  int  n, s0, s1, s2, *xopt;
  double  fx, fopt, wx;

  n = rvar;
  xopt = x + (n + 2);
  fopt = *fk * (double)0.999999999999;
  wx = wPrWeight(x, n);
  loop
  {
    wEstimate(A, x, lpol, npol, mons, wx, rel, &fx, &s0, &s1, &s2, wNsqr, rvar);
    if (fx > fopt)
    {
      if (s0!=0)
        x[s0]--;
      else if (s1!=0)
      {
        x[s1]--;
        x[s2]--;
      }
      else
        break;
    }
    else
    {
      fopt = fx;
      if (s0!=0)
      {
        x[s0]--;
        memcpy(xopt, x + 1, n * sizeof(int));
        if (s1==0)
          break;
      }
      else if (s1!=0)
      {
        x[s1]--;
        x[s2]--;
        memcpy(xopt, x + 1, n * sizeof(int));
      }
      else
        break;
    }
    if (s0!=0)
      wSub(A, mons, s0, 1, rvar);
    else
    {
      wSub(A, mons, s1, 1, rvar);
      wSub(A, mons, s2, 1, rvar);
    }
    wx = wPrWeight(x, n);
  }
  *fk = fopt;
}

Variable Documentation

double(* wFunctional) (int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)

Definition at line 28 of file weight.cc.