My Project
Loading...
Searching...
No Matches
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...
 
virtual std::string toString () const
 A method for providing a printable version of the represented MinorProcessor. 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...
 
virtual bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
 A method for testing whether a matrix entry is zero. 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{
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 {
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: */
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: */
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);
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 {
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();
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();
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: ";
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: