Loading...
Searching...
No Matches
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.
virtual | ~MinorProcessor ()
| A destructor for deleting an instance.
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.
void | setMinorSize (const int minorSize)
| Sets the size of the minor(s) of interest.
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.
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.
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.
virtual std::string | toString () const
| A method for providing a printable version of the represented MinorProcessor.
void | print () const
| A method for printing a string representation of the given MinorProcessor to std::cout.

## 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.
int | getBestLine (const int k, const MinorKey &mk) const
| A method for identifying the row or column with the most zeros.
virtual bool | isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
| A method for testing whether a matrix entry is zero.

## 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.
static int | IOverJ (const int i, const int j)
| A static method for computing the binomial coefficient i over j.
static int | Faculty (const int i)
| A static method for computing the factorial of i.

## 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.
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*).
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*).
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.
int | _minorSize
| private store for the dimension of the minor(s) of interest
int | _rows
| private store for the number of rows in the underlying matrix
int | _columns
| private store for the number of columns in the underlying matrix

## 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::_minor
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
Definition MinorProcessor.h:156
MinorProcessor::_containerRows
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
Definition MinorProcessor.h:142
MinorProcessor::_columns
int _columns
private store for the number of columns in the underlying matrix
Definition MinorProcessor.h:171
MinorProcessor::_minorSize
int _minorSize
private store for the dimension of the minor(s) of interest
Definition MinorProcessor.h:161
MinorProcessor::_container
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
Definition MinorProcessor.h:135
MinorProcessor::_rows
int _rows
private store for the number of rows in the underlying matrix
Definition MinorProcessor.h:166
MinorProcessor::_containerColumns
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
Definition MinorProcessor.h:149
NULL
#define NULL
Definition omList.c:12

## ~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);
}
i
int i
Definition cfEzgcd.cc:132
offset
STATIC_VAR int offset
Definition janet.cc:29
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211

## Faculty()

int MinorProcessor::Faculty | ( | const int | i | ) |

static protected

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;
}
result
return result
Definition facAbsBiFact.cc:76
j
int j
Definition facHensel.cc:110
assume
#define assume(x)
Definition mod2.h:389

## 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;
}
k
int k
Definition cfEzgcd.cc:99
MinorKey::getAbsoluteColumnIndex
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this.
Definition Minor.cc:149
MinorKey::getAbsoluteRowIndex
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this.
Definition Minor.cc:117
MinorProcessor::isEntryZero
virtual bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
Definition MinorProcessor.cc:205

## 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);
}
MinorProcessor::setNextKeys
bool setNextKeys(const int k)
A method for iterating through all possible subsets of k rows and k columns inside a pre-defined subm...
Definition MinorProcessor.cc:169

## IOverJ()

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

static protected

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);
}
binom
int binom(int n, int r)
Definition simpleideals.cc:1212

## isEntryZero()

bool MinorProcessor::isEntryZero | ( | const int | absoluteRowIndex,
|  | const int | absoluteColumnIndex ) const

protected virtual

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 )

static protected

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;
}
MinorProcessor::IOverJ
static int IOverJ(const int i, const int j)
A static method for computing the binomial coefficient i over j.
Definition MinorProcessor.cc:218
MinorProcessor::Faculty
static int Faculty(const int i)
A static method for computing the factorial of i.
Definition MinorProcessor.cc:235

## 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());
}
MinorProcessor::toString
virtual std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
Definition MinorProcessor.cc:212
PrintS
void PrintS(const char *s)
Definition reporter.cc:288

## 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