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

m	the matrix from which to compute minors
minorSize	the size of the minors to be computed
k	the number of minors to be computed
algorithm	the algorithm to be used for the computation
i	NULL or an ideal which encodes a standard basis
allDifferent	if 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.

{
  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
     to enable faster computations in the case of matrices which contain
     only numbers. But so far, this method is not yet usable as it replaces
     the numbers by ints which may result in overflows during computations
     of minors. */
  int rowCount = mat->nrows;
  int columnCount = mat->ncols;
  poly* myPolyMatrix = (poly*)(mat->m);
  int length = rowCount * columnCount;
  ideal iii; /* the ideal to be filled and returned */
 
  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
      && (!rField_is_Ring(currRing)) && (!allDifferent))
  {
    /* In this case, we call an optimized procedure, dating back to
       Wilfried Pohl. It may be used whenever
       - all minors are requested,
       - requested minors need not be mutually distinct, and
       - coefficients come from a field (i.e., the ring Z is not
         allowed for this implementation). */
    iii = (iSB == NULL ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
                                                          iSB));
  }
  else
  {
  /* copy all polynomials and reduce them w.r.t. iSB
     (if iSB is present, i.e., not the NULL pointer) */
 
    poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
    if (iSB != NULL)
    {
      for (int i = 0; i < length; i++)
      {
        nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
      }
    }
    else
    {
      for (int i = 0; i < length; i++)
      {
        nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
      }
    }
    iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
                             k, algorithm, iSB, allDifferent);
 
    /* clean up */
    for (int j = length-1; j>=0; j--) pDelete(&nfPolyMatrix[j]);
    omFree(nfPolyMatrix);
  }
 
  return iii;
}

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

m	the matrix from which to compute minors
minorSize	the size of the minors to be computed
k	the number of minors to be computed
i	NULL or an ideal which encodes a standard basis
cacheStrategy	one of {1, .., 5}; see Minor.cc
cacheN	maximum number of cached polynomials (=subdeterminantes)
cacheW	maximum weight of the cache
allDifferent	if 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.

{
  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
     to enable faster computations in the case of matrices which contain
     only numbers. But so far, this method is not yet usable as it replaces
     the numbers by ints which may result in overflows during computations
     of minors. */
  int rowCount = mat->nrows;
  int columnCount = mat->ncols;
  poly* myPolyMatrix = (poly*)(mat->m);
  int length = rowCount * columnCount;
  poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
  ideal iii; /* the ideal to be filled and returned */
 
  /* copy all polynomials and reduce them w.r.t. iSB
     (if iSB is present, i.e., not the NULL pointer) */
  for (int i = 0; i < length; i++)
  {
    if (iSB==NULL)
      nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
    else
      nfPolyMatrix[i] = kNF(iSB, currRing->qideal, myPolyMatrix[i]);
  }
 
  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
                                minorSize, k, iSB, cacheStrategy,
                                cacheN, cacheW, allDifferent);
 
  /* clean up */
  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
  omFree(nfPolyMatrix);
 
  return iii;
}

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

m	the matrix from which to compute minors
minorSize	the size of the minors to be computed
k	the number of minors to be computed
i	NULL or an ideal which encodes a standard basis
allDifferent	if 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.

{
  int vars = currRing->N;
 
  /* here comes the heuristic, as of 29 January 2010:
 
     integral domain and minorSize <= 2                -> Bareiss
     integral domain and minorSize >= 3 and vars <= 2  -> Bareiss
     field case and minorSize >= 3 and vars = 3
       and c in {2, 3, ..., 32749}                     -> Bareiss
 
     otherwise:
     if not all minors are requested                   -> Laplace, no Caching
     otherwise:
     minorSize >= 3 and vars <= 4 and
       (rowCount over minorSize)*(columnCount over minorSize) >= 100
                                                       -> Laplace with Caching
     minorSize >= 3 and vars >= 5 and
       (rowCount over minorSize)*(columnCount over minorSize) >= 40
                                                       -> Laplace with Caching
 
     otherwise:                                        -> Laplace, no Caching
  */
 
  bool b = false; /* Bareiss */
  bool l = false; /* Laplace without caching */
  // bool c = false; /* Laplace with caching */
  if (rField_is_Domain(currRing))
  { /* the field case or ring Z */
    if      (minorSize <= 2)                                     b = true;
    else if (vars <= 2)                                          b = true;
    else if ((!rField_is_Ring(currRing)) && (vars == 3)
             && (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
          b = true;
  }
  if (!b)
  { /* the non-Bareiss cases */
    if (k != 0) /* this means, not all minors are requested */   l = true;
    else
    { /* k == 0, i.e., all minors are requested */
      l = true;
    }
  }
 
  if      (b)    return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
                                      allDifferent);
  else if (l)    return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
                                      allDifferent);
  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
                                      3, 200, 100000, allDifferent);
}