My Project
Loading...
Searching...
No Matches
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 58 of file tgbgauss.h.

Function Documentation

◆ mac_destroy()

void mac_destroy ( mac_poly  p)

Definition at line 113 of file tgbgauss.cc.

114{
116 while(iter)
117 {
118 mac_poly next=iter->next;
119 nDelete(&iter->coef);
120 delete iter;
121 iter=next;
122 }
123}
int p
Definition: cfModGcd.cc:4078
CFFListIterator iter
Definition: facAbsBiFact.cc:53
ListNode * next
Definition: janet.h:31
#define nDelete(n)
Definition: numbers.h:16

◆ mac_length()

int mac_length ( mac_poly  p)

Definition at line 102 of file tgbgauss.cc.

103{
104 int l=0;
105 while(p){
106 l++;
107 p=p->next;
108 }
109 return l;
110}
int l
Definition: cfEzgcd.cc:100

◆ mac_mult_cons()

void mac_mult_cons ( mac_poly  p,
number  c 
)

Definition at line 91 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 }
100}
int m
Definition: cfEzgcd.cc:128
#define nMult(n1, n2)
Definition: numbers.h:17

◆ mac_p_add_ff_qq()

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

Definition at line 16 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;
89}
CanonicalForm b
Definition: cfModGcd.cc:4103
FILE * f
Definition: checklibs.c:9
mac_poly_r * next
Definition: tgbgauss.h:51
number coef
Definition: tgbgauss.h:50
int exp
Definition: tgbgauss.h:52
#define nIsZero(n)
Definition: numbers.h:19
#define nAdd(n1, n2)
Definition: numbers.h:18
#define NULL
Definition: omList.c:12

◆ simple_gauss()

void simple_gauss ( tgb_sparse_matrix mat,
slimgb_alg c 
)

Definition at line 125 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); // row_content does normalize
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);
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
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);
363}
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int i
Definition: cfEzgcd.cc:132
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:782
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:798
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:909
BOOLEAN zero_row(int row)
Definition: tgbgauss.cc:822
void perm_rows(int i, int j)
Definition: tgbgauss.h:80
int non_zero_entries(int row)
Definition: tgbgauss.cc:903
void mult_row(int row, number factor)
Definition: tgbgauss.cc:914
void row_content(int row)
Definition: tgbgauss.cc:847
number get(int i, int j)
Definition: tgbgauss.cc:766
int j
Definition: facHensel.cc:110
STATIC_VAR poly last
Definition: hdegree.cc:1173
STATIC_VAR scmon act
Definition: hdegree.cc:1174
STATIC_VAR Poly * h
Definition: janet.cc:971
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition: kbuckets.cc:1504
#define assume(x)
Definition: mod2.h:389
#define nInpNeg(n)
Definition: numbers.h:21
#define nSize(n)
Definition: numbers.h:39
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
static const int bundle_size
Definition: tgbgauss.cc:14

◆ simple_gauss2()

void simple_gauss2 ( tgb_matrix mat)

Definition at line 365 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 }
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 }
456}
void mult_row(int row, number factor)
Definition: tgbgauss.cc:619
void add_lambda_times_row(int add_to, int summand, number factor)
Definition: tgbgauss.cc:603
int min_col_not_zero_in_row(int row)
Definition: tgbgauss.cc:557
int non_zero_entries(int row)
Definition: tgbgauss.cc:590
BOOLEAN is_zero_entry(int i, int j)
Definition: tgbgauss.cc:544
void perm_rows(int i, int j)
Definition: tgbgauss.cc:549
number get(int i, int j)
Definition: tgbgauss.cc:537
int get_columns()
Definition: tgbgauss.cc:532
int get_rows()
Definition: tgbgauss.cc:527
#define nCopy(n)
Definition: numbers.h:15