Loading...
Searching...
No Matches
mayanPyramidAlg Class Reference

## Public Member Functions

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

## 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[].
mprfloat | vDistance (Coord_t *acoords, int dim)
| Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords[].
void | mn_mx_MinkowskiSum (int dim, Coord_t *minR, Coord_t *maxR)
| LP for finding min/max coord in MinkowskiSum, given previous coors.
bool | storeMinkowskiSumPoint ()
| Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.

## Private Attributes

pointSet ** | Qi
pointSet * | E
mprfloat * | shift
int | n
int | idelem
Coord_t | acoords [MAXVARS+2]
simplex * | pLP

## 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.

: n((currRing->N)), pLP(_pLP) {}
mayanPyramidAlg::pLP
simplex * pLP
Definition mpr_base.cc:325
mayanPyramidAlg::n
int n
Definition mpr_base.cc:321
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13

## ~mayanPyramidAlg()

mayanPyramidAlg::~mayanPyramidAlg | ( |  | ) |

inline

Definition at line 281 of file mpr_base.cc.

{}

## 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.

{
int i;
Qi= _q_i;
shift= _shift;
E= new pointSet( Qi[0]->dim ); // E has same dim as Qi[...]
for ( i= 0; i < MAXVARS+2; i++ ) acoords[i]= 0;
runMayanPyramid(0);
mprSTICKYPROT("\n");
return E;
}
i
int i
Definition cfEzgcd.cc:132
mayanPyramidAlg::E
pointSet * E
Definition mpr_base.cc:318
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
mayanPyramidAlg::Qi
pointSet ** Qi
Definition mpr_base.cc:317
mayanPyramidAlg::shift
mprfloat * shift
Definition mpr_base.cc:319
mayanPyramidAlg::acoords
Coord_t acoords[MAXVARS+2]
Definition mpr_base.cc:323
MAXVARS
#define MAXVARS
Definition mpr_base.cc:55
mprSTICKYPROT
#define mprSTICKYPROT(msg)
Definition mpr_global.h:54
dim
int dim(ideal I, ring r)
Definition tropicalStrategy.cc:23

## 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.

{
int i, j, k, cols, cons;
int la_cons_row;
cons = n+dim+2;
// first, compute minimum
//
// common part of the matrix
pLP->LiPM[1][1] = 0.0;
for( i=2; i<=n+2; i++)
{
pLP->LiPM[i][1] = 1.0; // 1st col
pLP->LiPM[i][2] = 0.0; // 2nd col
}
la_cons_row = 1;
cols = 2;
for( i=0; i<=n; i++)
{
la_cons_row++;
for( j=1; j<= Qi[i]->num; j++)
{
cols++;
pLP->LiPM[1][cols] = 0.0; // set 1st row 0
for( k=2; k<=n+2; k++)
{ // lambdas sum up to 1
if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
else pLP->LiPM[k][cols] = -1.0;
}
for( k=1; k<=n; k++)
pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
} // j
} // i
for( i= 0; i < dim; i++ )
{ // fixed coords
pLP->LiPM[i+n+3][1] = acoords[i];
pLP->LiPM[i+n+3][2] = 0.0;
}
pLP->LiPM[dim+n+3][1] = 0.0;
pLP->LiPM[1][2] = -1.0; // minimize
pLP->LiPM[dim+n+3][2] = 1.0;
#ifdef mprDEBUG_ALL
Print("\nThats the matrix for minR, dim= %d, acoords= ",dim);
for( i= 0; i < dim; i++ )
Print(" %d",acoords[i]);
PrintLn();
print_mat( pLP->LiPM, cons+1, cols);
#endif
// simplx finds MIN for obj.fnc, puts it in [1,1]
pLP->m= cons;
pLP->n= cols-1;
pLP->m3= cons;
pLP->compute();
if ( pLP->icase != 0 )
{ // check for errors
if( pLP->icase < 0)
WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: infeasible");
else if( pLP->icase > 0)
WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: unbounded");
}
*minR = (Coord_t)( -pLP->LiPM[1][1] + 1.0 - SIMPLEX_EPS );
// now compute maximum
//
// common part of the matrix again
pLP->LiPM[1][1] = 0.0;
for( i=2; i<=n+2; i++)
{
pLP->LiPM[i][1] = 1.0;
pLP->LiPM[i][2] = 0.0;
}
la_cons_row = 1;
cols = 2;
for( i=0; i<=n; i++)
{
la_cons_row++;
for( j=1; j<=Qi[i]->num; j++)
{
cols++;
pLP->LiPM[1][cols] = 0.0;
for( k=2; k<=n+2; k++)
{
if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
else pLP->LiPM[k][cols] = -1.0;
}
for( k=1; k<=n; k++)
pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
} // j
} // i
for( i= 0; i < dim; i++ )
{ // fixed coords
pLP->LiPM[i+n+3][1] = acoords[i];
pLP->LiPM[i+n+3][2] = 0.0;
}
pLP->LiPM[dim+n+3][1] = 0.0;
pLP->LiPM[1][2] = 1.0; // maximize
pLP->LiPM[dim+n+3][2] = 1.0; // var = sum of pnt coords
#ifdef mprDEBUG_ALL
Print("\nThats the matrix for maxR, dim= %d\n",dim);
print_mat( pLP->LiPM, cons+1, cols);
#endif
pLP->m= cons;
pLP->n= cols-1;
pLP->m3= cons;
// simplx finds MAX for obj.fnc, puts it in [1,1]
pLP->compute();
if ( pLP->icase != 0 )
{
if( pLP->icase < 0)
WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: infeasible");
else if( pLP->icase > 0)
WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: unbounded");
}
*maxR = (Coord_t)( pLP->LiPM[1][1] + SIMPLEX_EPS );
#ifdef mprDEBUG_ALL
Print(" Range for dim=%d: [%d,%d]\n", dim, *minR, *maxR);
#endif
}
k
int k
Definition cfEzgcd.cc:99
Print
#define Print
Definition emacs.cc:80
j
int j
Definition facHensel.cc:110
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
Coord_t
unsigned int Coord_t
Definition mpr_base.cc:131
mprfloat
double mprfloat
Definition mpr_global.h:17
SIMPLEX_EPS
#define SIMPLEX_EPS
Definition mpr_numeric.h:181
PrintLn
void PrintLn()
Definition reporter.cc:314

## 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.

{
Coord_t minR, maxR;
mprfloat dist;
// step 3
mn_mx_MinkowskiSum( dim, &minR, &maxR );
#ifdef mprDEBUG_ALL
int i;
for( i=0; i <= dim; i++) Print("acoords[%d]=%d ",i,(int)acoords[i]);
Print(":: [%d,%d]\n", minR, maxR);
#endif
// step 5 -> terminate
if( dim == n-1 )
{
int lastKilled = 0;
// insert points
acoords[dim] = minR;
while( acoords[dim] <= maxR )
{
if( !storeMinkowskiSumPoint() )
lastKilled++;
acoords[dim]++;
}
mprSTICKYPROT(ST_SPARSE_MPEND);
return;
}
// step 4 -> recurse at step 3
acoords[dim] = minR;
while ( acoords[dim] <= maxR )
{
if ( (acoords[dim] > minR) && (acoords[dim] <= maxR) )
{ // acoords[dim] >= minR ??
mprSTICKYPROT(ST_SPARSE_MREC1);
runMayanPyramid( dim + 1 ); // recurse with higher dimension
}
else
{
// get v-distance of pt
dist= vDistance( &(acoords[0]), dim + 1 );// dim+1 == known coordinates
if( dist >= SIMPLEX_EPS )
{
mprSTICKYPROT(ST_SPARSE_MREC2);
runMayanPyramid( dim + 1 ); // recurse with higher dimension
}
}
acoords[dim]++;
} // while
}
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::vDistance
mprfloat vDistance(Coord_t *acoords, int dim)
Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords...
Definition mpr_base.cc:909
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
ST_SPARSE_MREC2
#define ST_SPARSE_MREC2
Definition mpr_global.h:74
ST_SPARSE_MPEND
#define ST_SPARSE_MPEND
Definition mpr_global.h:72
ST_SPARSE_MREC1
#define ST_SPARSE_MREC1
Definition mpr_global.h:73

## 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.

{
mprfloat dist;
// determine v-distance of point pt
dist= vDistance( &(acoords[0]), n );
// store only points with v-distance > minVdist
if( dist <= MINVDIST + SIMPLEX_EPS )
{
mprSTICKYPROT(ST_SPARSE_VREJ);
return false;
}
E->addPoint( &(acoords[0]) );
mprSTICKYPROT(ST_SPARSE_VADD);
return true;
}
MINVDIST
#define MINVDIST
Definition mpr_base.cc:52
ST_SPARSE_VADD
#define ST_SPARSE_VADD
Definition mpr_global.h:70
ST_SPARSE_VREJ
#define ST_SPARSE_VREJ
Definition mpr_global.h:71

## vDistance()

mprfloat mayanPyramidAlg::vDistance | ( | Coord_t * | acoords,
|  | int | dim )

private

Compute v-distance via Linear Programming 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.

{
int i, ii, j, k, col, r;
int numverts, cols;
numverts = 0;
for( i=0; i<=n; i++)
{
numverts += Qi[i]->num;
}
cols = numverts + 2;
//if( dim < 1 || dim > n )
// WerrorS("mayanPyramidAlg::vDistance: Known coords dim off range");
pLP->LiPM[1][1] = 0.0;
pLP->LiPM[1][2] = 1.0; // maximize
for( j=3; j<=cols; j++) pLP->LiPM[1][j] = 0.0;
for( i=0; i <= n; i++ )
{
pLP->LiPM[i+2][1] = 1.0;
pLP->LiPM[i+2][2] = 0.0;
}
for( i=1; i<=dim; i++)
{
pLP->LiPM[n+2+i][1] = (mprfloat)(acoords_a[i-1]);
pLP->LiPM[n+2+i][2] = -shift[i];
}
ii = -1;
col = 2;
for ( i= 0; i <= n; i++ )
{
ii++;
for( k= 1; k <= Qi[ii]->num; k++ )
{
col++;
for ( r= 0; r <= n; r++ )
{
if ( r == i ) pLP->LiPM[r+2][col] = -1.0;
else pLP->LiPM[r+2][col] = 0.0;
}
for( r= 1; r <= dim; r++ )
pLP->LiPM[r+n+2][col] = -(mprfloat)((*Qi[ii])[k]->point[r]);
}
}
if( col != cols)
Werror("mayanPyramidAlg::vDistance:"
"setting up matrix for udist: col %d != cols %d",col,cols);
pLP->m = n+dim+1;
pLP->m3= pLP->m;
pLP->n=cols-1;
#ifdef mprDEBUG_ALL
Print("vDistance LP, known koords dim=%d, constr %d, cols %d, acoords= ",
dim,pLP->m,cols);
for( i= 0; i < dim; i++ )
Print(" %d",acoords_a[i]);
PrintLn();
print_mat( pLP->LiPM, pLP->m+1, cols);
#endif
pLP->compute();
#ifdef mprDEBUG_ALL
PrintS("LP returns matrix\n");
print_bmat( pLP->LiPM, pLP->m+1, cols+1-pLP->m, cols, pLP->iposv);
#endif
if( pLP->icase != 0 )
{ // check for errors
WerrorS("mayanPyramidAlg::vDistance:");
if( pLP->icase == 1 )
WerrorS(" Unbounded v-distance: probably 1st v-coor=0");
else if( pLP->icase == -1 )
WerrorS(" Infeasible v-distance");
else
WerrorS(" Unknown error");
return -1.0;
}
return pLP->LiPM[1][1];
}
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
Werror
void Werror(const char *fmt,...)
Definition reporter.cc:189

## 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:

- kernel/numeric/mpr_base.cc