MinorProcessor Class Reference

Class MinorProcessor implements the key methods for computing one or all sub-determinantes of a given size in a pre-defined matrix; either without caching or by using a cache. More...

#include <MinorProcessor.h>

Public Member Functions
	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	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...

Static Protected Member Functions
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
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 MinorProcessor implements the key methods for computing one or all sub-determinantes of a given size in a pre-defined matrix; either without caching or by using a cache.

After defining the entire matrix (e.g. 10 x 14) using
MinorProcessor::defineMatrix (const int, const int, const int*),
the user may do two different things:

1. He/she can simply compute a minor in this matrix using
   MinorProcessor::getMinor (const int, const int*, const int*, Cache<MinorKey, MinorValue>&), or
   MinorProcessor::getMinor (const int, const int*, const int*);
   depending on whether a cache shall or shall not be used, respectively.
   In the first case, the user simply provides all row and column indices of the desired minor.
2. He/she may define a smaller sub-matrix (e.g. 8 x 7) using MinorValue::defineSubMatrix (const int, const int*, const int, const int*). Afterwards, he/she may compute all minors of an even smaller size (e.g. 5 x 5) that consist exclusively of rows and columns of this (8 x 7) sub-matrix (inside the entire 10 x 14 matrix).
   The implementation at hand eases the iteration over all such minors. Also in the second case there are both implementations, i.e., with and without using a cache.
   
   MinorProcessor makes use of MinorKey, MinorValue, and Cache. The implementation of all mentioned classes (MinorKey, MinorValue, and MinorProcessor) is generic to allow for the use of different types of keys and values.

   Author

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

Definition at line 57 of file MinorProcessor.h.

Constructor & Destructor Documentation

MinorProcessor()

MinorProcessor::MinorProcessor

(

)

The default constructor.

Definition at line 277 of file MinorProcessor.cc.

                                :
  _container(0, NULL, 0, NULL),
  _minor(0, NULL, 0, NULL),
  _containerRows(0),
  _containerColumns(0),
  _minorSize(0),
  _rows(0),
  _columns(0)
{
}

~MinorProcessor()

MinorProcessor::~MinorProcessor ( )

virtual

A destructor for deleting an instance.

We must make this destructor virtual so that destructors of all derived classes will automatically also call the destructor of the base class MinorProcessor.

Definition at line 288 of file MinorProcessor.cc.

{ }

Member Function Documentation

defineSubMatrix()

void MinorProcessor::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.

Parameters

numberOfRows	the number of rows in the sub-matrix
rowIndices	an array with the (0-based) indices of rows inside the pre-defined matrix
numberOfColumns	the number of columns in the sub-matrix
columnIndices	an array with the (0-based) indices of columns inside the pre-defined matrix

See also

MinorValue::defineMatrix (const int, const int, const int*)

Definition at line 129 of file MinorProcessor.cc.

{
  /* The method assumes ascending row and column indices in the
     two argument arrays. These indices are understood to be zero-based.
     The method will set the two arrays of ints in _container.
     Example: The indices 0, 2, 3, 7 will be converted to an array with
     one int representing the binary number 10001101
     (check bits from right to left). */
 
  _containerRows = numberOfRows;
  int highestRowIndex = rowIndices[numberOfRows - 1];
  int rowBlockCount = (highestRowIndex / 32) + 1;
  unsigned *rowBlocks=(unsigned*)omAlloc(rowBlockCount*sizeof(unsigned));
  for (int i = 0; i < rowBlockCount; i++) rowBlocks[i] = 0;
  for (int i = 0; i < numberOfRows; i++)
  {
    int blockIndex = rowIndices[i] / 32;
    int offset = rowIndices[i] % 32;
    rowBlocks[blockIndex] += (1 << offset);
  }
 
  _containerColumns = numberOfColumns;
  int highestColumnIndex = columnIndices[numberOfColumns - 1];
  int columnBlockCount = (highestColumnIndex / 32) + 1;
  unsigned *columnBlocks=(unsigned*)omAlloc0(columnBlockCount*sizeof(unsigned));
  for (int i = 0; i < numberOfColumns; i++)
  {
    int blockIndex = columnIndices[i] / 32;
    int offset = columnIndices[i] % 32;
    columnBlocks[blockIndex] += (1 << offset);
  }
 
  _container.set(rowBlockCount, rowBlocks, columnBlockCount, columnBlocks);
  omFree(columnBlocks);
  omFree(rowBlocks);
}

Faculty()

int MinorProcessor::Faculty ( const int  i )

staticprotected

A static method for computing the factorial of i.

Assert

The method checks whether i >= 0.

Parameters

i	an integer greater than or equal to 0

Returns

the factorial of i

Definition at line 235 of file MinorProcessor.cc.

{
  /* This is a non-recursive implementation. */
  assume(i >= 0);
  int result = 1;
  for (int j = 1; j <= i; j++) result *= j;
  // Now, result = 1 * 2 * ... * i = i!
  return result;
}

getBestLine()

int MinorProcessor::getBestLine ( const int  k, const MinorKey &  mk  ) const

protected

A method for identifying the row or column with the most zeros.

Using Laplace's Theorem, a minor can more efficiently be computed when developing along this best line. The returned index bestIndex is 0-based within the pre-defined matrix. If some row has the most zeros, then the (0-based) row index is returned. If, contrarywise, some column has the most zeros, then x = - 1 - c where c is the column index, is returned. (Note that in this case c can be reconstructed by computing c = - 1 - x.)

Parameters

k	the size of the minor / all minors of interest
mk	the representation of rows and columns of the minor of interest

Returns

an int encoding which row or column has the most zeros

Definition at line 57 of file MinorProcessor.cc.

{
  /* This method identifies the row or column with the most zeros.
     The returned index (bestIndex) is absolute within the pre-
     defined matrix.
     If some row has the most zeros, then the absolute (0-based)
     row index is returned.
     If, contrariwise, some column has the most zeros, then -1 minus
     the absolute (0-based) column index is returned. */
  int numberOfZeros = 0;
  int bestIndex = 100000;    /* We start with an invalid row/column index. */
  int maxNumberOfZeros = -1; /* We update this variable whenever we find
                                a new so-far optimal row or column. */
  for (int r = 0; r < k; r++)
  {
    /* iterate through all k rows of the momentary minor */
    int absoluteR = mk.getAbsoluteRowIndex(r);
    numberOfZeros = 0;
    for (int c = 0; c < k; c++)
    {
      int absoluteC = mk.getAbsoluteColumnIndex(c);
      if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
    }
    if (numberOfZeros > maxNumberOfZeros)
    {
      /* We found a new best line which is a row. */
      bestIndex = absoluteR;
      maxNumberOfZeros = numberOfZeros;
    }
  };
  for (int c = 0; c < k; c++)
  {
    int absoluteC = mk.getAbsoluteColumnIndex(c);
    numberOfZeros = 0;
    for (int r = 0; r < k; r++)
    {
      int absoluteR = mk.getAbsoluteRowIndex(r);
      if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
    }
    if (numberOfZeros > maxNumberOfZeros)
    {
      /* We found a new best line which is a column. So we transform
         the return value. Note that we can easily retrieve absoluteC
         from bestLine: absoluteC = - 1 - bestLine. */
      bestIndex = - absoluteC - 1;
      maxNumberOfZeros = numberOfZeros;
    }
  };
  return bestIndex;
}

getCurrentColumnIndices()

void MinorProcessor::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.

This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
The user of this method needs to know the number of columns in order to know which entries of the newly filled target will be valid.

Parameters

target

an int array to be filled with the column indices

See also

MinorProcessor::hasNextMinor ()

Definition at line 124 of file MinorProcessor.cc.

{
  return _minor.getAbsoluteColumnIndices(target);
}

getCurrentRowIndices()

void MinorProcessor::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.

This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
The user of this method needs to know the number of rows in order to know which entries of the newly filled target will be valid.

Parameters

target

an int array to be filled with the row indices

See also

MinorProcessor::hasNextMinor ()

Definition at line 119 of file MinorProcessor.cc.

{
  return _minor.getAbsoluteRowIndices(target);
}

hasNextMinor()

bool MinorProcessor::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.

The number of rows and columns has to be set before using MinorValue::setMinorSize(const int).
After calling MinorValue::hasNextMinor (), the current sets of rows and columns may be inspected using MinorValue::getCurrentRowIndices(int* const) const and MinorValue::getCurrentColumnIndices(int* const) const.

Returns

true iff there is a next choice of rows and columns

See also

MinorProcessor::getMinor (const int, const int*, const int*)

MinorValue::getCurrentRowIndices(int* const) const

MinorValue::getCurrentColumnIndices(int* const) const

Definition at line 114 of file MinorProcessor.cc.

{
  return setNextKeys(_minorSize);
}

IOverJ()

int MinorProcessor::IOverJ ( const int  i, const int  j  )

staticprotected

A static method for computing the binomial coefficient i over j.

Assert

The method checks whether i >= j >= 0.

Parameters

i	a positive integer greater than or equal to j
j	a positive integer less than or equal to i, and greater than or equal to 0.

Returns

the binomial coefficient i over j

Definition at line 218 of file MinorProcessor.cc.

{
  /* This is a non-recursive implementation. */
  assume( (i >= 0) && (j >= 0) && (i >= j));
  if (j == 0 || i == j) return 1;
  #if 0
  int result = 1;
  for (int k = i - j + 1; k <= i; k++) result *= k;
  /* Now, result = (i - j + 1) * ... * i. */
  for (int k = 2; k <= j; k++) result /= k;
  /* Now, result = (i - j + 1) * ... * i / 1 / 2 ...
   ... / j = i! / j! / (i - j)!. */
  return result;
  #endif
  return binom(i,j);
}

isEntryZero()

bool MinorProcessor::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 in IntMinorProcessor, and PolyMinorProcessor.

Definition at line 205 of file MinorProcessor.cc.

{
  assume(false);
  return false;
}

NumberOfRetrievals()

int MinorProcessor::NumberOfRetrievals ( const int  rows, const int  columns, const int  containerMinorSize, const int  minorSize, const bool  multipleMinors  )

staticprotected

A static method for computing the maximum number of retrievals of a minor.

More concretely, we are given a matrix of size rows x columns. We furthermore assume that we have - as part of this matrix - a minor of size containerMinorSize x containerMinorSize. Now we are interested in the number of times a minor of yet smaller size minorSize x minorSize will be needed when we compute the containerMinor by Laplace's Theorem.
The method returns the combinatorial results for both cases: containerMinor is fixed within the matrix (multipleMinors == false), or it can vary inside the matrix (multipleMinors == true).
The notion is here that we want to cache the small minor of size minorSize x minorSize, i.e. compute it just once.

Parameters

rows	the number of rows of the underlying matrix
columns	the number of columns of the underlying matrix
containerMinorSize	the size of the container minor
minorSize	the size of the small minor (which may be retrieved multiple times)
multipleMinors	decides whether containerMinor is fixed within the underlying matrix or not

Returns

the number of times, the small minor will be needed when computing one or all containerMinors

Definition at line 245 of file MinorProcessor.cc.

{
  /* This method computes the number of potential retrievals
     of a single minor when computing all minors of a given size
     within a matrix of given size. */
  int result = 0;
  if (multipleMinors)
  {
    /* Here, we would like to compute all minors of size
       containerMinorSize x containerMinorSize in a matrix
       of size rows x columns.
       Then, we need to retrieve any minor of size
       minorSize x minorSize exactly n times, where n is as
       follows: */
    result = IOverJ(rows - minorSize, containerMinorSize - minorSize)
           * IOverJ(columns - minorSize, containerMinorSize - minorSize)
           * Faculty(containerMinorSize - minorSize);
  }
  else
  {
    /* Here, we would like to compute just one minor of size
       containerMinorSize x containerMinorSize. Then, we need
       to retrieve any minor of size minorSize x minorSize exactly
       (containerMinorSize - minorSize)! times: */
    result = Faculty(containerMinorSize - minorSize);
  }
  return result;
}

print()

void MinorProcessor::print

(

)

const

A method for printing a string representation of the given MinorProcessor to std::cout.

Definition at line 52 of file MinorProcessor.cc.

{
  PrintS(this->toString().c_str());
}

setMinorSize()

void MinorProcessor::setMinorSize

(

const int

minorSize

)

Sets the size of the minor(s) of interest.

This method needs to be performed before beginning to compute all minors of size minorSize inside a pre-defined submatrix of an underlying (also pre-defined) matrix.

Parameters

minorSize

the size of the minor(s) of interest

See also

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

Definition at line 108 of file MinorProcessor.cc.

{
  _minorSize = minorSize;
  _minor.reset();
}

setNextKeys()

bool MinorProcessor::setNextKeys ( const int  k )

protected

A method for iterating through all possible subsets of k rows and k columns inside a pre-defined submatrix of a pre-defined matrix.

The method will set _rowKey and columnKey to represent the next possible subsets of k rows and columns inside the submatrix determined by _globalRowKey and _globalColumnKey.
When first called, this method will just shift _rowKey and _columnKey to point to the first sensible choices. Every subsequent call will move to the next _columnKey until there is no next. In this situation, a next _rowKey will be set, and _columnKey again to the first possible choice.
Finally, in case there is also no next _rowkey, the method returns false. (Otherwise true is returned.)

Parameters

k	the size of the minor / all minors of interest

Returns

true iff there is a next possible choice of rows and columns

Definition at line 169 of file MinorProcessor.cc.

{
  /* This method moves _minor to the next valid (k x k)-minor within
     _container. It returns true iff this is successful, i.e. iff
     _minor did not already encode the terminal (k x k)-minor. */
  if (_minor.compare(MinorKey(0, 0, 0, 0)) == 0)
  {
    /* This means that we haven't started yet. Thus, we are about
       to compute the first (k x k)-minor. */
    _minor.selectFirstRows(k, _container);
    _minor.selectFirstColumns(k, _container);
    return true;
  }
  else if (_minor.selectNextColumns(k, _container))
  {
    /* Here we were able to pick a next subset of columns
       within the same subset of rows. */
    return true;
  }
  else if (_minor.selectNextRows(k, _container))
  {
    /* Here we were not able to pick a next subset of columns
       within the same subset of rows. But we could pick a next
       subset of rows. We must hence reset the subset of columns: */
    _minor.selectFirstColumns(k, _container);
    return true;
  }
  else
  {
    /* We were neither able to pick a next subset
       of columns nor of rows. I.e., we have iterated through
       all sensible choices of subsets of rows and columns. */
    return false;
  }
}

toString()

string MinorProcessor::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 in IntMinorProcessor, and PolyMinorProcessor.

Definition at line 212 of file MinorProcessor.cc.

{
  assume(false);
  return "";
}

Field Documentation

_columns

int MinorProcessor::_columns

protected

private store for the number of columns in the underlying matrix

Definition at line 171 of file MinorProcessor.h.

_container

MinorKey MinorProcessor::_container

protected

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.

40 x 50) of a larger matrix (e.g. 70 x 100). This is useful when we would like to compute all minors of a given size (e.g. 4 x 4) inside such a pre-defined submatrix.

Definition at line 135 of file MinorProcessor.h.

_containerColumns

int MinorProcessor::_containerColumns

protected

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*).

Definition at line 149 of file MinorProcessor.h.

_containerRows

int MinorProcessor::_containerRows

protected

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*).

Definition at line 142 of file MinorProcessor.h.

_minor

MinorKey MinorProcessor::_minor

protected

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.

Definition at line 156 of file MinorProcessor.h.

_minorSize

int MinorProcessor::_minorSize

protected

private store for the dimension of the minor(s) of interest

Definition at line 161 of file MinorProcessor.h.

_rows

int MinorProcessor::_rows

protected

private store for the number of rows in the underlying matrix

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