My Project
Public Member Functions | Private Member Functions | Private Attributes
sparse_mat Class Reference

Public Member Functions

 sparse_mat (ideal, const ring)
 
 ~sparse_mat ()
 
int smGetSign ()
 
smpolysmGetAct ()
 
int smGetRed ()
 
ideal smRes2Mod ()
 
poly smDet ()
 
void smNewBareiss (int, int)
 
void smToIntvec (intvec *)
 

Private Member Functions

void smColToRow ()
 
void smRowToCol ()
 
void smFinalMult ()
 
void smSparseHomog ()
 
void smWeights ()
 
void smPivot ()
 
void smNewWeights ()
 
void smNewPivot ()
 
void smZeroElim ()
 
void smToredElim ()
 
void smCopToRes ()
 
void smSelectPR ()
 
void sm1Elim ()
 
void smHElim ()
 
void smMultCol ()
 
poly smMultPoly (smpoly)
 
void smActDel ()
 
void smColDel ()
 
void smPivDel ()
 
void smSign ()
 
void smInitPerm ()
 
int smCheckNormalize ()
 
void smNormalize ()
 

Private Attributes

int nrows
 
int ncols
 
int sign
 
int act
 
int crd
 
int tored
 
int inred
 
int rpiv
 
int cpiv
 
int normalize
 
int * perm
 
float wpoints
 
float * wrw
 
float * wcl
 
smpolym_act
 
smpolym_res
 
smpolym_row
 
smpoly red
 
smpoly piv
 
smpoly oldpiv
 
smpoly dumm
 
ring _R
 

Detailed Description

Definition at line 124 of file sparsmat.cc.

Constructor & Destructor Documentation

◆ sparse_mat()

sparse_mat::sparse_mat ( ideal  smat,
const ring  RR 
)

Definition at line 386 of file sparsmat.cc.

387 {
388  int i;
389  poly* pmat;
390  _R=RR;
391 
392  ncols = smat->ncols;
393  nrows = id_RankFreeModule(smat,RR);
394  if (nrows <= 0)
395  {
396  m_act = NULL;
397  return;
398  }
399  sign = 1;
400  inred = act = ncols;
401  crd = 0;
402  tored = nrows; // without border
403  i = tored+1;
404  perm = (int *)omAlloc(sizeof(int)*(i+1));
405  perm[i] = 0;
406  m_row = (smpoly *)omAlloc0(sizeof(smpoly)*i);
407  wrw = (float *)omAlloc(sizeof(float)*i);
408  i = ncols+1;
409  wcl = (float *)omAlloc(sizeof(float)*i);
410  m_act = (smpoly *)omAlloc(sizeof(smpoly)*i);
411  m_res = (smpoly *)omAlloc0(sizeof(smpoly)*i);
414  m_res[0]->m = NULL;
415  pmat = smat->m;
416  for(i=ncols; i; i--)
417  {
418  m_act[i] = sm_Poly2Smpoly(pmat[i-1], RR);
419  pmat[i-1] = NULL;
420  }
421  this->smZeroElim();
422  oldpiv = NULL;
423 }
int i
Definition: cfEzgcd.cc:132
smpoly * m_row
Definition: sparsmat.cc:139
float * wcl
Definition: sparsmat.cc:136
smpoly * m_res
Definition: sparsmat.cc:138
smpoly dumm
Definition: sparsmat.cc:142
float * wrw
Definition: sparsmat.cc:136
smpoly * m_act
Definition: sparsmat.cc:137
smpoly oldpiv
Definition: sparsmat.cc:141
void smZeroElim()
Definition: sparsmat.cc:1134
int * perm
Definition: sparsmat.cc:134
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
VAR omBin smprec_bin
Definition: sparsmat.cc:74
sm_prec * smpoly
Definition: sparsmat.cc:46
static smpoly sm_Poly2Smpoly(poly, const ring)
Definition: sparsmat.cc:2097

◆ ~sparse_mat()

sparse_mat::~sparse_mat ( )

Definition at line 428 of file sparsmat.cc.

429 {
430  int i;
431  if (m_act == NULL) return;
434  i = ncols+1;
435  omFreeSize((ADDRESS)m_res, sizeof(smpoly)*i);
436  omFreeSize((ADDRESS)m_act, sizeof(smpoly)*i);
437  omFreeSize((ADDRESS)wcl, sizeof(float)*i);
438  i = nrows+1;
439  omFreeSize((ADDRESS)wrw, sizeof(float)*i);
440  omFreeSize((ADDRESS)m_row, sizeof(smpoly)*i);
441  omFreeSize((ADDRESS)perm, sizeof(int)*(i+1));
442 }
void * ADDRESS
Definition: auxiliary.h:119
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259

Member Function Documentation

◆ sm1Elim()

void sparse_mat::sm1Elim ( )
private

Definition at line 799 of file sparsmat.cc.

800 {
801  poly p = piv->m; // pivotelement
802  smpoly c = m_act[act]; // pivotcolumn
803  smpoly r = red; // row to reduce
804  smpoly res, a, b;
805  poly w, ha, hb;
806 
807  if ((c == NULL) || (r == NULL))
808  {
809  while (r!=NULL) sm_ElemDelete(&r,_R);
810  return;
811  }
812  do
813  {
814  a = m_act[r->pos];
815  res = dumm;
816  res->n = NULL;
817  b = c;
818  w = r->m;
819  loop // combine the chains a and b: p*a + w*b
820  {
821  if (a == NULL)
822  {
823  do
824  {
825  res = res->n = smElemCopy(b);
826  res->m = pp_Mult_qq(b->m, w,_R);
827  res->e = 1;
828  res->f = sm_PolyWeight(res,_R);
829  b = b->n;
830  } while (b != NULL);
831  break;
832  }
833  if (a->pos < b->pos)
834  {
835  res = res->n = a;
836  a = a->n;
837  }
838  else if (a->pos > b->pos)
839  {
840  res = res->n = smElemCopy(b);
841  res->m = pp_Mult_qq(b->m, w,_R);
842  res->e = 1;
843  res->f = sm_PolyWeight(res,_R);
844  b = b->n;
845  }
846  else
847  {
848  ha = pp_Mult_qq(a->m, p,_R);
849  p_Delete(&a->m,_R);
850  hb = pp_Mult_qq(b->m, w,_R);
851  ha = p_Add_q(ha, hb,_R);
852  if (ha != NULL)
853  {
854  a->m = ha;
855  a->e = 1;
856  a->f = sm_PolyWeight(a,_R);
857  res = res->n = a;
858  a = a->n;
859  }
860  else
861  {
862  sm_ElemDelete(&a,_R);
863  }
864  b = b->n;
865  }
866  if (b == NULL)
867  {
868  res->n = a;
869  break;
870  }
871  }
872  m_act[r->pos] = dumm->n;
873  sm_ElemDelete(&r,_R);
874  } while (r != NULL);
875 }
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
smpoly red
Definition: sparsmat.cc:140
smpoly piv
Definition: sparsmat.cc:141
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:896
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1111
static void sm_ElemDelete(smpoly *, const ring)
Definition: sparsmat.cc:2076
static float sm_PolyWeight(smpoly, const ring)
Definition: sparsmat.cc:2175
static smpoly smElemCopy(smpoly)
Definition: sparsmat.cc:2085
#define loop
Definition: structs.h:80

◆ smActDel()

void sparse_mat::smActDel ( )
private

Definition at line 1475 of file sparsmat.cc.

1476 {
1477  smpoly a;
1478  int i;
1479 
1480  for (i=act; i; i--)
1481  {
1482  a = m_act[i];
1483  do
1484  {
1485  sm_ElemDelete(&a,_R);
1486  } while (a != NULL);
1487  }
1488 }

◆ smCheckNormalize()

int sparse_mat::smCheckNormalize ( )
private

Definition at line 1413 of file sparsmat.cc.

1414 {
1415  int i;
1416  smpoly a;
1417 
1418  for (i=act; i; i--)
1419  {
1420  a = m_act[i];
1421  do
1422  {
1423  if(sm_HaveDenom(a->m,_R)) return 1;
1424  a = a->n;
1425  } while (a != NULL);
1426  }
1427  return 0;
1428 }
static BOOLEAN sm_HaveDenom(poly, const ring)
Definition: sparsmat.cc:2204

◆ smColDel()

void sparse_mat::smColDel ( )
private

Definition at line 1493 of file sparsmat.cc.

1494 {
1495  smpoly a = m_act[act];
1496 
1497  while (a != NULL)
1498  {
1499  sm_ElemDelete(&a,_R);
1500  }
1501 }

◆ smColToRow()

void sparse_mat::smColToRow ( )
private

Definition at line 1081 of file sparsmat.cc.

1082 {
1083  smpoly c = m_act[act];
1084  smpoly h;
1085 
1086  while (c != NULL)
1087  {
1088  h = c;
1089  c = c->n;
1090  h->n = m_row[h->pos];
1091  m_row[h->pos] = h;
1092  h->pos = crd;
1093  }
1094 }
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ smCopToRes()

void sparse_mat::smCopToRes ( )
private

Definition at line 1203 of file sparsmat.cc.

1204 {
1205  smpoly a,ap,r,h;
1206  int i,j,k,l;
1207 
1208  i = 0;
1209  if (act)
1210  {
1211  a = m_act[act]; // init perm
1212  do
1213  {
1214  i++;
1215  perm[crd+i] = a->pos;
1216  a = a->n;
1217  } while ((a != NULL) && (a->pos <= tored));
1218  for (j=act-1;j;j--) // load all positions of perm
1219  {
1220  a = m_act[j];
1221  k = 1;
1222  loop
1223  {
1224  if (perm[crd+k] >= a->pos)
1225  {
1226  if (perm[crd+k] > a->pos)
1227  {
1228  for (l=i;l>=k;l--) perm[crd+l+1] = perm[crd+l];
1229  perm[crd+k] = a->pos;
1230  i++;
1231  }
1232  a = a->n;
1233  if ((a == NULL) || (a->pos > tored)) break;
1234  }
1235  k++;
1236  if ((k > i) && (a->pos <= tored))
1237  {
1238  do
1239  {
1240  i++;
1241  perm[crd+i] = a->pos;
1242  a = a->n;
1243  } while ((a != NULL) && (a->pos <= tored));
1244  break;
1245  }
1246  }
1247  }
1248  }
1249  for (j=act;j;j--) // renumber m_act
1250  {
1251  k = 1;
1252  a = m_act[j];
1253  while ((a != NULL) && (a->pos <= tored))
1254  {
1255  if (perm[crd+k] == a->pos)
1256  {
1257  a->pos = crd+k;
1258  a = a->n;
1259  }
1260  k++;
1261  }
1262  }
1263  tored = crd+i;
1264  for(k=1;k<=i;k++) // clean this from m_row
1265  {
1266  j = perm[crd+k];
1267  if (m_row[j] != NULL)
1268  {
1269  r = m_row[j];
1270  m_row[j] = NULL;
1271  do
1272  {
1273  ap = m_res[r->pos];
1274  loop
1275  {
1276  a = ap->n;
1277  if (a == NULL)
1278  {
1279  h = ap->n = r;
1280  r = r->n;
1281  h->n = NULL;
1282  h->pos = crd+k;
1283  break;
1284  }
1285  ap = a;
1286  }
1287  } while (r!=NULL);
1288  }
1289  }
1290  while(act) // clean m_act
1291  {
1292  crd++;
1293  m_res[crd] = m_act[act];
1294  act--;
1295  }
1296  for (i=1;i<=tored;i++) // take the rest of m_row
1297  {
1298  if(m_row[i] != NULL)
1299  {
1300  tored++;
1301  r = m_row[i];
1302  m_row[i] = NULL;
1303  perm[tored] = i;
1304  do
1305  {
1306  ap = m_res[r->pos];
1307  loop
1308  {
1309  a = ap->n;
1310  if (a == NULL)
1311  {
1312  h = ap->n = r;
1313  r = r->n;
1314  h->n = NULL;
1315  h->pos = tored;
1316  break;
1317  }
1318  ap = a;
1319  }
1320  } while (r!=NULL);
1321  }
1322  }
1323  for (i=tored+1;i<=nrows;i++) // take the rest of m_row
1324  {
1325  if(m_row[i] != NULL)
1326  {
1327  r = m_row[i];
1328  m_row[i] = NULL;
1329  do
1330  {
1331  ap = m_res[r->pos];
1332  loop
1333  {
1334  a = ap->n;
1335  if (a == NULL)
1336  {
1337  h = ap->n = r;
1338  r = r->n;
1339  h->n = NULL;
1340  h->pos = i;
1341  break;
1342  }
1343  ap = a;
1344  }
1345  } while (r!=NULL);
1346  }
1347  }
1348  while (inred < ncols) // take unreducable
1349  {
1350  crd++;
1351  inred++;
1352  m_res[crd] = m_res[inred];
1353  }
1354 }
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
int j
Definition: facHensel.cc:110
Definition: ap.h:40

◆ smDet()

poly sparse_mat::smDet ( )

Definition at line 475 of file sparsmat.cc.

476 {
477  poly res = NULL;
478 
479  if (sign == 0)
480  {
481  this->smActDel();
482  return NULL;
483  }
484  if (act < 2)
485  {
486  if (act != 0) res = m_act[1]->m;
487  omFreeBin((void *)m_act[1], smprec_bin);
488  return res;
489  }
490  normalize = 0;
491  this->smInitPerm();
492  this->smPivot();
493  this->smSign();
494  this->smSelectPR();
495  this->sm1Elim();
496  crd++;
497  m_res[crd] = piv;
498  this->smColDel();
499  act--;
500  this->smZeroElim();
501  if (sign == 0)
502  {
503  this->smActDel();
504  return NULL;
505  }
506  if (act < 2)
507  {
508  this->smFinalMult();
509  this->smPivDel();
510  if (act != 0) res = m_act[1]->m;
511  omFreeBin((void *)m_act[1], smprec_bin);
512  return res;
513  }
514  loop
515  {
516  this->smNewPivot();
517  this->smSign();
518  this->smSelectPR();
519  this->smMultCol();
520  this->smHElim();
521  crd++;
522  m_res[crd] = piv;
523  this->smColDel();
524  act--;
525  this->smZeroElim();
526  if (sign == 0)
527  {
528  this->smPivDel();
529  this->smActDel();
530  return NULL;
531  }
532  if (act < 2)
533  {
534  if (TEST_OPT_PROT) PrintS(".\n");
535  this->smFinalMult();
536  this->smPivDel();
537  if (act != 0) res = m_act[1]->m;
538  omFreeBin((void *)m_act[1], smprec_bin);
539  return res;
540  }
541  }
542 }
void smFinalMult()
Definition: sparsmat.cc:1384
void smInitPerm()
Definition: sparsmat.cc:1548
void smActDel()
Definition: sparsmat.cc:1475
void sm1Elim()
Definition: sparsmat.cc:799
void smPivDel()
Definition: sparsmat.cc:1506
void smColDel()
Definition: sparsmat.cc:1493
void smPivot()
Definition: sparsmat.cc:642
int normalize
Definition: sparsmat.cc:133
void smSelectPR()
Definition: sparsmat.cc:1017
void smSign()
Definition: sparsmat.cc:1520
void smHElim()
Definition: sparsmat.cc:878
void smMultCol()
Definition: sparsmat.cc:1359
void smNewPivot()
Definition: sparsmat.cc:737
#define TEST_OPT_PROT
Definition: options.h:103
void PrintS(const char *s)
Definition: reporter.cc:284

◆ smFinalMult()

void sparse_mat::smFinalMult ( )
private

Definition at line 1384 of file sparsmat.cc.

1385 {
1386  smpoly a;
1387  poly ha;
1388  int i, f;
1389  int e = crd;
1390 
1391  for (i=act; i; i--)
1392  {
1393  a = m_act[i];
1394  do
1395  {
1396  f = a->e;
1397  if (f < e)
1398  {
1399  ha = SM_MULT(a->m, m_res[e]->m, m_res[f]->m, _R);
1400  p_Delete(&a->m,_R);
1401  if (f) SM_DIV(ha, m_res[f]->m, _R);
1402  a->m = ha;
1403  }
1404  if (normalize) p_Normalize(a->m, _R);
1405  a = a->n;
1406  } while (a != NULL);
1407  }
1408 }
int m
Definition: cfEzgcd.cc:128
FILE * f
Definition: checklibs.c:9
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3842
#define SM_DIV
Definition: sparsmat.h:24
#define SM_MULT
Definition: sparsmat.h:23

◆ smGetAct()

smpoly* sparse_mat::smGetAct ( )
inline

Definition at line 172 of file sparsmat.cc.

172 { return m_act; }

◆ smGetRed()

int sparse_mat::smGetRed ( )
inline

Definition at line 173 of file sparsmat.cc.

173 { return tored; }

◆ smGetSign()

int sparse_mat::smGetSign ( )
inline

Definition at line 171 of file sparsmat.cc.

171 { return sign; }

◆ smHElim()

void sparse_mat::smHElim ( )
private

Definition at line 878 of file sparsmat.cc.

879 {
880  poly hp = this->smMultPoly(piv);
881  poly gp = piv->m; // pivotelement
882  smpoly c = m_act[act]; // pivotcolumn
883  smpoly r = red; // row to reduce
884  smpoly res, a, b;
885  poly ha, hr, x, y;
886  int e, ip, ir, ia;
887 
888  if ((c == NULL) || (r == NULL))
889  {
890  while(r!=NULL) sm_ElemDelete(&r,_R);
891  p_Delete(&hp,_R);
892  return;
893  }
894  e = crd+1;
895  ip = piv->e;
896  do
897  {
898  a = m_act[r->pos];
899  res = dumm;
900  res->n = NULL;
901  b = c;
902  hr = r->m;
903  ir = r->e;
904  loop // combine the chains a and b: (hp,gp)*a(l) + hr*b(h)
905  {
906  if (a == NULL)
907  {
908  do
909  {
910  res = res->n = smElemCopy(b);
911  x = SM_MULT(b->m, hr, m_res[ir]->m,_R);
912  b = b->n;
913  if(ir) SM_DIV(x, m_res[ir]->m,_R);
914  res->m = x;
915  res->e = e;
916  res->f = sm_PolyWeight(res,_R);
917  } while (b != NULL);
918  break;
919  }
920  if (a->pos < b->pos)
921  {
922  res = res->n = a;
923  a = a->n;
924  }
925  else if (a->pos > b->pos)
926  {
927  res = res->n = smElemCopy(b);
928  x = SM_MULT(b->m, hr, m_res[ir]->m,_R);
929  b = b->n;
930  if(ir) SM_DIV(x, m_res[ir]->m,_R);
931  res->m = x;
932  res->e = e;
933  res->f = sm_PolyWeight(res,_R);
934  }
935  else
936  {
937  ha = a->m;
938  ia = a->e;
939  if (ir >= ia)
940  {
941  if (ir > ia)
942  {
943  x = SM_MULT(ha, m_res[ir]->m, m_res[ia]->m,_R);
944  p_Delete(&ha,_R);
945  ha = x;
946  if (ia) SM_DIV(ha, m_res[ia]->m,_R);
947  ia = ir;
948  }
949  x = SM_MULT(ha, gp, m_res[ia]->m,_R);
950  p_Delete(&ha,_R);
951  y = SM_MULT(b->m, hr, m_res[ia]->m,_R);
952  }
953  else if (ir >= ip)
954  {
955  if (ia < crd)
956  {
957  x = SM_MULT(ha, m_res[crd]->m, m_res[ia]->m,_R);
958  p_Delete(&ha,_R);
959  ha = x;
960  SM_DIV(ha, m_res[ia]->m,_R);
961  }
962  y = hp;
963  if(ir > ip)
964  {
965  y = SM_MULT(y, m_res[ir]->m, m_res[ip]->m,_R);
966  if (ip) SM_DIV(y, m_res[ip]->m,_R);
967  }
968  ia = ir;
969  x = SM_MULT(ha, y, m_res[ia]->m,_R);
970  if (y != hp) p_Delete(&y,_R);
971  p_Delete(&ha,_R);
972  y = SM_MULT(b->m, hr, m_res[ia]->m,_R);
973  }
974  else
975  {
976  x = SM_MULT(hr, m_res[ia]->m, m_res[ir]->m,_R);
977  if (ir) SM_DIV(x, m_res[ir]->m,_R);
978  y = SM_MULT(b->m, x, m_res[ia]->m,_R);
979  p_Delete(&x,_R);
980  x = SM_MULT(ha, gp, m_res[ia]->m,_R);
981  p_Delete(&ha,_R);
982  }
983  ha = p_Add_q(x, y,_R);
984  if (ha != NULL)
985  {
986  if (ia) SM_DIV(ha, m_res[ia]->m,_R);
987  a->m = ha;
988  a->e = e;
989  a->f = sm_PolyWeight(a,_R);
990  res = res->n = a;
991  a = a->n;
992  }
993  else
994  {
995  a->m = NULL;
996  sm_ElemDelete(&a,_R);
997  }
998  b = b->n;
999  }
1000  if (b == NULL)
1001  {
1002  res->n = a;
1003  break;
1004  }
1005  }
1006  m_act[r->pos] = dumm->n;
1007  sm_ElemDelete(&r,_R);
1008  } while (r != NULL);
1009  p_Delete(&hp,_R);
1010 }
Variable x
Definition: cfModGcd.cc:4084
CanonicalForm gp
Definition: cfModGcd.cc:4104
poly smMultPoly(smpoly)
Definition: sparsmat.cc:1453
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ smInitPerm()

void sparse_mat::smInitPerm ( )
private

Definition at line 1548 of file sparsmat.cc.

1549 {
1550  int i;
1551  for (i=act;i;i--) perm[i]=i;
1552 }

◆ smMultCol()

void sparse_mat::smMultCol ( )
private

Definition at line 1359 of file sparsmat.cc.

1360 {
1361  smpoly a = m_act[act];
1362  int e = crd;
1363  poly ha;
1364  int f;
1365 
1366  while (a != NULL)
1367  {
1368  f = a->e;
1369  if (f < e)
1370  {
1371  ha = SM_MULT(a->m, m_res[e]->m, m_res[f]->m,_R);
1372  p_Delete(&a->m,_R);
1373  if (f) SM_DIV(ha, m_res[f]->m,_R);
1374  a->m = ha;
1375  if (normalize) p_Normalize(a->m,_R);
1376  }
1377  a = a->n;
1378  }
1379 }

◆ smMultPoly()

poly sparse_mat::smMultPoly ( smpoly  a)
private

Definition at line 1453 of file sparsmat.cc.

1454 {
1455  int f = a->e;
1456  poly r, h;
1457 
1458  if (f < crd)
1459  {
1460  h = r = a->m;
1461  h = SM_MULT(h, m_res[crd]->m, m_res[f]->m, _R);
1462  if (f) SM_DIV(h, m_res[f]->m, _R);
1463  a->m = h;
1464  if (normalize) p_Normalize(a->m,_R);
1465  a->f = sm_PolyWeight(a,_R);
1466  return r;
1467  }
1468  else
1469  return NULL;
1470 }

◆ smNewBareiss()

void sparse_mat::smNewBareiss ( int  x,
int  y 
)

Definition at line 549 of file sparsmat.cc.

550 {
551  if ((x > 0) && (x < nrows))
552  {
553  tored -= x;
554  this->smToredElim();
555  }
556  if (y < 1) y = 1;
557  if (act <= y)
558  {
559  this->smCopToRes();
560  return;
561  }
562  normalize = this->smCheckNormalize();
563  if (normalize) this->smNormalize();
564  this->smPivot();
565  this->smSelectPR();
566  this->sm1Elim();
567  crd++;
568  this->smColToRow();
569  act--;
570  this->smRowToCol();
571  this->smZeroElim();
572  if (tored != nrows)
573  this->smToredElim();
574  if (act <= y)
575  {
576  this->smFinalMult();
577  this->smCopToRes();
578  return;
579  }
580  loop
581  {
582  if (normalize) this->smNormalize();
583  this->smNewPivot();
584  this->smSelectPR();
585  this->smMultCol();
586  this->smHElim();
587  crd++;
588  this->smColToRow();
589  act--;
590  this->smRowToCol();
591  this->smZeroElim();
592  if (tored != nrows)
593  this->smToredElim();
594  if (act <= y)
595  {
596  if (TEST_OPT_PROT) PrintS(".\n");
597  this->smFinalMult();
598  this->smCopToRes();
599  return;
600  }
601  }
602 }
void smCopToRes()
Definition: sparsmat.cc:1203
void smToredElim()
Definition: sparsmat.cc:1164
void smColToRow()
Definition: sparsmat.cc:1081
void smNormalize()
Definition: sparsmat.cc:1433
int smCheckNormalize()
Definition: sparsmat.cc:1413
void smRowToCol()
Definition: sparsmat.cc:1101

◆ smNewPivot()

void sparse_mat::smNewPivot ( )
private

Definition at line 737 of file sparsmat.cc.

738 {
739  float wopt = 1.0e30, hp = piv->f;
740  float wc, wr, wp, w;
741  smpoly a;
742  int i, copt, ropt, f, e = crd;
743 
744  this->smNewWeights();
745  for (i=act; i; i--)
746  {
747  a = m_act[i];
748  loop
749  {
750  if (a->pos > tored)
751  break;
752  w = a->f;
753  f = a->e;
754  if (f < e)
755  {
756  w *= hp;
757  if (f) w /= m_res[f]->f;
758  }
759  wc = wcl[i]-w;
760  wr = wrw[a->pos]-w;
761  if ((wr<0.25) || (wc<0.25)) // row or column with only one point
762  {
763  if (w<wopt)
764  {
765  wopt = w;
766  copt = i;
767  ropt = a->pos;
768  }
769  }
770  else // elimination
771  {
772  wp = w*(wpoints-wcl[i]-wr);
773  wp += wr*wc;
774  if (wp < wopt)
775  {
776  wopt = wp;
777  copt = i;
778  ropt = a->pos;
779  }
780  }
781  a = a->n;
782  if (a == NULL)
783  break;
784  }
785  }
786  rpiv = ropt;
787  cpiv = copt;
788  if (cpiv != act)
789  {
790  a = m_act[act];
791  m_act[act] = m_act[cpiv];
792  m_act[cpiv] = a;
793  }
794 }
float wpoints
Definition: sparsmat.cc:135
void smNewWeights()
Definition: sparsmat.cc:699

◆ smNewWeights()

void sparse_mat::smNewWeights ( )
private

Definition at line 699 of file sparsmat.cc.

700 {
701  float wc, wp, w, hp = piv->f;
702  smpoly a;
703  int i, f, e = crd;
704 
705  wp = 0.0;
706  for (i=tored; i; i--) wrw[i] = 0.0; // ???
707  for (i=act; i; i--)
708  {
709  wc = 0.0;
710  a = m_act[i];
711  loop
712  {
713  if (a->pos > tored)
714  break;
715  w = a->f;
716  f = a->e;
717  if (f < e)
718  {
719  w *= hp;
720  if (f) w /= m_res[f]->f;
721  }
722  wc += w;
723  wrw[a->pos] += w;
724  a = a->n;
725  if (a == NULL)
726  break;
727  }
728  wp += wc;
729  wcl[i] = wc;
730  }
731  wpoints = wp;
732 }

◆ smNormalize()

void sparse_mat::smNormalize ( )
private

Definition at line 1433 of file sparsmat.cc.

1434 {
1435  smpoly a;
1436  int i;
1437  int e = crd;
1438 
1439  for (i=act; i; i--)
1440  {
1441  a = m_act[i];
1442  do
1443  {
1444  if (e == a->e) p_Normalize(a->m,_R);
1445  a = a->n;
1446  } while (a != NULL);
1447  }
1448 }

◆ smPivDel()

void sparse_mat::smPivDel ( )
private

Definition at line 1506 of file sparsmat.cc.

1507 {
1508  int i=crd;
1509 
1510  while (i != 0)
1511  {
1512  sm_ElemDelete(&m_res[i],_R);
1513  i--;
1514  }
1515 }

◆ smPivot()

void sparse_mat::smPivot ( )
private

Definition at line 642 of file sparsmat.cc.

643 {
644  float wopt = 1.0e30;
645  float wc, wr, wp, w;
646  smpoly a;
647  int i, copt, ropt;
648 
649  this->smWeights();
650  for (i=act; i; i--)
651  {
652  a = m_act[i];
653  loop
654  {
655  if (a->pos > tored)
656  break;
657  w = a->f;
658  wc = wcl[i]-w;
659  wr = wrw[a->pos]-w;
660  if ((wr<0.25) || (wc<0.25)) // row or column with only one point
661  {
662  if (w<wopt)
663  {
664  wopt = w;
665  copt = i;
666  ropt = a->pos;
667  }
668  }
669  else // elimination
670  {
671  wp = w*(wpoints-wcl[i]-wr);
672  wp += wr*wc;
673  if (wp < wopt)
674  {
675  wopt = wp;
676  copt = i;
677  ropt = a->pos;
678  }
679  }
680  a = a->n;
681  if (a == NULL)
682  break;
683  }
684  }
685  rpiv = ropt;
686  cpiv = copt;
687  if (cpiv != act)
688  {
689  a = m_act[act];
690  m_act[act] = m_act[cpiv];
691  m_act[cpiv] = a;
692  }
693 }
void smWeights()
Definition: sparsmat.cc:610

◆ smRes2Mod()

ideal sparse_mat::smRes2Mod ( )

Definition at line 448 of file sparsmat.cc.

449 {
450  ideal res = idInit(crd, crd);
451  int i;
452 
453  for (i=crd; i; i--)
454  {
455  res->m[i-1] = sm_Smpoly2Poly(m_res[i],_R);
456  res->rank=si_max(res->rank, p_MaxComp(res->m[i-1],_R));
457  }
458  return res;
459 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:292
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
static poly sm_Smpoly2Poly(smpoly, const ring)
Definition: sparsmat.cc:2134

◆ smRowToCol()

void sparse_mat::smRowToCol ( )
private

Definition at line 1101 of file sparsmat.cc.

1102 {
1103  smpoly r = m_row[rpiv];
1104  smpoly a, ap, h;
1105 
1106  m_row[rpiv] = NULL;
1107  perm[crd] = rpiv;
1108  piv->pos = crd;
1109  m_res[crd] = piv;
1110  while (r != NULL)
1111  {
1112  ap = m_res[r->pos];
1113  loop
1114  {
1115  a = ap->n;
1116  if (a == NULL)
1117  {
1118  ap->n = h = r;
1119  r = r->n;
1120  h->n = a;
1121  h->pos = crd;
1122  break;
1123  }
1124  ap = a;
1125  }
1126  }
1127 }

◆ smSelectPR()

void sparse_mat::smSelectPR ( )
private

Definition at line 1017 of file sparsmat.cc.

1018 {
1019  smpoly b = dumm;
1020  smpoly a, ap;
1021  int i;
1022 
1023  if (TEST_OPT_PROT)
1024  {
1025  if ((crd+1)%10)
1026  PrintS(".");
1027  else
1028  PrintS(".\n");
1029  }
1030  a = m_act[act];
1031  if (a->pos < rpiv)
1032  {
1033  do
1034  {
1035  ap = a;
1036  a = a->n;
1037  } while (a->pos < rpiv);
1038  ap->n = a->n;
1039  }
1040  else
1041  m_act[act] = a->n;
1042  piv = a;
1043  a->n = NULL;
1044  for (i=1; i<act; i++)
1045  {
1046  a = m_act[i];
1047  if (a->pos < rpiv)
1048  {
1049  loop
1050  {
1051  ap = a;
1052  a = a->n;
1053  if ((a == NULL) || (a->pos > rpiv))
1054  break;
1055  if (a->pos == rpiv)
1056  {
1057  ap->n = a->n;
1058  a->m = p_Neg(a->m,_R);
1059  b = b->n = a;
1060  b->pos = i;
1061  break;
1062  }
1063  }
1064  }
1065  else if (a->pos == rpiv)
1066  {
1067  m_act[i] = a->n;
1068  a->m = p_Neg(a->m,_R);
1069  b = b->n = a;
1070  b->pos = i;
1071  }
1072  }
1073  b->n = NULL;
1074  red = dumm->n;
1075 }
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1067

◆ smSign()

void sparse_mat::smSign ( )
private

Definition at line 1520 of file sparsmat.cc.

1521 {
1522  int j,i;
1523  if (act > 2)
1524  {
1525  if (cpiv!=act) sign=-sign;
1526  if ((act%2)==0) sign=-sign;
1527  i=1;
1528  j=perm[1];
1529  while(j<rpiv)
1530  {
1531  sign=-sign;
1532  i++;
1533  j=perm[i];
1534  }
1535  while(perm[i]!=0)
1536  {
1537  perm[i]=perm[i+1];
1538  i++;
1539  }
1540  }
1541  else
1542  {
1543  if (cpiv!=1) sign=-sign;
1544  if (rpiv!=perm[1]) sign=-sign;
1545  }
1546 }

◆ smSparseHomog()

void sparse_mat::smSparseHomog ( )
private

◆ smToIntvec()

void sparse_mat::smToIntvec ( intvec v)

Definition at line 464 of file sparsmat.cc.

465 {
466  int i;
467 
468  for (i=v->rows()-1; i>=0; i--)
469  (*v)[i] = perm[i+1];
470 }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39

◆ smToredElim()

void sparse_mat::smToredElim ( )
private

Definition at line 1164 of file sparsmat.cc.

1165 {
1166  int i = 0;
1167  int j;
1168 
1169  loop
1170  {
1171  i++;
1172  if (i > act) return;
1173  if (m_act[i]->pos > tored)
1174  {
1175  m_res[inred] = m_act[i];
1176  inred--;
1177  break;
1178  }
1179  }
1180  j = i;
1181  loop
1182  {
1183  j++;
1184  if (j > act) break;
1185  if (m_act[j]->pos > tored)
1186  {
1187  m_res[inred] = m_act[j];
1188  inred--;
1189  }
1190  else
1191  {
1192  m_act[i] = m_act[j];
1193  i++;
1194  }
1195  }
1196  act -= (j-i);
1197  sign = 0;
1198 }

◆ smWeights()

void sparse_mat::smWeights ( )
private

Definition at line 610 of file sparsmat.cc.

611 {
612  float wc, wp, w;
613  smpoly a;
614  int i;
615 
616  wp = 0.0;
617  for (i=tored; i; i--) wrw[i] = 0.0; // ???
618  for (i=act; i; i--)
619  {
620  wc = 0.0;
621  a = m_act[i];
622  loop
623  {
624  if (a->pos > tored)
625  break;
626  w = a->f = sm_PolyWeight(a,_R);
627  wc += w;
628  wrw[a->pos] += w;
629  a = a->n;
630  if (a == NULL)
631  break;
632  }
633  wp += wc;
634  wcl[i] = wc;
635  }
636  wpoints = wp;
637 }

◆ smZeroElim()

void sparse_mat::smZeroElim ( )
private

Definition at line 1134 of file sparsmat.cc.

1135 {
1136  int i = 0;
1137  int j;
1138 
1139  loop
1140  {
1141  i++;
1142  if (i > act) return;
1143  if (m_act[i] == NULL) break;
1144  }
1145  j = i;
1146  loop
1147  {
1148  j++;
1149  if (j > act) break;
1150  if (m_act[j] != NULL)
1151  {
1152  m_act[i] = m_act[j];
1153  i++;
1154  }
1155  }
1156  act -= (j-i);
1157  sign = 0;
1158 }

Field Documentation

◆ _R

ring sparse_mat::_R
private

Definition at line 143 of file sparsmat.cc.

◆ act

int sparse_mat::act
private

Definition at line 128 of file sparsmat.cc.

◆ cpiv

int sparse_mat::cpiv
private

Definition at line 132 of file sparsmat.cc.

◆ crd

int sparse_mat::crd
private

Definition at line 129 of file sparsmat.cc.

◆ dumm

smpoly sparse_mat::dumm
private

Definition at line 142 of file sparsmat.cc.

◆ inred

int sparse_mat::inred
private

Definition at line 131 of file sparsmat.cc.

◆ m_act

smpoly* sparse_mat::m_act
private

Definition at line 137 of file sparsmat.cc.

◆ m_res

smpoly* sparse_mat::m_res
private

Definition at line 138 of file sparsmat.cc.

◆ m_row

smpoly* sparse_mat::m_row
private

Definition at line 139 of file sparsmat.cc.

◆ ncols

int sparse_mat::ncols
private

Definition at line 126 of file sparsmat.cc.

◆ normalize

int sparse_mat::normalize
private

Definition at line 133 of file sparsmat.cc.

◆ nrows

int sparse_mat::nrows
private

Definition at line 126 of file sparsmat.cc.

◆ oldpiv

smpoly sparse_mat::oldpiv
private

Definition at line 141 of file sparsmat.cc.

◆ perm

int* sparse_mat::perm
private

Definition at line 134 of file sparsmat.cc.

◆ piv

smpoly sparse_mat::piv
private

Definition at line 141 of file sparsmat.cc.

◆ red

smpoly sparse_mat::red
private

Definition at line 140 of file sparsmat.cc.

◆ rpiv

int sparse_mat::rpiv
private

Definition at line 132 of file sparsmat.cc.

◆ sign

int sparse_mat::sign
private

Definition at line 127 of file sparsmat.cc.

◆ tored

int sparse_mat::tored
private

Definition at line 130 of file sparsmat.cc.

◆ wcl

float * sparse_mat::wcl
private

Definition at line 136 of file sparsmat.cc.

◆ wpoints

float sparse_mat::wpoints
private

Definition at line 135 of file sparsmat.cc.

◆ wrw

float* sparse_mat::wrw
private

Definition at line 136 of file sparsmat.cc.


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