My Project  debian-1:4.1.1-p2+ds-4build2
Functions | Variables
tgbgauss.cc File Reference
#include "kernel/mod2.h"
#include "misc/options.h"
#include "kernel/GBEngine/tgbgauss.h"
#include "omalloc/omalloc.h"
#include <stdlib.h>
#include "kernel/GBEngine/kutil.h"
#include "kernel/polys.h"

Go to the source code of this file.

Functions

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)
 
void simple_gauss (tgb_sparse_matrix *mat, slimgb_alg *)
 
void simple_gauss2 (tgb_matrix *mat)
 
static int row_cmp_gen (const void *a, const void *b)
 

Variables

static const int bundle_size =100
 

Function Documentation

◆ mac_destroy()

void mac_destroy ( mac_poly  p)

Definition at line 114 of file tgbgauss.cc.

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

◆ mac_length()

int mac_length ( mac_poly  p)

Definition at line 103 of file tgbgauss.cc.

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

◆ mac_mult_cons()

void mac_mult_cons ( mac_poly  p,
number  c 
)

Definition at line 92 of file tgbgauss.cc.

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

◆ mac_p_add_ff_qq()

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

Definition at line 17 of file tgbgauss.cc.

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

◆ row_cmp_gen()

static int row_cmp_gen ( const void *  a,
const void *  b 
)
static

Definition at line 684 of file tgbgauss.cc.

685 {
686  const mac_poly ap= *((mac_poly*) a);
687  const mac_poly bp=*((mac_poly*) b);
688  if (ap==NULL) return 1;
689  if (bp==NULL) return -1;
690  if (ap->exp<bp->exp) return -1;
691  return 1;
692 }

◆ simple_gauss()

void simple_gauss ( tgb_sparse_matrix mat,
slimgb_alg  
)

Definition at line 126 of file tgbgauss.cc.

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

◆ simple_gauss2()

void simple_gauss2 ( tgb_matrix mat)

Definition at line 366 of file tgbgauss.cc.

367 {
368  int col, row;
369  col=0;
370  row=0;
371  int i;
372  int pn=mat->get_rows();
373  assume(pn>0);
374  //first clear zeroes
375 // for(i=0;i<pn;i++)
376 // {
377 // if(mat->zero_row(i))
378 // {
379 // mat->perm_rows(i,pn-1);
380 // pn--;
381 // if(i!=pn){i--;}
382 // }
383 // }
384  while((row<pn-1)&&(col<mat->get_columns())){
385  //row is the row where pivot should be
386  // row== pn-1 means we have only to act on one row so no red nec.
387  //we assume further all rows till the pn-1 row are non-zero
388 
389  //select column
390 
391  // col=mat->min_col_not_zero_in_row(row);
392  assume(col!=mat->get_columns());
393  int found_in_row=-1;
394 
395  // found_in_row=row;
396  assume(pn<=mat->get_rows());
397  for(i=row;i<pn;i++)
398  {
399  // int first=mat->min_col_not_zero_in_row(i);
400  // if(first<col)
401  if(!(mat->is_zero_entry(i,col)))
402  {
403  found_in_row=i;
404  break;
405  }
406  }
407  if(found_in_row!=-1)
408  {
409  //select pivot
410  int act_l=mat->non_zero_entries(found_in_row);
411  for(i=i+1;i<pn;i++)
412  {
413  int vgl;
414  assume(mat->min_col_not_zero_in_row(i)>=col);
415  if((!(mat->is_zero_entry(i,col)))
416  &&((vgl=mat->non_zero_entries(i))<act_l))
417  {
418  found_in_row=i;
419  act_l=vgl;
420  }
421 
422  }
423  mat->perm_rows(row,found_in_row);
424 
425  //reduction
426  for(i=row+1;i<pn;i++){
427  assume(mat->min_col_not_zero_in_row(i)>=col);
428  if(!(mat->is_zero_entry(i,col)))
429  {
430  number c1=nCopy(mat->get(i,col));
431  c1=nInpNeg(c1);
432  number c2=mat->get(row,col);
433  number n1=c1;
434  number n2=c2;
435 
436  ksCheckCoeff(&n1,&n2,currRing->cf);
437  nDelete(&c1);
438  mat->mult_row(i,n2);
439  mat->add_lambda_times_row(i,row,n1);
440  assume(mat->is_zero_entry(i,col));
441  }
442  assume(mat->min_col_not_zero_in_row(i)>col);
443  }
444  row++;
445  }
446  col++;
447  // for(i=row+1;i<pn;i++)
448 // {
449 // if(mat->zero_row(i))
450 // {
451 // mat->perm_rows(i,pn-1);
452 // pn--;
453 // if(i!=pn){i--;}
454 // }
455 // }
456  }
457 }

Variable Documentation

◆ bundle_size

const int bundle_size =100
static

Definition at line 15 of file tgbgauss.cc.

ksCheckCoeff
int ksCheckCoeff(number *a, number *b)
FALSE
#define FALSE
Definition: auxiliary.h:94
mac_poly_r::next
mac_poly_r * next
Definition: tgbgauss.h:51
tgb_sparse_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:799
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:261
tgb_sparse_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:910
tgb_sparse_matrix::perm_rows
void perm_rows(int i, int j)
Definition: tgbgauss.h:80
tgb_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:545
nAdd
#define nAdd(n1, n2)
Definition: numbers.h:19
tgb_sparse_matrix::mult_row
void mult_row(int row, number factor)
Definition: tgbgauss.cc:915
tgb_sparse_matrix::row_normalize
void row_normalize(int row)
Definition: tgbgauss.cc:832
tgb_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:604
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
b
CanonicalForm b
Definition: cfModGcd.cc:4044
ap
Definition: ap.h:39
tgb_sparse_matrix::sort_rows
void sort_rows()
Definition: tgbgauss.cc:694
next
ListNode * next
Definition: janet.h:31
nInpNeg
#define nInpNeg(n)
Definition: numbers.h:22
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
act
static scmon act
Definition: hdegree.cc:1078
mac_poly_r
Definition: tgbgauss.h:44
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
tgb_sparse_matrix::non_zero_entries
int non_zero_entries(int row)
Definition: tgbgauss.cc:904
tgb_matrix::get
number get(int i, int j)
Definition: tgbgauss.cc:538
h
static Poly * h
Definition: janet.cc:972
bundle_size
static const int bundle_size
Definition: tgbgauss.cc:15
tgb_sparse_matrix::get_columns
int get_columns()
Definition: tgbgauss.cc:762
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
tgb_matrix::mult_row
void mult_row(int row, number factor)
Definition: tgbgauss.cc:620
tgb_sparse_matrix::get_rows
int get_rows()
Definition: tgbgauss.cc:757
last
static poly last
Definition: hdegree.cc:1077
tgb_matrix::perm_rows
void perm_rows(int i, int j)
Definition: tgbgauss.cc:550
mac_poly_r::exp
int exp
Definition: tgbgauss.h:52
nIsZero
#define nIsZero(n)
Definition: numbers.h:20
nMult
#define nMult(n1, n2)
Definition: numbers.h:18
tgb_sparse_matrix::row_content
void row_content(int row)
Definition: tgbgauss.cc:848
m
int m
Definition: cfEzgcd.cc:121
tgb_matrix::get_rows
int get_rows()
Definition: tgbgauss.cc:528
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
tgb_matrix::non_zero_entries
int non_zero_entries(int row)
Definition: tgbgauss.cc:591
l
int l
Definition: cfEzgcd.cc:93
nDelete
#define nDelete(n)
Definition: numbers.h:17
tgb_sparse_matrix::get
number get(int i, int j)
Definition: tgbgauss.cc:767
p
int p
Definition: cfModGcd.cc:4019
tgb_sparse_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:783
mac_poly_r::coef
number coef
Definition: tgbgauss.h:50
tgb_matrix::get_columns
int get_columns()
Definition: tgbgauss.cc:533
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
nCopy
#define nCopy(n)
Definition: numbers.h:16
tgb_sparse_matrix::zero_row
BOOLEAN zero_row(int row)
Definition: tgbgauss.cc:823
tgb_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:558
nSize
#define nSize(n)
Definition: numbers.h:40