Loading...
Searching...
No Matches
MinorInterface.h File Reference
`#include "polys/monomials/ring.h"`
`#include "kernel/polys.h"`

Go to the source code of this file.

## Functions

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

## Function Documentation

## 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
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
j
int j
Definition facHensel.cc:110
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
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
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
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
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491

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

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