My Project  UNKNOWN_GIT_VERSION
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 2330 of file sparsmat.cc.

Constructor & Destructor Documentation

◆ sparse_number_mat()

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

Definition at line 2406 of file sparsmat.cc.

2407 {
2408  int i;
2409  poly* pmat;
2410  _R=R;
2411 
2412  crd = sing = 0;
2413  act = ncols = smat->ncols;
2414  tored = nrows = smat->rank;
2415  i = tored+1;
2416  perm = (int *)omAlloc(sizeof(int)*i);
2417  m_row = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2418  wrw = (int *)omAlloc(sizeof(int)*i);
2419  i = ncols+1;
2420  wcl = (int *)omAlloc(sizeof(int)*i);
2421  m_act = (smnumber *)omAlloc(sizeof(smnumber)*i);
2422  m_res = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2424  pmat = smat->m;
2425  for(i=ncols; i; i--)
2426  {
2427  m_act[i] = sm_Poly2Smnumber(pmat[i-1],_R);
2428  }
2429  omFreeSize((ADDRESS)pmat,smat->ncols*sizeof(poly));
2431 }
void * ADDRESS
Definition: auxiliary.h:133
int i
Definition: cfEzgcd.cc:125
smnumber * m_act
Definition: sparsmat.cc:2341
smnumber * m_res
Definition: sparsmat.cc:2342
smnumber * m_row
Definition: sparsmat.cc:2343
#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
omBin sip_sideal_bin
Definition: simpleideals.cc:29
#define R
Definition: sirandom.c:26
static omBin smnrec_bin
Definition: sparsmat.cc:2319
static smnumber sm_Poly2Smnumber(poly, const ring)
Definition: sparsmat.cc:2900
sm_nrec * smnumber
Definition: sparsmat.cc:2312

◆ ~sparse_number_mat()

sparse_number_mat::~sparse_number_mat ( )

Definition at line 2436 of file sparsmat.cc.

2437 {
2438  int i;
2440  i = ncols+1;
2441  omFreeSize((ADDRESS)m_res, sizeof(smnumber)*i);
2442  omFreeSize((ADDRESS)m_act, sizeof(smnumber)*i);
2443  omFreeSize((ADDRESS)wcl, sizeof(int)*i);
2444  i = nrows+1;
2445  omFreeSize((ADDRESS)wrw, sizeof(int)*i);
2446  omFreeSize((ADDRESS)m_row, sizeof(smnumber)*i);
2447  omFreeSize((ADDRESS)perm, sizeof(int)*i);
2448 }

Member Function Documentation

◆ smAllDel()

void sparse_number_mat::smAllDel ( )
private

Definition at line 2850 of file sparsmat.cc.

2851 {
2852  smnumber a;
2853  int i;
2854 
2855  for (i=act; i; i--)
2856  {
2857  a = m_act[i];
2858  while (a != NULL)
2859  sm_NumberDelete(&a,_R);
2860  }
2861  for (i=crd; i; i--)
2862  {
2863  a = m_res[i];
2864  while (a != NULL)
2865  sm_NumberDelete(&a,_R);
2866  }
2867  if (act)
2868  {
2869  for (i=nrows; i; i--)
2870  {
2871  a = m_row[i];
2872  while (a != NULL)
2873  sm_NumberDelete(&a,_R);
2874  }
2875  }
2876 }
#define NULL
Definition: omList.c:10
static void sm_NumberDelete(smnumber *, const ring R)
Definition: sparsmat.cc:2880

◆ smColToRow()

void sparse_number_mat::smColToRow ( )
private

Definition at line 2775 of file sparsmat.cc.

2776 {
2777  smnumber c = m_act[act];
2778  smnumber h;
2779 
2780  while (c != NULL)
2781  {
2782  h = c;
2783  c = c->n;
2784  h->n = m_row[h->pos];
2785  m_row[h->pos] = h;
2786  h->pos = crd;
2787  }
2788 }
static Poly * h
Definition: janet.cc:972

◆ smGElim()

void sparse_number_mat::smGElim ( )
private

Definition at line 2631 of file sparsmat.cc.

2632 {
2633  number p = n_Invers(piv->m,_R->cf); // pivotelement
2634  smnumber c = m_act[act]; // pivotcolumn
2635  smnumber r = red; // row to reduce
2636  smnumber res, a, b;
2637  number w, ha, hb;
2638 
2639  if ((c == NULL) || (r == NULL))
2640  {
2641  while (r!=NULL) sm_NumberDelete(&r,_R);
2642  return;
2643  }
2644  do
2645  {
2646  a = m_act[r->pos];
2647  res = dumm;
2648  res->n = NULL;
2649  b = c;
2650  w = n_Mult(r->m, p,_R->cf);
2651  n_Delete(&r->m,_R->cf);
2652  r->m = w;
2653  loop // combine the chains a and b: a + w*b
2654  {
2655  if (a == NULL)
2656  {
2657  do
2658  {
2659  res = res->n = smNumberCopy(b);
2660  res->m = n_Mult(b->m, w,_R->cf);
2661  b = b->n;
2662  } while (b != NULL);
2663  break;
2664  }
2665  if (a->pos < b->pos)
2666  {
2667  res = res->n = a;
2668  a = a->n;
2669  }
2670  else if (a->pos > b->pos)
2671  {
2672  res = res->n = smNumberCopy(b);
2673  res->m = n_Mult(b->m, w,_R->cf);
2674  b = b->n;
2675  }
2676  else
2677  {
2678  hb = n_Mult(b->m, w,_R->cf);
2679  ha = n_Add(a->m, hb,_R->cf);
2680  n_Delete(&hb,_R->cf);
2681  n_Delete(&a->m,_R->cf);
2682  if (n_IsZero(ha,_R->cf))
2683  {
2684  sm_NumberDelete(&a,_R);
2685  }
2686  else
2687  {
2688  a->m = ha;
2689  res = res->n = a;
2690  a = a->n;
2691  }
2692  b = b->n;
2693  }
2694  if (b == NULL)
2695  {
2696  res->n = a;
2697  break;
2698  }
2699  }
2700  m_act[r->pos] = dumm->n;
2701  sm_NumberDelete(&r,_R);
2702  } while (r != NULL);
2703  n_Delete(&p,_R->cf);
2704 }
int p
Definition: cfModGcd.cc:4019
CanonicalForm b
Definition: cfModGcd.cc:4044
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:636
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:656
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:564
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
CanonicalForm res
Definition: facAbsFact.cc:64
const CanonicalForm & w
Definition: facAbsFact.cc:55
static smnumber smNumberCopy(smnumber)
Definition: sparsmat.cc:2889
#define loop
Definition: structs.h:78

◆ smIsSing()

int sparse_number_mat::smIsSing ( )
inline

Definition at line 2358 of file sparsmat.cc.

2358 { return sing; }

◆ smRealPivot()

void sparse_number_mat::smRealPivot ( )
private

Definition at line 2580 of file sparsmat.cc.

2581 {
2582  smnumber a;
2583  number x, xo;
2584  int i, copt, ropt;
2585 
2586  xo=n_Init(0,_R->cf);
2587  for (i=act; i; i--)
2588  {
2589  a = m_act[i];
2590  while ((a!=NULL) && (a->pos<=tored))
2591  {
2592  x = a->m;
2593  if (n_GreaterZero(x,_R->cf))
2594  {
2595  if (n_Greater(x,xo,_R->cf))
2596  {
2597  n_Delete(&xo,_R->cf);
2598  xo = n_Copy(x,_R->cf);
2599  copt = i;
2600  ropt = a->pos;
2601  }
2602  }
2603  else
2604  {
2605  xo = n_InpNeg(xo,_R->cf);
2606  if (n_Greater(xo,x,_R->cf))
2607  {
2608  n_Delete(&xo,_R->cf);
2609  xo = n_Copy(x,_R->cf);
2610  copt = i;
2611  ropt = a->pos;
2612  }
2613  xo = n_InpNeg(xo,_R->cf);
2614  }
2615  a = a->n;
2616  }
2617  }
2618  rpiv = ropt;
2619  if (copt != act)
2620  {
2621  a = m_act[act];
2622  m_act[act] = m_act[copt];
2623  m_act[copt] = a;
2624  }
2625  n_Delete(&xo,_R->cf);
2626 }
Variable x
Definition: cfModGcd.cc:4023
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
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:494
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:557
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:511
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:538

◆ smRes2Ideal()

ideal sparse_number_mat::smRes2Ideal ( )

Definition at line 2561 of file sparsmat.cc.

2562 {
2563  int i, j;
2564  ideal res = idInit(crd, 1);
2565 
2566  for (i=crd; i; i--)
2567  {
2568  j = perm[i]-1;
2569  res->m[j] = sm_Smnumber2Poly(sol[i],_R);
2570  }
2571  omFreeSize((ADDRESS)sol, sizeof(number)*(crd+1));
2572  return res;
2573 }
int j
Definition: facHensel.cc:105
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
static poly sm_Smnumber2Poly(number, const ring)
Definition: sparsmat.cc:2931

◆ smRowToCol()

void sparse_number_mat::smRowToCol ( )
private

Definition at line 2795 of file sparsmat.cc.

2796 {
2797  smnumber r = m_row[rpiv];
2798  smnumber a, ap, h;
2799 
2800  m_row[rpiv] = NULL;
2801  perm[crd] = rpiv;
2802  piv->pos = crd;
2803  m_res[crd] = piv;
2804  while (r != NULL)
2805  {
2806  ap = m_res[r->pos];
2807  loop
2808  {
2809  a = ap->n;
2810  if (a == NULL)
2811  {
2812  ap->n = h = r;
2813  r = r->n;
2814  h->n = a;
2815  h->pos = crd;
2816  break;
2817  }
2818  ap = a;
2819  }
2820  }
2821 }
Definition: ap.h:40

◆ smSelectPR()

void sparse_number_mat::smSelectPR ( )
private

Definition at line 2711 of file sparsmat.cc.

2712 {
2713  smnumber b = dumm;
2714  smnumber a, ap;
2715  int i;
2716 
2717  if (TEST_OPT_PROT)
2718  {
2719  if ((crd+1)%10)
2720  PrintS(".");
2721  else
2722  PrintS(".\n");
2723  }
2724  a = m_act[act];
2725  if (a->pos < rpiv)
2726  {
2727  do
2728  {
2729  ap = a;
2730  a = a->n;
2731  } while (a->pos < rpiv);
2732  ap->n = a->n;
2733  }
2734  else
2735  m_act[act] = a->n;
2736  piv = a;
2737  a->n = NULL;
2738  for (i=1; i<act; i++)
2739  {
2740  a = m_act[i];
2741  if (a->pos < rpiv)
2742  {
2743  loop
2744  {
2745  ap = a;
2746  a = a->n;
2747  if ((a == NULL) || (a->pos > rpiv))
2748  break;
2749  if (a->pos == rpiv)
2750  {
2751  ap->n = a->n;
2752  a->m = n_InpNeg(a->m,_R->cf);
2753  b = b->n = a;
2754  b->pos = i;
2755  break;
2756  }
2757  }
2758  }
2759  else if (a->pos == rpiv)
2760  {
2761  m_act[i] = a->n;
2762  a->m = n_InpNeg(a->m,_R->cf);
2763  b = b->n = a;
2764  b->pos = i;
2765  }
2766  }
2767  b->n = NULL;
2768  red = dumm->n;
2769 }
#define TEST_OPT_PROT
Definition: options.h:102
void PrintS(const char *s)
Definition: reporter.cc:284

◆ smSolv()

void sparse_number_mat::smSolv ( )

Definition at line 2484 of file sparsmat.cc.

2485 {
2486  int i, j;
2487  number x, y, z;
2488  smnumber s, d, r = m_row[nrows];
2489 
2490  m_row[nrows] = NULL;
2491  sol = (number *)omAlloc0(sizeof(number)*(crd+1));
2492  while (r != NULL) // expand the rigth hand side
2493  {
2494  sol[r->pos] = r->m;
2495  s = r;
2496  r = r->n;
2498  }
2499  i = crd; // solve triangular system
2500  if (sol[i] != NULL)
2501  {
2502  x = sol[i];
2503  sol[i] = n_Div(x, m_res[i]->m,_R->cf);
2504  n_Delete(&x,_R->cf);
2505  }
2506  i--;
2507  while (i > 0)
2508  {
2509  x = NULL;
2510  d = m_res[i];
2511  s = d->n;
2512  while (s != NULL)
2513  {
2514  j = s->pos;
2515  if (sol[j] != NULL)
2516  {
2517  z = n_Mult(sol[j], s->m,_R->cf);
2518  if (x != NULL)
2519  {
2520  y = x;
2521  x = n_Sub(y, z,_R->cf);
2522  n_Delete(&y,_R->cf);
2523  n_Delete(&z,_R->cf);
2524  }
2525  else
2526  x = n_InpNeg(z,_R->cf);
2527  }
2528  s = s->n;
2529  }
2530  if (sol[i] != NULL)
2531  {
2532  if (x != NULL)
2533  {
2534  y = n_Add(x, sol[i],_R->cf);
2535  n_Delete(&x,_R->cf);
2536  if (n_IsZero(y,_R->cf))
2537  {
2538  n_Delete(&sol[i],_R->cf);
2539  sol[i] = NULL;
2540  }
2541  else
2542  sol[i] = y;
2543  }
2544  }
2545  else
2546  sol[i] = x;
2547  if (sol[i] != NULL)
2548  {
2549  x = sol[i];
2550  sol[i] = n_Div(x, d->m,_R->cf);
2551  n_Delete(&x,_R->cf);
2552  }
2553  i--;
2554  }
2555  this->smAllDel();
2556 }
int m
Definition: cfEzgcd.cc:121
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:615
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:669
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57

◆ smTriangular()

void sparse_number_mat::smTriangular ( )

Definition at line 2453 of file sparsmat.cc.

2454 {
2455  tored--;
2456  this->smZeroToredElim();
2457  if (sing != 0) return;
2458  while (act > 1)
2459  {
2460  this->smRealPivot();
2461  this->smSelectPR();
2462  this->smGElim();
2463  crd++;
2464  this->smColToRow();
2465  act--;
2466  this->smRowToCol();
2467  this->smZeroToredElim();
2468  if (sing != 0) return;
2469  }
2470  if (TEST_OPT_PROT) PrintS(".\n");
2471  piv = m_act[1];
2472  rpiv = piv->pos;
2473  m_act[1] = piv->n;
2474  piv->n = NULL;
2475  crd++;
2476  this->smColToRow();
2477  act--;
2478  this->smRowToCol();
2479 }
void smZeroToredElim()
Definition: sparsmat.cc:2828

◆ smZeroToredElim()

void sparse_number_mat::smZeroToredElim ( )
private

Definition at line 2828 of file sparsmat.cc.

2829 {
2830  smnumber a;
2831  int i = act;
2832 
2833  loop
2834  {
2835  if (i == 0) return;
2836  a = m_act[i];
2837  if ((a==NULL) || (a->pos>tored))
2838  {
2839  sing = 1;
2840  this->smAllDel();
2841  return;
2842  }
2843  i--;
2844  }
2845 }

Field Documentation

◆ _R

ring sparse_number_mat::_R
private

Definition at line 2347 of file sparsmat.cc.

◆ act

int sparse_number_mat::act
private

Definition at line 2333 of file sparsmat.cc.

◆ crd

int sparse_number_mat::crd
private

Definition at line 2334 of file sparsmat.cc.

◆ dumm

smnumber sparse_number_mat::dumm
private

Definition at line 2346 of file sparsmat.cc.

◆ m_act

smnumber* sparse_number_mat::m_act
private

Definition at line 2341 of file sparsmat.cc.

◆ m_res

smnumber* sparse_number_mat::m_res
private

Definition at line 2342 of file sparsmat.cc.

◆ m_row

smnumber* sparse_number_mat::m_row
private

Definition at line 2343 of file sparsmat.cc.

◆ ncols

int sparse_number_mat::ncols
private

Definition at line 2332 of file sparsmat.cc.

◆ nrows

int sparse_number_mat::nrows
private

Definition at line 2332 of file sparsmat.cc.

◆ perm

int* sparse_number_mat::perm
private

Definition at line 2338 of file sparsmat.cc.

◆ piv

smnumber sparse_number_mat::piv
private

Definition at line 2345 of file sparsmat.cc.

◆ red

smnumber sparse_number_mat::red
private

Definition at line 2344 of file sparsmat.cc.

◆ rpiv

int sparse_number_mat::rpiv
private

Definition at line 2337 of file sparsmat.cc.

◆ sing

int sparse_number_mat::sing
private

Definition at line 2336 of file sparsmat.cc.

◆ sol

number* sparse_number_mat::sol
private

Definition at line 2339 of file sparsmat.cc.

◆ tored

int sparse_number_mat::tored
private

Definition at line 2335 of file sparsmat.cc.

◆ wcl

int * sparse_number_mat::wcl
private

Definition at line 2340 of file sparsmat.cc.

◆ wrw

int* sparse_number_mat::wrw
private

Definition at line 2340 of file sparsmat.cc.


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