My Project  debian-1:4.1.2-p1+ds-2
Public Member Functions | Private Member Functions | Private Attributes
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
 
smnumberm_act
 
smnumberm_res
 
smnumberm_row
 
smnumber red
 
smnumber piv
 
smnumber dumm
 
ring _R
 

Detailed Description

Definition at line 2274 of file sparsmat.cc.

Constructor & Destructor Documentation

◆ sparse_number_mat()

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

Definition at line 2350 of file sparsmat.cc.

2352 {
2353  int i;
2354  poly* pmat;
2355  _R=R;
2356 
2357  crd = sing = 0;
2358  act = ncols = smat->ncols;
2359  tored = nrows = smat->rank;
2360  i = tored+1;
2361  perm = (int *)omAlloc(sizeof(int)*i);
2362  m_row = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2363  wrw = (int *)omAlloc(sizeof(int)*i);
2364  i = ncols+1;
2365  wcl = (int *)omAlloc(sizeof(int)*i);
2366  m_act = (smnumber *)omAlloc(sizeof(smnumber)*i);
2367  m_res = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2369  pmat = smat->m;
2370  for(i=ncols; i; i--)
2371  {
2372  m_act[i] = sm_Poly2Smnumber(pmat[i-1],_R);
2373  }
2374  omFreeSize((ADDRESS)pmat,smat->ncols*sizeof(poly));

◆ ~sparse_number_mat()

sparse_number_mat::~sparse_number_mat ( )

Definition at line 2380 of file sparsmat.cc.

2382 {
2383  int i;
2385  i = ncols+1;
2386  omFreeSize((ADDRESS)m_res, sizeof(smnumber)*i);
2387  omFreeSize((ADDRESS)m_act, sizeof(smnumber)*i);
2388  omFreeSize((ADDRESS)wcl, sizeof(int)*i);
2389  i = nrows+1;
2390  omFreeSize((ADDRESS)wrw, sizeof(int)*i);
2391  omFreeSize((ADDRESS)m_row, sizeof(smnumber)*i);
2392  omFreeSize((ADDRESS)perm, sizeof(int)*i);

Member Function Documentation

◆ smAllDel()

void sparse_number_mat::smAllDel ( )
private

Definition at line 2794 of file sparsmat.cc.

2796 {
2797  smnumber a;
2798  int i;
2799 
2800  for (i=act; i; i--)
2801  {
2802  a = m_act[i];
2803  while (a != NULL)
2804  sm_NumberDelete(&a,_R);
2805  }
2806  for (i=crd; i; i--)
2807  {
2808  a = m_res[i];
2809  while (a != NULL)
2810  sm_NumberDelete(&a,_R);
2811  }
2812  if (act)
2813  {
2814  for (i=nrows; i; i--)
2815  {
2816  a = m_row[i];
2817  while (a != NULL)
2818  sm_NumberDelete(&a,_R);
2819  }
2820  }

◆ smColToRow()

void sparse_number_mat::smColToRow ( )
private

Definition at line 2719 of file sparsmat.cc.

2721 {
2722  smnumber c = m_act[act];
2723  smnumber h;
2724 
2725  while (c != NULL)
2726  {
2727  h = c;
2728  c = c->n;
2729  h->n = m_row[h->pos];
2730  m_row[h->pos] = h;
2731  h->pos = crd;
2732  }

◆ smGElim()

void sparse_number_mat::smGElim ( )
private

Definition at line 2575 of file sparsmat.cc.

2577 {
2578  number p = n_Invers(piv->m,_R->cf); // pivotelement
2579  smnumber c = m_act[act]; // pivotcolumn
2580  smnumber r = red; // row to reduce
2581  smnumber res, a, b;
2582  number w, ha, hb;
2583 
2584  if ((c == NULL) || (r == NULL))
2585  {
2586  while (r!=NULL) sm_NumberDelete(&r,_R);
2587  return;
2588  }
2589  do
2590  {
2591  a = m_act[r->pos];
2592  res = dumm;
2593  res->n = NULL;
2594  b = c;
2595  w = n_Mult(r->m, p,_R->cf);
2596  n_Delete(&r->m,_R->cf);
2597  r->m = w;
2598  loop // combine the chains a and b: a + w*b
2599  {
2600  if (a == NULL)
2601  {
2602  do
2603  {
2604  res = res->n = smNumberCopy(b);
2605  res->m = n_Mult(b->m, w,_R->cf);
2606  b = b->n;
2607  } while (b != NULL);
2608  break;
2609  }
2610  if (a->pos < b->pos)
2611  {
2612  res = res->n = a;
2613  a = a->n;
2614  }
2615  else if (a->pos > b->pos)
2616  {
2617  res = res->n = smNumberCopy(b);
2618  res->m = n_Mult(b->m, w,_R->cf);
2619  b = b->n;
2620  }
2621  else
2622  {
2623  hb = n_Mult(b->m, w,_R->cf);
2624  ha = n_Add(a->m, hb,_R->cf);
2625  n_Delete(&hb,_R->cf);
2626  n_Delete(&a->m,_R->cf);
2627  if (n_IsZero(ha,_R->cf))
2628  {
2629  sm_NumberDelete(&a,_R);
2630  }
2631  else
2632  {
2633  a->m = ha;
2634  res = res->n = a;
2635  a = a->n;
2636  }
2637  b = b->n;
2638  }
2639  if (b == NULL)
2640  {
2641  res->n = a;
2642  break;
2643  }
2644  }
2645  m_act[r->pos] = dumm->n;
2646  sm_NumberDelete(&r,_R);
2647  } while (r != NULL);
2648  n_Delete(&p,_R->cf);

◆ smIsSing()

int sparse_number_mat::smIsSing ( )
inline

Definition at line 2302 of file sparsmat.cc.

2303 { return sing; }

◆ smRealPivot()

void sparse_number_mat::smRealPivot ( )
private

Definition at line 2524 of file sparsmat.cc.

2526 {
2527  smnumber a;
2528  number x, xo;
2529  int i, copt, ropt;
2530 
2531  xo=n_Init(0,_R->cf);
2532  for (i=act; i; i--)
2533  {
2534  a = m_act[i];
2535  while ((a!=NULL) && (a->pos<=tored))
2536  {
2537  x = a->m;
2538  if (n_GreaterZero(x,_R->cf))
2539  {
2540  if (n_Greater(x,xo,_R->cf))
2541  {
2542  n_Delete(&xo,_R->cf);
2543  xo = n_Copy(x,_R->cf);
2544  copt = i;
2545  ropt = a->pos;
2546  }
2547  }
2548  else
2549  {
2550  xo = n_InpNeg(xo,_R->cf);
2551  if (n_Greater(xo,x,_R->cf))
2552  {
2553  n_Delete(&xo,_R->cf);
2554  xo = n_Copy(x,_R->cf);
2555  copt = i;
2556  ropt = a->pos;
2557  }
2558  xo = n_InpNeg(xo,_R->cf);
2559  }
2560  a = a->n;
2561  }
2562  }
2563  rpiv = ropt;
2564  if (copt != act)
2565  {
2566  a = m_act[act];
2567  m_act[act] = m_act[copt];
2568  m_act[copt] = a;
2569  }
2570  n_Delete(&xo,_R->cf);

◆ smRes2Ideal()

ideal sparse_number_mat::smRes2Ideal ( )

Definition at line 2505 of file sparsmat.cc.

2507 {
2508  int i, j;
2509  ideal res = idInit(crd, 1);
2510 
2511  for (i=crd; i; i--)
2512  {
2513  j = perm[i]-1;
2514  res->m[j] = sm_Smnumber2Poly(sol[i],_R);
2515  }
2516  omFreeSize((ADDRESS)sol, sizeof(number)*(crd+1));
2517  return res;

◆ smRowToCol()

void sparse_number_mat::smRowToCol ( )
private

Definition at line 2739 of file sparsmat.cc.

2741 {
2742  smnumber r = m_row[rpiv];
2743  smnumber a, ap, h;
2744 
2745  m_row[rpiv] = NULL;
2746  perm[crd] = rpiv;
2747  piv->pos = crd;
2748  m_res[crd] = piv;
2749  while (r != NULL)
2750  {
2751  ap = m_res[r->pos];
2752  loop
2753  {
2754  a = ap->n;
2755  if (a == NULL)
2756  {
2757  ap->n = h = r;
2758  r = r->n;
2759  h->n = a;
2760  h->pos = crd;
2761  break;
2762  }
2763  ap = a;
2764  }
2765  }

◆ smSelectPR()

void sparse_number_mat::smSelectPR ( )
private

Definition at line 2655 of file sparsmat.cc.

2657 {
2658  smnumber b = dumm;
2659  smnumber a, ap;
2660  int i;
2661 
2662  if (TEST_OPT_PROT)
2663  {
2664  if ((crd+1)%10)
2665  PrintS(".");
2666  else
2667  PrintS(".\n");
2668  }
2669  a = m_act[act];
2670  if (a->pos < rpiv)
2671  {
2672  do
2673  {
2674  ap = a;
2675  a = a->n;
2676  } while (a->pos < rpiv);
2677  ap->n = a->n;
2678  }
2679  else
2680  m_act[act] = a->n;
2681  piv = a;
2682  a->n = NULL;
2683  for (i=1; i<act; i++)
2684  {
2685  a = m_act[i];
2686  if (a->pos < rpiv)
2687  {
2688  loop
2689  {
2690  ap = a;
2691  a = a->n;
2692  if ((a == NULL) || (a->pos > rpiv))
2693  break;
2694  if (a->pos == rpiv)
2695  {
2696  ap->n = a->n;
2697  a->m = n_InpNeg(a->m,_R->cf);
2698  b = b->n = a;
2699  b->pos = i;
2700  break;
2701  }
2702  }
2703  }
2704  else if (a->pos == rpiv)
2705  {
2706  m_act[i] = a->n;
2707  a->m = n_InpNeg(a->m,_R->cf);
2708  b = b->n = a;
2709  b->pos = i;
2710  }
2711  }
2712  b->n = NULL;
2713  red = dumm->n;

◆ smSolv()

void sparse_number_mat::smSolv ( )

Definition at line 2428 of file sparsmat.cc.

2430 {
2431  int i, j;
2432  number x, y, z;
2433  smnumber s, d, r = m_row[nrows];
2434 
2435  m_row[nrows] = NULL;
2436  sol = (number *)omAlloc0(sizeof(number)*(crd+1));
2437  while (r != NULL) // expand the rigth hand side
2438  {
2439  sol[r->pos] = r->m;
2440  s = r;
2441  r = r->n;
2443  }
2444  i = crd; // solve triangular system
2445  if (sol[i] != NULL)
2446  {
2447  x = sol[i];
2448  sol[i] = n_Div(x, m_res[i]->m,_R->cf);
2449  n_Delete(&x,_R->cf);
2450  }
2451  i--;
2452  while (i > 0)
2453  {
2454  x = NULL;
2455  d = m_res[i];
2456  s = d->n;
2457  while (s != NULL)
2458  {
2459  j = s->pos;
2460  if (sol[j] != NULL)
2461  {
2462  z = n_Mult(sol[j], s->m,_R->cf);
2463  if (x != NULL)
2464  {
2465  y = x;
2466  x = n_Sub(y, z,_R->cf);
2467  n_Delete(&y,_R->cf);
2468  n_Delete(&z,_R->cf);
2469  }
2470  else
2471  x = n_InpNeg(z,_R->cf);
2472  }
2473  s = s->n;
2474  }
2475  if (sol[i] != NULL)
2476  {
2477  if (x != NULL)
2478  {
2479  y = n_Add(x, sol[i],_R->cf);
2480  n_Delete(&x,_R->cf);
2481  if (n_IsZero(y,_R->cf))
2482  {
2483  n_Delete(&sol[i],_R->cf);
2484  sol[i] = NULL;
2485  }
2486  else
2487  sol[i] = y;
2488  }
2489  }
2490  else
2491  sol[i] = x;
2492  if (sol[i] != NULL)
2493  {
2494  x = sol[i];
2495  sol[i] = n_Div(x, d->m,_R->cf);
2496  n_Delete(&x,_R->cf);
2497  }
2498  i--;
2499  }
2500  this->smAllDel();

◆ smTriangular()

void sparse_number_mat::smTriangular ( )

Definition at line 2397 of file sparsmat.cc.

2399 {
2400  tored--;
2401  this->smZeroToredElim();
2402  if (sing != 0) return;
2403  while (act > 1)
2404  {
2405  this->smRealPivot();
2406  this->smSelectPR();
2407  this->smGElim();
2408  crd++;
2409  this->smColToRow();
2410  act--;
2411  this->smRowToCol();
2412  this->smZeroToredElim();
2413  if (sing != 0) return;
2414  }
2415  if (TEST_OPT_PROT) PrintS(".\n");
2416  piv = m_act[1];
2417  rpiv = piv->pos;
2418  m_act[1] = piv->n;
2419  piv->n = NULL;
2420  crd++;
2421  this->smColToRow();
2422  act--;
2423  this->smRowToCol();

◆ smZeroToredElim()

void sparse_number_mat::smZeroToredElim ( )
private

Definition at line 2772 of file sparsmat.cc.

2774 {
2775  smnumber a;
2776  int i = act;
2777 
2778  loop
2779  {
2780  if (i == 0) return;
2781  a = m_act[i];
2782  if ((a==NULL) || (a->pos>tored))
2783  {
2784  sing = 1;
2785  this->smAllDel();
2786  return;
2787  }
2788  i--;
2789  }

Field Documentation

◆ _R

ring sparse_number_mat::_R
private

Definition at line 2291 of file sparsmat.cc.

◆ act

int sparse_number_mat::act
private

Definition at line 2277 of file sparsmat.cc.

◆ crd

int sparse_number_mat::crd
private

Definition at line 2278 of file sparsmat.cc.

◆ dumm

smnumber sparse_number_mat::dumm
private

Definition at line 2290 of file sparsmat.cc.

◆ m_act

smnumber* sparse_number_mat::m_act
private

Definition at line 2285 of file sparsmat.cc.

◆ m_res

smnumber* sparse_number_mat::m_res
private

Definition at line 2286 of file sparsmat.cc.

◆ m_row

smnumber* sparse_number_mat::m_row
private

Definition at line 2287 of file sparsmat.cc.

◆ ncols

int sparse_number_mat::ncols
private

Definition at line 2276 of file sparsmat.cc.

◆ nrows

int sparse_number_mat::nrows
private

Definition at line 2276 of file sparsmat.cc.

◆ perm

int* sparse_number_mat::perm
private

Definition at line 2282 of file sparsmat.cc.

◆ piv

smnumber sparse_number_mat::piv
private

Definition at line 2289 of file sparsmat.cc.

◆ red

smnumber sparse_number_mat::red
private

Definition at line 2288 of file sparsmat.cc.

◆ rpiv

int sparse_number_mat::rpiv
private

Definition at line 2281 of file sparsmat.cc.

◆ sing

int sparse_number_mat::sing
private

Definition at line 2280 of file sparsmat.cc.

◆ sol

number* sparse_number_mat::sol
private

Definition at line 2283 of file sparsmat.cc.

◆ tored

int sparse_number_mat::tored
private

Definition at line 2279 of file sparsmat.cc.

◆ wcl

int * sparse_number_mat::wcl
private

Definition at line 2284 of file sparsmat.cc.

◆ wrw

int* sparse_number_mat::wrw
private

Definition at line 2284 of file sparsmat.cc.


The documentation for this class was generated from the following file:
sparse_number_mat::smGElim
void smGElim()
Definition: sparsmat.cc:2575
sparse_number_mat::crd
int crd
Definition: sparsmat.cc:2278
sparse_number_mat::smRowToCol
void smRowToCol()
Definition: sparsmat.cc:2739
j
int j
Definition: facHensel.cc:105
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:100
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
sparse_number_mat::wcl
int * wcl
Definition: sparsmat.cc:2284
ADDRESS
void * ADDRESS
Definition: auxiliary.h:135
h
STATIC_VAR Poly * h
Definition: janet.cc:971
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:454
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:463
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:510
loop
#define loop
Definition: structs.h:79
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
sparse_number_mat::m_row
smnumber * m_row
Definition: sparsmat.cc:2287
sparse_number_mat::m_res
smnumber * m_res
Definition: sparsmat.cc:2286
ap
Definition: ap.h:35
sm_Poly2Smnumber
static smnumber sm_Poly2Smnumber(poly, const ring)
Definition: sparsmat.cc:2844
sparse_number_mat::dumm
smnumber dumm
Definition: sparsmat.cc:2290
sparse_number_mat::ncols
int ncols
Definition: sparsmat.cc:2276
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:655
i
int i
Definition: cfEzgcd.cc:125
res
CanonicalForm res
Definition: facAbsFact.cc:64
sm_Smnumber2Poly
static poly sm_Smnumber2Poly(number, const ring)
Definition: sparsmat.cc:2875
smnumber
sm_nrec * smnumber
Definition: sparsmat.cc:2256
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
sparse_number_mat::smColToRow
void smColToRow()
Definition: sparsmat.cc:2719
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
sm_NumberDelete
static void sm_NumberDelete(smnumber *, const ring R)
Definition: sparsmat.cc:2824
sparse_number_mat::rpiv
int rpiv
Definition: sparsmat.cc:2281
sparse_number_mat::smZeroToredElim
void smZeroToredElim()
Definition: sparsmat.cc:2772
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:635
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
sparse_number_mat::smSelectPR
void smSelectPR()
Definition: sparsmat.cc:2655
sparse_number_mat::smRealPivot
void smRealPivot()
Definition: sparsmat.cc:2524
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:537
sparse_number_mat::perm
int * perm
Definition: sparsmat.cc:2282
sparse_number_mat::wrw
int * wrw
Definition: sparsmat.cc:2284
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:556
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:668
sparse_number_mat::sing
int sing
Definition: sparsmat.cc:2280
sip_sideal_bin
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:26
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:563
sparse_number_mat::nrows
int nrows
Definition: sparsmat.cc:2276
sparse_number_mat::_R
ring _R
Definition: sparsmat.cc:2291
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:34
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:493
sparse_number_mat::smAllDel
void smAllDel()
Definition: sparsmat.cc:2794
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:450
sparse_number_mat::red
smnumber red
Definition: sparsmat.cc:2288
m
int m
Definition: cfEzgcd.cc:121
NULL
#define NULL
Definition: omList.c:11
sparse_number_mat::tored
int tored
Definition: sparsmat.cc:2279
R
#define R
Definition: sirandom.c:27
p
int p
Definition: cfModGcd.cc:4019
sparse_number_mat::act
int act
Definition: sparsmat.cc:2277
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
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:614
smnrec_bin
STATIC_VAR omBin smnrec_bin
Definition: sparsmat.cc:2263
sparse_number_mat::m_act
smnumber * m_act
Definition: sparsmat.cc:2285
smNumberCopy
static smnumber smNumberCopy(smnumber)
Definition: sparsmat.cc:2833
sparse_number_mat::piv
smnumber piv
Definition: sparsmat.cc:2289
sparse_number_mat::sol
number * sol
Definition: sparsmat.cc:2283
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:257
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209