My Project
Functions
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. More...
 
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. More...
 
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. More...
 

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
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
algorithmthe algorithm to be used for the computation
iNULL or an ideal which encodes a standard basis
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 240 of file MinorInterface.cc.

243 {
244  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
245  to enable faster computations in the case of matrices which contain
246  only numbers. But so far, this method is not yet usable as it replaces
247  the numbers by ints which may result in overflows during computations
248  of minors. */
249  int rowCount = mat->nrows;
250  int columnCount = mat->ncols;
251  poly* myPolyMatrix = (poly*)(mat->m);
252  int length = rowCount * columnCount;
253  ideal iii; /* the ideal to be filled and returned */
254 
255  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
256  && (!rField_is_Ring(currRing)) && (!allDifferent))
257  {
258  /* In this case, we call an optimized procedure, dating back to
259  Wilfried Pohl. It may be used whenever
260  - all minors are requested,
261  - requested minors need not be mutually distinct, and
262  - coefficients come from a field (i.e., the ring Z is not
263  allowed for this implementation). */
264  iii = (iSB == NULL ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
265  iSB));
266  }
267  else
268  {
269  /* copy all polynomials and reduce them w.r.t. iSB
270  (if iSB is present, i.e., not the NULL pointer) */
271 
272  poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
273  if (iSB != NULL)
274  {
275  for (int i = 0; i < length; i++)
276  {
277  nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
278  }
279  }
280  else
281  {
282  for (int i = 0; i < length; i++)
283  {
284  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
285  }
286  }
287  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
288  k, algorithm, iSB, allDifferent);
289 
290  /* clean up */
291  for (int j = length-1; j>=0; j--) pDelete(&nfPolyMatrix[j]);
292  omFree(nfPolyMatrix);
293  }
294 
295  return iii;
296 }
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)
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int j
Definition: facHensel.cc:110
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:1964
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3158
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:12
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pDelete(p_ptr)
Definition: polys.h:186
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:489

◆ 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
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
iNULL or an ideal which encodes a standard basis
cacheStrategyone of {1, .., 5}; see Minor.cc
cacheNmaximum number of cached polynomials (=subdeterminantes)
cacheWmaximum weight of the cache
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 459 of file MinorInterface.cc.

463 {
464  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
465  to enable faster computations in the case of matrices which contain
466  only numbers. But so far, this method is not yet usable as it replaces
467  the numbers by ints which may result in overflows during computations
468  of minors. */
469  int rowCount = mat->nrows;
470  int columnCount = mat->ncols;
471  poly* myPolyMatrix = (poly*)(mat->m);
472  int length = rowCount * columnCount;
473  poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
474  ideal iii; /* the ideal to be filled and returned */
475 
476  /* copy all polynomials and reduce them w.r.t. iSB
477  (if iSB is present, i.e., not the NULL pointer) */
478  for (int i = 0; i < length; i++)
479  {
480  if (iSB==NULL)
481  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
482  else
483  nfPolyMatrix[i] = kNF(iSB, currRing->qideal, myPolyMatrix[i]);
484  }
485 
486  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
487  minorSize, k, iSB, cacheStrategy,
488  cacheN, cacheW, allDifferent);
489 
490  /* clean up */
491  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
492  omFree(nfPolyMatrix);
493 
494  return iii;
495 }
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)

◆ 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
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
iNULL or an ideal which encodes a standard basis
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 497 of file MinorInterface.cc.

500 {
501  int vars = currRing->N;
502 
503  /* here comes the heuristic, as of 29 January 2010:
504 
505  integral domain and minorSize <= 2 -> Bareiss
506  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
507  field case and minorSize >= 3 and vars = 3
508  and c in {2, 3, ..., 32749} -> Bareiss
509 
510  otherwise:
511  if not all minors are requested -> Laplace, no Caching
512  otherwise:
513  minorSize >= 3 and vars <= 4 and
514  (rowCount over minorSize)*(columnCount over minorSize) >= 100
515  -> Laplace with Caching
516  minorSize >= 3 and vars >= 5 and
517  (rowCount over minorSize)*(columnCount over minorSize) >= 40
518  -> Laplace with Caching
519 
520  otherwise: -> Laplace, no Caching
521  */
522 
523  bool b = false; /* Bareiss */
524  bool l = false; /* Laplace without caching */
525  // bool c = false; /* Laplace with caching */
527  { /* the field case or ring Z */
528  if (minorSize <= 2) b = true;
529  else if (vars <= 2) b = true;
530  else if ((!rField_is_Ring(currRing)) && (vars == 3)
531  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
532  b = true;
533  }
534  if (!b)
535  { /* the non-Bareiss cases */
536  if (k != 0) /* this means, not all minors are requested */ l = true;
537  else
538  { /* k == 0, i.e., all minors are requested */
539  l = true;
540  }
541  }
542 
543  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
544  allDifferent);
545  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
546  allDifferent);
547  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
548  3, 200, 100000, allDifferent);
549 }
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 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.
int l
Definition: cfEzgcd.cc:100
CanonicalForm b
Definition: cfModGcd.cc:4105
#define NV_MAX_PRIME
Definition: modulop.h:29
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:492