My Project  debian-1:4.1.2-p1+ds-2
Data Structures | Typedefs | Functions
tgbgauss.h File Reference
#include "coeffs/numbers.h"
#include "polys/monomials/p_polys.h"
#include "omalloc/omalloc.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 57 of file tgbgauss.h.

Function Documentation

◆ mac_destroy()

void mac_destroy ( mac_poly  p)

Definition at line 112 of file tgbgauss.cc.

114 {
115  mac_poly iter=p;
116  while(iter)
117  {
118  mac_poly next=iter->next;
119  nDelete(&iter->coef);
120  delete iter;
121  iter=next;
122  }

◆ mac_length()

int mac_length ( mac_poly  p)

Definition at line 101 of file tgbgauss.cc.

103 {
104  int l=0;
105  while(p){
106  l++;
107  p=p->next;
108  }
109  return l;

◆ mac_mult_cons()

void mac_mult_cons ( mac_poly  p,
number  c 
)

Definition at line 90 of file tgbgauss.cc.

92 {
93  while(p)
94  {
95  number m=nMult(p->coef,c);
96  nDelete(&(p->coef));
97  p->coef=m;
98  p=p->next;
99  }

◆ mac_p_add_ff_qq()

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

Definition at line 15 of file tgbgauss.cc.

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

◆ simple_gauss()

void simple_gauss ( tgb_sparse_matrix mat,
slimgb_alg c 
)

Definition at line 124 of file tgbgauss.cc.

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

◆ simple_gauss2()

void simple_gauss2 ( tgb_matrix mat)

Definition at line 364 of file tgbgauss.cc.

366 {
367  int col, row;
368  col=0;
369  row=0;
370  int i;
371  int pn=mat->get_rows();
372  assume(pn>0);
373  //first clear zeroes
374 // for(i=0;i<pn;i++)
375 // {
376 // if(mat->zero_row(i))
377 // {
378 // mat->perm_rows(i,pn-1);
379 // pn--;
380 // if(i!=pn){i--;}
381 // }
382 // }
383  while((row<pn-1)&&(col<mat->get_columns())){
384  //row is the row where pivot should be
385  // row== pn-1 means we have only to act on one row so no red nec.
386  //we assume further all rows till the pn-1 row are non-zero
387 
388  //select column
389 
390  // col=mat->min_col_not_zero_in_row(row);
391  assume(col!=mat->get_columns());
392  int found_in_row=-1;
393 
394  // found_in_row=row;
395  assume(pn<=mat->get_rows());
396  for(i=row;i<pn;i++)
397  {
398  // int first=mat->min_col_not_zero_in_row(i);
399  // if(first<col)
400  if(!(mat->is_zero_entry(i,col)))
401  {
402  found_in_row=i;
403  break;
404  }
405  }
406  if(found_in_row!=-1)
407  {
408  //select pivot
409  int act_l=mat->non_zero_entries(found_in_row);
410  for(i=i+1;i<pn;i++)
411  {
412  int vgl;
413  assume(mat->min_col_not_zero_in_row(i)>=col);
414  if((!(mat->is_zero_entry(i,col)))
415  &&((vgl=mat->non_zero_entries(i))<act_l))
416  {
417  found_in_row=i;
418  act_l=vgl;
419  }
420 
421  }
422  mat->perm_rows(row,found_in_row);
423 
424  //reduction
425  for(i=row+1;i<pn;i++){
426  assume(mat->min_col_not_zero_in_row(i)>=col);
427  if(!(mat->is_zero_entry(i,col)))
428  {
429  number c1=nCopy(mat->get(i,col));
430  c1=nInpNeg(c1);
431  number c2=mat->get(row,col);
432  number n1=c1;
433  number n2=c2;
434 
435  ksCheckCoeff(&n1,&n2,currRing->cf);
436  nDelete(&c1);
437  mat->mult_row(i,n2);
438  mat->add_lambda_times_row(i,row,n1);
439  assume(mat->is_zero_entry(i,col));
440  }
441  assume(mat->min_col_not_zero_in_row(i)>col);
442  }
443  row++;
444  }
445  col++;
446  // for(i=row+1;i<pn;i++)
447 // {
448 // if(mat->zero_row(i))
449 // {
450 // mat->perm_rows(i,pn-1);
451 // pn--;
452 // if(i!=pn){i--;}
453 // }
454 // }
455  }
ksCheckCoeff
int ksCheckCoeff(number *a, number *b)
FALSE
#define FALSE
Definition: auxiliary.h:96
mac_poly_r::next
mac_poly_r * next
Definition: tgbgauss.h:50
tgb_sparse_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:797
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:259
tgb_sparse_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:908
tgb_sparse_matrix::perm_rows
void perm_rows(int i, int j)
Definition: tgbgauss.h:79
last
STATIC_VAR poly last
Definition: hdegree.cc:1076
tgb_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:543
nAdd
#define nAdd(n1, n2)
Definition: numbers.h:17
tgb_sparse_matrix::mult_row
void mult_row(int row, number factor)
Definition: tgbgauss.cc:913
h
STATIC_VAR Poly * h
Definition: janet.cc:971
tgb_sparse_matrix::row_normalize
void row_normalize(int row)
Definition: tgbgauss.cc:830
tgb_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:602
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
b
CanonicalForm b
Definition: cfModGcd.cc:4044
tgb_sparse_matrix::sort_rows
void sort_rows()
Definition: tgbgauss.cc:692
next
ListNode * next
Definition: janet.h:31
nInpNeg
#define nInpNeg(n)
Definition: numbers.h:20
TRUE
#define TRUE
Definition: auxiliary.h:100
i
int i
Definition: cfEzgcd.cc:125
mac_poly_r
Definition: tgbgauss.h:43
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:87
tgb_sparse_matrix::non_zero_entries
int non_zero_entries(int row)
Definition: tgbgauss.cc:902
tgb_matrix::get
number get(int i, int j)
Definition: tgbgauss.cc:536
bundle_size
static const int bundle_size
Definition: tgbgauss.cc:13
tgb_sparse_matrix::get_columns
int get_columns()
Definition: tgbgauss.cc:760
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
tgb_matrix::mult_row
void mult_row(int row, number factor)
Definition: tgbgauss.cc:618
tgb_sparse_matrix::get_rows
int get_rows()
Definition: tgbgauss.cc:755
tgb_matrix::perm_rows
void perm_rows(int i, int j)
Definition: tgbgauss.cc:548
mac_poly_r::exp
int exp
Definition: tgbgauss.h:51
nIsZero
#define nIsZero(n)
Definition: numbers.h:18
nMult
#define nMult(n1, n2)
Definition: numbers.h:16
tgb_sparse_matrix::row_content
void row_content(int row)
Definition: tgbgauss.cc:846
act
STATIC_VAR scmon act
Definition: hdegree.cc:1077
m
int m
Definition: cfEzgcd.cc:121
tgb_matrix::get_rows
int get_rows()
Definition: tgbgauss.cc:526
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:11
tgb_matrix::non_zero_entries
int non_zero_entries(int row)
Definition: tgbgauss.cc:589
l
int l
Definition: cfEzgcd.cc:93
nDelete
#define nDelete(n)
Definition: numbers.h:15
tgb_sparse_matrix::get
number get(int i, int j)
Definition: tgbgauss.cc:765
p
int p
Definition: cfModGcd.cc:4019
tgb_sparse_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:781
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
mac_poly_r::coef
number coef
Definition: tgbgauss.h:49
tgb_matrix::get_columns
int get_columns()
Definition: tgbgauss.cc:531
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:585
nCopy
#define nCopy(n)
Definition: numbers.h:14
tgb_sparse_matrix::zero_row
BOOLEAN zero_row(int row)
Definition: tgbgauss.cc:821
tgb_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:556
nSize
#define nSize(n)
Definition: numbers.h:38