My Project  debian-1:4.1.2-p1+ds-2
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 123 of file sparsmat.cc.

Constructor & Destructor Documentation

◆ sparse_mat()

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

Definition at line 385 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;

◆ ~sparse_mat()

sparse_mat::~sparse_mat ( )

Definition at line 427 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));

Member Function Documentation

◆ sm1Elim()

void sparse_mat::sm1Elim ( )
private

Definition at line 798 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);

◆ smActDel()

void sparse_mat::smActDel ( )
private

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

◆ smCheckNormalize()

int sparse_mat::smCheckNormalize ( )
private

Definition at line 1412 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;

◆ smColDel()

void sparse_mat::smColDel ( )
private

Definition at line 1492 of file sparsmat.cc.

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

◆ smColToRow()

void sparse_mat::smColToRow ( )
private

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

◆ smCopToRes()

void sparse_mat::smCopToRes ( )
private

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

◆ smDet()

poly sparse_mat::smDet ( )

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

◆ smFinalMult()

void sparse_mat::smFinalMult ( )
private

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

◆ smGetAct()

smpoly* sparse_mat::smGetAct ( )
inline

Definition at line 171 of file sparsmat.cc.

171 { return sign; }

◆ smGetRed()

int sparse_mat::smGetRed ( )
inline

Definition at line 172 of file sparsmat.cc.

172 { return m_act; }

◆ smGetSign()

int sparse_mat::smGetSign ( )
inline

Definition at line 170 of file sparsmat.cc.

171 { return sign; }

◆ smHElim()

void sparse_mat::smHElim ( )
private

Definition at line 877 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);

◆ smInitPerm()

void sparse_mat::smInitPerm ( )
private

Definition at line 1547 of file sparsmat.cc.

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

◆ smMultCol()

void sparse_mat::smMultCol ( )
private

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

◆ smMultPoly()

poly sparse_mat::smMultPoly ( smpoly  a)
private

Definition at line 1452 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;

◆ smNewBareiss()

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

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

◆ smNewPivot()

void sparse_mat::smNewPivot ( )
private

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

◆ smNewWeights()

void sparse_mat::smNewWeights ( )
private

Definition at line 698 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;

◆ smNormalize()

void sparse_mat::smNormalize ( )
private

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

◆ smPivDel()

void sparse_mat::smPivDel ( )
private

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

◆ smPivot()

void sparse_mat::smPivot ( )
private

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

◆ smRes2Mod()

ideal sparse_mat::smRes2Mod ( )

Definition at line 447 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;

◆ smRowToCol()

void sparse_mat::smRowToCol ( )
private

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

◆ smSelectPR()

void sparse_mat::smSelectPR ( )
private

Definition at line 1016 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;

◆ smSign()

void sparse_mat::smSign ( )
private

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

◆ smSparseHomog()

void sparse_mat::smSparseHomog ( )
private

◆ smToIntvec()

void sparse_mat::smToIntvec ( intvec v)

Definition at line 463 of file sparsmat.cc.

465 {
466  int i;
467 
468  for (i=v->rows()-1; i>=0; i--)
469  (*v)[i] = perm[i+1];

◆ smToredElim()

void sparse_mat::smToredElim ( )
private

Definition at line 1163 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;

◆ smWeights()

void sparse_mat::smWeights ( )
private

Definition at line 609 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;

◆ smZeroElim()

void sparse_mat::smZeroElim ( )
private

Definition at line 1133 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;

Field Documentation

◆ _R

ring sparse_mat::_R
private

Definition at line 142 of file sparsmat.cc.

◆ act

int sparse_mat::act
private

Definition at line 127 of file sparsmat.cc.

◆ cpiv

int sparse_mat::cpiv
private

Definition at line 131 of file sparsmat.cc.

◆ crd

int sparse_mat::crd
private

Definition at line 128 of file sparsmat.cc.

◆ dumm

smpoly sparse_mat::dumm
private

Definition at line 141 of file sparsmat.cc.

◆ inred

int sparse_mat::inred
private

Definition at line 130 of file sparsmat.cc.

◆ m_act

smpoly* sparse_mat::m_act
private

Definition at line 136 of file sparsmat.cc.

◆ m_res

smpoly* sparse_mat::m_res
private

Definition at line 137 of file sparsmat.cc.

◆ m_row

smpoly* sparse_mat::m_row
private

Definition at line 138 of file sparsmat.cc.

◆ ncols

int sparse_mat::ncols
private

Definition at line 125 of file sparsmat.cc.

◆ normalize

int sparse_mat::normalize
private

Definition at line 132 of file sparsmat.cc.

◆ nrows

int sparse_mat::nrows
private

Definition at line 125 of file sparsmat.cc.

◆ oldpiv

smpoly sparse_mat::oldpiv
private

Definition at line 140 of file sparsmat.cc.

◆ perm

int* sparse_mat::perm
private

Definition at line 133 of file sparsmat.cc.

◆ piv

smpoly sparse_mat::piv
private

Definition at line 140 of file sparsmat.cc.

◆ red

smpoly sparse_mat::red
private

Definition at line 139 of file sparsmat.cc.

◆ rpiv

int sparse_mat::rpiv
private

Definition at line 131 of file sparsmat.cc.

◆ sign

int sparse_mat::sign
private

Definition at line 126 of file sparsmat.cc.

◆ tored

int sparse_mat::tored
private

Definition at line 129 of file sparsmat.cc.

◆ wcl

float * sparse_mat::wcl
private

Definition at line 135 of file sparsmat.cc.

◆ wpoints

float sparse_mat::wpoints
private

Definition at line 134 of file sparsmat.cc.

◆ wrw

float* sparse_mat::wrw
private

Definition at line 135 of file sparsmat.cc.


The documentation for this class was generated from the following file:
sparse_mat::sign
int sign
Definition: sparsmat.cc:126
sparse_mat::smPivot
void smPivot()
Definition: sparsmat.cc:641
sparse_mat::cpiv
int cpiv
Definition: sparsmat.cc:131
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
sparse_mat::inred
int inred
Definition: sparsmat.cc:130
sm_PolyWeight
static float sm_PolyWeight(smpoly, const ring)
Definition: sparsmat.cc:2174
sparse_mat::smCheckNormalize
int smCheckNormalize()
Definition: sparsmat.cc:1412
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3729
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:100
k
int k
Definition: cfEzgcd.cc:92
smElemCopy
static smpoly smElemCopy(smpoly)
Definition: sparsmat.cc:2084
sparse_mat::smNewWeights
void smNewWeights()
Definition: sparsmat.cc:698
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
sparse_mat::smActDel
void smActDel()
Definition: sparsmat.cc:1474
SM_MULT
#define SM_MULT
Definition: sparsmat.h:22
ADDRESS
void * ADDRESS
Definition: auxiliary.h:135
sparse_mat::smWeights
void smWeights()
Definition: sparsmat.cc:609
h
STATIC_VAR Poly * h
Definition: janet.cc:971
p_Neg
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1031
sm_Smpoly2Poly
static poly sm_Smpoly2Poly(smpoly, const ring)
Definition: sparsmat.cc:2133
sparse_mat::smNormalize
void smNormalize()
Definition: sparsmat.cc:1432
sparse_mat::smRowToCol
void smRowToCol()
Definition: sparsmat.cc:1100
smprec_bin
VAR omBin smprec_bin
Definition: sparsmat.cc:73
sparse_mat::ncols
int ncols
Definition: sparsmat.cc:125
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
sparse_mat::dumm
smpoly dumm
Definition: sparsmat.cc:141
sparse_mat::wpoints
float wpoints
Definition: sparsmat.cc:134
sparse_mat::smSelectPR
void smSelectPR()
Definition: sparsmat.cc:1016
loop
#define loop
Definition: structs.h:79
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
sparse_mat::normalize
int normalize
Definition: sparsmat.cc:132
ap
Definition: ap.h:35
sparse_mat::nrows
int nrows
Definition: sparsmat.cc:125
sm_Poly2Smpoly
static smpoly sm_Poly2Smpoly(poly, const ring)
Definition: sparsmat.cc:2096
sparse_mat::rpiv
int rpiv
Definition: sparsmat.cc:131
i
int i
Definition: cfEzgcd.cc:125
res
CanonicalForm res
Definition: facAbsFact.cc:64
id_RankFreeModule
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
Definition: simpleideals.cc:790
SM_DIV
#define SM_DIV
Definition: sparsmat.h:23
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
sparse_mat::red
smpoly red
Definition: sparsmat.cc:139
smpoly
sm_prec * smpoly
Definition: sparsmat.cc:45
gp
CanonicalForm gp
Definition: cfModGcd.cc:4043
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1075
sparse_mat::smHElim
void smHElim()
Definition: sparsmat.cc:877
sparse_mat::piv
smpoly piv
Definition: sparsmat.cc:140
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
sparse_mat::smPivDel
void smPivDel()
Definition: sparsmat.cc:1505
sparse_mat::m_row
smpoly * m_row
Definition: sparsmat.cc:138
sparse_mat::smInitPerm
void smInitPerm()
Definition: sparsmat.cc:1547
sparse_mat::smNewPivot
void smNewPivot()
Definition: sparsmat.cc:736
sparse_mat::act
int act
Definition: sparsmat.cc:127
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:845
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:880
sparse_mat::smColDel
void smColDel()
Definition: sparsmat.cc:1492
sparse_mat::tored
int tored
Definition: sparsmat.cc:129
sm_ElemDelete
static void sm_ElemDelete(smpoly *, const ring)
Definition: sparsmat.cc:2075
sparse_mat::wrw
float * wrw
Definition: sparsmat.cc:135
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:140
sparse_mat::m_act
smpoly * m_act
Definition: sparsmat.cc:136
sparse_mat::_R
ring _R
Definition: sparsmat.cc:142
sparse_mat::smColToRow
void smColToRow()
Definition: sparsmat.cc:1080
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:34
sparse_mat::smMultPoly
poly smMultPoly(smpoly)
Definition: sparsmat.cc:1452
m
int m
Definition: cfEzgcd.cc:121
sparse_mat::perm
int * perm
Definition: sparsmat.cc:133
NULL
#define NULL
Definition: omList.c:11
l
int l
Definition: cfEzgcd.cc:93
sparse_mat::crd
int crd
Definition: sparsmat.cc:128
sparse_mat::smToredElim
void smToredElim()
Definition: sparsmat.cc:1163
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
sparse_mat::sm1Elim
void sm1Elim()
Definition: sparsmat.cc:798
sparse_mat::smFinalMult
void smFinalMult()
Definition: sparsmat.cc:1383
p
int p
Definition: cfModGcd.cc:4019
sparse_mat::wcl
float * wcl
Definition: sparsmat.cc:135
sparse_mat::smSign
void smSign()
Definition: sparsmat.cc:1519
sparse_mat::smMultCol
void smMultCol()
Definition: sparsmat.cc:1358
sm_HaveDenom
static BOOLEAN sm_HaveDenom(poly, const ring)
Definition: sparsmat.cc:2203
sparse_mat::smCopToRes
void smCopToRes()
Definition: sparsmat.cc:1202
sparse_mat::oldpiv
smpoly oldpiv
Definition: sparsmat.cc:140
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:257
p_MaxComp
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:282
sparse_mat::m_res
smpoly * m_res
Definition: sparsmat.cc:137
sparse_mat::smZeroElim
void smZeroElim()
Definition: sparsmat.cc:1133
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209