Class PolyMinorProcessor is derived from class MinorProcessor. More...

#include <MinorProcessor.h>

Public Member Functions
	PolyMinorProcessor ()
	A constructor for creating an instance. More...

	~PolyMinorProcessor ()
	A destructor for deleting an instance. More...

void	defineMatrix (const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
	A method for defining a matrix with polynomial entries. More...

PolyMinorValue	getMinor (const int dimension, const int rowIndices, const int columnIndices, const char *algorithm, const ideal &iSB)
	A method for computing the value of a minor, without using a cache. More...

PolyMinorValue	getMinor (const int dimension, const int rowIndices, const int columnIndices, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
	A method for computing the value of a minor, using a cache. More...

PolyMinorValue	getNextMinor (const char *algorithm, const ideal &iSB)
	A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...

PolyMinorValue	getNextMinor (Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
	A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...

std::string	toString () const
	A method for providing a printable version of the represented MinorProcessor. More...

Public Member Functions inherited from MinorProcessor
	MinorProcessor ()
	The default constructor. More...

virtual	~MinorProcessor ()
	A destructor for deleting an instance. More...

void	defineSubMatrix (const int numberOfRows, const int rowIndices, const int numberOfColumns, const int columnIndices)
	A method for defining a sub-matrix within a pre-defined matrix. More...

void	setMinorSize (const int minorSize)
	Sets the size of the minor(s) of interest. More...

bool	hasNextMinor ()
	A method for checking whether there is a next choice of rows and columns when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...

void	getCurrentRowIndices (int *const target) const
	A method for obtaining the current set of rows corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...

void	getCurrentColumnIndices (int *const target) const
	A method for obtaining the current set of columns corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...

virtual std::string	toString () const
	A method for providing a printable version of the represented MinorProcessor. More...

void	print () const
	A method for printing a string representation of the given MinorProcessor to std::cout. More...

Protected Member Functions
bool	isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
	A method for testing whether a matrix entry is zero. More...

Protected Member Functions inherited from MinorProcessor
bool	setNextKeys (const int k)
	A method for iterating through all possible subsets of `k` rows and `k` columns inside a pre-defined submatrix of a pre-defined matrix. More...

int	getBestLine (const int k, const MinorKey &mk) const
	A method for identifying the row or column with the most zeros. More...

virtual bool	isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
	A method for testing whether a matrix entry is zero. More...

Private Member Functions
poly	getEntry (const int rowIndex, const int columnIndex) const
	A method for retrieving the matrix entry. More...

PolyMinorValue	getMinorPrivateLaplace (const int k, const MinorKey &mk, const bool multipleMinors, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
	A method for computing the value of a minor, using a cache. More...

PolyMinorValue	getMinorPrivateLaplace (const int k, const MinorKey &mk, const ideal &iSB)
	A method for computing the value of a minor, without using a cache. More...

PolyMinorValue	getMinorPrivateBareiss (const int k, const MinorKey &mk, const ideal &iSB)
	A method for computing the value of a minor, without using a cache. More...

Private Attributes
poly *	_polyMatrix
	private store for polynomial matrix entries More...

Additional Inherited Members
Static Protected Member Functions inherited from MinorProcessor
static int	NumberOfRetrievals (const int rows, const int columns, const int containerMinorSize, const int minorSize, const bool multipleMinors)
	A static method for computing the maximum number of retrievals of a minor. More...

static int	IOverJ (const int i, const int j)
	A static method for computing the binomial coefficient i over j. More...

static int	Faculty (const int i)
	A static method for computing the factorial of i. More...

Protected Attributes inherited from MinorProcessor
MinorKey	_container
	private store for the rows and columns of the container minor within the underlying matrix; `_container` will be used to fix a submatrix (e.g. More...

int	_containerRows
	private store for the number of rows in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int, const int, const int). More...

int	_containerColumns
	private store for the number of columns in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int, const int, const int). More...

MinorKey	_minor
	private store for the rows and columns of the minor of interest; Usually, this minor will encode subsets of the rows and columns in _container. More...

int	_minorSize
	private store for the dimension of the minor(s) of interest More...

int	_rows
	private store for the number of rows in the underlying matrix More...

int	_columns
	private store for the number of columns in the underlying matrix More...

Detailed Description

Class PolyMinorProcessor is derived from class MinorProcessor.

This class implements the special case of polynomial matrices.

Author: Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch

Definition at line 560 of file MinorProcessor.h.

Constructor & Destructor Documentation

◆ PolyMinorProcessor()

PolyMinorProcessor::PolyMinorProcessor ( )

A constructor for creating an instance.

Definition at line 810 of file MinorProcessor.cc.

{
  _polyMatrix = NULL;
}

◆ ~PolyMinorProcessor()

PolyMinorProcessor::~PolyMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 860 of file MinorProcessor.cc.

{
  /* free memory of _polyMatrix */
  int n = _rows * _columns;
  for (int i = 0; i < n; i++)
    p_Delete(&_polyMatrix[i], currRing);
  omfree(_polyMatrix); _polyMatrix = NULL;
}

Member Function Documentation

◆ defineMatrix()

void PolyMinorProcessor::defineMatrix	(	const int	numberOfRows,
		const int	numberOfColumns,
		const poly *	polyMatrix
	)

A method for defining a matrix with polynomial entries.

Parameters

numberOfRows	the number of rows
numberOfColumns	the number of columns
polyMatrix	the matrix entries in a linear array, i.e., from left to right and top to bottom

See also: MinorValue::defineSubMatrix (const int, const int*, const int, const int*)

Definition at line 869 of file MinorProcessor.cc.

{
  /* free memory of _polyMatrix */
  int n = _rows * _columns;
  for (int i = 0; i < n; i++)
    p_Delete(&_polyMatrix[i], currRing);
  omfree(_polyMatrix); _polyMatrix = NULL;
 
  _rows = numberOfRows;
  _columns = numberOfColumns;
  n = _rows * _columns;
 
  /* allocate memory for new entries in _polyMatrix */
  _polyMatrix = (poly*)omAlloc(n*sizeof(poly));
 
  /* copying values from one-dimensional method
     parameter "polyMatrix" */
  for (int i = 0; i < n; i++)
    _polyMatrix[i] = pCopy(polyMatrix[i]);
}

◆ getEntry()

poly PolyMinorProcessor::getEntry	(	const int	rowIndex,
		const int	columnIndex
	)		const

private

A method for retrieving the matrix entry.

Parameters

rowIndex	the absolute (zero-based) row index
columnIndex	the absolute (zero-based) column index

Returns: the specified matrix entry

Definition at line 815 of file MinorProcessor.cc.

{
  return _polyMatrix[rowIndex * _columns + columnIndex];
}

◆ getMinor() [1/2]

PolyMinorValue PolyMinorProcessor::getMinor	(	const int	dimension,
		const int *	rowIndices,
		const int *	columnIndices,
		Cache< MinorKey, PolyMinorValue > &	c,
		const ideal &	iSB
	)

A method for computing the value of a minor, using a cache.

The sub-matrix is determined by rowIndices and columnIndices. Computation works recursively using Laplace's Theorem. We always develop along the row or column with most zeros; see MinorProcessor::getBestLine (const int, const int, const int). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

dimension	the size of the minor to be computed
rowIndices	0-based indices of the rows of the minor
columnIndices	0-based indices of the column of the minor
c	a cache to be used for caching reusable sub-minors
iSB	NULL or a standard basis

Returns: an instance of MinorValue representing the value of the corresponding minor

See also: MinorProcessor::(const int dimension, const int* rowIndices, const int* columnIndices, const char* algorithm, const ideal& iSB)

Definition at line 892 of file MinorProcessor.cc.

{
  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
  _minorSize = dimension;
  /* call a helper method which recursively computes the minor using the cache
     c: */
  return getMinorPrivateLaplace(dimension, _container, false, c, iSB);
}

◆ getMinor() [2/2]

PolyMinorValue PolyMinorProcessor::getMinor	(	const int	dimension,
		const int *	rowIndices,
		const int *	columnIndices,
		const char *	algorithm,
		const ideal &	iSB
	)

A method for computing the value of a minor, without using a cache.

The sub-matrix is determined by rowIndices and columnIndices. Computation works either by Laplace's algorithm or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

dimension	the size of the minor to be computed
rowIndices	0-based indices of the rows of the minor
columnIndices	0-based indices of the column of the minor
algorithm	either "Laplace" or "Bareiss"
iSB	NULL or a standard basis

Returns: an instance of MinorValue representing the value of the corresponding minor

See also: MinorProcessor::getMinor (const int dimension, const int* rowIndices, const int* columnIndices, Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB)

Definition at line 905 of file MinorProcessor.cc.

{
  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
  _minorSize = dimension;
  /* call a helper method which computes the minor (without using a cache): */
  if (strcmp(algorithm, "Laplace") == 0)
    return getMinorPrivateLaplace(_minorSize, _container, iSB);
  else if (strcmp(algorithm, "Bareiss") == 0)
    return getMinorPrivateBareiss(_minorSize, _container, iSB);
  else assume(false);
 
  /* The following code is never reached and just there to make the
     compiler happy: */
  return PolyMinorValue();
}

◆ getMinorPrivateBareiss()

PolyMinorValue PolyMinorProcessor::getMinorPrivateBareiss	(	const int	k,
		const MinorKey &	mk,
		const ideal &	iSB
	)

private

A method for computing the value of a minor, without using a cache.

The sub-matrix is specified by mk. Computation works using Bareiss's algorithm. If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

k	the number of rows and columns in the minor to be comuted
mk	the representation of rows and columns of the minor to be comuted
iSB	NULL or a standard basis

Returns: an instance of MinorValue representing the value of the corresponding minor

See also: MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const ideal& iSB)

Definition at line 1388 of file MinorProcessor.cc.

{
  assume(k > 0); /* k is the minor's dimension; the minor must be at least
                    1x1 */
  int *theRows=(int*)omAlloc(k*sizeof(int));
  mk.getAbsoluteRowIndices(theRows);
  int *theColumns=(int*)omAlloc(k*sizeof(int));
  mk.getAbsoluteColumnIndices(theColumns);
  if (k == 1)
  {
    PolyMinorValue tmp=PolyMinorValue(getEntry(theRows[0], theColumns[0]),
                          0, 0, 0, 0, -1, -1);
    omFree(theColumns);
    omFree(theRows);
    return tmp;
  }
  else /* k > 0 */
  {
    /* the matrix to perform Bareiss with */
    poly* tempMatrix = (poly*)omAlloc(k * k * sizeof(poly));
    /* copy correct set of entries from _polyMatrix to tempMatrix */
    int i = 0;
    for (int r = 0; r < k; r++)
      for (int c = 0; c < k; c++)
        tempMatrix[i++] = pCopy(getEntry(theRows[r], theColumns[c]));
 
    /* Bareiss algorithm operating on tempMatrix which is at least 2x2 */
    int sign = 1; /* This will store the correct sign resulting from
                     permuting the rows of tempMatrix. */
    int *rowPermutation=(int*)omAlloc(k*sizeof(int));
                 /* This is for storing the permutation of rows
                                resulting from searching for a non-zero pivot
                                element. */
    for (int i = 0; i < k; i++) rowPermutation[i] = i;
    poly divisor = NULL;
    int divisorLength = 0;
    number divisorLC;
    for (int r = 0; r <= k - 2; r++)
    {
      /* look for a non-zero entry in column r, rows = r .. (k - 1)
         s.t. the polynomial has least complexity: */
      int minComplexity = -1; int complexity = 0; int bestRow = -1;
      poly pp = NULL;
      for (int i = r; i < k; i++)
      {
        pp = tempMatrix[rowPermutation[i] * k + r];
        if (pp != NULL)
        {
          if (minComplexity == -1)
          {
            minComplexity = pSize(pp);
            bestRow = i;
          }
          else
          {
            complexity = 0;
            while ((pp != NULL) && (complexity < minComplexity))
            {
              complexity += nSize(pGetCoeff(pp)); pp = pNext(pp);
            }
            if (complexity < minComplexity)
            {
              minComplexity = complexity;
              bestRow = i;
            }
          }
          if (minComplexity <= 1) break; /* terminate the search */
        }
      }
      if (bestRow == -1)
      {
        /* There is no non-zero entry; hence the minor is zero. */
        for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
        return PolyMinorValue(NULL, 0, 0, 0, 0, -1, -1);
      }
      pNormalize(tempMatrix[rowPermutation[bestRow] * k + r]);
      if (bestRow != r)
      {
        /* We swap the rows with indices r and i: */
        int j = rowPermutation[bestRow];
        rowPermutation[bestRow] = rowPermutation[r];
        rowPermutation[r] = j;
        /* Now we know that tempMatrix[rowPermutation[r] * k + r] is not zero.
           But carefull; we have to negate the sign, as there is always an odd
           number of row transpositions to swap two given rows of a matrix. */
        sign = -sign;
      }
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
      poly w = NULL; int wl = 0;
      printf("matrix after %d steps:\n", r);
      for (int u = 0; u < k; u++)
      {
        for (int v = 0; v < k; v++)
        {
          if ((v < r) && (u > v))
            wl = 0;
          else
          {
            w = tempMatrix[rowPermutation[u] * k + v];
            wl = pLength(w);
          }
          printf("%5d  ", wl);
        }
        printf("\n");
      }
      printCounters ("", false);
#endif
      if (r != 0)
      {
        divisor = tempMatrix[rowPermutation[r - 1] * k + r - 1];
        pNormalize(divisor);
        divisorLength = pLength(divisor);
        divisorLC = pGetCoeff(divisor);
      }
      for (int rr = r + 1; rr < k; rr++)
        for (int cc = r + 1; cc < k; cc++)
        {
          if (r == 0)
            elimOperationBucketNoDiv(tempMatrix[rowPermutation[rr] * k + cc],
                                     tempMatrix[rowPermutation[r]  * k + r],
                                     tempMatrix[rowPermutation[r]  * k + cc],
                                     tempMatrix[rowPermutation[rr] * k + r]);
          else
            elimOperationBucket(tempMatrix[rowPermutation[rr] * k + cc],
                                tempMatrix[rowPermutation[r]  * k + r],
                                tempMatrix[rowPermutation[r]  * k + cc],
                                tempMatrix[rowPermutation[rr] * k + r],
                                divisor, divisorLC, divisorLength);
        }
    }
#if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
    poly w = NULL; int wl = 0;
    printf("matrix after %d steps:\n", k - 1);
    for (int u = 0; u < k; u++)
    {
      for (int v = 0; v < k; v++)
      {
        if ((v < k - 1) && (u > v))
          wl = 0;
        else
        {
          w = tempMatrix[rowPermutation[u] * k + v];
          wl = pLength(w);
        }
        printf("%5d  ", wl);
      }
      printf("\n");
    }
#endif
    poly result = tempMatrix[rowPermutation[k - 1] * k + k - 1];
    tempMatrix[rowPermutation[k - 1] * k + k - 1]=NULL; /*value now in result*/
    if (sign == -1) result = pNeg(result);
    if (iSB != NULL)
    {
      poly tmpresult = kNF(iSB, currRing->qideal, result);
      pDelete(&result);
      result=tmpresult;
    }
    PolyMinorValue mv(result, 0, 0, 0, 0, -1, -1);
    for (int i = 0; i < k * k; i++) pDelete(&tempMatrix[i]);
    omFreeSize(tempMatrix, k * k * sizeof(poly));
    omFree(rowPermutation);
    omFree(theColumns);
    omFree(theRows);
    return mv;
  }
}

◆ getMinorPrivateLaplace() [1/2]

PolyMinorValue PolyMinorProcessor::getMinorPrivateLaplace	(	const int	k,
		const MinorKey &	mk,
		const bool	multipleMinors,
		Cache< MinorKey, PolyMinorValue > &	c,
		const ideal &	iSB
	)

private

A method for computing the value of a minor, using a cache.

The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

k	the number of rows and columns in the minor to be comuted
mk	the representation of rows and columns of the minor to be comuted
multipleMinors	decides whether we compute just one or all minors of a specified size
c	a cache to be used for caching reusable sub-minors
iSB	NULL or a standard basis

Returns: an instance of MinorValue representing the value of the corresponding minor

See also: MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const ideal& iSB)

Definition at line 1083 of file MinorProcessor.cc.

{
  assume(k > 0); /* k is the minor's dimension; the minor must be at least
                    1x1 */
  /* The method works by recursion, and using Lapace's Theorem along
     the row/column with the most zeros. */
  if (k == 1)
  {
    PolyMinorValue pmv(getEntry(mk.getAbsoluteRowIndex(0),
                                mk.getAbsoluteColumnIndex(0)),
                       0, 0, 0, 0, -1, -1);
    /* we set "-1" as, for k == 1, we do not have any cache retrievals */
    return pmv;
  }
  else
  {
    int b = getBestLine(k, mk);                   /* row or column with most
                                                     zeros */
    poly result = NULL;                           /* This will contain the
                                                     value of the minor. */
    int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
                                                     and multiplications,
                                                     ..."a*" for accumulated
                                                     operation counters */
    bool hadNonZeroEntry = false;
    if (b >= 0)
    {
      /* This means that the best line is the row with absolute (0-based)
         index b.
         Using Laplace, the sign of the contributing minors must be iterating;
         the initial sign depends on the relative index of b in
         minorRowKey: */
      int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
      for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
      {
        int absoluteC = mk.getAbsoluteColumnIndex(c);
        if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
                                           this sub-determinante. */
        {
          hadNonZeroEntry = true;
          PolyMinorValue mv; /* for storing all intermediate minors */
          /* Next MinorKey is mk with row b and column absoluteC omitted. */
          MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
          if (cch.hasKey(subMk))
          { /* trying to find the result in the cache */
            mv = cch.getValue(subMk);
            mv.incrementRetrievals(); /* once more, we made use of the cached
                                         value for key mk */
            cch.put(subMk, mv); /* We need to do this with "put", as the
                                   (altered) number of retrievals may have an
                                   impact on the internal ordering among cache
                                   entries. */
          }
          else
          {
            /* recursive call: */
            mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
                                        iSB);
            /* As this minor was not in the cache, we count the additions and
               multiplications that we needed to do in the recursive call: */
            m += mv.getMultiplications();
            s += mv.getAdditions();
          }
          /* In any case, we count all nested operations in the accumulative
             counters: */
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          poly signPoly = pISet(sign);
          poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
                                 currRing);
          temp = p_Mult_q(signPoly, temp, currRing);
          result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
          multsPoly++;
          addsPoly++;
          multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
#endif
          s++; m++; as++; am++; /* This is for the addition and multiplication
                                   in the previous lines of code. */
        }
        sign = - sign; /* alternating the sign */
      }
    }
    else
    {
      b = - b - 1;
      /* This means that the best line is the column with absolute (0-based)
         index b.
         Using Laplace, the sign of the contributing minors must be iterating;
         the initial sign depends on the relative index of b in
         minorColumnKey: */
      int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
      for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
      {
        int absoluteR = mk.getAbsoluteRowIndex(r);
        if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
                                           this sub-determinante. */
        {
          hadNonZeroEntry = true;
          PolyMinorValue mv; /* for storing all intermediate minors */
          /* Next MinorKey is mk with row absoluteR and column b omitted. */
          MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
          if (cch.hasKey(subMk))
          { /* trying to find the result in the cache */
            mv = cch.getValue(subMk);
            mv.incrementRetrievals(); /* once more, we made use of the cached
                                         value for key mk */
            cch.put(subMk, mv); /* We need to do this with "put", as the
                                   (altered) number of retrievals may have an
                                   impact on the internal ordering among the
                                   cached entries. */
          }
          else
          {
            mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
                                        iSB); /* recursive call */
            /* As this minor was not in the cache, we count the additions and
               multiplications that we needed to do in the recursive call: */
            m += mv.getMultiplications();
            s += mv.getAdditions();
          }
          /* In any case, we count all nested operations in the accumulative
             counters: */
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          poly signPoly = pISet(sign);
          poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
                                 currRing);
          temp = p_Mult_q(signPoly, temp, currRing);
          result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
          multsPoly++;
          addsPoly++;
          multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
#endif
          s++; m++; as++; am++; /* This is for the addition and multiplication
                                   in the previous lines of code. */
        }
        sign = - sign; /* alternating the sign */
      }
    }
    /* Let's cache the newly computed minor: */
    int potentialRetrievals = NumberOfRetrievals(_containerRows,
                                                 _containerColumns,
                                                 _minorSize,
                                                 k,
                                                 multipleMinors);
    if (hadNonZeroEntry)
    {
      s--; as--; /* first addition was 0 + ..., so we do not count it */
#ifdef COUNT_AND_PRINT_OPERATIONS
      addsPoly--;
#endif
    }
    if (s < 0) s = 0; /* may happen when all subminors are zero and no
                         addition needs to be performed */
    if (as < 0) as = 0; /* may happen when all subminors are zero and no
                           addition needs to be performed */
    if (iSB != NULL)
    {
      poly tmpresult = kNF(iSB, currRing->qideal, result);
      pDelete(&tmpresult);
      result=tmpresult;
    }
    PolyMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
    pDelete(&result); result = NULL;
    cch.put(mk, newMV); /* Here's the actual put inside the cache. */
    return newMV;
  }
}

◆ getMinorPrivateLaplace() [2/2]

PolyMinorValue PolyMinorProcessor::getMinorPrivateLaplace	(	const int	k,
		const MinorKey &	mk,
		const ideal &	iSB
	)

private

A method for computing the value of a minor, without using a cache.

The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

k	the number of rows and columns in the minor to be comuted
mk	the representation of rows and columns of the minor to be comuted
iSB	NULL or a standard basis

Returns: an instance of MinorValue representing the value of the corresponding minor

See also: MinorProcessor::getMinorPrivate (const int, const MinorKey&, const bool, Cache<MinorKey, MinorValue>&)

Definition at line 950 of file MinorProcessor.cc.

{
  assume(k > 0); /* k is the minor's dimension; the minor must be at least
                    1x1 */
  /* The method works by recursion, and using Lapace's Theorem along the
     row/column with the most zeros. */
  if (k == 1)
  {
    PolyMinorValue pmv(getEntry(mk.getAbsoluteRowIndex(0),
                                mk.getAbsoluteColumnIndex(0)),
                       0, 0, 0, 0, -1, -1);
    /* "-1" is to signal that any statistics about the number of retrievals
       does not make sense, as we do not use a cache. */
    return pmv;
  }
  else
  {
    /* Here, the minor must be 2x2 or larger. */
    int b = getBestLine(k, mk);                   /* row or column with most
                                                     zeros */
    poly result = NULL;                           /* This will contain the
                                                     value of the minor. */
    int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
                                                     and multiplications,
                                                     ..."a*" for accumulated
                                                     operation counters */
    bool hadNonZeroEntry = false;
    if (b >= 0)
    {
      /* This means that the best line is the row with absolute (0-based)
         index b.
         Using Laplace, the sign of the contributing minors must be iterating;
         the initial sign depends on the relative index of b in minorRowKey: */
      int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
      for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
      {
        int absoluteC = mk.getAbsoluteColumnIndex(c);
        if (!isEntryZero(b, absoluteC)) /* Only then do we have to consider
                                           this sub-determinante. */
        {
          hadNonZeroEntry = true;
          /* Next MinorKey is mk with row b and column absoluteC omitted. */
          MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
          /* recursive call: */
          PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
          m += mv.getMultiplications();
          s += mv.getAdditions();
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          poly signPoly = pISet(sign);
          poly temp = pp_Mult_qq(mv.getResult(), getEntry(b, absoluteC),
                                 currRing);
          temp = p_Mult_q(signPoly, temp, currRing);
          result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
          multsPoly++;
          addsPoly++;
          multsMon += pLength(mv.getResult()) * pLength(getEntry(b, absoluteC));
#endif
          s++; m++; as++, am++; /* This is for the addition and multiplication
                                   in the previous lines of code. */
        }
        sign = - sign; /* alternating the sign */
      }
    }
    else
    {
      b = - b - 1;
      /* This means that the best line is the column with absolute (0-based)
         index b.
         Using Laplace, the sign of the contributing minors must be iterating;
         the initial sign depends on the relative index of b in
         minorColumnKey: */
      int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
      for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
      {
        int absoluteR = mk.getAbsoluteRowIndex(r);
        if (!isEntryZero(absoluteR, b)) /* Only then do we have to consider
                                           this sub-determinante. */
        {
          hadNonZeroEntry = true;
          /* This is mk with row absoluteR and column b omitted. */
          MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
          /* recursive call: */
          PolyMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, iSB);
          m += mv.getMultiplications();
          s += mv.getAdditions();
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          poly signPoly = pISet(sign);
          poly temp = pp_Mult_qq(mv.getResult(), getEntry(absoluteR, b),
                                 currRing);
          temp = p_Mult_q(signPoly, temp, currRing);
          result = p_Add_q(result, temp, currRing);
#ifdef COUNT_AND_PRINT_OPERATIONS
          multsPoly++;
          addsPoly++;
          multsMon += pLength(mv.getResult()) * pLength(getEntry(absoluteR, b));
#endif
          s++; m++; as++, am++; /* This is for the addition and multiplication
                                   in the previous lines of code. */
        }
        sign = - sign; /* alternating the sign */
      }
    }
    if (hadNonZeroEntry)
    {
      s--; as--; /* first addition was 0 + ..., so we do not count it */
#ifdef COUNT_AND_PRINT_OPERATIONS
      addsPoly--;
#endif
    }
    if (s < 0) s = 0; /* may happen when all subminors are zero and no
                         addition needs to be performed */
    if (as < 0) as = 0; /* may happen when all subminors are zero and no
                           addition needs to be performed */
    if (iSB != NULL)
    {
      poly tmpresult = kNF(iSB, currRing->qideal, result);
      pDelete(&result);
      result=tmpresult;
    }
    PolyMinorValue newMV(result, m, s, am, as, -1, -1);
    /* "-1" is to signal that any statistics about the number of retrievals
       does not make sense, as we do not use a cache. */
    pDelete(&result);
    return newMV;
  }
}

◆ getNextMinor() [1/2]

PolyMinorValue PolyMinorProcessor::getNextMinor	(	Cache< MinorKey, PolyMinorValue > &	c,
		const ideal &	iSB
	)

A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.

This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works using Laplace's algorithm and a cache c which may already contain useful results from previous calls of PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

iSB	NULL or a standard basis

Returns: the next minor

See also: PolyMinorValue::getNextMinor (const char* algorithm, const ideal& iSB)

Definition at line 941 of file MinorProcessor.cc.

{
    /* computation with cache */
    return getMinorPrivateLaplace(_minorSize, _minor, true, c, iSB);
}

◆ getNextMinor() [2/2]

PolyMinorValue PolyMinorProcessor::getNextMinor	(	const char *	algorithm,
		const ideal &	iSB
	)

A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.

This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works either by Laplace's algorithm (without using a cache) or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis.

Parameters

algorithm	either "Laplace" or "Bareiss"
iSB	NULL or a standard basis

Returns: true iff there is a next choice of rows and columns

See also: PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c, const ideal& iSB)

Definition at line 925 of file MinorProcessor.cc.

{
  /* call a helper method which computes the minor (without using a
     cache): */
  if (strcmp(algorithm, "Laplace") == 0)
    return getMinorPrivateLaplace(_minorSize, _minor, iSB);
  else if (strcmp(algorithm, "Bareiss") == 0)
    return getMinorPrivateBareiss(_minorSize, _minor, iSB);
  else assume(false);
 
  /* The following code is never reached and just there to make the
     compiler happy: */
  return PolyMinorValue();
}

◆ isEntryZero()

bool PolyMinorProcessor::isEntryZero	(	const int	absoluteRowIndex,
		const int	absoluteColumnIndex
	)		const

protectedvirtual

A method for testing whether a matrix entry is zero.

Parameters

absoluteRowIndex	the absolute (zero-based) row index
absoluteColumnIndex	the absolute (zero-based) column index

Returns: true iff the specified matrix entry is zero

Reimplemented from MinorProcessor.

Definition at line 821 of file MinorProcessor.cc.

{
  return getEntry(absoluteRowIndex, absoluteColumnIndex) == NULL;
}

◆ toString()

string PolyMinorProcessor::toString ( ) const

virtual

A method for providing a printable version of the represented MinorProcessor.

Returns: a printable version of the given instance as instance of class string

Reimplemented from MinorProcessor.

Definition at line 827 of file MinorProcessor.cc.

{
  char h[32];
  string t = "";
  string s = "PolyMinorProcessor:";
  s += "\n   matrix: ";
  sprintf(h, "%d", _rows); s += h;
  s += " x ";
  sprintf(h, "%d", _columns); s += h;
  int myIndexArray[500];
  s += "\n   considered submatrix has row indices: ";
  _container.getAbsoluteRowIndices(myIndexArray);
  for (int k = 0; k < _containerRows; k++)
  {
    if (k != 0) s += ", ";
    sprintf(h, "%d", myIndexArray[k]); s += h;
  }
  s += " (first row of matrix has index 0)";
  s += "\n   considered submatrix has column indices: ";
  _container.getAbsoluteColumnIndices(myIndexArray);
  for (int k = 0; k < _containerColumns; k++)
  {
    if (k != 0) s += ", ";
    sprintf(h, "%d", myIndexArray[k]); s += h;
  }
  s += " (first column of matrix has index 0)";
  s += "\n   size of considered minor(s): ";
  sprintf(h, "%d", _minorSize); s += h;
  s += "x";
  s += h;
  return s;
}

Field Documentation

◆ _polyMatrix

poly* PolyMinorProcessor::_polyMatrix

private

private store for polynomial matrix entries

Definition at line 566 of file MinorProcessor.h.

The documentation for this class was generated from the following files:

kernel/linear_algebra/MinorProcessor.h
kernel/linear_algebra/MinorProcessor.cc

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ PolyMinorProcessor()

◆ ~PolyMinorProcessor()

Member Function Documentation

◆ defineMatrix()

◆ getEntry()

◆ getMinor() [1/2]

◆ getMinor() [2/2]

◆ getMinorPrivateBareiss()

◆ getMinorPrivateLaplace() [1/2]

◆ getMinorPrivateLaplace() [2/2]

◆ getNextMinor() [1/2]

◆ getNextMinor() [2/2]

◆ isEntryZero()

◆ toString()

Field Documentation

◆ _polyMatrix