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 280 of file mpr_base.cc.

Constructor & Destructor Documentation

mayanPyramidAlg::mayanPyramidAlg ( simplex _pLP)
inline

Definition at line 283 of file mpr_base.cc.

283 : n((currRing->N)), pLP(_pLP) {}
simplex * pLP
Definition: mpr_base.cc:328
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
mayanPyramidAlg::~mayanPyramidAlg ( )
inline

Definition at line 284 of file mpr_base.cc.

284 {}

Member Function Documentation

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

Drive Mayan Pyramid Algorithm.

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

Definition at line 894 of file mpr_base.cc.

895 {
896  int i;
897 
898  Qi= _q_i;
899  shift= _shift;
900 
901  E= new pointSet( Qi[0]->dim ); // E has same dim as Qi[...]
902 
903  for ( i= 0; i < MAXVARS+2; i++ ) acoords[i]= 0;
904 
905  runMayanPyramid(0);
906 
907  mprSTICKYPROT("\n");
908 
909  return E;
910 }
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:54
Coord_t acoords[MAXVARS+2]
Definition: mpr_base.cc:326
mprfloat * shift
Definition: mpr_base.cc:322
pointSet * E
Definition: mpr_base.cc:321
int dim(ideal I, ring r)
int i
Definition: cfEzgcd.cc:123
#define MAXVARS
Definition: mpr_base.cc:58
void runMayanPyramid(int dim)
Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold M...
Definition: mpr_base.cc:1165
pointSet ** Qi
Definition: mpr_base.cc:320
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 999 of file mpr_base.cc.

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

1166 {
1167  Coord_t minR, maxR;
1168  mprfloat dist;
1169 
1170  // step 3
1171  mn_mx_MinkowskiSum( dim, &minR, &maxR );
1172 
1173 #ifdef mprDEBUG_ALL
1174  int i;
1175  for( i=0; i <= dim; i++) Print("acoords[%d]=%d ",i,(int)acoords[i]);
1176  Print(":: [%d,%d]\n", minR, maxR);
1177 #endif
1178 
1179  // step 5 -> terminate
1180  if( dim == n-1 )
1181  {
1182  int lastKilled = 0;
1183  // insert points
1184  acoords[dim] = minR;
1185  while( acoords[dim] <= maxR )
1186  {
1187  if( !storeMinkowskiSumPoint() )
1188  lastKilled++;
1189  acoords[dim]++;
1190  }
1192  return;
1193  }
1194 
1195  // step 4 -> recurse at step 3
1196  acoords[dim] = minR;
1197  while ( acoords[dim] <= maxR )
1198  {
1199  if ( (acoords[dim] > minR) && (acoords[dim] <= maxR) )
1200  { // acoords[dim] >= minR ??
1202  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1203  }
1204  else
1205  {
1206  // get v-distance of pt
1207  dist= vDistance( &(acoords[0]), dim + 1 );// dim+1 == known coordinates
1208 
1209  if( dist >= SIMPLEX_EPS )
1210  {
1212  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1213  }
1214  }
1215  acoords[dim]++;
1216  } // while
1217 }
#define ST_SPARSE_MREC1
Definition: mpr_global.h:73
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:54
#define ST_SPARSE_MREC2
Definition: mpr_global.h:74
#define Print
Definition: emacs.cc:83
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:999
Coord_t acoords[MAXVARS+2]
Definition: mpr_base.cc:326
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:912
double mprfloat
Definition: mpr_global.h:17
int dim(ideal I, ring r)
int i
Definition: cfEzgcd.cc:123
#define SIMPLEX_EPS
Definition: mpr_numeric.h:181
unsigned int Coord_t
Definition: mpr_base.cc:134
#define ST_SPARSE_MPEND
Definition: mpr_global.h:72
void runMayanPyramid(int dim)
Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold M...
Definition: mpr_base.cc:1165
bool storeMinkowskiSumPoint()
Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.
Definition: mpr_base.cc:1141
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 1141 of file mpr_base.cc.

1142 {
1143  mprfloat dist;
1144 
1145  // determine v-distance of point pt
1146  dist= vDistance( &(acoords[0]), n );
1147 
1148  // store only points with v-distance > minVdist
1149  if( dist <= MINVDIST + SIMPLEX_EPS )
1150  {
1152  return false;
1153  }
1154 
1155  E->addPoint( &(acoords[0]) );
1157 
1158  return true;
1159 }
#define mprSTICKYPROT(msg)
Definition: mpr_global.h:54
#define ST_SPARSE_VREJ
Definition: mpr_global.h:71
Coord_t acoords[MAXVARS+2]
Definition: mpr_base.cc:326
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:912
#define MINVDIST
Definition: mpr_base.cc:55
double mprfloat
Definition: mpr_global.h:17
pointSet * E
Definition: mpr_base.cc:321
#define SIMPLEX_EPS
Definition: mpr_numeric.h:181
bool addPoint(const onePointP vert)
Adds a point to pointSet, copy vert[0,...,dim] ot point[num+1][0,...,dim].
Definition: mpr_base.cc:467
#define ST_SPARSE_VADD
Definition: mpr_global.h:70
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 occured.

Definition at line 912 of file mpr_base.cc.

913 {
914  int i, ii, j, k, col, r;
915  int numverts, cols;
916 
917  numverts = 0;
918  for( i=0; i<=n; i++)
919  {
920  numverts += Qi[i]->num;
921  }
922  cols = numverts + 2;
923 
924  //if( dim < 1 || dim > n )
925  // WerrorS("mayanPyramidAlg::vDistance: Known coords dim off range");
926 
927  pLP->LiPM[1][1] = 0.0;
928  pLP->LiPM[1][2] = 1.0; // maximize
929  for( j=3; j<=cols; j++) pLP->LiPM[1][j] = 0.0;
930 
931  for( i=0; i <= n; i++ )
932  {
933  pLP->LiPM[i+2][1] = 1.0;
934  pLP->LiPM[i+2][2] = 0.0;
935  }
936  for( i=1; i<=dim; i++)
937  {
938  pLP->LiPM[n+2+i][1] = (mprfloat)(acoords_a[i-1]);
939  pLP->LiPM[n+2+i][2] = -shift[i];
940  }
941 
942  ii = -1;
943  col = 2;
944  for ( i= 0; i <= n; i++ )
945  {
946  ii++;
947  for( k= 1; k <= Qi[ii]->num; k++ )
948  {
949  col++;
950  for ( r= 0; r <= n; r++ )
951  {
952  if ( r == i ) pLP->LiPM[r+2][col] = -1.0;
953  else pLP->LiPM[r+2][col] = 0.0;
954  }
955  for( r= 1; r <= dim; r++ )
956  pLP->LiPM[r+n+2][col] = -(mprfloat)((*Qi[ii])[k]->point[r]);
957  }
958  }
959 
960  if( col != cols)
961  Werror("mayanPyramidAlg::vDistance:"
962  "setting up matrix for udist: col %d != cols %d",col,cols);
963 
964  pLP->m = n+dim+1;
965  pLP->m3= pLP->m;
966  pLP->n=cols-1;
967 
968 #ifdef mprDEBUG_ALL
969  Print("vDistance LP, known koords dim=%d, constr %d, cols %d, acoords= ",
970  dim,pLP->m,cols);
971  for( i= 0; i < dim; i++ )
972  Print(" %d",acoords_a[i]);
973  PrintLn();
974  print_mat( pLP->LiPM, pLP->m+1, cols);
975 #endif
976 
977  pLP->compute();
978 
979 #ifdef mprDEBUG_ALL
980  PrintS("LP returns matrix\n");
981  print_bmat( pLP->LiPM, pLP->m+1, cols+1-pLP->m, cols, pLP->iposv);
982 #endif
983 
984  if( pLP->icase != 0 )
985  { // check for errors
986  WerrorS("mayanPyramidAlg::vDistance:");
987  if( pLP->icase == 1 )
988  WerrorS(" Unbounded v-distance: probably 1st v-coor=0");
989  else if( pLP->icase == -1 )
990  WerrorS(" Infeasible v-distance");
991  else
992  WerrorS(" Unknown error");
993  return -1.0;
994  }
995 
996  return pLP->LiPM[1][1];
997 }
void PrintLn()
Definition: reporter.cc:322
void compute()
#define Print
Definition: emacs.cc:83
simplex * pLP
Definition: mpr_base.cc:328
mprfloat * shift
Definition: mpr_base.cc:322
void WerrorS(const char *s)
Definition: feFopen.cc:23
int k
Definition: cfEzgcd.cc:93
double mprfloat
Definition: mpr_global.h:17
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
int * iposv
Definition: mpr_numeric.h:203
int dim(ideal I, ring r)
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
mprfloat ** LiPM
Definition: mpr_numeric.h:205
int num
Definition: mpr_base.cc:170
int icase
Definition: mpr_numeric.h:201
void Werror(const char *fmt,...)
Definition: reporter.cc:199
pointSet ** Qi
Definition: mpr_base.cc:320

Field Documentation

Coord_t mayanPyramidAlg::acoords[MAXVARS+2]
private

Definition at line 326 of file mpr_base.cc.

pointSet* mayanPyramidAlg::E
private

Definition at line 321 of file mpr_base.cc.

int mayanPyramidAlg::idelem
private

Definition at line 324 of file mpr_base.cc.

int mayanPyramidAlg::n
private

Definition at line 324 of file mpr_base.cc.

simplex* mayanPyramidAlg::pLP
private

Definition at line 328 of file mpr_base.cc.

pointSet** mayanPyramidAlg::Qi
private

Definition at line 320 of file mpr_base.cc.

mprfloat* mayanPyramidAlg::shift
private

Definition at line 322 of file mpr_base.cc.


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