My Project
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 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.

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));
2376 }
void * ADDRESS
Definition: auxiliary.h:119
int i
Definition: cfEzgcd.cc:132
smnumber * m_act
Definition: sparsmat.cc:2286
smnumber * m_res
Definition: sparsmat.cc:2287
smnumber * m_row
Definition: sparsmat.cc:2288
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:27
#define R
Definition: sirandom.c:27
STATIC_VAR omBin smnrec_bin
Definition: sparsmat.cc:2264
static smnumber sm_Poly2Smnumber(poly, const ring)
Definition: sparsmat.cc:2845
sm_nrec * smnumber
Definition: sparsmat.cc:2257

◆ ~sparse_number_mat()

sparse_number_mat::~sparse_number_mat ( )

Definition at line 2381 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);
2393 }

Member Function Documentation

◆ smAllDel()

void sparse_number_mat::smAllDel ( )
private

Definition at line 2795 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  }
2821 }
#define NULL
Definition: omList.c:12
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.

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  }
2733 }
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ smGElim()

void sparse_number_mat::smGElim ( )
private

Definition at line 2576 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);
2649 }
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
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:633
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:647
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:561
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
static smnumber smNumberCopy(smnumber)
Definition: sparsmat.cc:2834
#define loop
Definition: structs.h:75

◆ smIsSing()

int sparse_number_mat::smIsSing ( )
inline

Definition at line 2303 of file sparsmat.cc.

2303 { return sing; }

◆ smRealPivot()

void sparse_number_mat::smRealPivot ( )
private

Definition at line 2525 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);
2571 }
Variable x
Definition: cfModGcd.cc:4082
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:448
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:491
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:554
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:508
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:535

◆ smRes2Ideal()

ideal sparse_number_mat::smRes2Ideal ( )

Definition at line 2506 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;
2518 }
int j
Definition: facHensel.cc:110
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
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.

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  }
2766 }
Definition: ap.h:40

◆ smSelectPR()

void sparse_number_mat::smSelectPR ( )
private

Definition at line 2656 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;
2714 }
#define TEST_OPT_PROT
Definition: options.h:104
void PrintS(const char *s)
Definition: reporter.cc:284

◆ smSolv()

void sparse_number_mat::smSolv ( )

Definition at line 2429 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();
2501 }
int m
Definition: cfEzgcd.cc:128
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:612
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:652
const CanonicalForm int s
Definition: facAbsFact.cc:51
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.

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();
2424 }
void smZeroToredElim()
Definition: sparsmat.cc:2773

◆ smZeroToredElim()

void sparse_number_mat::smZeroToredElim ( )
private

Definition at line 2773 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  }
2790 }

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: