My Project  debian-1:4.1.1-p2+ds-4build4
Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes
PolyMinorProcessor Class Reference

Class PolyMinorProcessor is derived from class MinorProcessor. More...

#include <MinorProcessor.h>

Public Member Functions

 PolyMinorProcessor ()
 A constructor for creating an instance. More...
 
 ~PolyMinorProcessor ()
 A destructor for deleting an instance. More...
 
void defineMatrix (const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
 A method for defining a matrix with polynomial entries. More...
 
PolyMinorValue getMinor (const int dimension, const int *rowIndices, const int *columnIndices, const char *algorithm, const ideal &iSB)
 A method for computing the value of a minor, without using a cache. More...
 
PolyMinorValue getMinor (const int dimension, const int *rowIndices, const int *columnIndices, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
 A method for computing the value of a minor, using a cache. More...
 
PolyMinorValue getNextMinor (const char *algorithm, const ideal &iSB)
 A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
PolyMinorValue getNextMinor (Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
 A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
std::string toString () const
 A method for providing a printable version of the represented MinorProcessor. More...
 
- Public Member Functions inherited from MinorProcessor
 MinorProcessor ()
 The default constructor. More...
 
virtual ~MinorProcessor ()
 A destructor for deleting an instance. More...
 
void defineSubMatrix (const int numberOfRows, const int *rowIndices, const int numberOfColumns, const int *columnIndices)
 A method for defining a sub-matrix within a pre-defined matrix. More...
 
void setMinorSize (const int minorSize)
 Sets the size of the minor(s) of interest. More...
 
bool hasNextMinor ()
 A method for checking whether there is a next choice of rows and columns when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void getCurrentRowIndices (int *const target) const
 A method for obtaining the current set of rows corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void getCurrentColumnIndices (int *const target) const
 A method for obtaining the current set of columns corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void print () const
 A method for printing a string representation of the given MinorProcessor to std::cout. More...
 

Protected Member Functions

bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
 A method for testing whether a matrix entry is zero. More...
 
- Protected Member Functions inherited from MinorProcessor
bool setNextKeys (const int k)
 A method for iterating through all possible subsets of k rows and k columns inside a pre-defined submatrix of a pre-defined matrix. More...
 
int getBestLine (const int k, const MinorKey &mk) const
 A method for identifying the row or column with the most zeros. More...
 

Private Member Functions

poly getEntry (const int rowIndex, const int columnIndex) const
 A method for retrieving the matrix entry. More...
 
PolyMinorValue getMinorPrivateLaplace (const int k, const MinorKey &mk, const bool multipleMinors, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
 A method for computing the value of a minor, using a cache. More...
 
PolyMinorValue getMinorPrivateLaplace (const int k, const MinorKey &mk, const ideal &iSB)
 A method for computing the value of a minor, without using a cache. More...
 
PolyMinorValue getMinorPrivateBareiss (const int k, const MinorKey &mk, const ideal &iSB)
 A method for computing the value of a minor, without using a cache. More...
 

Private Attributes

poly * _polyMatrix
 private store for polynomial matrix entries More...
 

Additional Inherited Members

- Static Protected Member Functions inherited from MinorProcessor
static int NumberOfRetrievals (const int rows, const int columns, const int containerMinorSize, const int minorSize, const bool multipleMinors)
 A static method for computing the maximum number of retrievals of a minor. More...
 
static int IOverJ (const int i, const int j)
 A static method for computing the binomial coefficient i over j. More...
 
static int Faculty (const int i)
 A static method for computing the factorial of i. More...
 
- Protected Attributes inherited from MinorProcessor
MinorKey _container
 private store for the rows and columns of the container minor within the underlying matrix; _container will be used to fix a submatrix (e.g. More...
 
int _containerRows
 private store for the number of rows in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*). More...
 
int _containerColumns
 private store for the number of columns in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*). More...
 
MinorKey _minor
 private store for the rows and columns of the minor of interest; Usually, this minor will encode subsets of the rows and columns in _container. More...
 
int _minorSize
 private store for the dimension of the minor(s) of interest More...
 
int _rows
 private store for the number of rows in the underlying matrix More...
 
int _columns
 private store for the number of columns in the underlying matrix More...
 

Detailed Description

Class PolyMinorProcessor is derived from class MinorProcessor.

This class implements the special case of polynomial matrices.

Author
Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch

Definition at line 560 of file MinorProcessor.h.

Constructor & Destructor Documentation

◆ PolyMinorProcessor()

PolyMinorProcessor::PolyMinorProcessor ( )

A constructor for creating an instance.

Definition at line 810 of file MinorProcessor.cc.

811 {
812  _polyMatrix = NULL;
813 }
poly * _polyMatrix
private store for polynomial matrix entries
#define NULL
Definition: omList.c:10

◆ ~PolyMinorProcessor()

PolyMinorProcessor::~PolyMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 860 of file MinorProcessor.cc.

861 {
862  /* free memory of _polyMatrix */
863  int n = _rows * _columns;
864  for (int i = 0; i < n; i++)
867 }
int i
Definition: cfEzgcd.cc:125
int _columns
private store for the number of columns in the underlying matrix
int _rows
private store for the number of rows in the underlying matrix
#define omfree(addr)
Definition: omAllocDecl.h:237
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:857
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13

Member Function Documentation

◆ defineMatrix()

void PolyMinorProcessor::defineMatrix ( const int  numberOfRows,
const int  numberOfColumns,
const poly *  polyMatrix 
)

A method for defining a matrix with polynomial entries.

Parameters
numberOfRowsthe number of rows
numberOfColumnsthe number of columns
polyMatrixthe matrix entries in a linear array, i.e., from left to right and top to bottom
See also
MinorValue::defineSubMatrix (const int, const int*, const int, const int*)

Definition at line 869 of file MinorProcessor.cc.

872 {
873  /* free memory of _polyMatrix */
874  int n = _rows * _columns;
875  for (int i = 0; i < n; i++)
878 
879  _rows = numberOfRows;
880  _columns = numberOfColumns;
881  n = _rows * _columns;
882 
883  /* allocate memory for new entries in _polyMatrix */
884  _polyMatrix = (poly*)omAlloc(n*sizeof(poly));
885 
886  /* copying values from one-dimensional method
887  parameter "polyMatrix" */
888  for (int i = 0; i < n; i++)
889  _polyMatrix[i] = pCopy(polyMatrix[i]);
890 }
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define pCopy(p)
return a copy of the poly
Definition: polys.h:172

◆ getEntry()

poly PolyMinorProcessor::getEntry ( const int  rowIndex,
const int  columnIndex 
) const
private

A method for retrieving the matrix entry.

Parameters
rowIndexthe absolute (zero-based) row index
columnIndexthe absolute (zero-based) column index
Returns
the specified matrix entry

Definition at line 815 of file MinorProcessor.cc.

817 {
818  return _polyMatrix[rowIndex * _columns + columnIndex];
819 }

◆ getMinor() [1/2]

PolyMinorValue PolyMinorProcessor::getMinor ( const int  dimension,
const int *  rowIndices,
const int *  columnIndices,
Cache< MinorKey, PolyMinorValue > &  c,
const ideal &  iSB 
)

A method for computing the value of a minor, using a cache.


The sub-matrix is determined by rowIndices and columnIndices. Computation works recursively using Laplace's Theorem. We always develop along the row or column with most zeros; see MinorProcessor::getBestLine (const int, const int, const int). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
dimensionthe size of the minor to be computed
rowIndices0-based indices of the rows of the minor
columnIndices0-based indices of the column of the minor
ca cache to be used for caching reusable sub-minors
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::(const int dimension, const int* rowIndices, const int* columnIndices, const char* algorithm, const ideal& iSB)

Definition at line 892 of file MinorProcessor.cc.

897 {
898  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
900  /* call a helper method which recursively computes the minor using the cache
901  c: */
902  return getMinorPrivateLaplace(dimension, _container, false, c, iSB);
903 }
BOOLEAN dimension(leftv res, leftv args)
Definition: bbcone.cc:757
int _minorSize
private store for the dimension of the minor(s) of interest
void defineSubMatrix(const int numberOfRows, const int *rowIndices, const int numberOfColumns, const int *columnIndices)
A method for defining a sub-matrix within a pre-defined matrix.
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
PolyMinorValue getMinorPrivateLaplace(const int k, const MinorKey &mk, const bool multipleMinors, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
A method for computing the value of a minor, using a cache.

◆ getMinor() [2/2]

PolyMinorValue PolyMinorProcessor::getMinor ( const int  dimension,
const int *  rowIndices,
const int *  columnIndices,
const char *  algorithm,
const ideal &  iSB 
)

A method for computing the value of a minor, without using a cache.


The sub-matrix is determined by rowIndices and columnIndices. Computation works either by Laplace's algorithm or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
dimensionthe size of the minor to be computed
rowIndices0-based indices of the rows of the minor
columnIndices0-based indices of the column of the minor
algorithmeither "Laplace" or "Bareiss"
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinor (const int dimension, const int* rowIndices, const int* columnIndices, Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB)

Definition at line 905 of file MinorProcessor.cc.

910 {
911  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
913  /* call a helper method which computes the minor (without using a cache): */
914  if (strcmp(algorithm, "Laplace") == 0)
916  else if (strcmp(algorithm, "Bareiss") == 0)
918  else assume(false);
919 
920  /* The following code is never reached and just there to make the
921  compiler happy: */
922  return PolyMinorValue();
923 }
PolyMinorValue getMinorPrivateBareiss(const int k, const MinorKey &mk, const ideal &iSB)
A method for computing the value of a minor, without using a cache.
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:800
#define assume(x)
Definition: mod2.h:390

◆ getMinorPrivateBareiss()

PolyMinorValue PolyMinorProcessor::getMinorPrivateBareiss ( const int  k,
const MinorKey mk,
const ideal &  iSB 
)
private

A method for computing the value of a minor, without using a cache.


The sub-matrix is specified by mk. Computation works using Bareiss's algorithm. If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be comuted
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const ideal& iSB)

Definition at line 1388 of file MinorProcessor.cc.

1391 {
1392  assume(k > 0); /* k is the minor's dimension; the minor must be at least
1393  1x1 */
1394  int *theRows=(int*)omAlloc(k*sizeof(int));
1395  mk.getAbsoluteRowIndices(theRows);
1396  int *theColumns=(int*)omAlloc(k*sizeof(int));
1397  mk.getAbsoluteColumnIndices(theColumns);
1398  if (k == 1)
1399  {
1400  PolyMinorValue tmp=PolyMinorValue(getEntry(theRows[0], theColumns[0]),
1401  0, 0, 0, 0, -1, -1);
1402  omFree(theColumns);
1403  omFree(theRows);
1404  return tmp;
1405  }
1406  else /* k > 0 */
1407  {
1408  /* the matrix to perform Bareiss with */
1409  poly* tempMatrix = (poly*)omAlloc(k * k * sizeof(poly));
1410  /* copy correct set of entries from _polyMatrix to tempMatrix */
1411  int i = 0;
1412  for (int r = 0; r < k; r++)
1413  for (int c = 0; c < k; c++)
1414  tempMatrix[i++] = pCopy(getEntry(theRows[r], theColumns[c]));
1415 
1416  /* Bareiss algorithm operating on tempMatrix which is at least 2x2 */
1417  int sign = 1; /* This will store the correct sign resulting from
1418  permuting the rows of tempMatrix. */
1419  int *rowPermutation=(int*)omAlloc(k*sizeof(int));
1420  /* This is for storing the permutation of rows
1421  resulting from searching for a non-zero pivot
1422  element. */
1423  for (int i = 0; i < k; i++) rowPermutation[i] = i;
1424  poly divisor = NULL;
1425  int divisorLength = 0;
1426  number divisorLC;
1427  for (int r = 0; r <= k - 2; r++)
1428  {
1429  /* look for a non-zero entry in column r, rows = r .. (k - 1)
1430  s.t. the polynomial has least complexity: */
1431  int minComplexity = -1; int complexity = 0; int bestRow = -1;
1432  poly pp = NULL;
1433  for (int i = r; i < k; i++)
1434  {
1435  pp = tempMatrix[rowPermutation[i] * k + r];
1436  if (pp != NULL)
1437  {
1438  if (minComplexity == -1)
1439  {
1440  minComplexity = pSize(pp);
1441  bestRow = i;
1442  }
1443  else
1444  {
1445  complexity = 0;
1446  while ((pp != NULL) && (complexity < minComplexity))
1447  {
1448  complexity += nSize(pGetCoeff(pp)); pp = pNext(pp);
1449  }
1450  if (complexity < minComplexity)
1451  {
1452  minComplexity = complexity;
1453  bestRow = i;
1454  }
1455  }
1456  if (minComplexity <= 1) break; /* terminate the search */
1457  }
1458  }
1459  if (bestRow == -1)
1460  {
1461  /* There is no non-zero entry; hence the minor is zero. */
1462  for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
1463  return PolyMinorValue(NULL, 0, 0, 0, 0, -1, -1);
1464  }
1465  pNormalize(tempMatrix[rowPermutation[bestRow] * k + r]);
1466  if (bestRow != r)
1467  {
1468  /* We swap the rows with indices r and i: */
1469  int j = rowPermutation[bestRow];
1470  rowPermutation[bestRow] = rowPermutation[r];
1471  rowPermutation[r] = j;
1472  /* Now we know that tempMatrix[rowPermutation[r] * k + r] is not zero.
1473  But carefull; we have to negate the sign, as there is always an odd
1474  number of row transpositions to swap two given rows of a matrix. */
1475  sign = -sign;
1476  }
1477 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
1478  poly w = NULL; int wl = 0;
1479  printf("matrix after %d steps:\n", r);
1480  for (int u = 0; u < k; u++)
1481  {
1482  for (int v = 0; v < k; v++)
1483  {
1484  if ((v < r) && (u > v))
1485  wl = 0;
1486  else
1487  {
1488  w = tempMatrix[rowPermutation[u] * k + v];
1489  wl = pLength(w);
1490  }
1491  printf("%5d ", wl);
1492  }
1493  printf("\n");
1494  }
1495  printCounters ("", false);
1496 #endif
1497  if (r != 0)
1498  {
1499  divisor = tempMatrix[rowPermutation[r - 1] * k + r - 1];
1500  pNormalize(divisor);
1501  divisorLength = pLength(divisor);
1502  divisorLC = pGetCoeff(divisor);
1503  }
1504  for (int rr = r + 1; rr < k; rr++)
1505  for (int cc = r + 1; cc < k; cc++)
1506  {
1507  if (r == 0)
1508  elimOperationBucketNoDiv(tempMatrix[rowPermutation[rr] * k + cc],
1509  tempMatrix[rowPermutation[r] * k + r],
1510  tempMatrix[rowPermutation[r] * k + cc],
1511  tempMatrix[rowPermutation[rr] * k + r]);
1512  else
1513  elimOperationBucket(tempMatrix[rowPermutation[rr] * k + cc],
1514  tempMatrix[rowPermutation[r] * k + r],
1515  tempMatrix[rowPermutation[r] * k + cc],
1516  tempMatrix[rowPermutation[rr] * k + r],
1517  divisor, divisorLC, divisorLength);
1518  }
1519  }
1520 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
1521  poly w = NULL; int wl = 0;
1522  printf("matrix after %d steps:\n", k - 1);
1523  for (int u = 0; u < k; u++)
1524  {
1525  for (int v = 0; v < k; v++)
1526  {
1527  if ((v < k - 1) && (u > v))
1528  wl = 0;
1529  else
1530  {
1531  w = tempMatrix[rowPermutation[u] * k + v];
1532  wl = pLength(w);
1533  }
1534  printf("%5d ", wl);
1535  }
1536  printf("\n");
1537  }
1538 #endif
1539  poly result = tempMatrix[rowPermutation[k - 1] * k + k - 1];
1540  tempMatrix[rowPermutation[k - 1] * k + k - 1]=NULL; /*value now in result*/
1541  if (sign == -1) result = pNeg(result);
1542  if (iSB != NULL)
1543  {
1544  poly tmpresult = kNF(iSB, currRing->qideal, result);
1545  pDelete(&result);
1546  result=tmpresult;
1547  }
1548  PolyMinorValue mv(result, 0, 0, 0, 0, -1, -1);
1549  for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
1550  omFreeSize(tempMatrix, k * k * sizeof(poly));
1551  omFree(rowPermutation);
1552  omFree(theColumns);
1553  omFree(theRows);
1554  return mv;
1555  }
1556 }
static void elimOperationBucketNoDiv(poly &p1, poly p2, poly p3, poly p4)
void elimOperationBucket(poly &p1, poly &p2, poly &p3, poly &p4, poly &p5, number &c5, int p5Len)
void printCounters(char *prefix, bool resetToZero)
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
int k
Definition: cfEzgcd.cc:92
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
Definition: Minor.cc:202
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey.
Definition: Minor.cc:181
poly getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
return result
Definition: facAbsBiFact.cc:76
const CanonicalForm & w
Definition: facAbsFact.cc:55
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int j
Definition: facHensel.cc:105
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2813
#define pNext(p)
Definition: monomials.h:43
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:51
#define nSize(n)
Definition: numbers.h:40
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omFree(addr)
Definition: omAllocDecl.h:261
static unsigned pLength(poly a)
Definition: p_polys.h:192
#define pDelete(p_ptr)
Definition: polys.h:173
#define pNeg(p)
Definition: polys.h:185
#define pNormalize(p)
Definition: polys.h:303
#define pSize(p)
Definition: polys.h:304
static int sign(int x)
Definition: ring.cc:3328

◆ getMinorPrivateLaplace() [1/2]

PolyMinorValue PolyMinorProcessor::getMinorPrivateLaplace ( const int  k,
const MinorKey mk,
const bool  multipleMinors,
Cache< MinorKey, PolyMinorValue > &  c,
const ideal &  iSB 
)
private

A method for computing the value of a minor, using a cache.


The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be comuted
multipleMinorsdecides whether we compute just one or all minors of a specified size
ca cache to be used for caching reusable sub-minors
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const ideal& iSB)

Definition at line 1083 of file MinorProcessor.cc.

1089 {
1090  assume(k > 0); /* k is the minor's dimension; the minor must be at least
1091  1x1 */
1092  /* The method works by recursion, and using Lapace's Theorem along
1093  the row/column with the most zeros. */
1094  if (k == 1)
1095  {
1097  mk.getAbsoluteColumnIndex(0)),
1098  0, 0, 0, 0, -1, -1);
1099  /* we set "-1" as, for k == 1, we do not have any cache retrievals */
1100  return pmv;
1101  }
1102  else
1103  {
1104  int b = getBestLine(k, mk); /* row or column with most
1105  zeros */
1106  poly result = NULL; /* This will contain the
1107  value of the minor. */
1108  int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
1109  and multiplications,
1110  ..."a*" for accumulated
1111  operation counters */
1112  bool hadNonZeroEntry = false;
1113  if (b >= 0)
1114  {
1115  /* This means that the best line is the row with absolute (0-based)
1116  index b.
1117  Using Laplace, the sign of the contributing minors must be iterating;
1118  the initial sign depends on the relative index of b in
1119  minorRowKey: */
1120  int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
1121  for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
1122  {
1123  int absoluteC = mk.getAbsoluteColumnIndex(c);
1124  if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
1125  this sub-determinante. */
1126  {
1127  hadNonZeroEntry = true;
1128  PolyMinorValue mv; /* for storing all intermediate minors */
1129  /* Next MinorKey is mk with row b and column absoluteC omitted. */
1130  MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
1131  if (cch.hasKey(subMk))
1132  { /* trying to find the result in the cache */
1133  mv = cch.getValue(subMk);
1134  mv.incrementRetrievals(); /* once more, we made use of the cached
1135  value for key mk */
1136  cch.put(subMk, mv); /* We need to do this with "put", as the
1137  (altered) number of retrievals may have an
1138  impact on the internal ordering among cache
1139  entries. */
1140  }
1141  else
1142  {
1143  /* recursive call: */
1144  mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
1145  iSB);
1146  /* As this minor was not in the cache, we count the additions and
1147  multiplications that we needed to do in the recursive call: */
1148  m += mv.getMultiplications();
1149  s += mv.getAdditions();
1150  }
1151  /* In any case, we count all nested operations in the accumulative
1152  counters: */
1153  am += mv.getAccumulatedMultiplications();
1154  as += mv.getAccumulatedAdditions();
1155  poly signPoly = pISet(sign);
1156  poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
1157  currRing);
1158  temp = p_Mult_q(signPoly, temp, currRing);
1159  result = p_Add_q(result, temp, currRing);
1160 #ifdef COUNT_AND_PRINT_OPERATIONS
1161  multsPoly++;
1162  addsPoly++;
1163  multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
1164 #endif
1165  s++; m++; as++; am++; /* This is for the addition and multiplication
1166  in the previous lines of code. */
1167  }
1168  sign = - sign; /* alternating the sign */
1169  }
1170  }
1171  else
1172  {
1173  b = - b - 1;
1174  /* This means that the best line is the column with absolute (0-based)
1175  index b.
1176  Using Laplace, the sign of the contributing minors must be iterating;
1177  the initial sign depends on the relative index of b in
1178  minorColumnKey: */
1179  int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
1180  for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
1181  {
1182  int absoluteR = mk.getAbsoluteRowIndex(r);
1183  if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
1184  this sub-determinante. */
1185  {
1186  hadNonZeroEntry = true;
1187  PolyMinorValue mv; /* for storing all intermediate minors */
1188  /* Next MinorKey is mk with row absoluteR and column b omitted. */
1189  MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
1190  if (cch.hasKey(subMk))
1191  { /* trying to find the result in the cache */
1192  mv = cch.getValue(subMk);
1193  mv.incrementRetrievals(); /* once more, we made use of the cached
1194  value for key mk */
1195  cch.put(subMk, mv); /* We need to do this with "put", as the
1196  (altered) number of retrievals may have an
1197  impact on the internal ordering among the
1198  cached entries. */
1199  }
1200  else
1201  {
1202  mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
1203  iSB); /* recursive call */
1204  /* As this minor was not in the cache, we count the additions and
1205  multiplications that we needed to do in the recursive call: */
1206  m += mv.getMultiplications();
1207  s += mv.getAdditions();
1208  }
1209  /* In any case, we count all nested operations in the accumulative
1210  counters: */
1211  am += mv.getAccumulatedMultiplications();
1212  as += mv.getAccumulatedAdditions();
1213  poly signPoly = pISet(sign);
1214  poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
1215  currRing);
1216  temp = p_Mult_q(signPoly, temp, currRing);
1217  result = p_Add_q(result, temp, currRing);
1218 #ifdef COUNT_AND_PRINT_OPERATIONS
1219  multsPoly++;
1220  addsPoly++;
1221  multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
1222 #endif
1223  s++; m++; as++; am++; /* This is for the addition and multiplication
1224  in the previous lines of code. */
1225  }
1226  sign = - sign; /* alternating the sign */
1227  }
1228  }
1229  /* Let's cache the newly computed minor: */
1230  int potentialRetrievals = NumberOfRetrievals(_containerRows,
1232  _minorSize,
1233  k,
1234  multipleMinors);
1235  if (hadNonZeroEntry)
1236  {
1237  s--; as--; /* first addition was 0 + ..., so we do not count it */
1238 #ifdef COUNT_AND_PRINT_OPERATIONS
1239  addsPoly--;
1240 #endif
1241  }
1242  if (s < 0) s = 0; /* may happen when all subminors are zero and no
1243  addition needs to be performed */
1244  if (as < 0) as = 0; /* may happen when all subminors are zero and no
1245  addition needs to be performed */
1246  if (iSB != NULL)
1247  {
1248  poly tmpresult = kNF(iSB, currRing->qideal, result);
1249  pDelete(&tmpresult);
1250  result=tmpresult;
1251  }
1252  PolyMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
1253  pDelete(&result); result = NULL;
1254  cch.put(mk, newMV); /* Here's the actual put inside the cache. */
1255  return newMV;
1256  }
1257 }
int m
Definition: cfEzgcd.cc:121
CanonicalForm b
Definition: cfModGcd.cc:4044
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.
Definition: Minor.h:40
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
Definition: Minor.cc:343
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this.
Definition: Minor.cc:149
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
Definition: Minor.cc:223
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
Definition: Minor.cc:255
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this.
Definition: Minor.cc:117
static int NumberOfRetrievals(const int rows, const int columns, const int containerMinorSize, const int minorSize, const bool multipleMinors)
A static method for computing the maximum number of retrievals of a minor.
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
int getAdditions() const
A method for accessing the additions performed while computing this minor.
Definition: Minor.cc:888
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
Definition: Minor.cc:898
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
Definition: Minor.cc:883
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
Definition: Minor.cc:873
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
Definition: Minor.cc:893
bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1102
const CanonicalForm int s
Definition: facAbsFact.cc:55
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:892
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1050
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1093
#define pISet(i)
Definition: polys.h:298

◆ getMinorPrivateLaplace() [2/2]

PolyMinorValue PolyMinorProcessor::getMinorPrivateLaplace ( const int  k,
const MinorKey mk,
const ideal &  iSB 
)
private

A method for computing the value of a minor, without using a cache.


The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be comuted
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivate (const int, const MinorKey&, const bool, Cache<MinorKey, MinorValue>&)

Definition at line 950 of file MinorProcessor.cc.

953 {
954  assume(k > 0); /* k is the minor's dimension; the minor must be at least
955  1x1 */
956  /* The method works by recursion, and using Lapace's Theorem along the
957  row/column with the most zeros. */
958  if (k == 1)
959  {
961  mk.getAbsoluteColumnIndex(0)),
962  0, 0, 0, 0, -1, -1);
963  /* "-1" is to signal that any statistics about the number of retrievals
964  does not make sense, as we do not use a cache. */
965  return pmv;
966  }
967  else
968  {
969  /* Here, the minor must be 2x2 or larger. */
970  int b = getBestLine(k, mk); /* row or column with most
971  zeros */
972  poly result = NULL; /* This will contain the
973  value of the minor. */
974  int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
975  and multiplications,
976  ..."a*" for accumulated
977  operation counters */
978  bool hadNonZeroEntry = false;
979  if (b >= 0)
980  {
981  /* This means that the best line is the row with absolute (0-based)
982  index b.
983  Using Laplace, the sign of the contributing minors must be iterating;
984  the initial sign depends on the relative index of b in minorRowKey: */
985  int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
986  for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
987  {
988  int absoluteC = mk.getAbsoluteColumnIndex(c);
989  if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
990  this sub-determinante. */
991  {
992  hadNonZeroEntry = true;
993  /* Next MinorKey is mk with row b and column absoluteC omitted. */
994  MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
995  /* recursive call: */
996  PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
997  m += mv.getMultiplications();
998  s += mv.getAdditions();
1000  as += mv.getAccumulatedAdditions();
1001  poly signPoly = pISet(sign);
1002  poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
1003  currRing);
1004  temp = p_Mult_q(signPoly, temp, currRing);
1005  result = p_Add_q(result, temp, currRing);
1006 #ifdef COUNT_AND_PRINT_OPERATIONS
1007  multsPoly++;
1008  addsPoly++;
1009  multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
1010 #endif
1011  s++; m++; as++, am++; /* This is for the addition and multiplication
1012  in the previous lines of code. */
1013  }
1014  sign = - sign; /* alternating the sign */
1015  }
1016  }
1017  else
1018  {
1019  b = - b - 1;
1020  /* This means that the best line is the column with absolute (0-based)
1021  index b.
1022  Using Laplace, the sign of the contributing minors must be iterating;
1023  the initial sign depends on the relative index of b in
1024  minorColumnKey: */
1025  int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
1026  for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
1027  {
1028  int absoluteR = mk.getAbsoluteRowIndex(r);
1029  if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
1030  this sub-determinante. */
1031  {
1032  hadNonZeroEntry = true;
1033  /* This is mk with row absoluteR and column b omitted. */
1034  MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
1035  /* recursive call: */
1036  PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
1037  m += mv.getMultiplications();
1038  s += mv.getAdditions();
1039  am += mv.getAccumulatedMultiplications();
1040  as += mv.getAccumulatedAdditions();
1041  poly signPoly = pISet(sign);
1042  poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
1043  currRing);
1044  temp = p_Mult_q(signPoly, temp, currRing);
1045  result = p_Add_q(result, temp, currRing);
1046 #ifdef COUNT_AND_PRINT_OPERATIONS
1047  multsPoly++;
1048  addsPoly++;
1049  multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
1050 #endif
1051  s++; m++; as++, am++; /* This is for the addition and multiplication
1052  in the previous lines of code. */
1053  }
1054  sign = - sign; /* alternating the sign */
1055  }
1056  }
1057  if (hadNonZeroEntry)
1058  {
1059  s--; as--; /* first addition was 0 + ..., so we do not count it */
1060 #ifdef COUNT_AND_PRINT_OPERATIONS
1061  addsPoly--;
1062 #endif
1063  }
1064  if (s < 0) s = 0; /* may happen when all subminors are zero and no
1065  addition needs to be performed */
1066  if (as < 0) as = 0; /* may happen when all subminors are zero and no
1067  addition needs to be performed */
1068  if (iSB != NULL)
1069  {
1070  poly tmpresult = kNF(iSB, currRing->qideal, result);
1071  pDelete(&result);
1072  result=tmpresult;
1073  }
1074  PolyMinorValue newMV(result, m, s, am, as, -1, -1);
1075  /* "-1" is to signal that any statistics about the number of retrievals
1076  does not make sense, as we do not use a cache. */
1077  pDelete(&result);
1078  return newMV;
1079  }
1080 }

◆ getNextMinor() [1/2]

PolyMinorValue PolyMinorProcessor::getNextMinor ( Cache< MinorKey, PolyMinorValue > &  c,
const ideal &  iSB 
)

A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.


This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works using Laplace's algorithm and a cache c which may already contain useful results from previous calls of PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
iSBNULL or a standard basis
Returns
the next minor
See also
PolyMinorValue::getNextMinor (const char* algorithm, const ideal& iSB)

Definition at line 941 of file MinorProcessor.cc.

944 {
945  /* computation with cache */
946  return getMinorPrivateLaplace(_minorSize, _minor, true, c, iSB);
947 }
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...

◆ getNextMinor() [2/2]

PolyMinorValue PolyMinorProcessor::getNextMinor ( const char *  algorithm,
const ideal &  iSB 
)

A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.


This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works either by Laplace's algorithm (without using a cache) or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters
algorithmeither "Laplace" or "Bareiss"
iSBNULL or a standard basis
Returns
true iff there is a next choice of rows and columns
See also
PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB)

Definition at line 925 of file MinorProcessor.cc.

927 {
928  /* call a helper method which computes the minor (without using a
929  cache): */
930  if (strcmp(algorithm, "Laplace") == 0)
932  else if (strcmp(algorithm, "Bareiss") == 0)
934  else assume(false);
935 
936  /* The following code is never reached and just there to make the
937  compiler happy: */
938  return PolyMinorValue();
939 }

◆ isEntryZero()

bool PolyMinorProcessor::isEntryZero ( const int  absoluteRowIndex,
const int  absoluteColumnIndex 
) const
protectedvirtual

A method for testing whether a matrix entry is zero.

Parameters
absoluteRowIndexthe absolute (zero-based) row index
absoluteColumnIndexthe absolute (zero-based) column index
Returns
true iff the specified matrix entry is zero

Reimplemented from MinorProcessor.

Definition at line 821 of file MinorProcessor.cc.

823 {
824  return getEntry(absoluteRowIndex, absoluteColumnIndex) == NULL;
825 }

◆ toString()

string PolyMinorProcessor::toString ( ) const
virtual

A method for providing a printable version of the represented MinorProcessor.

Returns
a printable version of the given instance as instance of class string

Reimplemented from MinorProcessor.

Definition at line 827 of file MinorProcessor.cc.

828 {
829  char h[32];
830  string t = "";
831  string s = "PolyMinorProcessor:";
832  s += "\n matrix: ";
833  sprintf(h, "%d", _rows); s += h;
834  s += " x ";
835  sprintf(h, "%d", _columns); s += h;
836  int myIndexArray[500];
837  s += "\n considered submatrix has row indices: ";
838  _container.getAbsoluteRowIndices(myIndexArray);
839  for (int k = 0; k < _containerRows; k++)
840  {
841  if (k != 0) s += ", ";
842  sprintf(h, "%d", myIndexArray[k]); s += h;
843  }
844  s += " (first row of matrix has index 0)";
845  s += "\n considered submatrix has column indices: ";
846  _container.getAbsoluteColumnIndices(myIndexArray);
847  for (int k = 0; k < _containerColumns; k++)
848  {
849  if (k != 0) s += ", ";
850  sprintf(h, "%d", myIndexArray[k]); s += h;
851  }
852  s += " (first column of matrix has index 0)";
853  s += "\n size of considered minor(s): ";
854  sprintf(h, "%d", _minorSize); s += h;
855  s += "x";
856  s += h;
857  return s;
858 }
static Poly * h
Definition: janet.cc:972

Field Documentation

◆ _polyMatrix

poly* PolyMinorProcessor::_polyMatrix
private

private store for polynomial matrix entries

Definition at line 566 of file MinorProcessor.h.


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