My Project
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 813 of file MinorProcessor.cc.

814 {
815  _polyMatrix = NULL;
816 }
poly * _polyMatrix
private store for polynomial matrix entries
#define NULL
Definition: omList.c:12

◆ ~PolyMinorProcessor()

PolyMinorProcessor::~PolyMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 863 of file MinorProcessor.cc.

864 {
865  /* free memory of _polyMatrix */
866  int n = _rows * _columns;
867  for (int i = 0; i < n; i++)
870 }
int i
Definition: cfEzgcd.cc:132
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:899
VAR 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 872 of file MinorProcessor.cc.

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

◆ 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 818 of file MinorProcessor.cc.

820 {
821  return _polyMatrix[rowIndex * _columns + columnIndex];
822 }

◆ 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 895 of file MinorProcessor.cc.

900 {
901  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
903  /* call a helper method which recursively computes the minor using the cache
904  c: */
905  return getMinorPrivateLaplace(dimension, _container, false, c, iSB);
906 }
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 908 of file MinorProcessor.cc.

913 {
914  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
916  /* call a helper method which computes the minor (without using a cache): */
917  if (strcmp(algorithm, "Laplace") == 0)
919  else if (strcmp(algorithm, "Bareiss") == 0)
921  else assume(false);
922 
923  /* The following code is never reached and just there to make the
924  compiler happy: */
925  return PolyMinorValue();
926 }
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:389

◆ 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 computed
mkthe representation of rows and columns of the minor to be computed
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 1391 of file MinorProcessor.cc.

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

◆ 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 computed
mkthe representation of rows and columns of the minor to be computed
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 1086 of file MinorProcessor.cc.

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

◆ 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 computed
mkthe representation of rows and columns of the minor to be computed
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 953 of file MinorProcessor.cc.

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

◆ 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 944 of file MinorProcessor.cc.

947 {
948  /* computation with cache */
949  return getMinorPrivateLaplace(_minorSize, _minor, true, c, iSB);
950 }
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 928 of file MinorProcessor.cc.

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

◆ 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 824 of file MinorProcessor.cc.

826 {
827  return getEntry(absoluteRowIndex, absoluteColumnIndex) == NULL;
828 }

◆ 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 830 of file MinorProcessor.cc.

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

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: