Typedefs | Functions
MinorInterface.h File Reference

Go to the source code of this file.

Typedefs

typedef polyrec * poly
 
typedef ip_smatrixmatrix
 

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

Typedef Documentation

◆ matrix

typedef ip_smatrix* matrix

Definition at line 10 of file MinorInterface.h.

◆ poly

typedef polyrec* poly

Definition at line 5 of file MinorInterface.h.

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

255 {
256  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
257  to enable faster computations in the case of matrices which contain
258  only numbers. But so far, this method is not yet usable as it replaces
259  the numbers by ints which may result in overflows during computations
260  of minors. */
261  int rowCount = mat->nrows;
262  int columnCount = mat->ncols;
263  poly* myPolyMatrix = (poly*)(mat->m);
264  int length = rowCount * columnCount;
265  poly* nfPolyMatrix = new poly[length];
266  ideal iii; /* the ideal to be filled and returned */
267 
268  /* copy all polynomials and reduce them w.r.t. iSB
269  (if iSB is present, i.e., not the NULL pointer) */
270  if (iSB != NULL)
271  {
272  for (int i = 0; i < length; i++)
273  {
274  nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
275  }
276  }
277  else
278  {
279  for (int i = 0; i < length; i++)
280  {
281  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
282  }
283  }
284 
285  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
286  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
287  {
288  /* In this case, we call an optimized procedure, dating back to
289  Wilfried Pohl. It may be used whenever
290  - all minors are requested,
291  - requested minors need not be mutually distinct, and
292  - coefficients come from a field (i.e., the ring Z is not
293  allowed for this implementation). */
294  iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
295  iSB));
296  }
297  else
298  {
299  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
300  k, algorithm, iSB, allDifferent);
301  }
302 
303  /* clean up */
304  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
305  delete [] nfPolyMatrix;
306 
307  return iii;
308 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
int j
Definition: myNF.cc:70
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:1745
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
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)
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:474
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168

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

475 {
476  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
477  to enable faster computations in the case of matrices which contain
478  only numbers. But so far, this method is not yet usable as it replaces
479  the numbers by ints which may result in overflows during computations
480  of minors. */
481  int rowCount = mat->nrows;
482  int columnCount = mat->ncols;
483  poly* myPolyMatrix = (poly*)(mat->m);
484  int length = rowCount * columnCount;
485  poly* nfPolyMatrix = new poly[length];
486  ideal iii; /* the ideal to be filled and returned */
487 
488  /* copy all polynomials and reduce them w.r.t. iSB
489  (if iSB is present, i.e., not the NULL pointer) */
490  for (int i = 0; i < length; i++)
491  {
492  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
493  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
494  nfPolyMatrix[i]);
495  }
496 
497  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
498  minorSize, k, iSB, cacheStrategy,
499  cacheN, cacheW, allDifferent);
500 
501  /* clean up */
502  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
503  delete [] nfPolyMatrix;
504 
505  return iii;
506 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
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)
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168

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

511 {
512  int vars = 0; if (currRing != 0) vars = currRing->N;
513  int rowCount = mat->nrows;
514  int columnCount = mat->ncols;
515 
516  /* here comes the heuristic, as of 29 January 2010:
517 
518  integral domain and minorSize <= 2 -> Bareiss
519  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
520  field case and minorSize >= 3 and vars = 3
521  and c in {2, 3, ..., 32749} -> Bareiss
522 
523  otherwise:
524  if not all minors are requested -> Laplace, no Caching
525  otherwise:
526  minorSize >= 3 and vars <= 4 and
527  (rowCount over minorSize)*(columnCount over minorSize) >= 100
528  -> Laplace with Caching
529  minorSize >= 3 and vars >= 5 and
530  (rowCount over minorSize)*(columnCount over minorSize) >= 40
531  -> Laplace with Caching
532 
533  otherwise: -> Laplace, no Caching
534  */
535 
536  bool b = false; /* Bareiss */
537  bool l = false; /* Laplace without caching */
538  // bool c = false; /* Laplace with caching */
540  { /* the field case or ring Z */
541  if (minorSize <= 2) b = true;
542  else if (vars <= 2) b = true;
543  else if (currRingIsOverField() && (vars == 3)
544  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
545  b = true;
546  }
547  if (!b)
548  { /* the non-Bareiss cases */
549  if (k != 0) /* this means, not all minors are requested */ l = true;
550  else
551  { /* k == 0, i.e., all minors are requested */
552  int minorCount = binom(rowCount, minorSize);
553  minorCount *= binom(columnCount, minorSize);
554  // if ((minorSize >= 3) && (vars <= 4)
555  // && (minorCount >= 100)) c = true;
556  // else if ((minorSize >= 3) && (vars >= 5)
557  // && (minorCount >= 40)) c = true;
558  /*else*/ l = true;
559  }
560  }
561 
562  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
563  allDifferent);
564  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
565  allDifferent);
566  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
567  3, 200, 100000, allDifferent);
568 }
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.
bool currRingIsOverIntegralDomain()
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.
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
#define NV_MAX_PRIME
Definition: modulop.h:21
bool currRingIsOverField()
const poly b
Definition: syzextra.cc:213
int binom(int n, int r)
int l
Definition: cfEzgcd.cc:94