Loading...
Searching...
No Matches
sparse_number_mat Class Reference

## Public Member Functions

| sparse_number_mat (ideal, const ring)
| ~sparse_number_mat ()
int | smIsSing ()
void | smTriangular ()
void | smSolv ()
ideal | smRes2Ideal ()

## Private Member Functions

void | smColToRow ()
void | smRowToCol ()
void | smSelectPR ()
void | smRealPivot ()
void | smZeroToredElim ()
void | smGElim ()
void | smAllDel ()

## Private Attributes

int | nrows
int | ncols
int | act
int | crd
int | tored
int | sing
int | rpiv
int * | perm
number * | sol
int * | wrw
int * | wcl
smnumber * | m_act
smnumber * | m_res
smnumber * | m_row
smnumber | red
smnumber | piv
smnumber | dumm
ring | _R

## Detailed Description

Definition at line 2275 of file sparsmat.cc.

## Constructor & Destructor Documentation

## sparse_number_mat()

sparse_number_mat::sparse_number_mat | ( | ideal | smat,
|  | const ring | R )

Definition at line 2351 of file sparsmat.cc.

{
int i;
poly* pmat;
_R=R;
crd = sing = 0;
act = ncols = smat->ncols;
tored = nrows = smat->rank;
i = tored+1;
perm = (int *)omAlloc(sizeof(int)*i);
m_row = (smnumber *)omAlloc0(sizeof(smnumber)*i);
wrw = (int *)omAlloc(sizeof(int)*i);
i = ncols+1;
wcl = (int *)omAlloc(sizeof(int)*i);
m_act = (smnumber *)omAlloc(sizeof(smnumber)*i);
m_res = (smnumber *)omAlloc0(sizeof(smnumber)*i);
dumm = (smnumber)omAllocBin(smnrec_bin);
pmat = smat->m;
for(i=ncols; i; i--)
{
m_act[i] = sm_Poly2Smnumber(pmat[i-1],_R);
}
omFreeSize((ADDRESS)pmat,smat->ncols*sizeof(poly));
omFreeBin((ADDRESS)smat, sip_sideal_bin);
}
ADDRESS
void * ADDRESS
Definition auxiliary.h:120
i
int i
Definition cfEzgcd.cc:132
sparse_number_mat::perm
int * perm
Definition sparsmat.cc:2283
sparse_number_mat::ncols
int ncols
Definition sparsmat.cc:2277
sparse_number_mat::sing
int sing
Definition sparsmat.cc:2281
sparse_number_mat::m_act
smnumber * m_act
Definition sparsmat.cc:2286
sparse_number_mat::crd
int crd
Definition sparsmat.cc:2279
sparse_number_mat::tored
int tored
Definition sparsmat.cc:2280
sparse_number_mat::m_res
smnumber * m_res
Definition sparsmat.cc:2287
sparse_number_mat::wcl
int * wcl
Definition sparsmat.cc:2285
sparse_number_mat::wrw
int * wrw
Definition sparsmat.cc:2285
sparse_number_mat::nrows
int nrows
Definition sparsmat.cc:2277
sparse_number_mat::m_row
smnumber * m_row
Definition sparsmat.cc:2288
sparse_number_mat::act
int act
Definition sparsmat.cc:2278
sparse_number_mat::dumm
smnumber dumm
Definition sparsmat.cc:2291
sparse_number_mat::_R
ring _R
Definition sparsmat.cc:2292
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omAllocBin
#define omAllocBin(bin)
Definition omAllocDecl.h:205
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259
sip_sideal_bin
VAR omBin sip_sideal_bin
Definition simpleideals.cc:27
R
#define R
Definition sirandom.c:27
smnrec_bin
STATIC_VAR omBin smnrec_bin
Definition sparsmat.cc:2264
sm_Poly2Smnumber
static smnumber sm_Poly2Smnumber(poly, const ring)
Definition sparsmat.cc:2845
smnumber
sm_nrec * smnumber
Definition sparsmat.cc:2257

## ~sparse_number_mat()

sparse_number_mat::~sparse_number_mat | ( |  | ) |

Definition at line 2381 of file sparsmat.cc.

{
int i;
omFreeBin((ADDRESS)dumm, smnrec_bin);
i = ncols+1;
omFreeSize((ADDRESS)m_res, sizeof(smnumber)*i);
omFreeSize((ADDRESS)m_act, sizeof(smnumber)*i);
omFreeSize((ADDRESS)wcl, sizeof(int)*i);
i = nrows+1;
omFreeSize((ADDRESS)wrw, sizeof(int)*i);
omFreeSize((ADDRESS)m_row, sizeof(smnumber)*i);
omFreeSize((ADDRESS)perm, sizeof(int)*i);
}

## Member Function Documentation

## smAllDel()

void sparse_number_mat::smAllDel | ( |  | ) |

private

Definition at line 2795 of file sparsmat.cc.

{
smnumber a;
int i;
for (i=act; i; i--)
{
a = m_act[i];
while (a != NULL)
sm_NumberDelete(&a,_R);
}
for (i=crd; i; i--)
{
a = m_res[i];
while (a != NULL)
sm_NumberDelete(&a,_R);
}
if (act)
{
for (i=nrows; i; i--)
{
a = m_row[i];
while (a != NULL)
sm_NumberDelete(&a,_R);
}
}
}
NULL
#define NULL
Definition omList.c:12
sm_NumberDelete
static void sm_NumberDelete(smnumber *, const ring R)
Definition sparsmat.cc:2825

## smColToRow()

void sparse_number_mat::smColToRow | ( |  | ) |

private

Definition at line 2720 of file sparsmat.cc.

{
smnumber c = m_act[act];
smnumber h;
while (c != NULL)
{
h = c;
c = c->n;
h->n = m_row[h->pos];
m_row[h->pos] = h;
h->pos = crd;
}
}
h
STATIC_VAR Poly * h
Definition janet.cc:971

## smGElim()

void sparse_number_mat::smGElim | ( |  | ) |

private

Definition at line 2576 of file sparsmat.cc.

{
number p = n_Invers(piv->m,_R->cf); // pivotelement
smnumber c = m_act[act]; // pivotcolumn
smnumber r = red; // row to reduce
smnumber res, a, b;
number w, ha, hb;
if ((c == NULL) || (r == NULL))
{
while (r!=NULL) sm_NumberDelete(&r,_R);
return;
}
do
{
a = m_act[r->pos];
res = dumm;
res->n = NULL;
b = c;
w = n_Mult(r->m, p,_R->cf);
n_Delete(&r->m,_R->cf);
r->m = w;
loop // combine the chains a and b: a + w*b
{
if (a == NULL)
{
do
{
res = res->n = smNumberCopy(b);
res->m = n_Mult(b->m, w,_R->cf);
b = b->n;
} while (b != NULL);
break;
}
if (a->pos < b->pos)
{
res = res->n = a;
a = a->n;
}
else if (a->pos > b->pos)
{
res = res->n = smNumberCopy(b);
res->m = n_Mult(b->m, w,_R->cf);
b = b->n;
}
else
{
hb = n_Mult(b->m, w,_R->cf);
ha = n_Add(a->m, hb,_R->cf);
n_Delete(&hb,_R->cf);
n_Delete(&a->m,_R->cf);
if (n_IsZero(ha,_R->cf))
{
sm_NumberDelete(&a,_R);
}
else
{
a->m = ha;
res = res->n = a;
a = a->n;
}
b = b->n;
}
if (b == NULL)
{
res->n = a;
break;
}
}
m_act[r->pos] = dumm->n;
sm_NumberDelete(&r,_R);
} while (r != NULL);
n_Delete(&p,_R->cf);
}
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
sparse_number_mat::piv
smnumber piv
Definition sparsmat.cc:2290
sparse_number_mat::red
smnumber red
Definition sparsmat.cc:2289
n_Mult
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition coeffs.h:639
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition coeffs.h:653
n_Invers
static FORCE_INLINE number n_Invers(number a, const coeffs r)
return the multiplicative inverse of 'a'; raise an error if 'a' is not invertible
Definition coeffs.h:567
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:470
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
res
CanonicalForm res
Definition facAbsFact.cc:60
w
const CanonicalForm & w
Definition facAbsFact.cc:51
smNumberCopy
static smnumber smNumberCopy(smnumber)
Definition sparsmat.cc:2834
loop
#define loop
Definition structs.h:71

## smIsSing()

int sparse_number_mat::smIsSing | ( |  | ) |

inline

Definition at line 2303 of file sparsmat.cc.

{ return sing; }

## smRealPivot()

void sparse_number_mat::smRealPivot | ( |  | ) |

private

Definition at line 2525 of file sparsmat.cc.

{
smnumber a;
number x, xo;
int i, copt, ropt;
xo=n_Init(0,_R->cf);
for (i=act; i; i--)
{
a = m_act[i];
while ((a!=NULL) && (a->pos<=tored))
{
x = a->m;
if (n_GreaterZero(x,_R->cf))
{
if (n_Greater(x,xo,_R->cf))
{
n_Delete(&xo,_R->cf);
xo = n_Copy(x,_R->cf);
copt = i;
ropt = a->pos;
}
}
else
{
xo = n_InpNeg(xo,_R->cf);
if (n_Greater(xo,x,_R->cf))
{
n_Delete(&xo,_R->cf);
xo = n_Copy(x,_R->cf);
copt = i;
ropt = a->pos;
}
xo = n_InpNeg(xo,_R->cf);
}
a = a->n;
}
}
rpiv = ropt;
if (copt != act)
{
a = m_act[act];
m_act[act] = m_act[copt];
m_act[copt] = a;
}
n_Delete(&xo,_R->cf);
}
x
Variable x
Definition cfModGcd.cc:4090
sparse_number_mat::rpiv
int rpiv
Definition sparsmat.cc:2282
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition coeffs.h:457
n_GreaterZero
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition coeffs.h:500
n_InpNeg
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition coeffs.h:560
n_Greater
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition coeffs.h:517
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:541

## smRes2Ideal()

ideal sparse_number_mat::smRes2Ideal | ( |  | ) |

Definition at line 2506 of file sparsmat.cc.

{
int i, j;
ideal res = idInit(crd, 1);
for (i=crd; i; i--)
{
j = perm[i]-1;
res->m[j] = sm_Smnumber2Poly(sol[i],_R);
}
omFreeSize((ADDRESS)sol, sizeof(number)*(crd+1));
return res;
}
sparse_number_mat::sol
number * sol
Definition sparsmat.cc:2284
j
int j
Definition facHensel.cc:110
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
sm_Smnumber2Poly
static poly sm_Smnumber2Poly(number, const ring)
Definition sparsmat.cc:2876

## smRowToCol()

void sparse_number_mat::smRowToCol | ( |  | ) |

private

Definition at line 2740 of file sparsmat.cc.

{
smnumber r = m_row[rpiv];
smnumber a, ap, h;
m_row[rpiv] = NULL;
perm[crd] = rpiv;
piv->pos = crd;
m_res[crd] = piv;
while (r != NULL)
{
ap = m_res[r->pos];
loop
{
a = ap->n;
if (a == NULL)
{
ap->n = h = r;
r = r->n;
h->n = a;
h->pos = crd;
break;
}
ap = a;
}
}
}

## smSelectPR()

void sparse_number_mat::smSelectPR | ( |  | ) |

private

Definition at line 2656 of file sparsmat.cc.

{
smnumber b = dumm;
smnumber a, ap;
int i;
if (TEST_OPT_PROT)
{
if ((crd+1)%10)
PrintS(".");
else
PrintS(".\n");
}
a = m_act[act];
if (a->pos < rpiv)
{
do
{
ap = a;
a = a->n;
} while (a->pos < rpiv);
ap->n = a->n;
}
else
m_act[act] = a->n;
piv = a;
a->n = NULL;
for (i=1; i<act; i++)
{
a = m_act[i];
if (a->pos < rpiv)
{
loop
{
ap = a;
a = a->n;
if ((a == NULL) || (a->pos > rpiv))
break;
if (a->pos == rpiv)
{
ap->n = a->n;
a->m = n_InpNeg(a->m,_R->cf);
b = b->n = a;
b->pos = i;
break;
}
}
}
else if (a->pos == rpiv)
{
m_act[i] = a->n;
a->m = n_InpNeg(a->m,_R->cf);
b = b->n = a;
b->pos = i;
}
}
b->n = NULL;
red = dumm->n;
}
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
PrintS
void PrintS(const char *s)
Definition reporter.cc:288

## smSolv()

void sparse_number_mat::smSolv | ( |  | ) |

Definition at line 2429 of file sparsmat.cc.

{
int i, j;
number x, y, z;
smnumber s, d, r = m_row[nrows];
m_row[nrows] = NULL;
sol = (number *)omAlloc0(sizeof(number)*(crd+1));
while (r != NULL) // expand the right hand side
{
sol[r->pos] = r->m;
s = r;
r = r->n;
omFreeBin((ADDRESS)s, smnrec_bin);
}
i = crd; // solve triangular system
if (sol[i] != NULL)
{
x = sol[i];
sol[i] = n_Div(x, m_res[i]->m,_R->cf);
n_Delete(&x,_R->cf);
}
i--;
while (i > 0)
{
x = NULL;
d = m_res[i];
s = d->n;
while (s != NULL)
{
j = s->pos;
if (sol[j] != NULL)
{
z = n_Mult(sol[j], s->m,_R->cf);
if (x != NULL)
{
y = x;
x = n_Sub(y, z,_R->cf);
n_Delete(&y,_R->cf);
n_Delete(&z,_R->cf);
}
else
x = n_InpNeg(z,_R->cf);
}
s = s->n;
}
if (sol[i] != NULL)
{
if (x != NULL)
{
y = n_Add(x, sol[i],_R->cf);
n_Delete(&x,_R->cf);
if (n_IsZero(y,_R->cf))
{
n_Delete(&sol[i],_R->cf);
sol[i] = NULL;
}
else
sol[i] = y;
}
}
else
sol[i] = x;
if (sol[i] != NULL)
{
x = sol[i];
sol[i] = n_Div(x, d->m,_R->cf);
n_Delete(&x,_R->cf);
}
i--;
}
this->smAllDel();
}
m
int m
Definition cfEzgcd.cc:128
sparse_number_mat::smAllDel
void smAllDel()
Definition sparsmat.cc:2795
n_Div
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition coeffs.h:618
n_Sub
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition coeffs.h:658
s
const CanonicalForm int s
Definition facAbsFact.cc:51
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

## smTriangular()

void sparse_number_mat::smTriangular | ( |  | ) |

Definition at line 2398 of file sparsmat.cc.

{
tored--;
this->smZeroToredElim();
if (sing != 0) return;
while (act > 1)
{
this->smRealPivot();
this->smSelectPR();
this->smGElim();
crd++;
this->smColToRow();
act--;
this->smRowToCol();
this->smZeroToredElim();
if (sing != 0) return;
}
if (TEST_OPT_PROT) PrintS(".\n");
piv = m_act[1];
rpiv = piv->pos;
m_act[1] = piv->n;
piv->n = NULL;
crd++;
this->smColToRow();
act--;
this->smRowToCol();
}
sparse_number_mat::smGElim
void smGElim()
Definition sparsmat.cc:2576
sparse_number_mat::smRealPivot
void smRealPivot()
Definition sparsmat.cc:2525
sparse_number_mat::smZeroToredElim
void smZeroToredElim()
Definition sparsmat.cc:2773
sparse_number_mat::smColToRow
void smColToRow()
Definition sparsmat.cc:2720
sparse_number_mat::smRowToCol
void smRowToCol()
Definition sparsmat.cc:2740
sparse_number_mat::smSelectPR
void smSelectPR()
Definition sparsmat.cc:2656

## smZeroToredElim()

void sparse_number_mat::smZeroToredElim | ( |  | ) |

private

Definition at line 2773 of file sparsmat.cc.

{
smnumber a;
int i = act;
loop
{
if (i == 0) return;
a = m_act[i];
if ((a==NULL) || (a->pos>tored))
{
sing = 1;
this->smAllDel();
return;
}
i--;
}
}

## Field Documentation

## _R

ring sparse_number_mat::_R

private

Definition at line 2292 of file sparsmat.cc.

## act

int sparse_number_mat::act

private

Definition at line 2278 of file sparsmat.cc.

## crd

int sparse_number_mat::crd

private

Definition at line 2279 of file sparsmat.cc.

## dumm

smnumber sparse_number_mat::dumm

private

Definition at line 2291 of file sparsmat.cc.

## m_act

smnumber* sparse_number_mat::m_act

private

Definition at line 2286 of file sparsmat.cc.

## m_res

smnumber* sparse_number_mat::m_res

private

Definition at line 2287 of file sparsmat.cc.

## m_row

smnumber* sparse_number_mat::m_row

private

Definition at line 2288 of file sparsmat.cc.

## ncols

int sparse_number_mat::ncols

private

Definition at line 2277 of file sparsmat.cc.

## nrows

int sparse_number_mat::nrows

private

Definition at line 2277 of file sparsmat.cc.

## perm

int* sparse_number_mat::perm

private

Definition at line 2283 of file sparsmat.cc.

## piv

smnumber sparse_number_mat::piv

private

Definition at line 2290 of file sparsmat.cc.

## red

smnumber sparse_number_mat::red

private

Definition at line 2289 of file sparsmat.cc.

## rpiv

int sparse_number_mat::rpiv

private

Definition at line 2282 of file sparsmat.cc.

## sing

int sparse_number_mat::sing

private

Definition at line 2281 of file sparsmat.cc.

## sol

number* sparse_number_mat::sol

private

Definition at line 2284 of file sparsmat.cc.

## tored

int sparse_number_mat::tored

private

Definition at line 2280 of file sparsmat.cc.

## wcl

int * sparse_number_mat::wcl

private

Definition at line 2285 of file sparsmat.cc.

## wrw

int* sparse_number_mat::wrw

private

Definition at line 2285 of file sparsmat.cc.

The documentation for this class was generated from the following file:

- libpolys/polys/sparsmat.cc