Data Structures | Typedefs | Functions
tgbgauss.h File Reference
#include <coeffs/numbers.h>
#include <polys/monomials/p_polys.h>
#include <omalloc/omallocClass.h>

Go to the source code of this file.

Data Structures

class  tgb_matrix
 
class  mac_poly_r
 
class  tgb_sparse_matrix
 

Typedefs

typedef mac_poly_rmac_poly
 

Functions

void simple_gauss (tgb_sparse_matrix *mat, slimgb_alg *c)
 
void simple_gauss2 (tgb_matrix *mat)
 
mac_poly mac_p_add_ff_qq (mac_poly a, number f, mac_poly b)
 
void mac_mult_cons (mac_poly p, number c)
 
int mac_length (mac_poly p)
 
void mac_destroy (mac_poly p)
 

Typedef Documentation

§ mac_poly

typedef mac_poly_r* mac_poly

Definition at line 53 of file tgbgauss.h.

Function Documentation

§ mac_destroy()

void mac_destroy ( mac_poly  p)

Definition at line 116 of file tgbgauss.cc.

117 {
118  mac_poly iter=p;
119  while(iter)
120  {
121  mac_poly next=iter->next;
122  nDelete(&iter->coef);
123  delete iter;
124  iter=next;
125  }
126 }
return P p
Definition: myNF.cc:203
CFFListIterator iter
Definition: facAbsBiFact.cc:54
number coef
Definition: tgbgauss.h:45
mac_poly_r * next
Definition: tgbgauss.h:46
#define nDelete(n)
Definition: numbers.h:16
ListNode * next
Definition: janet.h:31

§ mac_length()

int mac_length ( mac_poly  p)

Definition at line 105 of file tgbgauss.cc.

106 {
107  int l=0;
108  while(p){
109  l++;
110  p=p->next;
111  }
112  return l;
113 }
mac_poly_r * next
Definition: tgbgauss.h:46
int l
Definition: cfEzgcd.cc:94

§ mac_mult_cons()

void mac_mult_cons ( mac_poly  p,
number  c 
)

Definition at line 94 of file tgbgauss.cc.

95 {
96  while(p)
97  {
98  number m=nMult(p->coef,c);
99  nDelete(&(p->coef));
100  p->coef=m;
101  p=p->next;
102  }
103 }
number coef
Definition: tgbgauss.h:45
mac_poly_r * next
Definition: tgbgauss.h:46
#define nMult(n1, n2)
Definition: numbers.h:17
int m
Definition: cfEzgcd.cc:119
#define nDelete(n)
Definition: numbers.h:16

§ mac_p_add_ff_qq()

mac_poly mac_p_add_ff_qq ( mac_poly  a,
number  f,
mac_poly  b 
)

Definition at line 19 of file tgbgauss.cc.

20 {
21  mac_poly erg;
22  mac_poly* set_this;
23  set_this=&erg;
24  while((a!=NULL) &&(b!=NULL))
25  {
26  if (a->exp<b->exp)
27  {
28  (*set_this)=a;
29  a=a->next;
30  set_this= &((*set_this)->next);
31  }
32  else
33  {
34  if (a->exp>b->exp)
35  {
36  mac_poly in =new mac_poly_r();
37  in->exp=b->exp;
38  in->coef=nMult(b->coef,f);
39  (*set_this)=in;
40  b=b->next;
41  set_this= &((*set_this)->next);
42  }
43  else
44  {
45  //a->exp==b->ecp
46  number n=nMult(b->coef,f);
47  number n2=nAdd(a->coef,n);
48  nDelete(&n);
49  nDelete(&(a->coef));
50  if (nIsZero(n2))
51  {
52  nDelete(&n2);
53  mac_poly ao=a;
54  a=a->next;
55  delete ao;
56  b=b->next;
57  }
58  else
59  {
60  a->coef=n2;
61  b=b->next;
62  (*set_this)=a;
63  a=a->next;
64  set_this= &((*set_this)->next);
65  }
66  }
67  }
68  }
69  if((a==NULL)&&(b==NULL))
70  {
71  (*set_this)=NULL;
72  return erg;
73  }
74  if (b==NULL)
75  {
76  (*set_this=a);
77  return erg;
78  }
79 
80  //a==NULL
81  while(b!=NULL)
82  {
83  mac_poly mp= new mac_poly_r();
84  mp->exp=b->exp;
85  mp->coef=nMult(f,b->coef);
86  (*set_this)=mp;
87  set_this=&(mp->next);
88  b=b->next;
89  }
90  (*set_this)=NULL;
91  return erg;
92 }
const poly a
Definition: syzextra.cc:212
int exp
Definition: tgbgauss.h:47
number coef
Definition: tgbgauss.h:45
mac_poly_r * next
Definition: tgbgauss.h:46
#define nMult(n1, n2)
Definition: numbers.h:17
FILE * f
Definition: checklibs.c:7
#define nDelete(n)
Definition: numbers.h:16
#define nIsZero(n)
Definition: numbers.h:19
#define NULL
Definition: omList.c:10
#define nAdd(n1, n2)
Definition: numbers.h:18

§ simple_gauss()

void simple_gauss ( tgb_sparse_matrix mat,
slimgb_alg c 
)

Definition at line 128 of file tgbgauss.cc.

129 {
130  int col, row;
131  int* row_cache=(int*) omAlloc(mat->get_rows()*sizeof(int));
132  col=0;
133  row=0;
134  int i;
135  int pn=mat->get_rows();
136  int matcol=mat->get_columns();
137  int* area=(int*) omAlloc(sizeof(int)*((matcol-1)/bundle_size+1));
138  const int max_area_index=(matcol-1)/bundle_size;
139  //rows are divided in areas
140  //if row begins with columns col, it is located in [area[col/bundle_size],area[col/bundle_size+1]-1]
141  assume(pn>0);
142  //first clear zeroes
143  for(i=0;i<pn;i++)
144  {
145  if(mat->zero_row(i))
146  {
147  mat->perm_rows(i,pn-1);
148  pn--;
149  if(i!=pn){i--;}
150  }
151 
152  }
153  mat->sort_rows();
154  for(i=0;i<pn;i++)
155  {
156  row_cache[i]=mat->min_col_not_zero_in_row(i);
157  // Print("row_cache:%d\n",row_cache[i]);
158  }
159  int last_area=-1;
160  for(i=0;i<pn;i++)
161  {
162  int this_area=row_cache[i]/bundle_size;
163  assume(this_area>=last_area);
164  if(this_area>last_area)
165  {
166  int j;
167  for(j=last_area+1;j<=this_area;j++)
168  area[j]=i;
169  last_area=this_area;
170  }
171  }
172  for(i=last_area+1;i<=max_area_index;i++)
173  {
174  area[i]=pn;
175  }
176  while(row<pn-1)
177  {
178  //row is the row where pivot should be
179  // row== pn-1 means we have only to act on one row so no red nec.
180  //we assume further all rows till the pn-1 row are non-zero
181 
182  //select column
183 
184  //col=mat->min_col_not_zero_in_row(row);
185  int max_in_area;
186  {
187  int tai=row_cache[row]/bundle_size;
188  assume(tai<=max_area_index);
189  if(tai==max_area_index)
190  max_in_area=pn-1;
191  else
192  max_in_area=area[tai+1]-1;
193  }
194  assume(row_cache[row]==mat->min_col_not_zero_in_row(row));
195  col=row_cache[row];
196 
197  assume(col!=matcol);
198  int found_in_row;
199 
200  found_in_row=row;
201  BOOLEAN must_reduce=FALSE;
202  assume(pn<=mat->get_rows());
203  for(i=row+1;i<=max_in_area;i++)
204  {
205  int first;//=mat->min_col_not_zero_in_row(i);
206  assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
207  first=row_cache[i];
208  assume(first!=matcol);
209  if(first<col)
210  {
211  col=first;
212  found_in_row=i;
213  must_reduce=FALSE;
214  }
215  else
216  {
217  if(first==col)
218  must_reduce=TRUE;
219  }
220  }
221  //select pivot
222  int act_l=nSize(mat->get(found_in_row,col))*mat->non_zero_entries(found_in_row);
223  if(must_reduce)
224  {
225  for(i=found_in_row+1;i<=max_in_area;i++)
226  {
227  assume(mat->min_col_not_zero_in_row(i)>=col);
228  assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
229 #ifndef SING_NDEBUG
230  int first=row_cache[i];
231  assume(first!=matcol);
232 #endif
233  // if((!(mat->is_zero_entry(i,col)))&&(mat->non_zero_entries(i)<act_l))
234  int nz;
235  if((row_cache[i]==col)&&((nz=nSize(mat->get(i,col))*mat->non_zero_entries(i))<act_l))
236  {
237  found_in_row=i;
238  act_l=nz;
239  }
240 
241  }
242  }
243  mat->perm_rows(row,found_in_row);
244  int h=row_cache[row];
245  row_cache[row]=row_cache[found_in_row];
246  row_cache[found_in_row]=h;
247 
248  if(!must_reduce)
249  {
250  row++;
251  continue;
252  }
253  //reduction
254  //must extract content and normalize here
255  mat->row_content(row);
256  mat->row_normalize(row);
257 
258  //for(i=row+1;i<pn;i++){
259  for(i=max_in_area;i>row;i--)
260  {
261  int col_area_index=col/bundle_size;
262  assume(col_area_index<=max_area_index);
263  assume(mat->min_col_not_zero_in_row(i)>=col);
264  assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
265 #ifndef SING_NDEBUG
266  int first=row_cache[i];
267  assume(first!=matcol);
268 #endif
269  if(row_cache[i]==col)
270  {
271 
272  number c1=mat->get(i,col);
273  number c2=mat->get(row,col);
274  number n1=c1;
275  number n2=c2;
276 
277  ksCheckCoeff(&n1,&n2,currRing->cf);
278  //nDelete(&c1);
279  n1=nInpNeg(n1);
280  mat->mult_row(i,n2);
281  mat->add_lambda_times_row(i,row,n1);
282  nDelete(&n1);
283  nDelete(&n2);
284  assume(mat->is_zero_entry(i,col));
285  row_cache[i]=mat->min_col_not_zero_in_row(i);
286  assume(mat->min_col_not_zero_in_row(i)>col);
287  if(row_cache[i]==matcol)
288  {
289  int index;
290  index=i;
291  int last_in_area;
292  int this_cai=col_area_index;
293  while(this_cai<max_area_index)
294  {
295  last_in_area=area[this_cai+1]-1;
296  int h_c=row_cache[last_in_area];
297  row_cache[last_in_area]=row_cache[index];
298  row_cache[index]=h_c;
299  mat->perm_rows(index,last_in_area);
300  index=last_in_area;
301  this_cai++;
302  area[this_cai]--;
303  }
304  mat->perm_rows(index,pn-1);
305  row_cache[index]=row_cache[pn-1];
306  row_cache[pn-1]=matcol;
307  pn--;
308  }
309  else
310  {
311  int index;
312  index=i;
313  int last_in_area;
314  int this_cai=col_area_index;
315  int final_cai=row_cache[index]/bundle_size;
316  assume(final_cai<=max_area_index);
317  while(this_cai<final_cai)
318  {
319  last_in_area=area[this_cai+1]-1;
320  int h_c=row_cache[last_in_area];
321  row_cache[last_in_area]=row_cache[index];
322  row_cache[index]=h_c;
323  mat->perm_rows(index,last_in_area);
324  index=last_in_area;
325  this_cai++;
326  area[this_cai]--;
327  }
328  }
329  }
330  else
331  assume(mat->min_col_not_zero_in_row(i)>col);
332  }
333 // for(i=row+1;i<pn;i++)
334 // {
335 // assume(mat->min_col_not_zero_in_row(i)==row_cache[i]);
336 // // if(mat->zero_row(i))
337 // assume(matcol==mat->get_columns());
338 // if(row_cache[i]==matcol)
339 // {
340 // assume(mat->zero_row(i));
341 // mat->perm_rows(i,pn-1);
342 // row_cache[i]=row_cache[pn-1];
343 // row_cache[pn-1]=matcol;
344 // pn--;
345 // if(i!=pn){i--;}
346 // }
347 // }
348 #ifdef TGB_DEBUG
349  {
350  int last=-1;
351  for(i=0;i<pn;i++)
352  {
353  int act=mat->min_col_not_zero_in_row(i);
354  assume(act>last);
355  }
356  for(i=pn;i<mat->get_rows();i++)
357  {
358  assume(mat->zero_row(i));
359  }
360  }
361 #endif
362  row++;
363  }
364  omFree(area);
365  omFree(row_cache);
366 }
void row_content(int row)
Definition: tgbgauss.cc:850
void row_normalize(int row)
Definition: tgbgauss.cc:834
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:785
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:801
#define FALSE
Definition: auxiliary.h:95
static poly last
Definition: hdegree.cc:1077
int ksCheckCoeff(number *a, number *b)
#define TRUE
Definition: auxiliary.h:99
#define omAlloc(size)
Definition: omAllocDecl.h:210
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:912
int j
Definition: myNF.cc:70
#define omFree(addr)
Definition: omAllocDecl.h:261
#define assume(x)
Definition: mod2.h:403
#define nInpNeg(n)
Definition: numbers.h:21
number get(int i, int j)
Definition: tgbgauss.cc:769
int i
Definition: cfEzgcd.cc:123
#define nDelete(n)
Definition: numbers.h:16
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
void perm_rows(int i, int j)
Definition: tgbgauss.h:74
void mult_row(int row, number factor)
Definition: tgbgauss.cc:917
BOOLEAN zero_row(int row)
Definition: tgbgauss.cc:825
#define nSize(n)
Definition: numbers.h:39
static scmon act
Definition: hdegree.cc:1078
int non_zero_entries(int row)
Definition: tgbgauss.cc:906
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:86
static const int bundle_size
Definition: tgbgauss.cc:17

§ simple_gauss2()

void simple_gauss2 ( tgb_matrix mat)

Definition at line 368 of file tgbgauss.cc.

369 {
370  int col, row;
371  col=0;
372  row=0;
373  int i;
374  int pn=mat->get_rows();
375  assume(pn>0);
376  //first clear zeroes
377 // for(i=0;i<pn;i++)
378 // {
379 // if(mat->zero_row(i))
380 // {
381 // mat->perm_rows(i,pn-1);
382 // pn--;
383 // if(i!=pn){i--;}
384 // }
385 // }
386  while((row<pn-1)&&(col<mat->get_columns())){
387  //row is the row where pivot should be
388  // row== pn-1 means we have only to act on one row so no red nec.
389  //we assume further all rows till the pn-1 row are non-zero
390 
391  //select column
392 
393  // col=mat->min_col_not_zero_in_row(row);
394  assume(col!=mat->get_columns());
395  int found_in_row=-1;
396 
397  // found_in_row=row;
398  assume(pn<=mat->get_rows());
399  for(i=row;i<pn;i++)
400  {
401  // int first=mat->min_col_not_zero_in_row(i);
402  // if(first<col)
403  if(!(mat->is_zero_entry(i,col)))
404  {
405  found_in_row=i;
406  break;
407  }
408  }
409  if(found_in_row!=-1)
410  {
411  //select pivot
412  int act_l=mat->non_zero_entries(found_in_row);
413  for(i=i+1;i<pn;i++)
414  {
415  int vgl;
416  assume(mat->min_col_not_zero_in_row(i)>=col);
417  if((!(mat->is_zero_entry(i,col)))
418  &&((vgl=mat->non_zero_entries(i))<act_l))
419  {
420  found_in_row=i;
421  act_l=vgl;
422  }
423 
424  }
425  mat->perm_rows(row,found_in_row);
426 
427  //reduction
428  for(i=row+1;i<pn;i++){
429  assume(mat->min_col_not_zero_in_row(i)>=col);
430  if(!(mat->is_zero_entry(i,col)))
431  {
432  number c1=nCopy(mat->get(i,col));
433  c1=nInpNeg(c1);
434  number c2=mat->get(row,col);
435  number n1=c1;
436  number n2=c2;
437 
438  ksCheckCoeff(&n1,&n2,currRing->cf);
439  nDelete(&c1);
440  mat->mult_row(i,n2);
441  mat->add_lambda_times_row(i,row,n1);
442  assume(mat->is_zero_entry(i,col));
443  }
444  assume(mat->min_col_not_zero_in_row(i)>col);
445  }
446  row++;
447  }
448  col++;
449  // for(i=row+1;i<pn;i++)
450 // {
451 // if(mat->zero_row(i))
452 // {
453 // mat->perm_rows(i,pn-1);
454 // pn--;
455 // if(i!=pn){i--;}
456 // }
457 // }
458  }
459 }
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:560
int ksCheckCoeff(number *a, number *b)
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:606
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
#define assume(x)
Definition: mod2.h:403
void perm_rows(int i, int j)
Definition: tgbgauss.cc:552
#define nInpNeg(n)
Definition: numbers.h:21
int i
Definition: cfEzgcd.cc:123
int get_rows()
Definition: tgbgauss.cc:530
number get(int i, int j)
Definition: tgbgauss.cc:540
#define nDelete(n)
Definition: numbers.h:16
void mult_row(int row, number factor)
Definition: tgbgauss.cc:622
int get_columns()
Definition: tgbgauss.cc:535
#define nCopy(n)
Definition: numbers.h:15
int non_zero_entries(int row)
Definition: tgbgauss.cc:593
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:547