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

Constructor & Destructor Documentation

§ mayanPyramidAlg()

mayanPyramidAlg::mayanPyramidAlg ( simplex _pLP)
inline

Definition at line 282 of file mpr_base.cc.

282 : n((currRing->N)), pLP(_pLP) {}
simplex * pLP
Definition: mpr_base.cc:327
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10

§ ~mayanPyramidAlg()

mayanPyramidAlg::~mayanPyramidAlg ( )
inline

Definition at line 283 of file mpr_base.cc.

283 {}

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

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

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

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

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

1165 {
1166  Coord_t minR, maxR;
1167  mprfloat dist;
1168 
1169  // step 3
1170  mn_mx_MinkowskiSum( dim, &minR, &maxR );
1171 
1172 #ifdef mprDEBUG_ALL
1173  int i;
1174  for( i=0; i <= dim; i++) Print("acoords[%d]=%d ",i,(int)acoords[i]);
1175  Print(":: [%d,%d]\n", minR, maxR);
1176 #endif
1177 
1178  // step 5 -> terminate
1179  if( dim == n-1 )
1180  {
1181  int lastKilled = 0;
1182  // insert points
1183  acoords[dim] = minR;
1184  while( acoords[dim] <= maxR )
1185  {
1186  if( !storeMinkowskiSumPoint() )
1187  lastKilled++;
1188  acoords[dim]++;
1189  }
1191  return;
1192  }
1193 
1194  // step 4 -> recurse at step 3
1195  acoords[dim] = minR;
1196  while ( acoords[dim] <= maxR )
1197  {
1198  if ( (acoords[dim] > minR) && (acoords[dim] <= maxR) )
1199  { // acoords[dim] >= minR ??
1201  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1202  }
1203  else
1204  {
1205  // get v-distance of pt
1206  dist= vDistance( &(acoords[0]), dim + 1 );// dim+1 == known coordinates
1207 
1208  if( dist >= SIMPLEX_EPS )
1209  {
1211  runMayanPyramid( dim + 1 ); // recurse with higer dimension
1212  }
1213  }
1214  acoords[dim]++;
1215  } // while
1216 }
#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:998
Coord_t acoords[MAXVARS+2]
Definition: mpr_base.cc:325
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:911
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:133
#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:1164
bool storeMinkowskiSumPoint()
Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.
Definition: mpr_base.cc:1140

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

1141 {
1142  mprfloat dist;
1143 
1144  // determine v-distance of point pt
1145  dist= vDistance( &(acoords[0]), n );
1146 
1147  // store only points with v-distance > minVdist
1148  if( dist <= MINVDIST + SIMPLEX_EPS )
1149  {
1151  return false;
1152  }
1153 
1154  E->addPoint( &(acoords[0]) );
1156 
1157  return true;
1158 }
#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:325
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:911
#define MINVDIST
Definition: mpr_base.cc:54
double mprfloat
Definition: mpr_global.h:17
pointSet * E
Definition: mpr_base.cc:320
#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:466
#define ST_SPARSE_VADD
Definition: mpr_global.h:70

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

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

Field Documentation

§ acoords

Coord_t mayanPyramidAlg::acoords[MAXVARS+2]
private

Definition at line 325 of file mpr_base.cc.

§ E

pointSet* mayanPyramidAlg::E
private

Definition at line 320 of file mpr_base.cc.

§ idelem

int mayanPyramidAlg::idelem
private

Definition at line 323 of file mpr_base.cc.

§ n

int mayanPyramidAlg::n
private

Definition at line 323 of file mpr_base.cc.

§ pLP

simplex* mayanPyramidAlg::pLP
private

Definition at line 327 of file mpr_base.cc.

§ Qi

pointSet** mayanPyramidAlg::Qi
private

Definition at line 319 of file mpr_base.cc.

§ shift

mprfloat* mayanPyramidAlg::shift
private

Definition at line 321 of file mpr_base.cc.


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