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 238 of file MinorInterface.cc.

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

◆ 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 457 of file MinorInterface.cc.

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

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