My Project  debian-1:4.1.1-p2+ds-4build1
Functions | Variables
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"

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

◆ iv2array()

short* iv2array ( intvec iv,
const ring  R 
)

Definition at line 205 of file weight.cc.

207 {
208  short *s=(short *)omAlloc0((rVar(R)+1)*sizeof(short));
209  int len=0;
210  if(iv!=NULL)
211  len=si_min(iv->length(),rVar(R)); // usually: rVar(R)==length()
212  int i;
213  //for(i=pVariables;i>len;i--) s[i]=1;
214  for(i=len;i>0;i--) s[i]=(*iv)[i-1];
215  return s;

◆ kEcartWeights()

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

Definition at line 187 of file weight.cc.

189 {
190  int n, i;
191  int *x;
192 
193  *eweight = 0;
194  n = rVar(R);
197  else
199  x = (int * )omAlloc(2 * (n + 1) * sizeof(int));
200  wCall(s, sl, x, (double)2.0 / (double)n, R);
201  for (i = n; i!=0; i--)
202  eweight[i] = x[i + n + 1];
203  omFreeSize((ADDRESS)x, 2 * (n + 1) * sizeof(int));

◆ maxdegreeWecart()

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

Definition at line 252 of file weight.cc.

254 {
255  short k=p_GetComp(p, r);
256  int ll=1;
257  long t,max;
258 
259  max=totaldegreeWecart(p, r);
260  pIter(p);
261  while ((p!=NULL) && (p_GetComp(p, r)==k))
262  {
263  t=totaldegreeWecart(p, r);
264  if (t>max) max=t;
265  ll++;
266  pIter(p);
267  }
268  *l=ll;
269  return max;

◆ totaldegreeWecart()

long totaldegreeWecart ( poly  p,
ring  r 
)

Definition at line 222 of file weight.cc.

224 {
225  int i;
226  long j =0;
227 
228  for (i=rVar(r); i>0; i--)
229  j += (int)(p_GetExp(p,i,r) * ecartWeights[i]);
230  return j;

◆ totaldegreeWecart_IV()

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

Definition at line 236 of file weight.cc.

238 {
239  int i;
240  long j =0;
241 
242  for (i=rVar(r); i>0; i--)
243  j += (long)((int)(p_GetExp(p,i,r) * w[i]));
244  return j;

◆ wAdd()

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

Definition at line 131 of file weight0.c.

133 {
134  int i, *B, *ex;
135 
136  B = A + ((kn - 1) * mons);
137  ex = A + (rvar * mons);
138  i = mons;
139  if (xx == 1)
140  {
141  for (/* i=mons */; i!=0 ; i--)
142  *ex++ += *B++;
143  }
144  else
145  {
146  for (/* i=mons */; i!=0 ; i--)
147  *ex++ += (*B++) * xx;
148  }

◆ wCall()

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

Definition at line 113 of file weight.cc.

115 {
116  int n, q, npol, mons, i;
117  int *A, *xopt, *lpol, *degw;
118  double f1, fx, eps, *rel;
119  void *adr;
120 
121  n = rVar(R);
122  lpol = (int * )omAlloc((sl + 1) * sizeof(int));
123  wDimensions(s, sl, lpol, &npol, &mons);
124  xopt = x + (n + 1);
125  for (i = n; i!=0; i--)
126  xopt[i] = 1;
127  if (mons==0)
128  {
129  omFreeSize((ADDRESS)lpol, (sl + 1) * sizeof(int));
130  return;
131  }
132  adr = (void * )omAllocAligned(npol * sizeof(double));
133  rel = (double*)adr;
134  q = (n + 1) * mons * sizeof(int);
135  A = (int * )omAlloc(q);
136  wInit(s, sl, mons, A, R);
137  degw = A + (n * mons);
138  memset(degw, 0, mons * sizeof(int));
139  for (i = n; i!=0; i--)
140  wAdd(A, mons, i, 1, rVar(R));
141  wNorm(degw, lpol, npol, rel);
142  f1 = (*wFunctional)(degw, lpol, npol, rel, (double)1.0, wNsqr);
143  if (TEST_OPT_PROT) Print("// %e\n",f1);
144  eps = f1;
145  fx = (double)2.0 * eps;
146  memset(x, 0, (n + 1) * sizeof(int));
147  wFirstSearch(A, x, mons, lpol, npol, rel, &fx, wNsqr, rVar(R));
148  if (TEST_OPT_PROT) Print("// %e\n",fx);
149  memcpy(x + 1, xopt + 1, n * sizeof(int));
150  memset(degw, 0, mons * sizeof(int));
151  for (i = n; i!=0; i--)
152  {
153  x[i] *= 16;
154  wAdd(A, mons, i, x[i], rVar(R));
155  }
156  wSecondSearch(A, x, lpol, npol, mons, rel, &fx, wNsqr, rVar(R));
157  if (TEST_OPT_PROT) Print("// %e\n",fx);
158  if (fx >= eps)
159  {
160  for (i = n; i!=0; i--)
161  xopt[i] = 1;
162  }
163  else
164  {
165  wGcd(xopt, n);
166 // if (BTEST1(22))
167 // {
168 // f1 = fx + (double)0.1 * (f1 - fx);
169 // wSimple(x, n);
170 // memset(degw, 0, mons * sizeof(int));
171 // for (i = n; i!=0; i--)
172 // wAdd(A, mons, i, x[i], rVar(R));
173 // eps = wPrWeight(x, n);
174 // fx = (*wFunctional)(degw, lpol, npol, rel, eps);
175 // if (fx < f1)
176 // {
177 // if (TEST_OPT_PROT) Print("// %e\n",fx);
178 // memcpy(xopt + 1, x + 1, n * sizeof(int));
179 // }
180 // }
181  }
182  omFreeSize((ADDRESS)A, q);
183  omFreeSize((ADDRESS)lpol, (sl + 1) * sizeof(int));
184  omFreeSize((ADDRESS)adr, npol * sizeof(double));

◆ wDimensions()

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

Definition at line 39 of file weight.cc.

41 {
42  int i, i1, j, k;
43  poly p, q;
44 
45  i1 = j = 0;
46  for (i = 0; i <= sl; i++)
47  {
48  p = s[i];
49  if (p!=NULL)
50  {
51  k = 1;
52  q = pNext(p);
53  while (q!=NULL)
54  {
55  k++;
56  q = pNext(q);
57  }
58  if (k > 1)
59  {
60  lpol[i1++] = k;
61  j += k;
62  }
63  }
64  }
65  *npol = i1;
66  *mons = j;

◆ wFirstSearch()

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

Definition at line 151 of file weight0.c.

154 {
155  int a0, a, n, xn, t, xx, y1;
156  int *y, *degw, *xopt;
157  double fy, fmax, wx;
158  double *pr;
159  void *adr;
160 
161  fy = *fopt;
162  n = rvar;
163  xn = n + 6 + (21 / n);
164  a0 = n * sizeof(double);
165  a = n * sizeof(int);
166  y = (int * )omAlloc((long)a);
167  adr = (void * )omAllocAligned((long)a0);
168  pr = adr;
169  *pr = (double)1.0;
170  *y = 0;
171  degw = A + (n * mons);
172  xopt = x + (n + 2);
173  t = 1;
174  loop
175  {
176  while (t < n)
177  {
178  xx = x[t] + 1;
179  wx = pr[t-1] * (double)xx;
180  y1 = y[t-1] + xx;
181  if ((y1 + n - t) <= xn)
182  {
183  pr[t] = wx;
184  y[t] = y1;
185  x[t] = xx;
186  if (xx > 1)
187  wAdd(A, mons, t, 1, rvar);
188  t++;
189  }
190  else
191  {
192  xx = x[t] - 1;
193  x[t] = 0;
194  if (xx!=0)
195  wSub(A, mons, t, xx, rvar);
196  t--;
197  if (t==0)
198  {
199  *fopt = fy;
200  omFreeSize((ADDRESS)y, (long)a);
201  omFreeSize((ADDRESS)adr, (long)a0);
202  return;
203  }
204  }
205  }
206  xx = xn - y[t-1];
207  wx = pr[t-1] * (double)xx;
208  x[t] = xx;
209  xx--;
210  if (xx!=0)
211  wAdd(A, mons, t, xx, rvar);
212  fmax = (*wFunctional)(degw, lpol, npol, rel, wx,wNsqr);
213  if (xx!=0)
214  wSub(A, mons, t, xx, rvar);
215  if (fmax < fy)
216  {
217  fy = fmax;
218  memcpy(xopt, x + 1, a);
219  }
220  t--;
221  } /* end loop */

◆ wFunctionalBuch()

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

Definition at line 77 of file weight0.c.

80 {
81  int i, j, ecl, ecu, ec;
82  int *ex;
83  double gfmax, ghom, pfmax;
84  double *r;
85 
86  ex = degw;
87  r = rel;
88  gfmax = (double)0.0;
89  ghom = (double)1.0;
90  for (i = 0; i < npol; i++)
91  {
92  ecu = ecl = *ex++;
93  for (j = lpol[i] - 1; j!=0 ; j--)
94  {
95  ec = *ex++;
96  if (ec < ecl)
97  ecl = ec;
98  else if (ec > ecu)
99  ecu = ec;
100  }
101  pfmax = (double)ecl / (double)ecu;
102  if (pfmax < ghom)
103  ghom = pfmax;
104  gfmax += (double)(ecu * ecu) * (*r++);
105  }
106  if (ghom > (double)0.5)
107  gfmax *= ((double)1.0 - (ghom * ghom)) / (double)0.75;
108  return gfmax / pow(wx, wNsqr);

◆ wFunctionalMora()

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

Definition at line 33 of file weight0.c.

36 {
37  int i, j, e1, ecu, ecl, ec;
38  int *ex;
39  double gfmax, gecart, ghom, pfmax;
40  double *r;
41 
42  ex = degw;
43  r = rel;
44  gfmax = (double)0.0;
45  gecart = (double)0.4 + (double)npol;
46  ghom = (double)1.0;
47  for (i = 0; i < npol; i++)
48  {
49  ecl = ecu = e1 = *ex++;
50  for (j = lpol[i] - 1; j!=0; j--)
51  {
52  ec = *ex++;
53  if (ec > ecu)
54  ecu = ec;
55  else if (ec < ecl)
56  ecl = ec;
57  }
58  pfmax = (double)ecl / (double)ecu;
59  if (pfmax < ghom)
60  ghom = pfmax;
61  pfmax = (double)e1 / (double)ecu;
62  if (pfmax > (double)0.5)
63  gecart -= (pfmax * pfmax);
64  else
65  gecart -= (double)0.25;
66  ecu = 2 * ecu - ecl;
67  gfmax += (double)(ecu * ecu) * (*r++);
68  }
69  if (ghom > (double)0.8)
70  {
71  ghom *= (double)5.0;
72  gecart *= ((double)5.0 - ghom);
73  }
74  return (gfmax * gecart) / pow(wx, wNsqr);

◆ wGcd()

void wGcd ( int *  x,
int  n 
)

Definition at line 351 of file weight0.c.

353 {
354  int i, b, a, h;
355 
356  i = n;
357  b = x[i];
358  loop
359  {
360  i--;
361  if (i==0)
362  break;
363  a = x[i];
364  if (a < b)
365  {
366  h = a;
367  a = b;
368  b = h;
369  }
370  do
371  {
372  h = a % b;
373  a = b;
374  b = h;
375  }
376  while (b!=0);
377  b = a;
378  if (b == 1)
379  return;
380  }
381  for (i = n; i!=0 ; i--)
382  x[i] /= b;

◆ wInit()

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

Definition at line 69 of file weight.cc.

71 {
72  int n, a, i, j, *B, *C;
73  poly p, q;
74  int *pl;
75 
76  B = A;
77  n = rVar(R);
78  a = (n + 1) * sizeof(int);
79  pl = (int *)omAlloc(a);
80  for (i = 0; i <= sl; i++)
81  {
82  p = s[i];
83  if (p!=NULL)
84  {
85  q = pNext(p);
86  if (q!=NULL)
87  {
88  C = B;
89  B++;
90  p_GetExpV(p, pl,R);
91  for (j = 0; j < n; j++)
92  {
93  *C = pl[j+1];
94  C += mons;
95  }
96  }
97  while (q!=NULL)
98  {
99  C = B;
100  B++;
101  p_GetExpV(q, pl,R);
102  for (j = 0; j < n; j++)
103  {
104  *C = pl[j+1];
105  C += mons;
106  }
107  pIter(q);
108  }
109  }
110  }
111  omFreeSize((ADDRESS)pl, a);

◆ wNorm()

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

Definition at line 462 of file weight0.c.

464 {
465  int i, j, ecu, ec;
466  int *ex;
467  double *r;
468 
469  ex = degw;
470  r = rel;
471  for (i = 0; i < npol; i++)
472  {
473  ecu = *ex++;
474  for (j = lpol[i] - 1; j!=0 ; j--)
475  {
476  ec = *ex++;
477  if (ec > ecu)
478  ecu = ec;
479  }
480  *r = (double)1.0 / (double)(ecu * ecu);
481  r++;
482  }

◆ wSecondSearch()

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

Definition at line 294 of file weight0.c.

297 {
298  int n, s0, s1, s2, *xopt;
299  double fx, fopt, wx;
300 
301  n = rvar;
302  xopt = x + (n + 2);
303  fopt = *fk * (double)0.999999999999;
304  wx = wPrWeight(x, n);
305  loop
306  {
307  wEstimate(A, x, lpol, npol, mons, wx, rel, &fx, &s0, &s1, &s2, wNsqr, rvar);
308  if (fx > fopt)
309  {
310  if (s0!=0)
311  x[s0]--;
312  else if (s1!=0)
313  {
314  x[s1]--;
315  x[s2]--;
316  }
317  else
318  break;
319  }
320  else
321  {
322  fopt = fx;
323  if (s0!=0)
324  {
325  x[s0]--;
326  memcpy(xopt, x + 1, n * sizeof(int));
327  if (s1==0)
328  break;
329  }
330  else if (s1!=0)
331  {
332  x[s1]--;
333  x[s2]--;
334  memcpy(xopt, x + 1, n * sizeof(int));
335  }
336  else
337  break;
338  }
339  if (s0!=0)
340  wSub(A, mons, s0, 1, rvar);
341  else
342  {
343  wSub(A, mons, s1, 1, rvar);
344  wSub(A, mons, s2, 1, rvar);
345  }
346  wx = wPrWeight(x, n);
347  }
348  *fk = fopt;

Variable Documentation

◆ wFunctional

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

Definition at line 25 of file weight.cc.

si_min
static int si_min(const int a, const int b)
Definition: auxiliary.h:139
wFunctionalBuch
double wFunctionalBuch(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
Definition: weight0.c:77
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:68
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:457
j
int j
Definition: facHensel.cc:105
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:101
k
int k
Definition: cfEzgcd.cc:92
wPrWeight
static double wPrWeight(int *x, int n)
Definition: weight0.c:224
ecartWeights
short * ecartWeights
Definition: weight0.c:27
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
ADDRESS
void * ADDRESS
Definition: auxiliary.h:133
wAdd
void wAdd(int *A, int mons, int kn, int xx, int rvar)
Definition: weight0.c:131
omAllocAligned
#define omAllocAligned
Definition: omAllocDecl.h:271
totaldegreeWecart
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:222
loop
#define loop
Definition: structs.h:77
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
xn
int xn
Definition: walk.cc:4448
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
i
int i
Definition: cfEzgcd.cc:125
rHasLocalOrMixedOrdering
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:751
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
wSecondSearch
void wSecondSearch(int *A, int *x, int *lpol, int npol, int mons, double *rel, double *fk, double wNsqr, int rvar)
Definition: weight0.c:294
wFunctionalMora
double wFunctionalMora(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
Definition: weight0.c:33
h
static Poly * h
Definition: janet.cc:972
max
static int max(int a, int b)
Definition: fast_mult.cc:264
wSub
static void wSub(int *A, int mons, int kn, int xx, int rvar)
Definition: weight0.c:111
wAdd
void wAdd(int *A, int mons, int kn, int xx, int rvar)
Definition: weight0.c:131
pIter
#define pIter(p)
Definition: monomials.h:41
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
wEstimate
static void wEstimate(int *A, int *x, int *lpol, int npol, int mons, double wx, double *rel, double *fopt, int *s0, int *s1, int *s2, double wNsqr, int rvar)
Definition: weight0.c:236
p_GetExpV
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1448
wFunctional
double(* wFunctional)(int *degw, int *lpol, int npol, double *rel, double wx, double wNsqr)
Definition: weight.cc:25
wCall
void wCall(poly *s, int sl, int *x, double wNsqr, const ring R)
Definition: weight.cc:113
wDimensions
static void wDimensions(poly *s, int sl, int *lpol, int *npol, int *mons)
Definition: weight.cc:39
Print
#define Print
Definition: emacs.cc:79
B
b *CanonicalForm B
Definition: facBivar.cc:52
wFirstSearch
void wFirstSearch(int *A, int *x, int mons, int *lpol, int npol, double *rel, double *fopt, double wNsqr, int rvar)
Definition: weight0.c:151
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
wNorm
void wNorm(int *degw, int *lpol, int npol, double *rel)
Definition: weight0.c:462
wInit
static void wInit(poly *s, int sl, int mons, int *A, const ring R)
Definition: weight.cc:69
NULL
#define NULL
Definition: omList.c:9
l
int l
Definition: cfEzgcd.cc:93
R
#define R
Definition: sirandom.c:26
p
int p
Definition: cfModGcd.cc:4019
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
intvec::length
int length() const
Definition: intvec.h:92
wGcd
void wGcd(int *x, int n)
Definition: weight0.c:351
A
#define A
Definition: sirandom.c:23
pNext
#define pNext(p)
Definition: monomials.h:40
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209