My Project
Loading...
Searching...
No Matches
Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes
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.

277 :
278 _container(0, NULL, 0, NULL),
279 _minor(0, NULL, 0, NULL),
282 _minorSize(0),
283 _rows(0),
284 _columns(0)
285{
286}
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
int _columns
private store for the number of columns in the underlying matrix
int _minorSize
private store for the dimension of the minor(s) of interest
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
int _rows
private store for the number of rows in the underlying matrix
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
#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.

288{ }

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
numberOfRowsthe number of rows in the sub-matrix
rowIndicesan array with the (0-based) indices of rows inside the pre-defined matrix
numberOfColumnsthe number of columns in the sub-matrix
columnIndicesan 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.

133{
134 /* The method assumes ascending row and column indices in the
135 two argument arrays. These indices are understood to be zero-based.
136 The method will set the two arrays of ints in _container.
137 Example: The indices 0, 2, 3, 7 will be converted to an array with
138 one int representing the binary number 10001101
139 (check bits from right to left). */
140
141 _containerRows = numberOfRows;
142 int highestRowIndex = rowIndices[numberOfRows - 1];
143 int rowBlockCount = (highestRowIndex / 32) + 1;
144 unsigned *rowBlocks=(unsigned*)omAlloc(rowBlockCount*sizeof(unsigned));
145 for (int i = 0; i < rowBlockCount; i++) rowBlocks[i] = 0;
146 for (int i = 0; i < numberOfRows; i++)
147 {
148 int blockIndex = rowIndices[i] / 32;
149 int offset = rowIndices[i] % 32;
150 rowBlocks[blockIndex] += (1 << offset);
151 }
152
153 _containerColumns = numberOfColumns;
154 int highestColumnIndex = columnIndices[numberOfColumns - 1];
155 int columnBlockCount = (highestColumnIndex / 32) + 1;
156 unsigned *columnBlocks=(unsigned*)omAlloc0(columnBlockCount*sizeof(unsigned));
157 for (int i = 0; i < numberOfColumns; i++)
158 {
159 int blockIndex = columnIndices[i] / 32;
160 int offset = columnIndices[i] % 32;
161 columnBlocks[blockIndex] += (1 << offset);
162 }
163
164 _container.set(rowBlockCount, rowBlocks, columnBlockCount, columnBlocks);
165 omFree(columnBlocks);
166 omFree(rowBlocks);
167}
int i
Definition: cfEzgcd.cc:132
void set(const int lengthOfRowArray, const unsigned int *rowKey, const int lengthOfColumnArray, const unsigned int *columnKey)
A setter method for class MinorKey.
Definition: Minor.cc:62
STATIC_VAR int offset
Definition: janet.cc:29
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211

◆ 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
ian integer greater than or equal to 0
Returns
the factorial of i

Definition at line 235 of file MinorProcessor.cc.

236{
237 /* This is a non-recursive implementation. */
238 assume(i >= 0);
239 int result = 1;
240 for (int j = 1; j <= i; j++) result *= j;
241 // Now, result = 1 * 2 * ... * i = i!
242 return result;
243}
return result
Definition: facAbsBiFact.cc:75
int j
Definition: facHensel.cc:110
#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
kthe size of the minor / all minors of interest
mkthe 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.

58{
59 /* This method identifies the row or column with the most zeros.
60 The returned index (bestIndex) is absolute within the pre-
61 defined matrix.
62 If some row has the most zeros, then the absolute (0-based)
63 row index is returned.
64 If, contrariwise, some column has the most zeros, then -1 minus
65 the absolute (0-based) column index is returned. */
66 int numberOfZeros = 0;
67 int bestIndex = 100000; /* We start with an invalid row/column index. */
68 int maxNumberOfZeros = -1; /* We update this variable whenever we find
69 a new so-far optimal row or column. */
70 for (int r = 0; r < k; r++)
71 {
72 /* iterate through all k rows of the momentary minor */
73 int absoluteR = mk.getAbsoluteRowIndex(r);
74 numberOfZeros = 0;
75 for (int c = 0; c < k; c++)
76 {
77 int absoluteC = mk.getAbsoluteColumnIndex(c);
78 if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
79 }
80 if (numberOfZeros > maxNumberOfZeros)
81 {
82 /* We found a new best line which is a row. */
83 bestIndex = absoluteR;
84 maxNumberOfZeros = numberOfZeros;
85 }
86 };
87 for (int c = 0; c < k; c++)
88 {
89 int absoluteC = mk.getAbsoluteColumnIndex(c);
90 numberOfZeros = 0;
91 for (int r = 0; r < k; r++)
92 {
93 int absoluteR = mk.getAbsoluteRowIndex(r);
94 if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
95 }
96 if (numberOfZeros > maxNumberOfZeros)
97 {
98 /* We found a new best line which is a column. So we transform
99 the return value. Note that we can easily retrieve absoluteC
100 from bestLine: absoluteC = - 1 - bestLine. */
101 bestIndex = - absoluteC - 1;
102 maxNumberOfZeros = numberOfZeros;
103 }
104 };
105 return bestIndex;
106}
int k
Definition: cfEzgcd.cc:99
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
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
virtual bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.

◆ 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
targetan int array to be filled with the column indices
See also
MinorProcessor::hasNextMinor ()

Definition at line 124 of file MinorProcessor.cc.

125{
126 return _minor.getAbsoluteColumnIndices(target);
127}
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
Definition: Minor.cc:202

◆ 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
targetan int array to be filled with the row indices
See also
MinorProcessor::hasNextMinor ()

Definition at line 119 of file MinorProcessor.cc.

120{
121 return _minor.getAbsoluteRowIndices(target);
122}
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey.
Definition: Minor.cc:181

◆ 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.

115{
116 return setNextKeys(_minorSize);
117}
bool setNextKeys(const int k)
A method for iterating through all possible subsets of k rows and k columns inside a pre-defined subm...

◆ 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
ia positive integer greater than or equal to j
ja 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.

219{
220 /* This is a non-recursive implementation. */
221 assume( (i >= 0) && (j >= 0) && (i >= j));
222 if (j == 0 || i == j) return 1;
223 #if 0
224 int result = 1;
225 for (int k = i - j + 1; k <= i; k++) result *= k;
226 /* Now, result = (i - j + 1) * ... * i. */
227 for (int k = 2; k <= j; k++) result /= k;
228 /* Now, result = (i - j + 1) * ... * i / 1 / 2 ...
229 ... / j = i! / j! / (i - j)!. */
230 return result;
231 #endif
232 return binom(i,j);
233}
int binom(int n, int r)

◆ isEntryZero()

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

A method for testing whether a matrix entry is zero.

Parameters
absoluteRowIndexthe absolute (zero-based) row index
absoluteColumnIndexthe 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.

207{
208 assume(false);
209 return false;
210}

◆ 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
rowsthe number of rows of the underlying matrix
columnsthe number of columns of the underlying matrix
containerMinorSizethe size of the container minor
minorSizethe size of the small minor (which may be retrieved multiple times)
multipleMinorsdecides 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.

249{
250 /* This method computes the number of potential retrievals
251 of a single minor when computing all minors of a given size
252 within a matrix of given size. */
253 int result = 0;
254 if (multipleMinors)
255 {
256 /* Here, we would like to compute all minors of size
257 containerMinorSize x containerMinorSize in a matrix
258 of size rows x columns.
259 Then, we need to retrieve any minor of size
260 minorSize x minorSize exactly n times, where n is as
261 follows: */
262 result = IOverJ(rows - minorSize, containerMinorSize - minorSize)
263 * IOverJ(columns - minorSize, containerMinorSize - minorSize)
264 * Faculty(containerMinorSize - minorSize);
265 }
266 else
267 {
268 /* Here, we would like to compute just one minor of size
269 containerMinorSize x containerMinorSize. Then, we need
270 to retrieve any minor of size minorSize x minorSize exactly
271 (containerMinorSize - minorSize)! times: */
272 result = Faculty(containerMinorSize - minorSize);
273 }
274 return result;
275}
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.

◆ 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.

53{
54 PrintS(this->toString().c_str());
55}
virtual std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
void PrintS(const char *s)
Definition: reporter.cc:284

◆ 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
minorSizethe 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.

109{
110 _minorSize = minorSize;
111 _minor.reset();
112}
void reset()
A method for deleting all entries of _rowKey and _columnKey.
Definition: Minor.cc:13

◆ 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
kthe 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.

170{
171 /* This method moves _minor to the next valid (k x k)-minor within
172 _container. It returns true iff this is successful, i.e. iff
173 _minor did not already encode the terminal (k x k)-minor. */
174 if (_minor.compare(MinorKey(0, 0, 0, 0)) == 0)
175 {
176 /* This means that we haven't started yet. Thus, we are about
177 to compute the first (k x k)-minor. */
180 return true;
181 }
183 {
184 /* Here we were able to pick a next subset of columns
185 within the same subset of rows. */
186 return true;
187 }
189 {
190 /* Here we were not able to pick a next subset of columns
191 within the same subset of rows. But we could pick a next
192 subset of rows. We must hence reset the subset of columns: */
194 return true;
195 }
196 else
197 {
198 /* We were neither able to pick a next subset
199 of columns nor of rows. I.e., we have iterated through
200 all sensible choices of subsets of rows and columns. */
201 return false;
202 }
203}
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.
Definition: Minor.h:40
void selectFirstRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
Definition: Minor.cc:457
bool selectNextColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
Definition: Minor.cc:669
void selectFirstColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
Definition: Minor.cc:498
bool selectNextRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
Definition: Minor.cc:538
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:412

◆ 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.

213{
214 assume(false);
215 return "";
216}

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: