My Project
|
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... | |
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:
Definition at line 57 of file MinorProcessor.h.
MinorProcessor::MinorProcessor | ( | ) |
The default constructor.
Definition at line 277 of file MinorProcessor.cc.
|
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.
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.
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 |
Definition at line 129 of file MinorProcessor.cc.
|
staticprotected |
A static method for computing the factorial of i.
i | an integer greater than or equal to 0 |
Definition at line 235 of file MinorProcessor.cc.
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
.)
k | the size of the minor / all minors of interest |
mk | the representation of rows and columns of the minor of interest |
Definition at line 57 of file MinorProcessor.cc.
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.
target | an int array to be filled with the column indices |
Definition at line 124 of file MinorProcessor.cc.
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.
target | an int array to be filled with the row indices |
Definition at line 119 of file MinorProcessor.cc.
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.
Definition at line 114 of file MinorProcessor.cc.
A static method for computing the binomial coefficient i over j.
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. |
Definition at line 218 of file MinorProcessor.cc.
|
protectedvirtual |
A method for testing whether a matrix entry is zero.
absoluteRowIndex | the absolute (zero-based) row index |
absoluteColumnIndex | the absolute (zero-based) column index |
Reimplemented in IntMinorProcessor, and PolyMinorProcessor.
Definition at line 205 of file MinorProcessor.cc.
|
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.
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 |
Definition at line 245 of file MinorProcessor.cc.
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.
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.
minorSize | the size of the minor(s) of interest |
Definition at line 108 of file MinorProcessor.cc.
|
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.)
k | the size of the minor / all minors of interest |
Definition at line 169 of file MinorProcessor.cc.
|
virtual |
A method for providing a printable version of the represented MinorProcessor.
Reimplemented in IntMinorProcessor, and PolyMinorProcessor.
Definition at line 212 of file MinorProcessor.cc.
|
protected |
private store for the number of columns in the underlying matrix
Definition at line 171 of file MinorProcessor.h.
|
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.
|
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.
|
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.
|
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.
|
protected |
private store for the dimension of the minor(s) of interest
Definition at line 161 of file MinorProcessor.h.
|
protected |
private store for the number of rows in the underlying matrix
Definition at line 166 of file MinorProcessor.h.