My Project  debian-1:4.1.1-p2+ds-4
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 440 of file sparsmat.cc.

442 {
443  int i;
444  poly* pmat;
445  _R=RR;
446 
447  ncols = smat->ncols;
448  nrows = id_RankFreeModule(smat,RR);
449  if (nrows <= 0)
450  {
451  m_act = NULL;
452  return;
453  }
454  sign = 1;
455  inred = act = ncols;
456  crd = 0;
457  tored = nrows; // without border
458  i = tored+1;
459  perm = (int *)omAlloc(sizeof(int)*(i+1));
460  perm[i] = 0;
461  m_row = (smpoly *)omAlloc0(sizeof(smpoly)*i);
462  wrw = (float *)omAlloc(sizeof(float)*i);
463  i = ncols+1;
464  wcl = (float *)omAlloc(sizeof(float)*i);
465  m_act = (smpoly *)omAlloc(sizeof(smpoly)*i);
466  m_res = (smpoly *)omAlloc0(sizeof(smpoly)*i);
469  m_res[0]->m = NULL;
470  pmat = smat->m;
471  for(i=ncols; i; i--)
472  {
473  m_act[i] = sm_Poly2Smpoly(pmat[i-1], RR);
474  pmat[i-1] = NULL;
475  }
476  this->smZeroElim();
477  oldpiv = NULL;

◆ ~sparse_mat()

sparse_mat::~sparse_mat ( )

Definition at line 482 of file sparsmat.cc.

484 {
485  int i;
486  if (m_act == NULL) return;
489  i = ncols+1;
490  omFreeSize((ADDRESS)m_res, sizeof(smpoly)*i);
491  omFreeSize((ADDRESS)m_act, sizeof(smpoly)*i);
492  omFreeSize((ADDRESS)wcl, sizeof(float)*i);
493  i = nrows+1;
494  omFreeSize((ADDRESS)wrw, sizeof(float)*i);
495  omFreeSize((ADDRESS)m_row, sizeof(smpoly)*i);
496  omFreeSize((ADDRESS)perm, sizeof(int)*(i+1));

Member Function Documentation

◆ sm1Elim()

void sparse_mat::sm1Elim ( )
private

Definition at line 853 of file sparsmat.cc.

855 {
856  poly p = piv->m; // pivotelement
857  smpoly c = m_act[act]; // pivotcolumn
858  smpoly r = red; // row to reduce
859  smpoly res, a, b;
860  poly w, ha, hb;
861 
862  if ((c == NULL) || (r == NULL))
863  {
864  while (r!=NULL) sm_ElemDelete(&r,_R);
865  return;
866  }
867  do
868  {
869  a = m_act[r->pos];
870  res = dumm;
871  res->n = NULL;
872  b = c;
873  w = r->m;
874  loop // combine the chains a and b: p*a + w*b
875  {
876  if (a == NULL)
877  {
878  do
879  {
880  res = res->n = smElemCopy(b);
881  res->m = pp_Mult_qq(b->m, w,_R);
882  res->e = 1;
883  res->f = sm_PolyWeight(res,_R);
884  b = b->n;
885  } while (b != NULL);
886  break;
887  }
888  if (a->pos < b->pos)
889  {
890  res = res->n = a;
891  a = a->n;
892  }
893  else if (a->pos > b->pos)
894  {
895  res = res->n = smElemCopy(b);
896  res->m = pp_Mult_qq(b->m, w,_R);
897  res->e = 1;
898  res->f = sm_PolyWeight(res,_R);
899  b = b->n;
900  }
901  else
902  {
903  ha = pp_Mult_qq(a->m, p,_R);
904  p_Delete(&a->m,_R);
905  hb = pp_Mult_qq(b->m, w,_R);
906  ha = p_Add_q(ha, hb,_R);
907  if (ha != NULL)
908  {
909  a->m = ha;
910  a->e = 1;
911  a->f = sm_PolyWeight(a,_R);
912  res = res->n = a;
913  a = a->n;
914  }
915  else
916  {
917  sm_ElemDelete(&a,_R);
918  }
919  b = b->n;
920  }
921  if (b == NULL)
922  {
923  res->n = a;
924  break;
925  }
926  }
927  m_act[r->pos] = dumm->n;
928  sm_ElemDelete(&r,_R);
929  } while (r != NULL);

◆ smActDel()

void sparse_mat::smActDel ( )
private

Definition at line 1529 of file sparsmat.cc.

1531 {
1532  smpoly a;
1533  int i;
1534 
1535  for (i=act; i; i--)
1536  {
1537  a = m_act[i];
1538  do
1539  {
1540  sm_ElemDelete(&a,_R);
1541  } while (a != NULL);
1542  }

◆ smCheckNormalize()

int sparse_mat::smCheckNormalize ( )
private

Definition at line 1467 of file sparsmat.cc.

1469 {
1470  int i;
1471  smpoly a;
1472 
1473  for (i=act; i; i--)
1474  {
1475  a = m_act[i];
1476  do
1477  {
1478  if(sm_HaveDenom(a->m,_R)) return 1;
1479  a = a->n;
1480  } while (a != NULL);
1481  }
1482  return 0;

◆ smColDel()

void sparse_mat::smColDel ( )
private

Definition at line 1547 of file sparsmat.cc.

1549 {
1550  smpoly a = m_act[act];
1551 
1552  while (a != NULL)
1553  {
1554  sm_ElemDelete(&a,_R);
1555  }

◆ smColToRow()

void sparse_mat::smColToRow ( )
private

Definition at line 1135 of file sparsmat.cc.

1137 {
1138  smpoly c = m_act[act];
1139  smpoly h;
1140 
1141  while (c != NULL)
1142  {
1143  h = c;
1144  c = c->n;
1145  h->n = m_row[h->pos];
1146  m_row[h->pos] = h;
1147  h->pos = crd;
1148  }

◆ smCopToRes()

void sparse_mat::smCopToRes ( )
private

Definition at line 1257 of file sparsmat.cc.

1259 {
1260  smpoly a,ap,r,h;
1261  int i,j,k,l;
1262 
1263  i = 0;
1264  if (act)
1265  {
1266  a = m_act[act]; // init perm
1267  do
1268  {
1269  i++;
1270  perm[crd+i] = a->pos;
1271  a = a->n;
1272  } while ((a != NULL) && (a->pos <= tored));
1273  for (j=act-1;j;j--) // load all positions of perm
1274  {
1275  a = m_act[j];
1276  k = 1;
1277  loop
1278  {
1279  if (perm[crd+k] >= a->pos)
1280  {
1281  if (perm[crd+k] > a->pos)
1282  {
1283  for (l=i;l>=k;l--) perm[crd+l+1] = perm[crd+l];
1284  perm[crd+k] = a->pos;
1285  i++;
1286  }
1287  a = a->n;
1288  if ((a == NULL) || (a->pos > tored)) break;
1289  }
1290  k++;
1291  if ((k > i) && (a->pos <= tored))
1292  {
1293  do
1294  {
1295  i++;
1296  perm[crd+i] = a->pos;
1297  a = a->n;
1298  } while ((a != NULL) && (a->pos <= tored));
1299  break;
1300  }
1301  }
1302  }
1303  }
1304  for (j=act;j;j--) // renumber m_act
1305  {
1306  k = 1;
1307  a = m_act[j];
1308  while ((a != NULL) && (a->pos <= tored))
1309  {
1310  if (perm[crd+k] == a->pos)
1311  {
1312  a->pos = crd+k;
1313  a = a->n;
1314  }
1315  k++;
1316  }
1317  }
1318  tored = crd+i;
1319  for(k=1;k<=i;k++) // clean this from m_row
1320  {
1321  j = perm[crd+k];
1322  if (m_row[j] != NULL)
1323  {
1324  r = m_row[j];
1325  m_row[j] = NULL;
1326  do
1327  {
1328  ap = m_res[r->pos];
1329  loop
1330  {
1331  a = ap->n;
1332  if (a == NULL)
1333  {
1334  h = ap->n = r;
1335  r = r->n;
1336  h->n = NULL;
1337  h->pos = crd+k;
1338  break;
1339  }
1340  ap = a;
1341  }
1342  } while (r!=NULL);
1343  }
1344  }
1345  while(act) // clean m_act
1346  {
1347  crd++;
1348  m_res[crd] = m_act[act];
1349  act--;
1350  }
1351  for (i=1;i<=tored;i++) // take the rest of m_row
1352  {
1353  if(m_row[i] != NULL)
1354  {
1355  tored++;
1356  r = m_row[i];
1357  m_row[i] = NULL;
1358  perm[tored] = i;
1359  do
1360  {
1361  ap = m_res[r->pos];
1362  loop
1363  {
1364  a = ap->n;
1365  if (a == NULL)
1366  {
1367  h = ap->n = r;
1368  r = r->n;
1369  h->n = NULL;
1370  h->pos = tored;
1371  break;
1372  }
1373  ap = a;
1374  }
1375  } while (r!=NULL);
1376  }
1377  }
1378  for (i=tored+1;i<=nrows;i++) // take the rest of m_row
1379  {
1380  if(m_row[i] != NULL)
1381  {
1382  r = m_row[i];
1383  m_row[i] = NULL;
1384  do
1385  {
1386  ap = m_res[r->pos];
1387  loop
1388  {
1389  a = ap->n;
1390  if (a == NULL)
1391  {
1392  h = ap->n = r;
1393  r = r->n;
1394  h->n = NULL;
1395  h->pos = i;
1396  break;
1397  }
1398  ap = a;
1399  }
1400  } while (r!=NULL);
1401  }
1402  }
1403  while (inred < ncols) // take unreducable
1404  {
1405  crd++;
1406  inred++;
1407  m_res[crd] = m_res[inred];
1408  }

◆ smDet()

poly sparse_mat::smDet ( )

Definition at line 529 of file sparsmat.cc.

531 {
532  poly res = NULL;
533 
534  if (sign == 0)
535  {
536  this->smActDel();
537  return NULL;
538  }
539  if (act < 2)
540  {
541  if (act != 0) res = m_act[1]->m;
542  omFreeBin((void *)m_act[1], smprec_bin);
543  return res;
544  }
545  normalize = 0;
546  this->smInitPerm();
547  this->smPivot();
548  this->smSign();
549  this->smSelectPR();
550  this->sm1Elim();
551  crd++;
552  m_res[crd] = piv;
553  this->smColDel();
554  act--;
555  this->smZeroElim();
556  if (sign == 0)
557  {
558  this->smActDel();
559  return NULL;
560  }
561  if (act < 2)
562  {
563  this->smFinalMult();
564  this->smPivDel();
565  if (act != 0) res = m_act[1]->m;
566  omFreeBin((void *)m_act[1], smprec_bin);
567  return res;
568  }
569  loop
570  {
571  this->smNewPivot();
572  this->smSign();
573  this->smSelectPR();
574  this->smMultCol();
575  this->smHElim();
576  crd++;
577  m_res[crd] = piv;
578  this->smColDel();
579  act--;
580  this->smZeroElim();
581  if (sign == 0)
582  {
583  this->smPivDel();
584  this->smActDel();
585  return NULL;
586  }
587  if (act < 2)
588  {
589  if (TEST_OPT_PROT) PrintS(".\n");
590  this->smFinalMult();
591  this->smPivDel();
592  if (act != 0) res = m_act[1]->m;
593  omFreeBin((void *)m_act[1], smprec_bin);
594  return res;
595  }
596  }

◆ smFinalMult()

void sparse_mat::smFinalMult ( )
private

Definition at line 1438 of file sparsmat.cc.

1440 {
1441  smpoly a;
1442  poly ha;
1443  int i, f;
1444  int e = crd;
1445 
1446  for (i=act; i; i--)
1447  {
1448  a = m_act[i];
1449  do
1450  {
1451  f = a->e;
1452  if (f < e)
1453  {
1454  ha = SM_MULT(a->m, m_res[e]->m, m_res[f]->m, _R);
1455  p_Delete(&a->m,_R);
1456  if (f) SM_DIV(ha, m_res[f]->m, _R);
1457  a->m = ha;
1458  }
1459  if (normalize) p_Normalize(a->m, _R);
1460  a = a->n;
1461  } while (a != NULL);
1462  }

◆ smGetAct()

smpoly* sparse_mat::smGetAct ( )
inline

Definition at line 172 of file sparsmat.cc.

172 { return sign; }

◆ smGetRed()

int sparse_mat::smGetRed ( )
inline

Definition at line 173 of file sparsmat.cc.

173 { return m_act; }

◆ smGetSign()

int sparse_mat::smGetSign ( )
inline

Definition at line 171 of file sparsmat.cc.

172 { return sign; }

◆ smHElim()

void sparse_mat::smHElim ( )
private

Definition at line 932 of file sparsmat.cc.

934 {
935  poly hp = this->smMultPoly(piv);
936  poly gp = piv->m; // pivotelement
937  smpoly c = m_act[act]; // pivotcolumn
938  smpoly r = red; // row to reduce
939  smpoly res, a, b;
940  poly ha, hr, x, y;
941  int e, ip, ir, ia;
942 
943  if ((c == NULL) || (r == NULL))
944  {
945  while(r!=NULL) sm_ElemDelete(&r,_R);
946  p_Delete(&hp,_R);
947  return;
948  }
949  e = crd+1;
950  ip = piv->e;
951  do
952  {
953  a = m_act[r->pos];
954  res = dumm;
955  res->n = NULL;
956  b = c;
957  hr = r->m;
958  ir = r->e;
959  loop // combine the chains a and b: (hp,gp)*a(l) + hr*b(h)
960  {
961  if (a == NULL)
962  {
963  do
964  {
965  res = res->n = smElemCopy(b);
966  x = SM_MULT(b->m, hr, m_res[ir]->m,_R);
967  b = b->n;
968  if(ir) SM_DIV(x, m_res[ir]->m,_R);
969  res->m = x;
970  res->e = e;
971  res->f = sm_PolyWeight(res,_R);
972  } while (b != NULL);
973  break;
974  }
975  if (a->pos < b->pos)
976  {
977  res = res->n = a;
978  a = a->n;
979  }
980  else if (a->pos > b->pos)
981  {
982  res = res->n = smElemCopy(b);
983  x = SM_MULT(b->m, hr, m_res[ir]->m,_R);
984  b = b->n;
985  if(ir) SM_DIV(x, m_res[ir]->m,_R);
986  res->m = x;
987  res->e = e;
988  res->f = sm_PolyWeight(res,_R);
989  }
990  else
991  {
992  ha = a->m;
993  ia = a->e;
994  if (ir >= ia)
995  {
996  if (ir > ia)
997  {
998  x = SM_MULT(ha, m_res[ir]->m, m_res[ia]->m,_R);
999  p_Delete(&ha,_R);
1000  ha = x;
1001  if (ia) SM_DIV(ha, m_res[ia]->m,_R);
1002  ia = ir;
1003  }
1004  x = SM_MULT(ha, gp, m_res[ia]->m,_R);
1005  p_Delete(&ha,_R);
1006  y = SM_MULT(b->m, hr, m_res[ia]->m,_R);
1007  }
1008  else if (ir >= ip)
1009  {
1010  if (ia < crd)
1011  {
1012  x = SM_MULT(ha, m_res[crd]->m, m_res[ia]->m,_R);
1013  p_Delete(&ha,_R);
1014  ha = x;
1015  SM_DIV(ha, m_res[ia]->m,_R);
1016  }
1017  y = hp;
1018  if(ir > ip)
1019  {
1020  y = SM_MULT(y, m_res[ir]->m, m_res[ip]->m,_R);
1021  if (ip) SM_DIV(y, m_res[ip]->m,_R);
1022  }
1023  ia = ir;
1024  x = SM_MULT(ha, y, m_res[ia]->m,_R);
1025  if (y != hp) p_Delete(&y,_R);
1026  p_Delete(&ha,_R);
1027  y = SM_MULT(b->m, hr, m_res[ia]->m,_R);
1028  }
1029  else
1030  {
1031  x = SM_MULT(hr, m_res[ia]->m, m_res[ir]->m,_R);
1032  if (ir) SM_DIV(x, m_res[ir]->m,_R);
1033  y = SM_MULT(b->m, x, m_res[ia]->m,_R);
1034  p_Delete(&x,_R);
1035  x = SM_MULT(ha, gp, m_res[ia]->m,_R);
1036  p_Delete(&ha,_R);
1037  }
1038  ha = p_Add_q(x, y,_R);
1039  if (ha != NULL)
1040  {
1041  if (ia) SM_DIV(ha, m_res[ia]->m,_R);
1042  a->m = ha;
1043  a->e = e;
1044  a->f = sm_PolyWeight(a,_R);
1045  res = res->n = a;
1046  a = a->n;
1047  }
1048  else
1049  {
1050  a->m = NULL;
1051  sm_ElemDelete(&a,_R);
1052  }
1053  b = b->n;
1054  }
1055  if (b == NULL)
1056  {
1057  res->n = a;
1058  break;
1059  }
1060  }
1061  m_act[r->pos] = dumm->n;
1062  sm_ElemDelete(&r,_R);
1063  } while (r != NULL);
1064  p_Delete(&hp,_R);

◆ smInitPerm()

void sparse_mat::smInitPerm ( )
private

Definition at line 1602 of file sparsmat.cc.

1604 {
1605  int i;
1606  for (i=act;i;i--) perm[i]=i;

◆ smMultCol()

void sparse_mat::smMultCol ( )
private

Definition at line 1413 of file sparsmat.cc.

1415 {
1416  smpoly a = m_act[act];
1417  int e = crd;
1418  poly ha;
1419  int f;
1420 
1421  while (a != NULL)
1422  {
1423  f = a->e;
1424  if (f < e)
1425  {
1426  ha = SM_MULT(a->m, m_res[e]->m, m_res[f]->m,_R);
1427  p_Delete(&a->m,_R);
1428  if (f) SM_DIV(ha, m_res[f]->m,_R);
1429  a->m = ha;
1430  if (normalize) p_Normalize(a->m,_R);
1431  }
1432  a = a->n;
1433  }

◆ smMultPoly()

poly sparse_mat::smMultPoly ( smpoly  a)
private

Definition at line 1507 of file sparsmat.cc.

1509 {
1510  int f = a->e;
1511  poly r, h;
1512 
1513  if (f < crd)
1514  {
1515  h = r = a->m;
1516  h = SM_MULT(h, m_res[crd]->m, m_res[f]->m, _R);
1517  if (f) SM_DIV(h, m_res[f]->m, _R);
1518  a->m = h;
1519  if (normalize) p_Normalize(a->m,_R);
1520  a->f = sm_PolyWeight(a,_R);
1521  return r;
1522  }
1523  else
1524  return NULL;

◆ smNewBareiss()

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

Definition at line 603 of file sparsmat.cc.

605 {
606  if ((x > 0) && (x < nrows))
607  {
608  tored -= x;
609  this->smToredElim();
610  }
611  if (y < 1) y = 1;
612  if (act <= y)
613  {
614  this->smCopToRes();
615  return;
616  }
617  normalize = this->smCheckNormalize();
618  if (normalize) this->smNormalize();
619  this->smPivot();
620  this->smSelectPR();
621  this->sm1Elim();
622  crd++;
623  this->smColToRow();
624  act--;
625  this->smRowToCol();
626  this->smZeroElim();
627  if (tored != nrows)
628  this->smToredElim();
629  if (act <= y)
630  {
631  this->smFinalMult();
632  this->smCopToRes();
633  return;
634  }
635  loop
636  {
637  if (normalize) this->smNormalize();
638  this->smNewPivot();
639  this->smSelectPR();
640  this->smMultCol();
641  this->smHElim();
642  crd++;
643  this->smColToRow();
644  act--;
645  this->smRowToCol();
646  this->smZeroElim();
647  if (tored != nrows)
648  this->smToredElim();
649  if (act <= y)
650  {
651  if (TEST_OPT_PROT) PrintS(".\n");
652  this->smFinalMult();
653  this->smCopToRes();
654  return;
655  }
656  }

◆ smNewPivot()

void sparse_mat::smNewPivot ( )
private

Definition at line 791 of file sparsmat.cc.

793 {
794  float wopt = 1.0e30, hp = piv->f;
795  float wc, wr, wp, w;
796  smpoly a;
797  int i, copt, ropt, f, e = crd;
798 
799  this->smNewWeights();
800  for (i=act; i; i--)
801  {
802  a = m_act[i];
803  loop
804  {
805  if (a->pos > tored)
806  break;
807  w = a->f;
808  f = a->e;
809  if (f < e)
810  {
811  w *= hp;
812  if (f) w /= m_res[f]->f;
813  }
814  wc = wcl[i]-w;
815  wr = wrw[a->pos]-w;
816  if ((wr<0.25) || (wc<0.25)) // row or column with only one point
817  {
818  if (w<wopt)
819  {
820  wopt = w;
821  copt = i;
822  ropt = a->pos;
823  }
824  }
825  else // elimination
826  {
827  wp = w*(wpoints-wcl[i]-wr);
828  wp += wr*wc;
829  if (wp < wopt)
830  {
831  wopt = wp;
832  copt = i;
833  ropt = a->pos;
834  }
835  }
836  a = a->n;
837  if (a == NULL)
838  break;
839  }
840  }
841  rpiv = ropt;
842  cpiv = copt;
843  if (cpiv != act)
844  {
845  a = m_act[act];
846  m_act[act] = m_act[cpiv];
847  m_act[cpiv] = a;
848  }

◆ smNewWeights()

void sparse_mat::smNewWeights ( )
private

Definition at line 753 of file sparsmat.cc.

755 {
756  float wc, wp, w, hp = piv->f;
757  smpoly a;
758  int i, f, e = crd;
759 
760  wp = 0.0;
761  for (i=tored; i; i--) wrw[i] = 0.0; // ???
762  for (i=act; i; i--)
763  {
764  wc = 0.0;
765  a = m_act[i];
766  loop
767  {
768  if (a->pos > tored)
769  break;
770  w = a->f;
771  f = a->e;
772  if (f < e)
773  {
774  w *= hp;
775  if (f) w /= m_res[f]->f;
776  }
777  wc += w;
778  wrw[a->pos] += w;
779  a = a->n;
780  if (a == NULL)
781  break;
782  }
783  wp += wc;
784  wcl[i] = wc;
785  }
786  wpoints = wp;

◆ smNormalize()

void sparse_mat::smNormalize ( )
private

Definition at line 1487 of file sparsmat.cc.

1489 {
1490  smpoly a;
1491  int i;
1492  int e = crd;
1493 
1494  for (i=act; i; i--)
1495  {
1496  a = m_act[i];
1497  do
1498  {
1499  if (e == a->e) p_Normalize(a->m,_R);
1500  a = a->n;
1501  } while (a != NULL);
1502  }

◆ smPivDel()

void sparse_mat::smPivDel ( )
private

Definition at line 1560 of file sparsmat.cc.

1562 {
1563  int i=crd;
1564 
1565  while (i != 0)
1566  {
1567  sm_ElemDelete(&m_res[i],_R);
1568  i--;
1569  }

◆ smPivot()

void sparse_mat::smPivot ( )
private

Definition at line 696 of file sparsmat.cc.

698 {
699  float wopt = 1.0e30;
700  float wc, wr, wp, w;
701  smpoly a;
702  int i, copt, ropt;
703 
704  this->smWeights();
705  for (i=act; i; i--)
706  {
707  a = m_act[i];
708  loop
709  {
710  if (a->pos > tored)
711  break;
712  w = a->f;
713  wc = wcl[i]-w;
714  wr = wrw[a->pos]-w;
715  if ((wr<0.25) || (wc<0.25)) // row or column with only one point
716  {
717  if (w<wopt)
718  {
719  wopt = w;
720  copt = i;
721  ropt = a->pos;
722  }
723  }
724  else // elimination
725  {
726  wp = w*(wpoints-wcl[i]-wr);
727  wp += wr*wc;
728  if (wp < wopt)
729  {
730  wopt = wp;
731  copt = i;
732  ropt = a->pos;
733  }
734  }
735  a = a->n;
736  if (a == NULL)
737  break;
738  }
739  }
740  rpiv = ropt;
741  cpiv = copt;
742  if (cpiv != act)
743  {
744  a = m_act[act];
745  m_act[act] = m_act[cpiv];
746  m_act[cpiv] = a;
747  }

◆ smRes2Mod()

ideal sparse_mat::smRes2Mod ( )

Definition at line 502 of file sparsmat.cc.

504 {
505  ideal res = idInit(crd, crd);
506  int i;
507 
508  for (i=crd; i; i--)
509  {
510  res->m[i-1] = sm_Smpoly2Poly(m_res[i],_R);
511  res->rank=si_max(res->rank, p_MaxComp(res->m[i-1],_R));
512  }
513  return res;

◆ smRowToCol()

void sparse_mat::smRowToCol ( )
private

Definition at line 1155 of file sparsmat.cc.

1157 {
1158  smpoly r = m_row[rpiv];
1159  smpoly a, ap, h;
1160 
1161  m_row[rpiv] = NULL;
1162  perm[crd] = rpiv;
1163  piv->pos = crd;
1164  m_res[crd] = piv;
1165  while (r != NULL)
1166  {
1167  ap = m_res[r->pos];
1168  loop
1169  {
1170  a = ap->n;
1171  if (a == NULL)
1172  {
1173  ap->n = h = r;
1174  r = r->n;
1175  h->n = a;
1176  h->pos = crd;
1177  break;
1178  }
1179  ap = a;
1180  }
1181  }

◆ smSelectPR()

void sparse_mat::smSelectPR ( )
private

Definition at line 1071 of file sparsmat.cc.

1073 {
1074  smpoly b = dumm;
1075  smpoly a, ap;
1076  int i;
1077 
1078  if (TEST_OPT_PROT)
1079  {
1080  if ((crd+1)%10)
1081  PrintS(".");
1082  else
1083  PrintS(".\n");
1084  }
1085  a = m_act[act];
1086  if (a->pos < rpiv)
1087  {
1088  do
1089  {
1090  ap = a;
1091  a = a->n;
1092  } while (a->pos < rpiv);
1093  ap->n = a->n;
1094  }
1095  else
1096  m_act[act] = a->n;
1097  piv = a;
1098  a->n = NULL;
1099  for (i=1; i<act; i++)
1100  {
1101  a = m_act[i];
1102  if (a->pos < rpiv)
1103  {
1104  loop
1105  {
1106  ap = a;
1107  a = a->n;
1108  if ((a == NULL) || (a->pos > rpiv))
1109  break;
1110  if (a->pos == rpiv)
1111  {
1112  ap->n = a->n;
1113  a->m = p_Neg(a->m,_R);
1114  b = b->n = a;
1115  b->pos = i;
1116  break;
1117  }
1118  }
1119  }
1120  else if (a->pos == rpiv)
1121  {
1122  m_act[i] = a->n;
1123  a->m = p_Neg(a->m,_R);
1124  b = b->n = a;
1125  b->pos = i;
1126  }
1127  }
1128  b->n = NULL;
1129  red = dumm->n;

◆ smSign()

void sparse_mat::smSign ( )
private

Definition at line 1574 of file sparsmat.cc.

1576 {
1577  int j,i;
1578  if (act > 2)
1579  {
1580  if (cpiv!=act) sign=-sign;
1581  if ((act%2)==0) sign=-sign;
1582  i=1;
1583  j=perm[1];
1584  while(j<rpiv)
1585  {
1586  sign=-sign;
1587  i++;
1588  j=perm[i];
1589  }
1590  while(perm[i]!=0)
1591  {
1592  perm[i]=perm[i+1];
1593  i++;
1594  }
1595  }
1596  else
1597  {
1598  if (cpiv!=1) sign=-sign;
1599  if (rpiv!=perm[1]) sign=-sign;
1600  }

◆ smSparseHomog()

void sparse_mat::smSparseHomog ( )
private

◆ smToIntvec()

void sparse_mat::smToIntvec ( intvec v)

Definition at line 518 of file sparsmat.cc.

520 {
521  int i;
522 
523  for (i=v->rows()-1; i>=0; i--)
524  (*v)[i] = perm[i+1];

◆ smToredElim()

void sparse_mat::smToredElim ( )
private

Definition at line 1218 of file sparsmat.cc.

1220 {
1221  int i = 0;
1222  int j;
1223 
1224  loop
1225  {
1226  i++;
1227  if (i > act) return;
1228  if (m_act[i]->pos > tored)
1229  {
1230  m_res[inred] = m_act[i];
1231  inred--;
1232  break;
1233  }
1234  }
1235  j = i;
1236  loop
1237  {
1238  j++;
1239  if (j > act) break;
1240  if (m_act[j]->pos > tored)
1241  {
1242  m_res[inred] = m_act[j];
1243  inred--;
1244  }
1245  else
1246  {
1247  m_act[i] = m_act[j];
1248  i++;
1249  }
1250  }
1251  act -= (j-i);
1252  sign = 0;

◆ smWeights()

void sparse_mat::smWeights ( )
private

Definition at line 664 of file sparsmat.cc.

666 {
667  float wc, wp, w;
668  smpoly a;
669  int i;
670 
671  wp = 0.0;
672  for (i=tored; i; i--) wrw[i] = 0.0; // ???
673  for (i=act; i; i--)
674  {
675  wc = 0.0;
676  a = m_act[i];
677  loop
678  {
679  if (a->pos > tored)
680  break;
681  w = a->f = sm_PolyWeight(a,_R);
682  wc += w;
683  wrw[a->pos] += w;
684  a = a->n;
685  if (a == NULL)
686  break;
687  }
688  wp += wc;
689  wcl[i] = wc;
690  }
691  wpoints = wp;

◆ smZeroElim()

void sparse_mat::smZeroElim ( )
private

Definition at line 1188 of file sparsmat.cc.

1190 {
1191  int i = 0;
1192  int j;
1193 
1194  loop
1195  {
1196  i++;
1197  if (i > act) return;
1198  if (m_act[i] == NULL) break;
1199  }
1200  j = i;
1201  loop
1202  {
1203  j++;
1204  if (j > act) break;
1205  if (m_act[j] != NULL)
1206  {
1207  m_act[i] = m_act[j];
1208  i++;
1209  }
1210  }
1211  act -= (j-i);
1212  sign = 0;

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:
sparse_mat::sign
int sign
Definition: sparsmat.cc:127
sparse_mat::smPivot
void smPivot()
Definition: sparsmat.cc:696
sparse_mat::cpiv
int cpiv
Definition: sparsmat.cc:132
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
sparse_mat::inred
int inred
Definition: sparsmat.cc:131
sm_PolyWeight
static float sm_PolyWeight(smpoly, const ring)
Definition: sparsmat.cc:2229
sparse_mat::smCheckNormalize
int smCheckNormalize()
Definition: sparsmat.cc:1467
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3706
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:101
k
int k
Definition: cfEzgcd.cc:92
smElemCopy
static smpoly smElemCopy(smpoly)
Definition: sparsmat.cc:2139
sparse_mat::smNewWeights
void smNewWeights()
Definition: sparsmat.cc:753
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:1529
SM_MULT
#define SM_MULT
Definition: sparsmat.h:22
smprec_bin
omBin smprec_bin
Definition: sparsmat.cc:74
ADDRESS
void * ADDRESS
Definition: auxiliary.h:133
sparse_mat::smWeights
void smWeights()
Definition: sparsmat.cc:664
p_Neg
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1028
sm_Smpoly2Poly
static poly sm_Smpoly2Poly(smpoly, const ring)
Definition: sparsmat.cc:2188
sparse_mat::smNormalize
void smNormalize()
Definition: sparsmat.cc:1487
sparse_mat::smRowToCol
void smRowToCol()
Definition: sparsmat.cc:1155
sparse_mat::ncols
int ncols
Definition: sparsmat.cc:126
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
sparse_mat::dumm
smpoly dumm
Definition: sparsmat.cc:142
sparse_mat::wpoints
float wpoints
Definition: sparsmat.cc:135
sparse_mat::smSelectPR
void smSelectPR()
Definition: sparsmat.cc:1071
loop
#define loop
Definition: structs.h:77
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
sparse_mat::normalize
int normalize
Definition: sparsmat.cc:133
ap
Definition: ap.h:35
sparse_mat::nrows
int nrows
Definition: sparsmat.cc:126
sm_Poly2Smpoly
static smpoly sm_Poly2Smpoly(poly, const ring)
Definition: sparsmat.cc:2151
sparse_mat::rpiv
int rpiv
Definition: sparsmat.cc:132
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:781
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:140
smpoly
sm_prec * smpoly
Definition: sparsmat.cc:46
h
static Poly * h
Definition: janet.cc:972
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:1078
sparse_mat::smHElim
void smHElim()
Definition: sparsmat.cc:932
sparse_mat::piv
smpoly piv
Definition: sparsmat.cc:141
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
sparse_mat::smPivDel
void smPivDel()
Definition: sparsmat.cc:1560
sparse_mat::m_row
smpoly * m_row
Definition: sparsmat.cc:139
sparse_mat::smInitPerm
void smInitPerm()
Definition: sparsmat.cc:1602
sparse_mat::smNewPivot
void smNewPivot()
Definition: sparsmat.cc:791
sparse_mat::act
int act
Definition: sparsmat.cc:128
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:842
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
sparse_mat::smColDel
void smColDel()
Definition: sparsmat.cc:1547
sparse_mat::tored
int tored
Definition: sparsmat.cc:130
sm_ElemDelete
static void sm_ElemDelete(smpoly *, const ring)
Definition: sparsmat.cc:2130
sparse_mat::wrw
float * wrw
Definition: sparsmat.cc:136
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
sparse_mat::m_act
smpoly * m_act
Definition: sparsmat.cc:137
sparse_mat::_R
ring _R
Definition: sparsmat.cc:143
sparse_mat::smColToRow
void smColToRow()
Definition: sparsmat.cc:1135
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:36
sparse_mat::smMultPoly
poly smMultPoly(smpoly)
Definition: sparsmat.cc:1507
m
int m
Definition: cfEzgcd.cc:121
sparse_mat::perm
int * perm
Definition: sparsmat.cc:134
NULL
#define NULL
Definition: omList.c:9
l
int l
Definition: cfEzgcd.cc:93
sparse_mat::crd
int crd
Definition: sparsmat.cc:129
sparse_mat::smToredElim
void smToredElim()
Definition: sparsmat.cc:1218
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
sparse_mat::sm1Elim
void sm1Elim()
Definition: sparsmat.cc:853
sparse_mat::smFinalMult
void smFinalMult()
Definition: sparsmat.cc:1438
p
int p
Definition: cfModGcd.cc:4019
sparse_mat::wcl
float * wcl
Definition: sparsmat.cc:136
sparse_mat::smSign
void smSign()
Definition: sparsmat.cc:1574
sparse_mat::smMultCol
void smMultCol()
Definition: sparsmat.cc:1413
sm_HaveDenom
static BOOLEAN sm_HaveDenom(poly, const ring)
Definition: sparsmat.cc:2258
sparse_mat::smCopToRes
void smCopToRes()
Definition: sparsmat.cc:1257
sparse_mat::oldpiv
smpoly oldpiv
Definition: sparsmat.cc:141
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:283
sparse_mat::m_res
smpoly * m_res
Definition: sparsmat.cc:138
sparse_mat::smZeroElim
void smZeroElim()
Definition: sparsmat.cc:1188
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209