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

typedef ip_smatrix* matrix

Definition at line 10 of file MinorInterface.h.

typedef polyrec* poly

Definition at line 5 of file MinorInterface.h.

Function Documentation

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

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

466 {
467  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
468  to enable faster computations in the case of matrices which contain
469  only numbers. But so far, this method is not yet usable as it replaces
470  the numbers by ints which may result in overflows during computations
471  of minors. */
472  int rowCount = mat->nrows;
473  int columnCount = mat->ncols;
474  poly* myPolyMatrix = (poly*)(mat->m);
475  int length = rowCount * columnCount;
476  poly* nfPolyMatrix = new poly[length];
477  ideal iii; /* the ideal to be filled and returned */
478 
479  /* copy all polynomials and reduce them w.r.t. iSB
480  (if iSB is present, i.e., not the NULL pointer) */
481  for (int i = 0; i < length; i++)
482  {
483  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
484  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
485  nfPolyMatrix[i]);
486  }
487 
488  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
489  minorSize, k, iSB, cacheStrategy,
490  cacheN, cacheW, allDifferent);
491 
492  /* clean up */
493  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
494  delete [] nfPolyMatrix;
495 
496  return iii;
497 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
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:12
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:157
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
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 499 of file MinorInterface.cc.

502 {
503  int vars = 0; if (currRing != 0) vars = currRing->N;
504  int rowCount = mat->nrows;
505  int columnCount = mat->ncols;
506 
507  /* here comes the heuristic, as of 29 January 2010:
508 
509  integral domain and minorSize <= 2 -> Bareiss
510  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
511  field case and minorSize >= 3 and vars = 3
512  and c in {2, 3, ..., 32003} -> Bareiss
513 
514  otherwise:
515  if not all minors are requested -> Laplace, no Caching
516  otherwise:
517  minorSize >= 3 and vars <= 4 and
518  (rowCount over minorSize)*(columnCount over minorSize) >= 100
519  -> Laplace with Caching
520  minorSize >= 3 and vars >= 5 and
521  (rowCount over minorSize)*(columnCount over minorSize) >= 40
522  -> Laplace with Caching
523 
524  otherwise: -> Laplace, no Caching
525  */
526 
527  bool b = false; /* Bareiss */
528  bool l = false; /* Laplace without caching */
529  // bool c = false; /* Laplace with caching */
531  { /* the field case or ring Z */
532  if (minorSize <= 2) b = true;
533  else if (vars <= 2) b = true;
534  else if (currRingIsOverField() && (vars == 3)
535  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= 32003))
536  b = true;
537  }
538  if (!b)
539  { /* the non-Bareiss cases */
540  if (k != 0) /* this means, not all minors are requested */ l = true;
541  else
542  { /* k == 0, i.e., all minors are requested */
543  int minorCount = binom(rowCount, minorSize);
544  minorCount *= binom(columnCount, minorSize);
545  // if ((minorSize >= 3) && (vars <= 4)
546  // && (minorCount >= 100)) c = true;
547  // else if ((minorSize >= 3) && (vars >= 5)
548  // && (minorCount >= 40)) c = true;
549  /*else*/ l = true;
550  }
551  }
552 
553  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
554  allDifferent);
555  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
556  allDifferent);
557  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
558  3, 200, 100000, allDifferent);
559 }
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:12
bool currRingIsOverField()
const poly b
Definition: syzextra.cc:213
int binom(int n, int r)
int l
Definition: cfEzgcd.cc:94