Loading...
Searching...
No Matches
PolyMinorProcessor Class Reference

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

`#include <MinorProcessor.h>`

## Public Member Functions

| PolyMinorProcessor ()
| A constructor for creating an instance.
| ~PolyMinorProcessor ()
| A destructor for deleting an instance.
void | defineMatrix (const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
| A method for defining a matrix with polynomial entries.
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.
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.
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.
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.
std::string | toString () const
| A method for providing a printable version of the represented MinorProcessor.
Public Member Functions inherited from MinorProcessor
| MinorProcessor ()
| The default constructor.
virtual | ~MinorProcessor ()
| A destructor for deleting an instance.
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.
void | setMinorSize (const int minorSize)
| Sets the size of the minor(s) of interest.
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.
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.
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.
void | print () const
| A method for printing a string representation of the given MinorProcessor to std::cout.

## Protected Member Functions

bool | isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
| A method for testing whether a matrix entry is zero.
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.
int | getBestLine (const int k, const MinorKey &mk) const
| A method for identifying the row or column with the most zeros.

## Private Member Functions

poly | getEntry (const int rowIndex, const int columnIndex) const
| A method for retrieving the matrix entry.
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.
PolyMinorValue | getMinorPrivateLaplace (const int k, const MinorKey &mk, const ideal &iSB)
| A method for computing the value of a minor, without using a cache.
PolyMinorValue | getMinorPrivateBareiss (const int k, const MinorKey &mk, const ideal &iSB)
| A method for computing the value of a minor, without using a cache.

## Private Attributes

poly * | _polyMatrix
| private store for polynomial matrix entries

## 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.
static int | IOverJ (const int i, const int j)
| A static method for computing the binomial coefficient i over j.
static int | Faculty (const int i)
| A static method for computing the factorial of i.
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.
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*).
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*).
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.
int | _minorSize
| private store for the dimension of the minor(s) of interest
int | _rows
| private store for the number of rows in the underlying matrix
int | _columns
| private store for the number of columns in the underlying matrix

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

{
_polyMatrix = NULL;
}
PolyMinorProcessor::_polyMatrix
poly * _polyMatrix
private store for polynomial matrix entries
Definition MinorProcessor.h:566
NULL
#define NULL
Definition omList.c:12

## ~PolyMinorProcessor()

PolyMinorProcessor::~PolyMinorProcessor | ( |  | ) |

A destructor for deleting an instance.

Definition at line 863 of file MinorProcessor.cc.

{
/* free memory of _polyMatrix */
int n = _rows * _columns;
for (int i = 0; i < n; i++)
p_Delete(&_polyMatrix[i], currRing);
omfree(_polyMatrix); _polyMatrix = NULL;
}
i
int i
Definition cfEzgcd.cc:132
MinorProcessor::_columns
int _columns
private store for the number of columns in the underlying matrix
Definition MinorProcessor.h:171
MinorProcessor::_rows
int _rows
private store for the number of rows in the underlying matrix
Definition MinorProcessor.h:166
omfree
#define omfree(addr)
Definition omAllocDecl.h:237
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
currRing
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

  numberOfRows | the number of rows
  numberOfColumns | the number of columns
  polyMatrix | the 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.

{
/* free memory of _polyMatrix */
int n = _rows * _columns;
for (int i = 0; i < n; i++)
p_Delete(&_polyMatrix[i], currRing);
omfree(_polyMatrix); _polyMatrix = NULL;
_rows = numberOfRows;
_columns = numberOfColumns;
n = _rows * _columns;
/* allocate memory for new entries in _polyMatrix */
_polyMatrix = (poly*)omAlloc(n*sizeof(poly));
/* copying values from one-dimensional method
parameter "polyMatrix" */
for (int i = 0; i < n; i++)
_polyMatrix[i] = pCopy(polyMatrix[i]);
}
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186

## getEntry()

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

private

A method for retrieving the matrix entry.

Parameters

  rowIndex | the absolute (zero-based) row index
  columnIndex | the absolute (zero-based) column index

Returns
  the specified matrix entry

Definition at line 818 of file MinorProcessor.cc.

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

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

  dimension | the size of the minor to be computed
  rowIndices | 0-based indices of the rows of the minor
  columnIndices | 0-based indices of the column of the minor
  c | a cache to be used for caching reusable sub-minors
  iSB | NULL 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.

{
defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
_minorSize = dimension;
/* call a helper method which recursively computes the minor using the cache
c: */
return getMinorPrivateLaplace(dimension, _container, false, c, iSB);
}
dimension
BOOLEAN dimension(leftv res, leftv args)
Definition bbcone.cc:757
MinorProcessor::_minorSize
int _minorSize
private store for the dimension of the minor(s) of interest
Definition MinorProcessor.h:161
MinorProcessor::defineSubMatrix
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.
Definition MinorProcessor.cc:129
MinorProcessor::_container
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
Definition MinorProcessor.h:135
PolyMinorProcessor::getMinorPrivateLaplace
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.
Definition MinorProcessor.cc:1086

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

  dimension | the size of the minor to be computed
  rowIndices | 0-based indices of the rows of the minor
  columnIndices | 0-based indices of the column of the minor
  algorithm | either "Laplace" or "Bareiss"
  iSB | NULL 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.

{
defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
_minorSize = dimension;
/* call a helper method which computes the minor (without using a cache): */
if (strcmp(algorithm, "Laplace") == 0)
return getMinorPrivateLaplace(_minorSize, _container, iSB);
else if (strcmp(algorithm, "Bareiss") == 0)
return getMinorPrivateBareiss(_minorSize, _container, iSB);
else assume(false);
/* The following code is never reached and just there to make the
compiler happy: */
return PolyMinorValue();
}
PolyMinorProcessor::getMinorPrivateBareiss
PolyMinorValue getMinorPrivateBareiss(const int k, const MinorKey &mk, const ideal &iSB)
A method for computing the value of a minor, without using a cache.
Definition MinorProcessor.cc:1391
assume
#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

  k | the number of rows and columns in the minor to be computed
  mk | the representation of rows and columns of the minor to be computed
  iSB | NULL 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.

{
assume(k > 0); /* k is the minor's dimension; the minor must be at least
1x1 */
int *theRows=(int*)omAlloc(k*sizeof(int));
mk.getAbsoluteRowIndices(theRows);
int *theColumns=(int*)omAlloc(k*sizeof(int));
mk.getAbsoluteColumnIndices(theColumns);
if (k == 1)
{
PolyMinorValue tmp=PolyMinorValue(getEntry(theRows[0], theColumns[0]),
0, 0, 0, 0, -1, -1);
omFree(theColumns);
omFree(theRows);
return tmp;
}
else /* k > 0 */
{
/* the matrix to perform Bareiss with */
poly* tempMatrix = (poly*)omAlloc(k * k * sizeof(poly));
/* copy correct set of entries from _polyMatrix to tempMatrix */
int i = 0;
for (int r = 0; r < k; r++)
for (int c = 0; c < k; c++)
tempMatrix[i++] = pCopy(getEntry(theRows[r], theColumns[c]));
/* Bareiss algorithm operating on tempMatrix which is at least 2x2 */
int sign = 1; /* This will store the correct sign resulting from
permuting the rows of tempMatrix. */
int *rowPermutation=(int*)omAlloc(k*sizeof(int));
/* This is for storing the permutation of rows
resulting from searching for a non-zero pivot
element. */
for (int i = 0; i < k; i++) rowPermutation[i] = i;
poly divisor = NULL;
int divisorLength = 0;
number divisorLC;
for (int r = 0; r <= k - 2; r++)
{
/* look for a non-zero entry in column r, rows = r .. (k - 1)
s.t. the polynomial has least complexity: */
int minComplexity = -1; int complexity = 0; int bestRow = -1;
poly pp = NULL;
for (int i = r; i < k; i++)
{
pp = tempMatrix[rowPermutation[i] * k + r];
if (pp != NULL)
{
if (minComplexity == -1)
{
minComplexity = pSize(pp);
bestRow = i;
}
else
{
complexity = 0;
while ((pp != NULL) && (complexity < minComplexity))
{
complexity += nSize(pGetCoeff(pp)); pp = pNext(pp);
}
if (complexity < minComplexity)
{
minComplexity = complexity;
bestRow = i;
}
}
if (minComplexity <= 1) break; /* terminate the search */
}
}
if (bestRow == -1)
{
/* There is no non-zero entry; hence the minor is zero. */
for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
return PolyMinorValue(NULL, 0, 0, 0, 0, -1, -1);
}
pNormalize(tempMatrix[rowPermutation[bestRow] * k + r]);
if (bestRow != r)
{
/* We swap the rows with indices r and i: */
int j = rowPermutation[bestRow];
rowPermutation[bestRow] = rowPermutation[r];
rowPermutation[r] = j;
/* Now we know that tempMatrix[rowPermutation[r] * k + r] is not zero.
But careful; we have to negate the sign, as there is always an odd
number of row transpositions to swap two given rows of a matrix. */
sign = -sign;
}
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
poly w = NULL; int wl = 0;
printf("matrix after %d steps:\n", r);
for (int u = 0; u < k; u++)
{
for (int v = 0; v < k; v++)
{
if ((v < r) && (u > v))
wl = 0;
else
{
w = tempMatrix[rowPermutation[u] * k + v];
wl = pLength(w);
}
printf("%5d ", wl);
}
printf("\n");
}
printCounters ("", false);
#endif
if (r != 0)
{
divisor = tempMatrix[rowPermutation[r - 1] * k + r - 1];
pNormalize(divisor);
divisorLength = pLength(divisor);
divisorLC = pGetCoeff(divisor);
}
for (int rr = r + 1; rr < k; rr++)
for (int cc = r + 1; cc < k; cc++)
{
if (r == 0)
elimOperationBucketNoDiv(tempMatrix[rowPermutation[rr] * k + cc],
tempMatrix[rowPermutation[r] * k + r],
tempMatrix[rowPermutation[r] * k + cc],
tempMatrix[rowPermutation[rr] * k + r]);
else
elimOperationBucket(tempMatrix[rowPermutation[rr] * k + cc],
tempMatrix[rowPermutation[r] * k + r],
tempMatrix[rowPermutation[r] * k + cc],
tempMatrix[rowPermutation[rr] * k + r],
divisor, divisorLC, divisorLength);
}
}
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
poly w = NULL; int wl = 0;
printf("matrix after %d steps:\n", k - 1);
for (int u = 0; u < k; u++)
{
for (int v = 0; v < k; v++)
{
if ((v < k - 1) && (u > v))
wl = 0;
else
{
w = tempMatrix[rowPermutation[u] * k + v];
wl = pLength(w);
}
printf("%5d ", wl);
}
printf("\n");
}
#endif
poly result = tempMatrix[rowPermutation[k - 1] * k + k - 1];
tempMatrix[rowPermutation[k - 1] * k + k - 1]=NULL; /*value now in result*/
if (sign == -1) result = pNeg(result);
if (iSB != NULL)
{
poly tmpresult = kNF(iSB, currRing->qideal, result);
pDelete(&result);
result=tmpresult;
}
PolyMinorValue mv(result, 0, 0, 0, 0, -1, -1);
for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
omFreeSize(tempMatrix, k * k * sizeof(poly));
omFree(rowPermutation);
omFree(theColumns);
omFree(theRows);
return mv;
}
}
elimOperationBucketNoDiv
static void elimOperationBucketNoDiv(poly &p1, poly p2, poly p3, poly p4)
Definition MinorProcessor.cc:1289
elimOperationBucket
void elimOperationBucket(poly &p1, poly &p2, poly &p3, poly &p4, poly &p5, number &c5, int p5Len)
Definition MinorProcessor.cc:1324
printCounters
void printCounters(char *prefix, bool resetToZero)
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
k
int k
Definition cfEzgcd.cc:99
MinorKey::getAbsoluteColumnIndices
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
MinorKey::getAbsoluteRowIndices
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
PolyMinorProcessor::getEntry
poly getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
Definition MinorProcessor.cc:818
result
return result
Definition facAbsBiFact.cc:76
w
const CanonicalForm & w
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
j
int j
Definition facHensel.cc:110
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3229
pNext
#define pNext(p)
Definition monomials.h:36
pGetCoeff
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
nSize
#define nSize(n)
Definition numbers.h:39
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
pLength
static int pLength(poly a)
Definition p_polys.h:190
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pNeg
#define pNeg(p)
Definition polys.h:199
pNormalize
#define pNormalize(p)
Definition polys.h:318
pSize
#define pSize(p)
Definition polys.h:319
sign
static int sign(int x)
Definition ring.cc:3504

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

  k | the number of rows and columns in the minor to be computed
  mk | the representation of rows and columns of the minor to be computed
  multipleMinors | decides whether we compute just one or all minors of a specified size
  c | a cache to be used for caching reusable sub-minors
  iSB | NULL 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.

{
assume(k > 0); /* k is the minor's dimension; the minor must be at least
1x1 */
/* The method works by recursion, and using Lapace's Theorem along
the row/column with the most zeros. */
if (k == 1)
{
PolyMinorValue pmv(getEntry(mk.getAbsoluteRowIndex(0),
mk.getAbsoluteColumnIndex(0)),
0, 0, 0, 0, -1, -1);
/* we set "-1" as, for k == 1, we do not have any cache retrievals */
return pmv;
}
else
{
int b = getBestLine(k, mk); /* row or column with most
zeros */
poly result = NULL; /* This will contain the
value of the minor. */
int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
and multiplications,
..."a*" for accumulated
operation counters */
bool hadNonZeroEntry = false;
if (b >= 0)
{
/* This means that the best line is the row with absolute (0-based)
index b.
Using Laplace, the sign of the contributing minors must be iterating;
the initial sign depends on the relative index of b in
minorRowKey: */
int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
{
int absoluteC = mk.getAbsoluteColumnIndex(c);
if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
this sub-determinante. */
{
hadNonZeroEntry = true;
PolyMinorValue mv; /* for storing all intermediate minors */
/* Next MinorKey is mk with row b and column absoluteC omitted. */
MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
if (cch.hasKey(subMk))
{ /* trying to find the result in the cache */
mv = cch.getValue(subMk);
mv.incrementRetrievals(); /* once more, we made use of the cached
value for key mk */
cch.put(subMk, mv); /* We need to do this with "put", as the
(altered) number of retrievals may have an
impact on the internal ordering among cache
entries. */
}
else
{
/* recursive call: */
mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
iSB);
/* As this minor was not in the cache, we count the additions and
multiplications that we needed to do in the recursive call: */
m += mv.getMultiplications();
s += mv.getAdditions();
}
/* In any case, we count all nested operations in the accumulative
counters: */
am += mv.getAccumulatedMultiplications();
as += mv.getAccumulatedAdditions();
poly signPoly = pISet(sign);
poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
currRing);
temp = p_Mult_q(signPoly, temp, currRing);
result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
multsPoly++;
addsPoly++;
multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
#endif
s++; m++; as++; am++; /* This is for the addition and multiplication
in the previous lines of code. */
}
sign = - sign; /* alternating the sign */
}
}
else
{
b = - b - 1;
/* This means that the best line is the column with absolute (0-based)
index b.
Using Laplace, the sign of the contributing minors must be iterating;
the initial sign depends on the relative index of b in
minorColumnKey: */
int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
{
int absoluteR = mk.getAbsoluteRowIndex(r);
if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
this sub-determinante. */
{
hadNonZeroEntry = true;
PolyMinorValue mv; /* for storing all intermediate minors */
/* Next MinorKey is mk with row absoluteR and column b omitted. */
MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
if (cch.hasKey(subMk))
{ /* trying to find the result in the cache */
mv = cch.getValue(subMk);
mv.incrementRetrievals(); /* once more, we made use of the cached
value for key mk */
cch.put(subMk, mv); /* We need to do this with "put", as the
(altered) number of retrievals may have an
impact on the internal ordering among the
cached entries. */
}
else
{
mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
iSB); /* recursive call */
/* As this minor was not in the cache, we count the additions and
multiplications that we needed to do in the recursive call: */
m += mv.getMultiplications();
s += mv.getAdditions();
}
/* In any case, we count all nested operations in the accumulative
counters: */
am += mv.getAccumulatedMultiplications();
as += mv.getAccumulatedAdditions();
poly signPoly = pISet(sign);
poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
currRing);
temp = p_Mult_q(signPoly, temp, currRing);
result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
multsPoly++;
addsPoly++;
multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
#endif
s++; m++; as++; am++; /* This is for the addition and multiplication
in the previous lines of code. */
}
sign = - sign; /* alternating the sign */
}
}
/* Let's cache the newly computed minor: */
int potentialRetrievals = NumberOfRetrievals(_containerRows,
_containerColumns,
_minorSize,
k,
multipleMinors);
if (hadNonZeroEntry)
{
s--; as--; /* first addition was 0 + ..., so we do not count it */
#ifdef COUNT_AND_PRINT_OPERATIONS
addsPoly--;
#endif
}
if (s < 0) s = 0; /* may happen when all subminors are zero and no
addition needs to be performed */
if (as < 0) as = 0; /* may happen when all subminors are zero and no
addition needs to be performed */
if (iSB != NULL)
{
poly tmpresult = kNF(iSB, currRing->qideal, result);
pDelete(&tmpresult);
result=tmpresult;
}
PolyMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
pDelete(&result); result = NULL;
cch.put(mk, newMV); /* Here's the actual put inside the cache. */
return newMV;
}
}
m
int m
Definition cfEzgcd.cc:128
b
CanonicalForm b
Definition cfModGcd.cc:4111
MinorKey::getSubMinorKey
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
MinorKey::getAbsoluteColumnIndex
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
MinorKey::getRelativeRowIndex
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
MinorKey::getRelativeColumnIndex
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
MinorKey::getAbsoluteRowIndex
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
MinorProcessor::NumberOfRetrievals
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.
Definition MinorProcessor.cc:245
MinorProcessor::_containerRows
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
Definition MinorProcessor.h:142
MinorProcessor::getBestLine
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
Definition MinorProcessor.cc:57
MinorProcessor::_containerColumns
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
Definition MinorProcessor.h:149
MinorValue::getAdditions
int getAdditions() const
A method for accessing the additions performed while computing this minor.
Definition Minor.cc:888
MinorValue::getAccumulatedAdditions
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
Definition Minor.cc:898
MinorValue::getMultiplications
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
Definition Minor.cc:883
MinorValue::incrementRetrievals
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
Definition Minor.cc:873
MinorValue::getAccumulatedMultiplications
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
Definition Minor.cc:893
PolyMinorProcessor::isEntryZero
bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
Definition MinorProcessor.cc:824
PolyMinorValue::getResult
poly getResult() const
Accessor for the private field _result.
Definition Minor.cc:1102
s
const CanonicalForm int s
Definition facAbsFact.cc:51
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
p_Mult_q
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1125
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition p_polys.h:1167
pISet
#define pISet(i)
Definition polys.h:313

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

  k | the number of rows and columns in the minor to be computed
  mk | the representation of rows and columns of the minor to be computed
  iSB | NULL 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.

{
assume(k > 0); /* k is the minor's dimension; the minor must be at least
1x1 */
/* The method works by recursion, and using Lapace's Theorem along the
row/column with the most zeros. */
if (k == 1)
{
PolyMinorValue pmv(getEntry(mk.getAbsoluteRowIndex(0),
mk.getAbsoluteColumnIndex(0)),
0, 0, 0, 0, -1, -1);
/* "-1" is to signal that any statistics about the number of retrievals
does not make sense, as we do not use a cache. */
return pmv;
}
else
{
/* Here, the minor must be 2x2 or larger. */
int b = getBestLine(k, mk); /* row or column with most
zeros */
poly result = NULL; /* This will contain the
value of the minor. */
int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
and multiplications,
..."a*" for accumulated
operation counters */
bool hadNonZeroEntry = false;
if (b >= 0)
{
/* This means that the best line is the row with absolute (0-based)
index b.
Using Laplace, the sign of the contributing minors must be iterating;
the initial sign depends on the relative index of b in minorRowKey: */
int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
{
int absoluteC = mk.getAbsoluteColumnIndex(c);
if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
this sub-determinante. */
{
hadNonZeroEntry = true;
/* Next MinorKey is mk with row b and column absoluteC omitted. */
MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
/* recursive call: */
PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
m += mv.getMultiplications();
s += mv.getAdditions();
am += mv.getAccumulatedMultiplications();
as += mv.getAccumulatedAdditions();
poly signPoly = pISet(sign);
poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
currRing);
temp = p_Mult_q(signPoly, temp, currRing);
result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
multsPoly++;
addsPoly++;
multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
#endif
s++; m++; as++, am++; /* This is for the addition and multiplication
in the previous lines of code. */
}
sign = - sign; /* alternating the sign */
}
}
else
{
b = - b - 1;
/* This means that the best line is the column with absolute (0-based)
index b.
Using Laplace, the sign of the contributing minors must be iterating;
the initial sign depends on the relative index of b in
minorColumnKey: */
int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
{
int absoluteR = mk.getAbsoluteRowIndex(r);
if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
this sub-determinante. */
{
hadNonZeroEntry = true;
/* This is mk with row absoluteR and column b omitted. */
MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
/* recursive call: */
PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
m += mv.getMultiplications();
s += mv.getAdditions();
am += mv.getAccumulatedMultiplications();
as += mv.getAccumulatedAdditions();
poly signPoly = pISet(sign);
poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
currRing);
temp = p_Mult_q(signPoly, temp, currRing);
result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
multsPoly++;
addsPoly++;
multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
#endif
s++; m++; as++, am++; /* This is for the addition and multiplication
in the previous lines of code. */
}
sign = - sign; /* alternating the sign */
}
}
if (hadNonZeroEntry)
{
s--; as--; /* first addition was 0 + ..., so we do not count it */
#ifdef COUNT_AND_PRINT_OPERATIONS
addsPoly--;
#endif
}
if (s < 0) s = 0; /* may happen when all subminors are zero and no
addition needs to be performed */
if (as < 0) as = 0; /* may happen when all subminors are zero and no
addition needs to be performed */
if (iSB != NULL)
{
poly tmpresult = kNF(iSB, currRing->qideal, result);
pDelete(&result);
result=tmpresult;
}
PolyMinorValue newMV(result, m, s, am, as, -1, -1);
/* "-1" is to signal that any statistics about the number of retrievals
does not make sense, as we do not use a cache. */
pDelete(&result);
return newMV;
}
}

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

  iSB | NULL 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.

{
/* computation with cache */
return getMinorPrivateLaplace(_minorSize, _minor, true, c, iSB);
}
MinorProcessor::_minor
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
Definition MinorProcessor.h:156

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

  algorithm | either "Laplace" or "Bareiss"
  iSB | NULL 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.

{
/* call a helper method which computes the minor (without using a
cache): */
if (strcmp(algorithm, "Laplace") == 0)
return getMinorPrivateLaplace(_minorSize, _minor, iSB);
else if (strcmp(algorithm, "Bareiss") == 0)
return getMinorPrivateBareiss(_minorSize, _minor, iSB);
else assume(false);
/* The following code is never reached and just there to make the
compiler happy: */
return PolyMinorValue();
}

## isEntryZero()

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

protected virtual

A method for testing whether a matrix entry is zero.

Parameters

  absoluteRowIndex | the absolute (zero-based) row index
  absoluteColumnIndex | the 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.

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

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

{
char h[32];
string t = "";
string s = "PolyMinorProcessor:";
s += "\n matrix: ";
snprintf(h,32, "%d", _rows); s += h;
s += " x ";
snprintf(h,32, "%d", _columns); s += h;
int myIndexArray[500];
s += "\n considered submatrix has row indices: ";
_container.getAbsoluteRowIndices(myIndexArray);
for (int k = 0; k < _containerRows; k++)
{
if (k != 0) s += ", ";
snprintf(h,32, "%d", myIndexArray[k]); s += h;
}
s += " (first row of matrix has index 0)";
s += "\n considered submatrix has column indices: ";
_container.getAbsoluteColumnIndices(myIndexArray);
for (int k = 0; k < _containerColumns; k++)
{
if (k != 0) s += ", ";
snprintf(h,32, "%d", myIndexArray[k]); s += h;
}
s += " (first column of matrix has index 0)";
s += "\n size of considered minor(s): ";
snprintf(h, 32, "%d", _minorSize); s += h;
s += "x";
s += h;
return s;
}
h
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:

- kernel/linear_algebra/MinorProcessor.h
- kernel/linear_algebra/MinorProcessor.cc