Loading...
Searching...
No Matches
MinorInterface.cc File Reference
`#include "kernel/mod2.h"`
`#include "kernel/linear_algebra/MinorInterface.h"`
`#include "kernel/linear_algebra/MinorProcessor.h"`
`#include "polys/simpleideals.h"`
`#include "coeffs/modulop.h"`
`#include "kernel/polys.h"`
`#include "kernel/structs.h"`
`#include "kernel/GBEngine/kstd1.h"`
`#include "kernel/ideals.h"`

Go to the source code of this file.

## Functions

bool | arrayIsNumberArray (const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
ideal | getMinorIdeal_Int (const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
ideal | getMinorIdeal_Poly (const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
ideal | getMinorIdeal_toBeDone (const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
ideal | getMinorIdeal (const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal iSB, const bool allDifferent)
| Returns the specified set of minors (= subdeterminantes) of the given matrix.
ideal | getMinorIdealCache_Int (const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
ideal | getMinorIdealCache_Poly (const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
ideal | getMinorIdealCache_toBeDone (const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
ideal | getMinorIdealCache (const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
| Returns the specified set of minors (= subdeterminantes) of the given matrix.
ideal | getMinorIdealHeuristic (const matrix mat, const int minorSize, const int k, const ideal iSB, const bool allDifferent)
| Returns the specified set of minors (= subdeterminantes) of the given matrix.

## Function Documentation

## arrayIsNumberArray()

bool arrayIsNumberArray | ( | const poly * | polyArray,
|  | const ideal | iSB,
|  | const int | length,
|  | int * | intArray,
|  | poly * | nfPolyArray,
|  | int & | zeroCounter )

Definition at line 29 of file MinorInterface.cc.

{
int n = 0; if (currRing != 0) n = currRing->N;
zeroCounter = 0;
bool result = true;
for (int i = 0; i < length; i++)
{
nfPolyArray[i] = pCopy(polyArray[i]);
if (iSB != NULL)
{
poly tmp = kNF(iSB, currRing->qideal, nfPolyArray[i]);
pDelete(&nfPolyArray[i]);
nfPolyArray[i]=tmp;
}
if (nfPolyArray[i] == NULL)
{
intArray[i] = 0;
zeroCounter++;
}
else
{
bool isConstant = true;
for (int j = 1; j <= n; j++)
if (pGetExp(nfPolyArray[i], j) > 0)
isConstant = false;
if (!isConstant) result = false;
else
{
intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing->cf);
if (intArray[i] == 0) zeroCounter++;
}
}
}
return result;
}
i
int i
Definition cfEzgcd.cc:132
n_Int
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ....
Definition coeffs.h:550
result
return result
Definition facAbsBiFact.cc:76
j
int j
Definition facHensel.cc:110
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3229
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
NULL
#define NULL
Definition omList.c:12
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pGetExp
#define pGetExp(p, i)
Exponent.
Definition polys.h:42
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186

## getMinorIdeal()

ideal getMinorIdeal | ( | const matrix | m,
|  | const int | minorSize,
|  | const int | k,
|  | const char * | algorithm,
|  | const ideal | i,
|  | const bool | allDifferent )

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
algorithm must be one of "Bareiss" and "Laplace".
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters

  m | the matrix from which to compute minors
  minorSize | the size of the minors to be computed
  k | the number of minors to be computed
  algorithm | the algorithm to be used for the computation
  i | NULL or an ideal which encodes a standard basis
  allDifferent | if true each minor is considered only once

Returns
  the ideal which has as generators the specified set of minors

Definition at line 238 of file MinorInterface.cc.

{
/* Note that this method should be replaced by getMinorIdeal_toBeDone,
to enable faster computations in the case of matrices which contain
only numbers. But so far, this method is not yet usable as it replaces
the numbers by ints which may result in overflows during computations
of minors. */
int rowCount = mat->nrows;
int columnCount = mat->ncols;
poly* myPolyMatrix = (poly*)(mat->m);
int length = rowCount * columnCount;
ideal iii; /* the ideal to be filled and returned */
if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
&& (!rField_is_Ring(currRing)) && (!allDifferent))
{
/* In this case, we call an optimized procedure, dating back to
Wilfried Pohl. It may be used whenever
- all minors are requested,
- requested minors need not be mutually distinct, and
- coefficients come from a field (i.e., the ring Z is not
allowed for this implementation). */
iii = (iSB == NULL ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
iSB));
}
else
{
/* copy all polynomials and reduce them w.r.t. iSB
(if iSB is present, i.e., not the NULL pointer) */
poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
if (iSB != NULL)
{
for (int i = 0; i < length; i++)
{
nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
}
}
else
{
for (int i = 0; i < length; i++)
{
nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
}
}
iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
k, algorithm, iSB, allDifferent);
/* clean up */
for (int j = length-1; j>=0; j--) pDelete(&nfPolyMatrix[j]);
omFree(nfPolyMatrix);
}
return iii;
}
getMinorIdeal_Poly
ideal getMinorIdeal_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
Definition MinorInterface.cc:129
k
int k
Definition cfEzgcd.cc:99
ip_smatrix::nrows
int nrows
Definition matpol.h:20
ip_smatrix::ncols
int ncols
Definition matpol.h:21
ip_smatrix::m
poly * m
Definition matpol.h:18
idMinors
ideal idMinors(matrix a, int ar, ideal R)
compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R ...
Definition ideals.cc:2031
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491

## getMinorIdeal_Int()

ideal getMinorIdeal_Int | ( | const int * | intMatrix,
|  | const int | rowCount,
|  | const int | columnCount,
|  | const int | minorSize,
|  | const int | k,
|  | const char * | algorithm,
|  | const ideal | i,
|  | const bool | allDifferent )

Definition at line 74 of file MinorInterface.cc.

{
/* setting up a MinorProcessor for matrices with integer entries: */
IntMinorProcessor mp;
mp.defineMatrix(rowCount, columnCount, intMatrix);
int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
mp.setMinorSize(minorSize);
/* containers for all upcoming results: */
IntMinorValue theMinor;
// int value = 0;
int collectedMinors = 0;
int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
/* the ideal to be returned: */
ideal iii = idInit(1);
bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
omitting zero minors */
bool duplicatesOk = (allDifferent ? false : true);
int kk = ABS(k); /* absolute value of k */
/* looping over all minors: */
while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
{
/* retrieving the next minor: */
theMinor = mp.getNextMinor(characteristic, i, algorithm);
poly f = NULL;
if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
collectedMinors++;
}
/* before we return the result, let's omit zero generators
in iii which come after the computed minors */
ideal jjj;
if (collectedMinors == 0) jjj = idInit(1);
else jjj = idCopyFirstK(iii, collectedMinors);
idDelete(&iii);
omFree(myColumnIndices);
omFree(myRowIndices);
return jjj;
}
ABS
static int ABS(int v)
Definition auxiliary.h:113
false
return false
Definition cfModGcd.cc:85
f
FILE * f
Definition checklibs.c:9
IntMinorProcessor
Class IntMinorProcessor is derived from class MinorProcessor.
Definition MinorProcessor.h:300
IntMinorProcessor::defineMatrix
void defineMatrix(const int numberOfRows, const int numberOfColumns, const int *matrix)
A method for defining a matrix with integer entries.
Definition MinorProcessor.cc:350
IntMinorProcessor::getNextMinor
IntMinorValue getNextMinor(const int characteristic, const ideal &iSB, const char *algorithm)
A method for obtaining the next minor when iterating through all minors of a given size within a pre-...
Definition MinorProcessor.cc:409
IntMinorValue
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition Minor.h:718
IntMinorValue::getResult
int getResult() const
Accessor for the private field _result.
Definition Minor.cc:1019
MinorProcessor::setMinorSize
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
Definition MinorProcessor.cc:108
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::hasNextMinor
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
Definition MinorProcessor.cc:114
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
idInsertPolyWithTests
BOOLEAN idInsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
Definition ideals.h:75
idCopyFirstK
static ideal idCopyFirstK(const ideal ide, const int k)
Definition ideals.h:20
pISet
#define pISet(i)
Definition polys.h:313
rChar
int rChar(ring r)
Definition ring.cc:719
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35

## getMinorIdeal_Poly()

ideal getMinorIdeal_Poly | ( | const poly * | polyMatrix,
|  | const int | rowCount,
|  | const int | columnCount,
|  | const int | minorSize,
|  | const int | k,
|  | const char * | algorithm,
|  | const ideal | i,
|  | const bool | allDifferent )

Definition at line 129 of file MinorInterface.cc.

{
/* setting up a MinorProcessor for matrices with polynomial entries: */
PolyMinorProcessor mp;
mp.defineMatrix(rowCount, columnCount, polyMatrix);
int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
mp.setMinorSize(minorSize);
/* containers for all upcoming results: */
PolyMinorValue theMinor;
poly f = NULL;
int collectedMinors = 0;
/* the ideal to be returned: */
ideal iii = idInit(1);
bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
requested, omitting zero minors */
bool duplicatesOk = (allDifferent ? false : true);
int kk = ABS(k); /* absolute value of k */
#ifdef COUNT_AND_PRINT_OPERATIONS
printCounters ("starting", true);
int qqq = 0;
#endif
/* looping over all minors: */
while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
{
/* retrieving the next minor: */
theMinor = mp.getNextMinor(algorithm, i);
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
qqq++;
Print("after %d", qqq);
printCounters ("-th minor", false);
#endif
f = theMinor.getResult();
if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
zeroOk, duplicatesOk))
collectedMinors++;
}
#ifdef COUNT_AND_PRINT_OPERATIONS
printCounters ("ending", true);
#endif
/* before we return the result, let's omit zero generators
in iii which come after the computed minors */
idKeepFirstK(iii, collectedMinors);
omFree(myColumnIndices);
omFree(myRowIndices);
return(iii);
}
printCounters
void printCounters(char *prefix, bool resetToZero)
PolyMinorProcessor
Class PolyMinorProcessor is derived from class MinorProcessor.
Definition MinorProcessor.h:561
PolyMinorProcessor::getNextMinor
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-...
Definition MinorProcessor.cc:928
PolyMinorProcessor::defineMatrix
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
Definition MinorProcessor.cc:872
PolyMinorValue
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition Minor.h:800
PolyMinorValue::getResult
poly getResult() const
Accessor for the private field _result.
Definition Minor.cc:1102
Print
#define Print
Definition emacs.cc:80
idKeepFirstK
void idKeepFirstK(ideal id, const int k)
keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero....
Definition ideals.cc:3179

## getMinorIdeal_toBeDone()

ideal getMinorIdeal_toBeDone | ( | const matrix | mat,
|  | const int | minorSize,
|  | const int | k,
|  | const char * | algorithm,
|  | const ideal | i,
|  | const bool | allDifferent )

Definition at line 187 of file MinorInterface.cc.

{
int rowCount = mat->nrows;
int columnCount = mat->ncols;
poly* myPolyMatrix = (poly*)(mat->m);
ideal iii; /* the ideal to be filled and returned */
int zz = 0;
/* divert to special implementations for pure number matrices and actual
polynomial matrices: */
int* myIntMatrix = (int*)omAlloc(rowCount * columnCount *sizeof(int));
poly* nfPolyMatrix = (poly*)omAlloc(rowCount * columnCount *sizeof(poly));
if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount,
myIntMatrix, nfPolyMatrix, zz))
iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k,
algorithm, i, allDifferent);
else
{
if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
&& (!rField_is_Z(currRing)) && (!allDifferent))
{
/* In this case, we call an optimized procedure, dating back to
Wilfried Pohl. It may be used whenever
- all minors are requested,
- requested minors need not be mutually distinct, and
- coefficients come from a field (i.e., Z is also not allowed
for this implementation). */
iii = (i == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize, i));
}
else
{
iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
k, algorithm, i, allDifferent);
}
}
/* clean up */
omFree(myIntMatrix);
for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
omFree(nfPolyMatrix);
return iii;
}
getMinorIdeal_Int
ideal getMinorIdeal_Int(const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
Definition MinorInterface.cc:74
arrayIsNumberArray
bool arrayIsNumberArray(const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
Definition MinorInterface.cc:29
rField_is_Z
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515

## getMinorIdealCache()

ideal getMinorIdealCache | ( | const matrix | m,
|  | const int | minorSize,
|  | const int | k,
|  | const ideal | i,
|  | const int | cacheStrategy,
|  | const int | cacheN,
|  | const int | cacheW,
|  | const bool | allDifferent )

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
The underlying algorithm is Laplace's algorithm with caching of certain subdeterminantes. The caching strategy can be set; see int MinorValue::getUtility () const in Minor.cc. cacheN is the maximum number of cached polynomials (=subdeterminantes); cacheW the maximum weight of the cache during all computations.
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters

  m | the matrix from which to compute minors
  minorSize | the size of the minors to be computed
  k | the number of minors to be computed
  i | NULL or an ideal which encodes a standard basis
  cacheStrategy | one of {1, .., 5}; see Minor.cc
  cacheN | maximum number of cached polynomials (=subdeterminantes)
  cacheW | maximum weight of the cache
  allDifferent | if true each minor is considered only once

Returns
  the ideal which has as generators the specified set of minors

Definition at line 457 of file MinorInterface.cc.

{
/* Note that this method should be replaced by getMinorIdealCache_toBeDone,
to enable faster computations in the case of matrices which contain
only numbers. But so far, this method is not yet usable as it replaces
the numbers by ints which may result in overflows during computations
of minors. */
int rowCount = mat->nrows;
int columnCount = mat->ncols;
poly* myPolyMatrix = (poly*)(mat->m);
int length = rowCount * columnCount;
poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
ideal iii; /* the ideal to be filled and returned */
/* copy all polynomials and reduce them w.r.t. iSB
(if iSB is present, i.e., not the NULL pointer) */
for (int i = 0; i < length; i++)
{
if (iSB==NULL)
nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
else
nfPolyMatrix[i] = kNF(iSB, currRing->qideal, myPolyMatrix[i]);
}
iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
minorSize, k, iSB, cacheStrategy,
cacheN, cacheW, allDifferent);
/* clean up */
for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
omFree(nfPolyMatrix);
return iii;
}
getMinorIdealCache_Poly
ideal getMinorIdealCache_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
Definition MinorInterface.cc:360

## getMinorIdealCache_Int()

ideal getMinorIdealCache_Int | ( | const int * | intMatrix,
|  | const int | rowCount,
|  | const int | columnCount,
|  | const int | minorSize,
|  | const int | k,
|  | const ideal | i,
|  | const int | cacheStrategy,
|  | const int | cacheN,
|  | const int | cacheW,
|  | const bool | allDifferent )

Definition at line 302 of file MinorInterface.cc.

{
/* setting up a MinorProcessor for matrices with integer entries: */
IntMinorProcessor mp;
mp.defineMatrix(rowCount, columnCount, intMatrix);
int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
mp.setMinorSize(minorSize);
MinorValue::SetRankingStrategy(cacheStrategy);
Cache<MinorKey, IntMinorValue> cch(cacheN, cacheW);
/* containers for all upcoming results: */
IntMinorValue theMinor;
// int value = 0;
int collectedMinors = 0;
int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
/* the ideal to be returned: */
ideal iii = idInit(1);
bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
requested, omitting zero minors */
bool duplicatesOk = (allDifferent ? false : true);
int kk = ABS(k); /* absolute value of k */
/* looping over all minors: */
while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
{
/* retrieving the next minor: */
theMinor = mp.getNextMinor(cch, characteristic, i);
poly f = NULL;
if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
collectedMinors++;
}
/* before we return the result, let's omit zero generators
in iii which come after the computed minors */
ideal jjj;
if (collectedMinors == 0) jjj = idInit(1);
else jjj = idCopyFirstK(iii, collectedMinors);
idDelete(&iii);
omFree(myColumnIndices);
omFree(myRowIndices);
return jjj;
}
Cache
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition Cache.h:69
MinorValue::SetRankingStrategy
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition Minor.cc:909

## getMinorIdealCache_Poly()

ideal getMinorIdealCache_Poly | ( | const poly * | polyMatrix,
|  | const int | rowCount,
|  | const int | columnCount,
|  | const int | minorSize,
|  | const int | k,
|  | const ideal | i,
|  | const int | cacheStrategy,
|  | const int | cacheN,
|  | const int | cacheW,
|  | const bool | allDifferent )

Definition at line 360 of file MinorInterface.cc.

{
/* setting up a MinorProcessor for matrices with polynomial entries: */
PolyMinorProcessor mp;
mp.defineMatrix(rowCount, columnCount, polyMatrix);
int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
mp.setMinorSize(minorSize);
MinorValue::SetRankingStrategy(cacheStrategy);
Cache<MinorKey, PolyMinorValue> cch(cacheN, cacheW);
/* containers for all upcoming results: */
PolyMinorValue theMinor;
poly f = NULL;
int collectedMinors = 0;
/* the ideal to be returned: */
ideal iii = idInit(1);
bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
requested, omitting zero minors */
bool duplicatesOk = (allDifferent ? false : true);
int kk = ABS(k); /* absolute value of k */
#ifdef COUNT_AND_PRINT_OPERATIONS
printCounters ("starting", true);
int qqq = 0;
#endif
/* looping over all minors: */
while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
{
/* retrieving the next minor: */
theMinor = mp.getNextMinor(cch, i);
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
qqq++;
Print("after %d", qqq);
printCounters ("-th minor", false);
#endif
f = theMinor.getResult();
if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
duplicatesOk))
collectedMinors++;
}
#ifdef COUNT_AND_PRINT_OPERATIONS
printCounters ("ending", true);
#endif
/* before we return the result, let's omit zero generators
in iii which come after the computed minors */
ideal jjj;
if (collectedMinors == 0) jjj = idInit(1);
else jjj = idCopyFirstK(iii, collectedMinors);
idDelete(&iii);
omFree(myColumnIndices);
omFree(myRowIndices);
return jjj;
}

## getMinorIdealCache_toBeDone()

ideal getMinorIdealCache_toBeDone | ( | const matrix | mat,
|  | const int | minorSize,
|  | const int | k,
|  | const ideal | iSB,
|  | const int | cacheStrategy,
|  | const int | cacheN,
|  | const int | cacheW,
|  | const bool | allDifferent )

Definition at line 424 of file MinorInterface.cc.

{
int rowCount = mat->nrows;
int columnCount = mat->ncols;
poly* myPolyMatrix = (poly*)(mat->m);
ideal iii; /* the ideal to be filled and returned */
int zz = 0;
/* divert to special implementation when myPolyMatrix has only number
entries: */
int* myIntMatrix = (int*)omAlloc(rowCount * columnCount *sizeof(int));
poly* nfPolyMatrix = (poly*)omAlloc(rowCount * columnCount *sizeof(poly));
if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount,
myIntMatrix, nfPolyMatrix, zz))
iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount,
minorSize, k, iSB, cacheStrategy, cacheN,
cacheW, allDifferent);
else
iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
minorSize, k, iSB, cacheStrategy, cacheN,
cacheW, allDifferent);
/* clean up */
omFree(myIntMatrix);
for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
omFree(nfPolyMatrix);
return iii;
}
getMinorIdealCache_Int
ideal getMinorIdealCache_Int(const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
Definition MinorInterface.cc:302

## getMinorIdealHeuristic()

ideal getMinorIdealHeuristic | ( | const matrix | m,
|  | const int | minorSize,
|  | const int | k,
|  | const ideal | i,
|  | const bool | allDifferent )

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
The algorithm is heuristically chosen among "Bareiss", "Laplace", and Laplace with caching (of subdeterminants).
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters

  m | the matrix from which to compute minors
  minorSize | the size of the minors to be computed
  k | the number of minors to be computed
  i | NULL or an ideal which encodes a standard basis
  allDifferent | if true each minor is considered only once

Returns
  the ideal which has as generators the specified set of minors

Definition at line 495 of file MinorInterface.cc.

{
int vars = currRing->N;
/* here comes the heuristic, as of 29 January 2010:
integral domain and minorSize <= 2 -> Bareiss
integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
field case and minorSize >= 3 and vars = 3
and c in {2, 3, ..., 32749} -> Bareiss
otherwise:
if not all minors are requested -> Laplace, no Caching
otherwise:
minorSize >= 3 and vars <= 4 and
(rowCount over minorSize)*(columnCount over minorSize) >= 100
-> Laplace with Caching
minorSize >= 3 and vars >= 5 and
(rowCount over minorSize)*(columnCount over minorSize) >= 40
-> Laplace with Caching
otherwise: -> Laplace, no Caching
*/
bool b = false; /* Bareiss */
bool l = false; /* Laplace without caching */
// bool c = false; /* Laplace with caching */
if (rField_is_Domain(currRing))
{ /* the field case or ring Z */
if (minorSize <= 2) b = true;
else if (vars <= 2) b = true;
else if ((!rField_is_Ring(currRing)) && (vars == 3)
&& (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
b = true;
}
if (!b)
{ /* the non-Bareiss cases */
if (k != 0) /* this means, not all minors are requested */ l = true;
else
{ /* k == 0, i.e., all minors are requested */
l = true;
}
}
if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
allDifferent);
else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
allDifferent);
else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
3, 200, 100000, allDifferent);
}
getMinorIdealCache
ideal getMinorIdealCache(const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
Returns the specified set of minors (= subdeterminantes) of the given matrix.
Definition MinorInterface.cc:457
getMinorIdeal
ideal getMinorIdeal(const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal iSB, const bool allDifferent)
Returns the specified set of minors (= subdeterminantes) of the given matrix.
Definition MinorInterface.cc:238
l
int l
Definition cfEzgcd.cc:100
b
CanonicalForm b
Definition cfModGcd.cc:4111
NV_MAX_PRIME
#define NV_MAX_PRIME
Definition modulop.h:37
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493