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

#include <MinorProcessor.h>

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

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

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

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

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

IntMinorValue	getNextMinor (const int characteristic, const ideal &iSB, const char *algorithm)
	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...

IntMinorValue	getNextMinor (Cache< MinorKey, IntMinorValue > &c, const int characteristic, 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
int	getEntry (const int rowIndex, const int columnIndex) const
	A method for retrieving the matrix entry. More...

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

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

IntMinorValue	getMinorPrivateBareiss (const int k, const MinorKey &mk, const int characteristic, const ideal &iSB)
	A method for computing the value of a minor using Bareiss's algorithm. More...

Private Attributes
int *	_intMatrix
	private store for integer 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 IntMinorProcessor is derived from class MinorProcessor.

This class implements the special case of integer matrices.

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

Definition at line 299 of file MinorProcessor.h.

Constructor & Destructor Documentation

◆ IntMinorProcessor()

IntMinorProcessor::IntMinorProcessor ( )

A constructor for creating an instance.

Definition at line 287 of file MinorProcessor.cc.

{
  _intMatrix = 0;
}

◆ ~IntMinorProcessor()

IntMinorProcessor::~IntMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 335 of file MinorProcessor.cc.

{
  /* free memory of _intMatrix */
  delete [] _intMatrix; _intMatrix = 0;
}

Member Function Documentation

◆ defineMatrix()

void IntMinorProcessor::defineMatrix	(	const int	numberOfRows,
		const int	numberOfColumns,
		const int *	matrix
	)

A method for defining a matrix with integer entries.

Parameters

numberOfRows	the number of rows
numberOfColumns	the number of columns
matrix	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 347 of file MinorProcessor.cc.

{
  /* free memory of _intMatrix */
  omFree(_intMatrix); _intMatrix = NULL;
 
  _rows = numberOfRows;
  _columns = numberOfColumns;
 
  /* allocate memory for new entries in _intMatrix */
  int n = _rows * _columns;
  _intMatrix = (int*)omAlloc(n*sizeof(int));
 
  /* copying values from one-dimensional method
     parameter "matrix" */
  for (int i = 0; i < n; i++)
    _intMatrix[i] = matrix[i];
}

◆ getEntry()

int IntMinorProcessor::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 650 of file MinorProcessor.cc.

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

◆ getMinor() [1/2]

IntMinorValue IntMinorProcessor::getMinor	(	const int	dimension,
		const int *	rowIndices,
		const int *	columnIndices,
		Cache< MinorKey, IntMinorValue > &	c,
		const int	characteristic,
		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 by Laplace's algorithm together with caching of subdeterminants.
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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

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	the cache for storing subdeterminants
characteristic	0 or the characteristic of the underlying coefficient ring/field
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, const int characteristic, const ideal& iSB, const char* algorithm)

Definition at line 367 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,
                                characteristic, iSB);
}

◆ getMinor() [2/2]

IntMinorValue IntMinorProcessor::getMinor	(	const int	dimension,
		const int *	rowIndices,
		const int *	columnIndices,
		const int	characteristic,
		const ideal &	iSB,
		const char *	algorithm
	)

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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

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
characteristic	0 or the characteristic of the underlying coefficient ring/field
iSB	NULL or a standard basis
algorithm	either "Bareiss" or "Laplace"

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, IntMinorValue>& c, const int characteristic, const ideal& iSB)

Definition at line 382 of file MinorProcessor.cc.

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

◆ getMinorPrivateBareiss()

IntMinorValue IntMinorProcessor::getMinorPrivateBareiss	(	const int	k,
		const MinorKey &	mk,
		const int	characteristic,
		const ideal &	iSB
	)

private

A method for computing the value of a minor using Bareiss's algorithm.

The sub-matrix is specified by 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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

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 computed
characteristic	0 or the characteristic of the underlying coefficient ring/field
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 int characteristic, const ideal& iSB)

Definition at line 563 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);
  /* the next line provides the return value for the case k = 1 */
  int e = getEntry(theRows[0], theColumns[0]);
  if (characteristic != 0) e = e % characteristic;
  if (iSB != 0) e = getReduction(e, iSB);
  IntMinorValue mv(e, 0, 0, 0, 0, -1, -1);
  if (k > 1)
  {
    /* the matrix to perform Bareiss with */
    long *tempMatrix=(long*)omAlloc(k * k *sizeof(long));
    /* copy correct set of entries from _intMatrix to tempMatrix */
    int i = 0;
    for (int r = 0; r < k; r++)
      for (int c = 0; c < k; c++)
      {
        e = getEntry(theRows[r], theColumns[c]);
        if (characteristic != 0) e = e % characteristic;
        tempMatrix[i++] = e;
      }
    /* 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;
    int divisor = 1;   /* the Bareiss divisor */
    for (int r = 0; r <= k - 2; r++)
    {
      /* look for a non-zero entry in column r: */
      int i = r;
      while ((i < k) && (tempMatrix[rowPermutation[i] * k + r] == 0))
        i++;
      if (i == k)
        /* There is no non-zero entry; hence the minor is zero. */
        return IntMinorValue(0, 0, 0, 0, 0, -1, -1);
      if (i != r)
      {
        /* We swap the rows with indices r and i: */
        int j = rowPermutation[i];
        rowPermutation[i] = 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 (r >= 1) divisor = tempMatrix[rowPermutation[r - 1] * k + r - 1];
      for (int rr = r + 1; rr < k; rr++)
        for (int cc = r + 1; cc < k; cc++)
        {
          e = rowPermutation[rr] * k + cc;
          /* Attention: The following may cause an overflow and
             thus a wrong result: */
          tempMatrix[e] = tempMatrix[e] * tempMatrix[rowPermutation[r] * k + r]
                         - tempMatrix[rowPermutation[r] * k + cc]
                         * tempMatrix[rowPermutation[rr] * k + r];
          /* The following is, by theory, always a division without
             remainder: */
          tempMatrix[e] = tempMatrix[e] / divisor;
          if (characteristic != 0)
            tempMatrix[e] = tempMatrix[e] % characteristic;
        }
      omFree(rowPermutation);
      omFree(tempMatrix);
    }
    int theValue = sign * tempMatrix[rowPermutation[k - 1] * k + k - 1];
    if (iSB != 0) theValue = getReduction(theValue, iSB);
    mv = IntMinorValue(theValue, 0, 0, 0, 0, -1, -1);
  }
  omFree(theRows);
  omFree(theColumns);
  return mv;
}

◆ getMinorPrivateLaplace() [1/2]

IntMinorValue IntMinorProcessor::getMinorPrivateLaplace	(	const int	k,
		const MinorKey &	mk,
		const bool	multipleMinors,
		Cache< MinorKey, IntMinorValue > &	c,
		int	characteristic,
		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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

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
characteristic	0 or the characteristic of the underlying coefficient ring/field
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 int characteristic, const ideal& iSB)

Definition at line 656 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)
  {
    int e = getEntry(mk.getAbsoluteRowIndex(0), mk.getAbsoluteColumnIndex(0));
    if (characteristic != 0) e = e % characteristic;
    if (iSB != 0) e = getReduction(e, iSB);
    return IntMinorValue(e, 0, 0, 0, 0, -1, -1);
    /* we set "-1" as, for k == 1, we do not have any cache retrievals */
  }
  else
  {
    int b = getBestLine(k, mk);                   /* row or column with
                                                     most zeros */
    int result = 0;                               /* 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 */
    IntMinorValue mv(0, 0, 0, 0, 0, 0, 0);        /* for storing all
                                                     intermediate minors */
    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 (getEntry(b, absoluteC) != 0) /* 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);
          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,
                   characteristic, iSB); /* recursive call */
              /* As this minor was not in the cache, we count the additions
                 and multiplications that we needed to perform 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();
          /* adding sub-determinante times matrix entry times appropriate
             sign */
          result += sign * mv.getResult() * getEntry(b, absoluteC);
          if (characteristic != 0) result = result % characteristic;
          s++; m++; as++; am++; /* This is for the last addition and
                                   multiplication. */
        }
        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 (getEntry(absoluteR, b) != 0) /* Only then do we have to consider
                                            this sub-determinante. */
        {
          hadNonZeroEntry = true;
          /* 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, characteristic, 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();
          /* adding sub-determinante times matrix entry times appropriate
             sign: */
          result += sign * mv.getResult() * getEntry(absoluteR, b);
          if (characteristic != 0) result = result % characteristic;
          s++; m++; as++; am++; /* This is for the last addition and
                                   multiplication. */
        }
        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 */
    }
    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 != 0) result = getReduction(result, iSB);
    IntMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
    cch.put(mk, newMV); /* Here's the actual put inside the cache. */
    return newMV;
  }
}

◆ getMinorPrivateLaplace() [2/2]

IntMinorValue IntMinorProcessor::getMinorPrivateLaplace	(	const int	k,
		const MinorKey &	mk,
		const int	characteristic,
		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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

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
characteristic	0 or the characteristic of the underlying coefficient ring/field
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 bool multipleMinors, Cache<MinorKey, IntMinorValue>& c, int characteristic, const ideal& iSB)

Definition at line 446 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)
  {
    int e = getEntry(mk.getAbsoluteRowIndex(0), mk.getAbsoluteColumnIndex(0));
    if (characteristic != 0) e = e % characteristic;
    if (iSB != 0) e = getReduction(e, iSB);
    return IntMinorValue(e, 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. */
  }
  else
  {
    /* Here, the minor must be 2x2 or larger. */
    int b = getBestLine(k, mk);                   /* row or column with most
                                                     zeros */
    int result = 0;                               /* 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 (getEntry(b, absoluteC) != 0) /* 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);
          IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk,
                             characteristic, iSB);  /* recursive call */
          m += mv.getMultiplications();
          s += mv.getAdditions();
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          /* adding sub-determinante times matrix entry
             times appropriate sign: */
          result += sign * mv.getResult() * getEntry(b, absoluteC);
 
          if (characteristic != 0) result = result % characteristic;
          s++; m++; as++, am++; /* This is for the last addition and
                                   multiplication. */
        }
        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 (getEntry(absoluteR, b) != 0) /* Only then do we have to consider
                                            this sub-determinante. */
        {
          hadNonZeroEntry = true;
          /* Next MinorKey is mk with row absoluteR and column b omitted. */
          MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
          IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, characteristic, iSB); /* recursive call */
          m += mv.getMultiplications();
          s += mv.getAdditions();
          am += mv.getAccumulatedMultiplications();
          as += mv.getAccumulatedAdditions();
          /* adding sub-determinante times matrix entry
             times appropriate sign: */
          result += sign * mv.getResult() * getEntry(absoluteR, b);
          if (characteristic != 0) result = result % characteristic;
          s++; m++; as++, am++; /* This is for the last addition and
                                   multiplication. */
        }
        sign = - sign; /* alternating the sign */
      }
    }
    if (hadNonZeroEntry)
    {
      s--; as--; /* first addition was 0 + ..., so we do not count it */
    }
    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 != 0) result = getReduction(result, iSB);
    IntMinorValue 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. */
    return newMV;
  }
}

◆ getNextMinor() [1/2]

IntMinorValue IntMinorProcessor::getNextMinor	(	Cache< MinorKey, IntMinorValue > &	c,
		const int	characteristic,
		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 the cache c which may already contain useful results from previous calls of IntMinorValue::getNextMinor (Cache<MinorKey, IntMinorValue>& c, const int characteristic, 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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters

c	the cache
characteristic	0 or the characteristic of the underlying coefficient ring/field
iSB	NULL or a standard basis

Returns: the next minor

See also: IntMinorValue::getNextMinor (const int characteristic, const ideal& iSB, const char* algorithm)

Definition at line 422 of file MinorProcessor.cc.

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

◆ getNextMinor() [2/2]

IntMinorValue IntMinorProcessor::getNextMinor	(	const int	characteristic,
		const ideal &	iSB,
		const char *	algorithm
	)

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 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. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters

characteristic	0 or the characteristic of the underlying coefficient ring/field
iSB	NULL or a standard basis
algorithm	either "Bareiss" or "Laplace"

Returns: the next minor

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

Definition at line 406 of file MinorProcessor.cc.

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

◆ isEntryZero()

bool IntMinorProcessor::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 341 of file MinorProcessor.cc.

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

◆ toString()

string IntMinorProcessor::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 292 of file MinorProcessor.cc.

{
  char h[32];
  string t = "";
  string s = "IntMinorProcessor:";
  s += "\n   matrix: ";
  sprintf(h, "%d", _rows); s += h;
  s += " x ";
  sprintf(h, "%d", _columns); s += h;
  for (int r = 0; r < _rows; r++)
  {
    s += "\n      ";
    for (int c = 0; c < _columns; c++)
    {
      sprintf(h, "%d", getEntry(r, c)); t = h;
      for (int k = 0; k < int(4 - strlen(h)); k++) s += " ";
      s += t;
    }
  }
  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

◆ _intMatrix

int* IntMinorProcessor::_intMatrix

private

private store for integer matrix entries

Definition at line 305 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

◆ IntMinorProcessor()

◆ ~IntMinorProcessor()

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

◆ _intMatrix