Loading...
Searching...
No Matches
tgbgauss.cc File Reference
`#include "kernel/mod2.h"`
`#include "misc/options.h"`
`#include "kernel/GBEngine/tgbgauss.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 113 of file tgbgauss.cc.

{
mac_poly iter=p;
while(iter)
{
mac_poly next=iter->next;
nDelete(&iter->coef);
delete iter;
iter=next;
}
}
p
int p
Definition cfModGcd.cc:4086
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
next
ListNode * next
Definition janet.h:31
nDelete
#define nDelete(n)
Definition numbers.h:16
mac_poly
mac_poly_r * mac_poly
Definition tgbgauss.h:58

## mac_length()

int mac_length | ( | mac_poly | p | ) |

Definition at line 102 of file tgbgauss.cc.

{
int l=0;
while(p){
l++;
p=p->next;
}
return l;
}
l
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.

{
while(p)
{
number m=nMult(p->coef,c);
nDelete(&(p->coef));
p->coef=m;
p=p->next;
}
}
m
int m
Definition cfEzgcd.cc:128
nMult
#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.

{
mac_poly erg;
mac_poly* set_this;
set_this=&erg;
while((a!=NULL) &&(b!=NULL))
{
if (a->exp<b->exp)
{
(*set_this)=a;
a=a->next;
set_this= &((*set_this)->next);
}
else
{
if (a->exp>b->exp)
{
mac_poly in =new mac_poly_r();
in->exp=b->exp;
in->coef=nMult(b->coef,f);
(*set_this)=in;
b=b->next;
set_this= &((*set_this)->next);
}
else
{
//a->exp==b->ecp
number n=nMult(b->coef,f);
number n2=nAdd(a->coef,n);
nDelete(&n);
nDelete(&(a->coef));
if (nIsZero(n2))
{
nDelete(&n2);
mac_poly ao=a;
a=a->next;
delete ao;
b=b->next;
}
else
{
a->coef=n2;
b=b->next;
(*set_this)=a;
a=a->next;
set_this= &((*set_this)->next);
}
}
}
}
if((a==NULL)&&(b==NULL))
{
(*set_this)=NULL;
return erg;
}
if (b==NULL)
{
(*set_this=a);
return erg;
}
//a==NULL
while(b!=NULL)
{
mac_poly mp= new mac_poly_r();
mp->exp=b->exp;
mp->coef=nMult(f,b->coef);
(*set_this)=mp;
set_this=&(mp->next);
b=b->next;
}
(*set_this)=NULL;
return erg;
}
b
CanonicalForm b
Definition cfModGcd.cc:4111
f
FILE * f
Definition checklibs.c:9
mac_poly_r
Definition tgbgauss.h:48
mac_poly_r::next
mac_poly_r * next
Definition tgbgauss.h:51
mac_poly_r::coef
number coef
Definition tgbgauss.h:50
mac_poly_r::exp
int exp
Definition tgbgauss.h:52
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nAdd
#define nAdd(n1, n2)
Definition numbers.h:18
NULL
#define NULL
Definition omList.c:12

## row_cmp_gen()

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

static

Definition at line 683 of file tgbgauss.cc.

{
const mac_poly ap= *((mac_poly*) a);
const mac_poly bp=*((mac_poly*) b);
if (ap==NULL) return 1;
if (bp==NULL) return -1;
if (ap->exp<bp->exp) return -1;
return 1;
}
ap
Definition ap.h:40

## simple_gauss()

void simple_gauss | ( | tgb_sparse_matrix * | mat,
|  | slimgb_alg * | c )

Definition at line 125 of file tgbgauss.cc.

{
int col, row;
int* row_cache=(int*) omAlloc(mat->get_rows()*sizeof(int));
col=0;
row=0;
int i;
int pn=mat->get_rows();
int matcol=mat->get_columns();
int* area=(int*) omAlloc(sizeof(int)*((matcol-1)/bundle_size+1));
const int max_area_index=(matcol-1)/bundle_size;
//rows are divided in areas
//if row begins with columns col, it is located in [area[col/bundle_size],area[col/bundle_size+1]-1]
assume(pn>0);
//first clear zeroes
for(i=0;i<pn;i++)
{
if(mat->zero_row(i))
{
mat->perm_rows(i,pn-1);
pn--;
if(i!=pn){i--;}
}
}
mat->sort_rows();
for(i=0;i<pn;i++)
{
row_cache[i]=mat->min_col_not_zero_in_row(i);
// Print("row_cache:%d\n",row_cache[i]);
}
int last_area=-1;
for(i=0;i<pn;i++)
{
int this_area=row_cache[i]/bundle_size;
assume(this_area>=last_area);
if(this_area>last_area)
{
int j;
for(j=last_area+1;j<=this_area;j++)
area[j]=i;
last_area=this_area;
}
}
for(i=last_area+1;i<=max_area_index;i++)
{
area[i]=pn;
}
while(row<pn-1)
{
//row is the row where pivot should be
// row== pn-1 means we have only to act on one row so no red nec.
//we assume further all rows till the pn-1 row are non-zero
//select column
//col=mat->min_col_not_zero_in_row(row);
int max_in_area;
{
int tai=row_cache[row]/bundle_size;
assume(tai<=max_area_index);
if(tai==max_area_index)
max_in_area=pn-1;
else
max_in_area=area[tai+1]-1;
}
assume(row_cache[row]==mat->min_col_not_zero_in_row(row));
col=row_cache[row];
assume(col!=matcol);
int found_in_row;
found_in_row=row;
BOOLEAN must_reduce=FALSE;
assume(pn<=mat->get_rows());
for(i=row+1;i<=max_in_area;i++)
{
int first;//=mat->min_col_not_zero_in_row(i);
assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
first=row_cache[i];
assume(first!=matcol);
if(first<col)
{
col=first;
found_in_row=i;
must_reduce=FALSE;
}
else
{
if(first==col)
must_reduce=TRUE;
}
}
//select pivot
int act_l=nSize(mat->get(found_in_row,col))*mat->non_zero_entries(found_in_row);
if(must_reduce)
{
for(i=found_in_row+1;i<=max_in_area;i++)
{
assume(mat->min_col_not_zero_in_row(i)>=col);
assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
#ifndef SING_NDEBUG
int first=row_cache[i];
assume(first!=matcol);
#endif
// if((!(mat->is_zero_entry(i,col)))&&(mat->non_zero_entries(i)<act_l))
int nz;
if((row_cache[i]==col)&&((nz=nSize(mat->get(i,col))*mat->non_zero_entries(i))<act_l))
{
found_in_row=i;
act_l=nz;
}
}
}
mat->perm_rows(row,found_in_row);
int h=row_cache[row];
row_cache[row]=row_cache[found_in_row];
row_cache[found_in_row]=h;
if(!must_reduce)
{
row++;
continue;
}
//reduction
//must extract content and normalize here
mat->row_content(row);
//mat->row_normalize(row); // row_content does normalize
//for(i=row+1;i<pn;i++){
for(i=max_in_area;i>row;i--)
{
int col_area_index=col/bundle_size;
assume(col_area_index<=max_area_index);
assume(mat->min_col_not_zero_in_row(i)>=col);
assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
#ifndef SING_NDEBUG
int first=row_cache[i];
assume(first!=matcol);
#endif
if(row_cache[i]==col)
{
number c1=mat->get(i,col);
number c2=mat->get(row,col);
number n1=c1;
number n2=c2;
ksCheckCoeff(&n1,&n2,currRing->cf);
//nDelete(&c1);
n1=nInpNeg(n1);
mat->mult_row(i,n2);
mat->add_lambda_times_row(i,row,n1);
nDelete(&n1);
nDelete(&n2);
assume(mat->is_zero_entry(i,col));
row_cache[i]=mat->min_col_not_zero_in_row(i);
assume(mat->min_col_not_zero_in_row(i)>col);
if(row_cache[i]==matcol)
{
int index;
index=i;
int last_in_area;
int this_cai=col_area_index;
while(this_cai<max_area_index)
{
last_in_area=area[this_cai+1]-1;
int h_c=row_cache[last_in_area];
row_cache[last_in_area]=row_cache[index];
row_cache[index]=h_c;
mat->perm_rows(index,last_in_area);
index=last_in_area;
this_cai++;
area[this_cai]--;
}
mat->perm_rows(index,pn-1);
row_cache[index]=row_cache[pn-1];
row_cache[pn-1]=matcol;
pn--;
}
else
{
int index;
index=i;
int last_in_area;
int this_cai=col_area_index;
int final_cai=row_cache[index]/bundle_size;
assume(final_cai<=max_area_index);
while(this_cai<final_cai)
{
last_in_area=area[this_cai+1]-1;
int h_c=row_cache[last_in_area];
row_cache[last_in_area]=row_cache[index];
row_cache[index]=h_c;
mat->perm_rows(index,last_in_area);
index=last_in_area;
this_cai++;
area[this_cai]--;
}
}
}
else
assume(mat->min_col_not_zero_in_row(i)>col);
}
// for(i=row+1;i<pn;i++)
// {
// assume(mat->min_col_not_zero_in_row(i)==row_cache[i]);
// // if(mat->zero_row(i))
// assume(matcol==mat->get_columns());
// if(row_cache[i]==matcol)
// {
// assume(mat->zero_row(i));
// mat->perm_rows(i,pn-1);
// row_cache[i]=row_cache[pn-1];
// row_cache[pn-1]=matcol;
// pn--;
// if(i!=pn){i--;}
// }
// }
#ifdef TGB_DEBUG
{
int last=-1;
for(i=0;i<pn;i++)
{
int act=mat->min_col_not_zero_in_row(i);
assume(act>last);
}
for(i=pn;i<mat->get_rows();i++)
{
assume(mat->zero_row(i));
}
}
#endif
row++;
}
omFree(area);
omFree(row_cache);
}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
i
int i
Definition cfEzgcd.cc:132
tgb_sparse_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition tgbgauss.cc:782
tgb_sparse_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition tgbgauss.cc:798
tgb_sparse_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition tgbgauss.cc:909
tgb_sparse_matrix::zero_row
BOOLEAN zero_row(int row)
Definition tgbgauss.cc:822
tgb_sparse_matrix::get_rows
int get_rows()
Definition tgbgauss.cc:756
tgb_sparse_matrix::perm_rows
void perm_rows(int i, int j)
Definition tgbgauss.h:80
tgb_sparse_matrix::sort_rows
void sort_rows()
Definition tgbgauss.cc:693
tgb_sparse_matrix::non_zero_entries
int non_zero_entries(int row)
Definition tgbgauss.cc:903
tgb_sparse_matrix::mult_row
void mult_row(int row, number factor)
Definition tgbgauss.cc:914
tgb_sparse_matrix::row_content
void row_content(int row)
Definition tgbgauss.cc:847
tgb_sparse_matrix::get
number get(int i, int j)
Definition tgbgauss.cc:766
tgb_sparse_matrix::get_columns
int get_columns()
Definition tgbgauss.cc:761
j
int j
Definition facHensel.cc:110
last
STATIC_VAR poly last
Definition hdegree.cc:1138
act
STATIC_VAR scmon act
Definition hdegree.cc:1139
h
STATIC_VAR Poly * h
Definition janet.cc:971
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
assume
#define assume(x)
Definition mod2.h:389
nInpNeg
#define nInpNeg(n)
Definition numbers.h:21
nSize
#define nSize(n)
Definition numbers.h:39
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
bundle_size
static const int bundle_size
Definition tgb.cc:36

## simple_gauss2()

void simple_gauss2 | ( | tgb_matrix * | mat | ) |

Definition at line 365 of file tgbgauss.cc.

{
int col, row;
col=0;
row=0;
int i;
int pn=mat->get_rows();
assume(pn>0);
//first clear zeroes
// for(i=0;i<pn;i++)
// {
// if(mat->zero_row(i))
// {
// mat->perm_rows(i,pn-1);
// pn--;
// if(i!=pn){i--;}
// }
// }
while((row<pn-1)&&(col<mat->get_columns())){
//row is the row where pivot should be
// row== pn-1 means we have only to act on one row so no red nec.
//we assume further all rows till the pn-1 row are non-zero
//select column
// col=mat->min_col_not_zero_in_row(row);
assume(col!=mat->get_columns());
int found_in_row=-1;
// found_in_row=row;
assume(pn<=mat->get_rows());
for(i=row;i<pn;i++)
{
// int first=mat->min_col_not_zero_in_row(i);
// if(first<col)
if(!(mat->is_zero_entry(i,col)))
{
found_in_row=i;
break;
}
}
if(found_in_row!=-1)
{
//select pivot
int act_l=mat->non_zero_entries(found_in_row);
for(i=i+1;i<pn;i++)
{
int vgl;
assume(mat->min_col_not_zero_in_row(i)>=col);
if((!(mat->is_zero_entry(i,col)))
&&((vgl=mat->non_zero_entries(i))<act_l))
{
found_in_row=i;
act_l=vgl;
}
}
mat->perm_rows(row,found_in_row);
//reduction
for(i=row+1;i<pn;i++){
assume(mat->min_col_not_zero_in_row(i)>=col);
if(!(mat->is_zero_entry(i,col)))
{
number c1=nCopy(mat->get(i,col));
c1=nInpNeg(c1);
number c2=mat->get(row,col);
number n1=c1;
number n2=c2;
ksCheckCoeff(&n1,&n2,currRing->cf);
nDelete(&c1);
mat->mult_row(i,n2);
mat->add_lambda_times_row(i,row,n1);
assume(mat->is_zero_entry(i,col));
}
assume(mat->min_col_not_zero_in_row(i)>col);
}
row++;
}
col++;
// for(i=row+1;i<pn;i++)
// {
// if(mat->zero_row(i))
// {
// mat->perm_rows(i,pn-1);
// pn--;
// if(i!=pn){i--;}
// }
// }
}
}
tgb_matrix::mult_row
void mult_row(int row, number factor)
Definition tgbgauss.cc:619
tgb_matrix::add_lambda_times_row
void add_lambda_times_row(int add_to, int summand, number factor)
Definition tgbgauss.cc:603
tgb_matrix::min_col_not_zero_in_row
int min_col_not_zero_in_row(int row)
Definition tgbgauss.cc:557
tgb_matrix::non_zero_entries
int non_zero_entries(int row)
Definition tgbgauss.cc:590
tgb_matrix::is_zero_entry
BOOLEAN is_zero_entry(int i, int j)
Definition tgbgauss.cc:544
tgb_matrix::perm_rows
void perm_rows(int i, int j)
Definition tgbgauss.cc:549
tgb_matrix::get
number get(int i, int j)
Definition tgbgauss.cc:537
tgb_matrix::get_columns
int get_columns()
Definition tgbgauss.cc:532
tgb_matrix::get_rows
int get_rows()
Definition tgbgauss.cc:527
nCopy
#define nCopy(n)
Definition numbers.h:15

## Variable Documentation

## bundle_size

const int bundle_size =100

static

Definition at line 14 of file tgbgauss.cc.