My Project  debian-1:4.1.2-p1+ds-2
Public Member Functions | Private Member Functions | Private Attributes
mayanPyramidAlg Class Reference

Public Member Functions

 mayanPyramidAlg (simplex *_pLP)
 
 ~mayanPyramidAlg ()
 
pointSetgetInnerPoints (pointSet **_q_i, mprfloat _shift[])
 Drive Mayan Pyramid Algorithm. More...
 

Private Member Functions

void runMayanPyramid (int dim)
 Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold MinkowskiSum of given point sets Qi[]. More...
 
mprfloat vDistance (Coord_t *acoords, int dim)
 Compute v-distance via Linear Programing Linear Program finds the v-distance of the point in accords[]. More...
 
void mn_mx_MinkowskiSum (int dim, Coord_t *minR, Coord_t *maxR)
 LP for finding min/max coord in MinkowskiSum, given previous coors. More...
 
bool storeMinkowskiSumPoint ()
 Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase. More...
 

Private Attributes

pointSet ** Qi
 
pointSetE
 
mprfloatshift
 
int n
 
int idelem
 
Coord_t acoords [MAXVARS+2]
 
simplexpLP
 

Detailed Description

Definition at line 277 of file mpr_base.cc.

Constructor & Destructor Documentation

◆ mayanPyramidAlg()

mayanPyramidAlg::mayanPyramidAlg ( simplex _pLP)
inline

Definition at line 280 of file mpr_base.cc.

280 : n((currRing->N)), pLP(_pLP) {}

◆ ~mayanPyramidAlg()

mayanPyramidAlg::~mayanPyramidAlg ( )
inline

Definition at line 281 of file mpr_base.cc.

281 {}

Member Function Documentation

◆ getInnerPoints()

pointSet * mayanPyramidAlg::getInnerPoints ( pointSet **  _q_i,
mprfloat  _shift[] 
)

Drive Mayan Pyramid Algorithm.

The Alg computes conv(Qi[]+shift[]).

Definition at line 891 of file mpr_base.cc.

892 {
893  int i;
894 
895  Qi= _q_i;
896  shift= _shift;
897 
898  E= new pointSet( Qi[0]->dim ); // E has same dim as Qi[...]
899 
900  for ( i= 0; i < MAXVARS+2; i++ ) acoords[i]= 0;
901 
902  runMayanPyramid(0);
903 
904  mprSTICKYPROT("\n");
905 
906  return E;
907 }

◆ mn_mx_MinkowskiSum()

void mayanPyramidAlg::mn_mx_MinkowskiSum ( int  dim,
Coord_t minR,
Coord_t maxR 
)
private

LP for finding min/max coord in MinkowskiSum, given previous coors.

Assume MinkowskiSum in non-negative quadrants coor in [0,n); fixed coords in acoords[0..coor)

Definition at line 996 of file mpr_base.cc.

997 {
998  int i, j, k, cols, cons;
999  int la_cons_row;
1000 
1001  cons = n+dim+2;
1002 
1003  // first, compute minimum
1004  //
1005 
1006  // common part of the matrix
1007  pLP->LiPM[1][1] = 0.0;
1008  for( i=2; i<=n+2; i++)
1009  {
1010  pLP->LiPM[i][1] = 1.0; // 1st col
1011  pLP->LiPM[i][2] = 0.0; // 2nd col
1012  }
1013 
1014  la_cons_row = 1;
1015  cols = 2;
1016  for( i=0; i<=n; i++)
1017  {
1018  la_cons_row++;
1019  for( j=1; j<= Qi[i]->num; j++)
1020  {
1021  cols++;
1022  pLP->LiPM[1][cols] = 0.0; // set 1st row 0
1023  for( k=2; k<=n+2; k++)
1024  { // lambdas sum up to 1
1025  if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
1026  else pLP->LiPM[k][cols] = -1.0;
1027  }
1028  for( k=1; k<=n; k++)
1029  pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
1030  } // j
1031  } // i
1032 
1033  for( i= 0; i < dim; i++ )
1034  { // fixed coords
1035  pLP->LiPM[i+n+3][1] = acoords[i];
1036  pLP->LiPM[i+n+3][2] = 0.0;
1037  }
1038  pLP->LiPM[dim+n+3][1] = 0.0;
1039 
1040 
1041  pLP->LiPM[1][2] = -1.0; // minimize
1042  pLP->LiPM[dim+n+3][2] = 1.0;
1043 
1044 #ifdef mprDEBUG_ALL
1045  Print("\nThats the matrix for minR, dim= %d, acoords= ",dim);
1046  for( i= 0; i < dim; i++ )
1047  Print(" %d",acoords[i]);
1048  PrintLn();
1049  print_mat( pLP->LiPM, cons+1, cols);
1050 #endif
1051 
1052  // simplx finds MIN for obj.fnc, puts it in [1,1]
1053  pLP->m= cons;
1054  pLP->n= cols-1;
1055  pLP->m3= cons;
1056 
1057  pLP->compute();
1058 
1059  if ( pLP->icase != 0 )
1060  { // check for errors
1061  if( pLP->icase < 0)
1062  WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: infeasible");
1063  else if( pLP->icase > 0)
1064  WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: unbounded");
1065  }
1066 
1067  *minR = (Coord_t)( -pLP->LiPM[1][1] + 1.0 - SIMPLEX_EPS );
1068 
1069  // now compute maximum
1070  //
1071 
1072  // common part of the matrix again
1073  pLP->LiPM[1][1] = 0.0;
1074  for( i=2; i<=n+2; i++)
1075  {
1076  pLP->LiPM[i][1] = 1.0;
1077  pLP->LiPM[i][2] = 0.0;
1078  }
1079  la_cons_row = 1;
1080  cols = 2;
1081  for( i=0; i<=n; i++)
1082  {
1083  la_cons_row++;
1084  for( j=1; j<=Qi[i]->num; j++)
1085  {
1086  cols++;
1087  pLP->LiPM[1][cols] = 0.0;
1088  for( k=2; k<=n+2; k++)
1089  {
1090  if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
1091  else pLP->LiPM[k][cols] = -1.0;
1092  }
1093  for( k=1; k<=n; k++)
1094  pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
1095  } // j
1096  } // i
1097 
1098  for( i= 0; i < dim; i++ )
1099  { // fixed coords
1100  pLP->LiPM[i+n+3][1] = acoords[i];
1101  pLP->LiPM[i+n+3][2] = 0.0;
1102  }
1103  pLP->LiPM[dim+n+3][1] = 0.0;
1104 
1105  pLP->LiPM[1][2] = 1.0; // maximize
1106  pLP->LiPM[dim+n+3][2] = 1.0; // var = sum of pnt coords
1107 
1108 #ifdef mprDEBUG_ALL
1109  Print("\nThats the matrix for maxR, dim= %d\n",dim);
1110  print_mat( pLP->LiPM, cons+1, cols);
1111 #endif
1112 
1113  pLP->m= cons;
1114  pLP->n= cols-1;
1115  pLP->m3= cons;
1116 
1117  // simplx finds MAX for obj.fnc, puts it in [1,1]
1118  pLP->compute();
1119 
1120  if ( pLP->icase != 0 )
1121  {
1122  if( pLP->icase < 0)
1123  WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: infeasible");
1124  else if( pLP->icase > 0)
1125  WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: unbounded");
1126  }
1127 
1128  *maxR = (Coord_t)( pLP->LiPM[1][1] + SIMPLEX_EPS );
1129 
1130 #ifdef mprDEBUG_ALL
1131  Print(" Range for dim=%d: [%d,%d]\n", dim, *minR, *maxR);
1132 #endif
1133 }

◆ runMayanPyramid()

void mayanPyramidAlg::runMayanPyramid ( int  dim)
private

Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold MinkowskiSum of given point sets Qi[].

Recursively for range of dim: dim in [0..n); acoords[0..var) fixed. Stores only MinkowskiSum points of udist > 0: done by storeMinkowskiSumPoints.

Definition at line 1162 of file mpr_base.cc.

1163 {
1164  Coord_t minR, maxR;
1165  mprfloat dist;
1166 
1167  // step 3
1168  mn_mx_MinkowskiSum( dim, &minR, &maxR );
1169 
1170 #ifdef mprDEBUG_ALL
1171  int i;
1172  for( i=0; i <= dim; i++) Print("acoords[%d]=%d ",i,(int)acoords[i]);
1173  Print(":: [%d,%d]\n", minR, maxR);
1174 #endif
1175 
1176  // step 5 -> terminate
1177  if( dim == n-1 )
1178  {
1179  int lastKilled = 0;
1180  // insert points
1181  acoords[dim] = minR;
1182  while( acoords[dim] <= maxR )
1183  {
1184  if( !storeMinkowskiSumPoint() )
1185  lastKilled++;
1186  acoords[dim]++;
1187  }
1189  return;
1190  }
1191 
1192  // step 4 -> recurse at step 3
1193  acoords[dim] = minR;
1194  while ( acoords[dim] <= maxR )
1195  {
1196  if ( (acoords[dim] > minR) && (acoords[dim] <= maxR) )
1197  { // acoords[dim] >= minR ??
1199  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1200  }
1201  else
1202  {
1203  // get v-distance of pt
1204  dist= vDistance( &(acoords[0]), dim + 1 );// dim+1 == known coordinates
1205 
1206  if( dist >= SIMPLEX_EPS )
1207  {
1209  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1210  }
1211  }
1212  acoords[dim]++;
1213  } // while
1214 }

◆ storeMinkowskiSumPoint()

bool mayanPyramidAlg::storeMinkowskiSumPoint ( )
private

Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.

Definition at line 1138 of file mpr_base.cc.

1139 {
1140  mprfloat dist;
1141 
1142  // determine v-distance of point pt
1143  dist= vDistance( &(acoords[0]), n );
1144 
1145  // store only points with v-distance > minVdist
1146  if( dist <= MINVDIST + SIMPLEX_EPS )
1147  {
1149  return false;
1150  }
1151 
1152  E->addPoint( &(acoords[0]) );
1154 
1155  return true;
1156 }

◆ vDistance()

mprfloat mayanPyramidAlg::vDistance ( Coord_t acoords,
int  dim 
)
private

Compute v-distance via Linear Programing Linear Program finds the v-distance of the point in accords[].

The v-distance is the distance along the direction v to boundary of Minkowski Sum of Qi (here vector v is represented by shift[]). Returns the v-distance or -1.0 if an error occurred.

Definition at line 909 of file mpr_base.cc.

910 {
911  int i, ii, j, k, col, r;
912  int numverts, cols;
913 
914  numverts = 0;
915  for( i=0; i<=n; i++)
916  {
917  numverts += Qi[i]->num;
918  }
919  cols = numverts + 2;
920 
921  //if( dim < 1 || dim > n )
922  // WerrorS("mayanPyramidAlg::vDistance: Known coords dim off range");
923 
924  pLP->LiPM[1][1] = 0.0;
925  pLP->LiPM[1][2] = 1.0; // maximize
926  for( j=3; j<=cols; j++) pLP->LiPM[1][j] = 0.0;
927 
928  for( i=0; i <= n; i++ )
929  {
930  pLP->LiPM[i+2][1] = 1.0;
931  pLP->LiPM[i+2][2] = 0.0;
932  }
933  for( i=1; i<=dim; i++)
934  {
935  pLP->LiPM[n+2+i][1] = (mprfloat)(acoords_a[i-1]);
936  pLP->LiPM[n+2+i][2] = -shift[i];
937  }
938 
939  ii = -1;
940  col = 2;
941  for ( i= 0; i <= n; i++ )
942  {
943  ii++;
944  for( k= 1; k <= Qi[ii]->num; k++ )
945  {
946  col++;
947  for ( r= 0; r <= n; r++ )
948  {
949  if ( r == i ) pLP->LiPM[r+2][col] = -1.0;
950  else pLP->LiPM[r+2][col] = 0.0;
951  }
952  for( r= 1; r <= dim; r++ )
953  pLP->LiPM[r+n+2][col] = -(mprfloat)((*Qi[ii])[k]->point[r]);
954  }
955  }
956 
957  if( col != cols)
958  Werror("mayanPyramidAlg::vDistance:"
959  "setting up matrix for udist: col %d != cols %d",col,cols);
960 
961  pLP->m = n+dim+1;
962  pLP->m3= pLP->m;
963  pLP->n=cols-1;
964 
965 #ifdef mprDEBUG_ALL
966  Print("vDistance LP, known koords dim=%d, constr %d, cols %d, acoords= ",
967  dim,pLP->m,cols);
968  for( i= 0; i < dim; i++ )
969  Print(" %d",acoords_a[i]);
970  PrintLn();
971  print_mat( pLP->LiPM, pLP->m+1, cols);
972 #endif
973 
974  pLP->compute();
975 
976 #ifdef mprDEBUG_ALL
977  PrintS("LP returns matrix\n");
978  print_bmat( pLP->LiPM, pLP->m+1, cols+1-pLP->m, cols, pLP->iposv);
979 #endif
980 
981  if( pLP->icase != 0 )
982  { // check for errors
983  WerrorS("mayanPyramidAlg::vDistance:");
984  if( pLP->icase == 1 )
985  WerrorS(" Unbounded v-distance: probably 1st v-coor=0");
986  else if( pLP->icase == -1 )
987  WerrorS(" Infeasible v-distance");
988  else
989  WerrorS(" Unknown error");
990  return -1.0;
991  }
992 
993  return pLP->LiPM[1][1];
994 }

Field Documentation

◆ acoords

Coord_t mayanPyramidAlg::acoords[MAXVARS+2]
private

Definition at line 323 of file mpr_base.cc.

◆ E

pointSet* mayanPyramidAlg::E
private

Definition at line 318 of file mpr_base.cc.

◆ idelem

int mayanPyramidAlg::idelem
private

Definition at line 321 of file mpr_base.cc.

◆ n

int mayanPyramidAlg::n
private

Definition at line 321 of file mpr_base.cc.

◆ pLP

simplex* mayanPyramidAlg::pLP
private

Definition at line 325 of file mpr_base.cc.

◆ Qi

pointSet** mayanPyramidAlg::Qi
private

Definition at line 317 of file mpr_base.cc.

◆ shift

mprfloat* mayanPyramidAlg::shift
private

Definition at line 319 of file mpr_base.cc.


The documentation for this class was generated from the following file:
dim
int dim(ideal I, ring r)
Definition: tropicalStrategy.cc:22
simplex::m
int m
Definition: mpr_numeric.h:197
MINVDIST
#define MINVDIST
Definition: mpr_base.cc:52
j
int j
Definition: facHensel.cc:105
ST_SPARSE_MPEND
#define ST_SPARSE_MPEND
Definition: mpr_global.h:71
k
int k
Definition: cfEzgcd.cc:92
ST_SPARSE_MREC2
#define ST_SPARSE_MREC2
Definition: mpr_global.h:73
simplex::LiPM
mprfloat ** LiPM
Definition: mpr_numeric.h:204
ST_SPARSE_VADD
#define ST_SPARSE_VADD
Definition: mpr_global.h:69
mayanPyramidAlg::runMayanPyramid
void runMayanPyramid(int dim)
Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold M...
Definition: mpr_base.cc:1162
ST_SPARSE_VREJ
#define ST_SPARSE_VREJ
Definition: mpr_global.h:70
mayanPyramidAlg::shift
mprfloat * shift
Definition: mpr_base.cc:319
mayanPyramidAlg::E
pointSet * E
Definition: mpr_base.cc:318
pointSet
Definition: mpr_base.cc:160
mprSTICKYPROT
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:53
mayanPyramidAlg::pLP
simplex * pLP
Definition: mpr_base.cc:325
i
int i
Definition: cfEzgcd.cc:125
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
simplex::icase
int icase
Definition: mpr_numeric.h:200
mayanPyramidAlg::vDistance
mprfloat vDistance(Coord_t *acoords, int dim)
Compute v-distance via Linear Programing Linear Program finds the v-distance of the point in accords[...
Definition: mpr_base.cc:909
pointSet::addPoint
bool addPoint(const onePointP vert)
Adds a point to pointSet, copy vert[0,...,dim] ot point[num+1][0,...,dim].
Definition: mpr_base.cc:464
mayanPyramidAlg::mn_mx_MinkowskiSum
void mn_mx_MinkowskiSum(int dim, Coord_t *minR, Coord_t *maxR)
LP for finding min/max coord in MinkowskiSum, given previous coors.
Definition: mpr_base.cc:996
mayanPyramidAlg::acoords
Coord_t acoords[MAXVARS+2]
Definition: mpr_base.cc:323
Coord_t
unsigned int Coord_t
Definition: mpr_base.cc:131
mayanPyramidAlg::n
int n
Definition: mpr_base.cc:321
MAXVARS
#define MAXVARS
Definition: mpr_base.cc:55
simplex::m3
int m3
Definition: mpr_numeric.h:199
mprfloat
double mprfloat
Definition: mpr_global.h:16
Print
#define Print
Definition: emacs.cc:79
ST_SPARSE_MREC1
#define ST_SPARSE_MREC1
Definition: mpr_global.h:72
Werror
void Werror(const char *fmt,...)
Definition: reporter.cc:188
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
SIMPLEX_EPS
#define SIMPLEX_EPS
Definition: mpr_numeric.h:180
simplex::compute
void compute()
Definition: mpr_numeric.cc:1093
pointSet::num
int num
Definition: mpr_base.cc:167
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
PrintLn
void PrintLn()
Definition: reporter.cc:309
simplex::n
int n
Definition: mpr_numeric.h:198
mayanPyramidAlg::storeMinkowskiSumPoint
bool storeMinkowskiSumPoint()
Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored,...
Definition: mpr_base.cc:1138
mayanPyramidAlg::Qi
pointSet ** Qi
Definition: mpr_base.cc:317
simplex::iposv
int * iposv
Definition: mpr_numeric.h:202