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  for (int i = 0; i < length; i++)
271  {
272  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
273  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
274  nfPolyMatrix[i]);
275  }
276 
277  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
278  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
279  {
280  /* In this case, we call an optimized procedure, dating back to
281  Wilfried Pohl. It may be used whenever
282  - all minors are requested,
283  - requested minors need not be mutually distinct, and
284  - coefficients come from a field (i.e., the ring Z is not
285  allowed for this implementation). */
286  iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
287  iSB));
288  }
289  else
290  {
291  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
292  k, algorithm, iSB, allDifferent);
293  }
294 
295  /* clean up */
296  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
297  delete [] nfPolyMatrix;
298 
299  return iii;
300 }
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:1744
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: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 463 of file MinorInterface.cc.

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

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