1 | #ifndef MINOR_H |
---|
2 | #define MINOR_H |
---|
3 | |
---|
4 | #include "kernel/mod2.h" |
---|
5 | #include "polys/monomials/ring.h" |
---|
6 | #include "kernel/polys.h" |
---|
7 | |
---|
8 | // #include <assert.h> |
---|
9 | #include <string> |
---|
10 | |
---|
11 | |
---|
12 | // using namespace std; |
---|
13 | |
---|
14 | /*! \class MinorKey |
---|
15 | \brief Class MinorKey can be used for representing keys in a cache for |
---|
16 | sub-determinantes; see class Cache. |
---|
17 | |
---|
18 | As such, it is a realization of the template class KeyClass which is used |
---|
19 | in the declaration of class Cache. Following the documentation of class |
---|
20 | Cache, we need to implement at least the methods:<br> |
---|
21 | <c>bool MinorKey::operator< (const MinorKey& key),</c><br> |
---|
22 | <c>bool MinorKey::operator== (const MinorKey& key),</c><br> |
---|
23 | MinorKey uses two private arrays of ints \c _rowKey and \c _columnKey to |
---|
24 | encode rows and columns of a pre-defined matrix. Semantically, the row |
---|
25 | indices and column indices form the key for caching the value of the |
---|
26 | corresponding minor.<br> |
---|
27 | More concretely, let us assume that the pre-defined matrix has |
---|
28 | <em>32*R+r, r<32,</em> rows and <em>32*C+c, c<32,</em> columns. All row |
---|
29 | indices can then be captured using R+1 ints, since an int is a |
---|
30 | 32-bit-number (regardless of the platform). The analog holds for the |
---|
31 | columns. Consequently, each instance of MinorKey encodes the sets of rows |
---|
32 | and columns which shall belong to the minor of interest (and which shall |
---|
33 | not).<br> |
---|
34 | Example: The \c _rowKey with \c _rowKey[1] = 0...011 and |
---|
35 | \c _rowKey[0] = 0...01101 encodes the rows with indices 33, 32, 3, 2, |
---|
36 | and 0. |
---|
37 | \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch |
---|
38 | */ |
---|
39 | class MinorKey |
---|
40 | { |
---|
41 | private: |
---|
42 | /** |
---|
43 | * a pointer to an array[0..k-1] of ints, capturing k*32 bits for |
---|
44 | * determining which rows of a pre-defined matrix shall belong to the |
---|
45 | * minor of interest; |
---|
46 | * for i < j, _rowKey[i] holds lower bits than _rowKey[j] |
---|
47 | */ |
---|
48 | unsigned int* _rowKey; |
---|
49 | |
---|
50 | /** |
---|
51 | * a pointer to an array[0..k-1] of ints, capturing k*32 bits for |
---|
52 | * determining which columns of a pre-defined matrix shall belong to the |
---|
53 | * minor of interest; |
---|
54 | * for i < j, _columnKey[i] holds lower bits than _columnKey[j] |
---|
55 | */ |
---|
56 | unsigned int* _columnKey; |
---|
57 | |
---|
58 | /** |
---|
59 | * the number of ints (i.e. 32-bit-numbers) we need to encode the set of |
---|
60 | * rows; |
---|
61 | * If the higest row index is 70, we need 3 blocks of 32 bits to also |
---|
62 | * encode the 70th bit. |
---|
63 | */ |
---|
64 | int _numberOfRowBlocks; |
---|
65 | |
---|
66 | /** |
---|
67 | * the number of ints (i.e. 32-bit-numbers) we need to encode the set of |
---|
68 | * columns; |
---|
69 | * If the higest column index is 70, we need 3 blocks of 32 bits to also |
---|
70 | * encode the 70th bit. |
---|
71 | */ |
---|
72 | int _numberOfColumnBlocks; |
---|
73 | |
---|
74 | /** |
---|
75 | * Inlined accessor of blockIndex-th element of _rowKey. |
---|
76 | * @param blockIndex the index of the int to be retrieved |
---|
77 | * @return an entry of _rowKey |
---|
78 | */ |
---|
79 | unsigned int getRowKey (const int blockIndex) const; |
---|
80 | |
---|
81 | /** |
---|
82 | * Accessor of blockIndex-th element of _columnKey. |
---|
83 | * @param blockIndex the index of the int to be retrieved |
---|
84 | * @return an entry of _columnKey |
---|
85 | */ |
---|
86 | unsigned int getColumnKey (const int blockIndex) const; |
---|
87 | |
---|
88 | /** |
---|
89 | * A method for setting the blockIndex-th element of _rowKey. |
---|
90 | * @param blockIndex the index of the int to be retrieved |
---|
91 | * @param rowKey the row key to be set |
---|
92 | */ |
---|
93 | void setRowKey (const int blockIndex, const unsigned int rowKey); |
---|
94 | |
---|
95 | /** |
---|
96 | * A method for setting the blockIndex-th element of _columnKey. |
---|
97 | * @param blockIndex the index of the int to be retrieved |
---|
98 | * @param columnKey the column key to be set |
---|
99 | */ |
---|
100 | void setColumnKey (const int blockIndex, const unsigned int columnKey); |
---|
101 | |
---|
102 | /** |
---|
103 | * Accessor of _numberOfRowBlocks. |
---|
104 | * @return the number of 32-bit-blocks needed to encode all rows of the |
---|
105 | * minor as a sequence of bits |
---|
106 | */ |
---|
107 | int getNumberOfRowBlocks () const; |
---|
108 | |
---|
109 | /** |
---|
110 | * Accessor of _numberOfColumnBlocks. |
---|
111 | * @return the number of 32-bit-blocks needed to encode all columns of |
---|
112 | * the minor as a sequence of bits |
---|
113 | */ |
---|
114 | int getNumberOfColumnBlocks () const; |
---|
115 | |
---|
116 | /** |
---|
117 | * A method for deleting all entries of _rowKey and _columnKey. |
---|
118 | */ |
---|
119 | void reset(); |
---|
120 | |
---|
121 | #ifndef SING_NDEBUG |
---|
122 | /** |
---|
123 | * A method for counting the number of set bits. |
---|
124 | * For a == 1, the number of set bits in _rowKey will be counted; |
---|
125 | * for a == 2 in _columnKey. |
---|
126 | * This method will only be called in the debug version. |
---|
127 | * @param a for controlling whether to count in _rowKey or _columnKey |
---|
128 | * @return the number of set bits either in _rowKey or _columnKey |
---|
129 | */ |
---|
130 | int getSetBits (const int a) const; |
---|
131 | #endif |
---|
132 | |
---|
133 | /** |
---|
134 | * For letting MinorProcessor see the private methods of this class. |
---|
135 | */ |
---|
136 | friend class MinorProcessor; |
---|
137 | public: |
---|
138 | /** |
---|
139 | * A constructor for class MinorKey. |
---|
140 | * The ints given in the array rowKey encode all rows which shall belong |
---|
141 | * to the minor. Each array entry encodes 32 rows, e.g. the i-th array |
---|
142 | * entry 0...01101 encodes the rows with absolute matrix row indices |
---|
143 | * 3+i*32, 2+i*32, and 0+i*32. Analog for columns. |
---|
144 | * @param lengthOfRowArray the length of the array rowKey |
---|
145 | * @param rowKey a pointer to an array of ints encoding the set of rows of |
---|
146 | * the minor |
---|
147 | * @param lengthOfColumnArray the length of the array columnKey |
---|
148 | * @param columnKey a pointer to an array of ints encoding the set of |
---|
149 | + columns of the minor |
---|
150 | */ |
---|
151 | MinorKey (const int lengthOfRowArray = 0, |
---|
152 | const unsigned int* const rowKey = NULL, |
---|
153 | const int lengthOfColumnArray = 0, |
---|
154 | const unsigned int* const columnKey = NULL); |
---|
155 | |
---|
156 | /** |
---|
157 | * A setter method for class MinorKey. |
---|
158 | * Just like the constructor of this class, this method will set all |
---|
159 | * private fields according to the given parameters. Note that this method |
---|
160 | * will change the given instance of MinorKey. |
---|
161 | * @param lengthOfRowArray the length of the array rowKey |
---|
162 | * @param rowKey a pointer to an array of ints encoding the set of rows of |
---|
163 | * the minor |
---|
164 | * @param lengthOfColumnArray the length of the array columnKey |
---|
165 | * @param columnKey a pointer to an array of ints encoding the set of |
---|
166 | * columns of the minor |
---|
167 | * @see MinorKey::MinorKey (const int lengthOfRowArray, const int* rowKey, |
---|
168 | const int lengthOfColumnArray, |
---|
169 | const int* columnKey) |
---|
170 | */ |
---|
171 | void set(const int lengthOfRowArray, const unsigned int* rowKey, |
---|
172 | const int lengthOfColumnArray, const unsigned int* columnKey); |
---|
173 | |
---|
174 | /** |
---|
175 | * A copy constructor. |
---|
176 | * This method overrides the shallow copy constructor by a self-written |
---|
177 | * deep copy version. |
---|
178 | * @param mk the MinorKey to be deep copied |
---|
179 | */ |
---|
180 | MinorKey (const MinorKey& mk); |
---|
181 | |
---|
182 | /** |
---|
183 | * A destructor for deleting an instance. |
---|
184 | */ |
---|
185 | ~MinorKey (); |
---|
186 | |
---|
187 | /** |
---|
188 | * just to make the compiler happy |
---|
189 | */ |
---|
190 | MinorKey& operator=(const MinorKey&); |
---|
191 | |
---|
192 | /** |
---|
193 | * just to make the compiler happy |
---|
194 | */ |
---|
195 | bool operator==(const MinorKey&) const; |
---|
196 | |
---|
197 | /** |
---|
198 | * just to make the compiler happy |
---|
199 | */ |
---|
200 | bool operator<(const MinorKey&) const; |
---|
201 | |
---|
202 | /** |
---|
203 | * A method for retrieving the (0-based) index of the i-th row in the set |
---|
204 | * of rows encoded in \a this. |
---|
205 | * Lower values for \c i result in lower absolute row indices. |
---|
206 | * \par Example: |
---|
207 | * Applied to the row pattern 10010001101 and i = 3, we get the 0-based |
---|
208 | * index of the 3-rd set bit counted from the right, i.e. 7. |
---|
209 | * \par Assertion |
---|
210 | * The method assumes that there are at least \c i rows encoded in the |
---|
211 | * given MinorKey. |
---|
212 | * @param i the relative index of the row, as encoded in \a this |
---|
213 | * @return (0-based) absolute row index of the i-th row in \a this |
---|
214 | */ |
---|
215 | int getAbsoluteRowIndex (const int i) const; |
---|
216 | |
---|
217 | /** |
---|
218 | * A method for retrieving the (0-based) index of the i-th column in the |
---|
219 | * set of columns encoded in \a this. |
---|
220 | * Lower values for \c i result in lower absolute column indices. |
---|
221 | * \par Example: |
---|
222 | * Applied to the column pattern 10010001101 and i = 3, we get the 0-based |
---|
223 | * index of the 3-rd set bit counted from the right, i.e. 7. |
---|
224 | * \par Assertion |
---|
225 | * The method assumes that there are at least \c i columns encoded in the |
---|
226 | * given MinorKey. |
---|
227 | * @param i the relative index of the column, as encoded in \a this |
---|
228 | * @return (0-based) absolute column index of the i-th row in \a this |
---|
229 | */ |
---|
230 | int getAbsoluteColumnIndex (const int i) const; |
---|
231 | |
---|
232 | /** |
---|
233 | * A method for retrieving the (0-based) relative index of the i-th row |
---|
234 | * in \a this MinorKey. |
---|
235 | * Lower values for \c i result in lower relative row indices. Note that |
---|
236 | * the absolute index \c i is 0-based, too. |
---|
237 | * \par Example: |
---|
238 | * Applied to the row pattern 10010001101 and i = 7, we get the relative |
---|
239 | * 0-based position of the bit representing the absolute index 7, i.e. 3. |
---|
240 | * \par Assertion |
---|
241 | * The method assumes that the bit which corresponds to the absolute index |
---|
242 | * i is actually set. |
---|
243 | * @param i the absolute 0-based index of a row encoded in \a this |
---|
244 | * @return (0-based) relative row index corresponding to \c i |
---|
245 | */ |
---|
246 | int getRelativeRowIndex (const int i) const; |
---|
247 | |
---|
248 | /** |
---|
249 | * A method for retrieving the (0-based) relative index of the i-th column |
---|
250 | * in \a this MinorKey. |
---|
251 | * Lower values for \c i result in lower relative column indices. Note that |
---|
252 | * the absolute index \c i is 0-based, too. |
---|
253 | * \par Example: |
---|
254 | * Applied to the column pattern 10010001101 and i = 7, we get the |
---|
255 | * relative 0-based position of the bit representing the absolute index 7, |
---|
256 | * i.e. 3. |
---|
257 | * \par Assertion |
---|
258 | * The method assumes that the bit which corresponds to the absolute index |
---|
259 | * i is actually set. |
---|
260 | * @param i the absolute 0-based index of a column encoded in \a this |
---|
261 | * @return (0-based) relative column index corresponding to \c i |
---|
262 | */ |
---|
263 | int getRelativeColumnIndex (const int i) const; |
---|
264 | |
---|
265 | /** |
---|
266 | * A method for retrieving the 0-based indices of all rows encoded in \a |
---|
267 | * this MinorKey. |
---|
268 | * The user of this method needs to know the number of rows in \a this, |
---|
269 | * in order to know which indices in \c target[k] will be valid. |
---|
270 | * \par Example: |
---|
271 | * The bit pattern <c>0...01101</c> will give rise to the settings |
---|
272 | * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs |
---|
273 | * to know in advance that there are three rows in \a this MinorKey. |
---|
274 | * \par Assertion |
---|
275 | * The method assumes that target has enough positions for all rows |
---|
276 | * encoded in \a this MinorKey. |
---|
277 | * @param target a pointer to some array of ints that is to be filled with |
---|
278 | * the requested indices |
---|
279 | */ |
---|
280 | void getAbsoluteRowIndices(int* const target) const; |
---|
281 | |
---|
282 | /** |
---|
283 | * A method for retrieving the 0-based indices of all columns encoded in |
---|
284 | * \a this MinorKey. |
---|
285 | * The user of this method needs to know the number of columns in \a this, |
---|
286 | * in order to know which indices in \c target[k] will be valid. |
---|
287 | * \par Example: |
---|
288 | * The bit pattern <c>0...01101</c> will give rise to the settings |
---|
289 | * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs |
---|
290 | * to know in advance that there are three columns in \a this MinorKey. |
---|
291 | * \par Assertion |
---|
292 | * The method assumes that target has enough positions for all columns |
---|
293 | * encoded in \a this MinorKey. |
---|
294 | * @param target a pointer to some array of ints that is to be filled |
---|
295 | * with the requested indices |
---|
296 | */ |
---|
297 | void getAbsoluteColumnIndices(int* const target) const; |
---|
298 | |
---|
299 | /** |
---|
300 | * A method for retrieving a sub-MinorKey resulting from omitting one row |
---|
301 | * and one column of \a this MinorKey. |
---|
302 | * \par Assertion |
---|
303 | * The method assumes that the row with absolute index |
---|
304 | * \c absoluteEraseRowIndex (counted from lower bits to higher bits) and |
---|
305 | * the column with absolute index \c absoluteEraseColumnIndex are actually |
---|
306 | * set in \c mk. |
---|
307 | * @param absoluteEraseRowIndex the 0-based absolute index of a row in |
---|
308 | * \a mk |
---|
309 | * @param absoluteEraseColumnIndex the 0-based absolute index of a column |
---|
310 | * in \a mk |
---|
311 | * @return the MinorKey when omitting the specified row and column |
---|
312 | */ |
---|
313 | MinorKey getSubMinorKey (const int absoluteEraseRowIndex, |
---|
314 | const int absoluteEraseColumnIndex) const; |
---|
315 | |
---|
316 | /** |
---|
317 | * A comparator for two instances of MinorKey. |
---|
318 | * The ordering induced by this implementation determines the ordering of |
---|
319 | * all (key --> value) pairs in a cache that uses MinorKey as KeyClass. |
---|
320 | * @param mk a second MinorKey to be compared with \a this instance |
---|
321 | * @return -1 iff \a this instance is smaller than \a mk; 0 for equality; |
---|
322 | * +1 otherwise |
---|
323 | * @see MinorKey::operator== (const MinorKey&) const |
---|
324 | */ |
---|
325 | int compare (const MinorKey& mk) const; |
---|
326 | |
---|
327 | /** |
---|
328 | * This method redefines the set of rows represented by \a this MinorKey. |
---|
329 | * After the method, the defined set of rows coincides with the lowest |
---|
330 | * \c k rows of \c mk. (Here, lowest means w.r.t. indices.)<br> |
---|
331 | * Note that the method modifies the given instance of MinorKey. |
---|
332 | * \par Assertion |
---|
333 | * It is assumed that \c mk represents at least \c k rows. |
---|
334 | * @param k the number of rows |
---|
335 | * @param mk the MinorKey from which to choose the lowest \c k rows |
---|
336 | * @see MinorKey::selectNextRows (const int k, const MinorKey& mk) |
---|
337 | */ |
---|
338 | void selectFirstRows (const int k, const MinorKey& mk); |
---|
339 | |
---|
340 | /** |
---|
341 | * This method redefines the set of rows represented by \a this MinorKey. |
---|
342 | * Both the old and the new set of \c k rows are subsets of the rows |
---|
343 | * represented by \c mk. After the method, the defined set of rows is |
---|
344 | * the next sensible choice of \c k rows of \c mk. (Here, next means |
---|
345 | * the next w.r.t. the increasing index ordering on multi-indices of |
---|
346 | * natural numbers.)<br> |
---|
347 | * Note that the method modifies the given instance of MinorKey. |
---|
348 | * \par Assertion |
---|
349 | * It is assumed that \c mk represents at least \c k rows. Furthermore, |
---|
350 | * the method assumes that the old set of rows represented by \a this |
---|
351 | * is also a subset of the rows given by \c mk. |
---|
352 | * @param k the number of rows |
---|
353 | * @param mk the MinorKey from which to choose the lowest \c k rows |
---|
354 | * @return true iff there is a next choice of \c k rows |
---|
355 | * @see MinorKey::selectFirstRows (const int k, const MinorKey& mk) |
---|
356 | */ |
---|
357 | bool selectNextRows (const int k, const MinorKey& mk); |
---|
358 | |
---|
359 | /** |
---|
360 | * This method redefines the set of columns represented by \a this |
---|
361 | * MinorKey. |
---|
362 | * After the method, the defined set of columns coincides with the lowest |
---|
363 | * \c k columns of \c mk. (Here, lowest means w.r.t. indices.)<br> |
---|
364 | * Note that the method modifies the given instance of MinorKey. |
---|
365 | * \par Assertion |
---|
366 | * It is assumed that \c mk represents at least \c k columns. |
---|
367 | * @param k the number of columns |
---|
368 | * @param mk the MinorKey from which to choose the lowest \c k columns |
---|
369 | * @see MinorKey::selectNextColumns (const int k, const MinorKey& mk) |
---|
370 | */ |
---|
371 | void selectFirstColumns (const int k, const MinorKey& mk); |
---|
372 | |
---|
373 | /** |
---|
374 | * This method redefines the set of columns represented by \a this |
---|
375 | * MinorKey. |
---|
376 | * Both the old and the new set of \c k columns are subsets of the columns |
---|
377 | * represented by \c mk. After the method, the defined set of columns is |
---|
378 | * the next sensible choice of \c k columns of \c mk. (Here, next means |
---|
379 | * the next w.r.t. the increasing index ordering on multi-indices of |
---|
380 | * natural numbers.)<br> |
---|
381 | * Note that the method modifies the given instance of MinorKey. |
---|
382 | * \par Assertion |
---|
383 | * It is assumed that \c mk represents at least \c k columns. Furthermore, |
---|
384 | * the method assumes that the old set of columns represented by \a this |
---|
385 | * is also a subset of the columns given by \c mk. |
---|
386 | * @param k the number of columns |
---|
387 | * @param mk the MinorKey from which to choose the lowest \c k columns |
---|
388 | * @return true iff there is a next choice of \c k columns |
---|
389 | * @see MinorKey::selectFirstColumns (const int k, const MinorKey& mk) |
---|
390 | */ |
---|
391 | bool selectNextColumns (const int k, const MinorKey& mk); |
---|
392 | |
---|
393 | /** |
---|
394 | * A method for providing a printable version of the represented MinorKey. |
---|
395 | * @return a printable version of the given instance as instance of class |
---|
396 | * string |
---|
397 | */ |
---|
398 | std::string toString () const; |
---|
399 | |
---|
400 | /** |
---|
401 | * A method for printing a string representation of the given MinorKey to |
---|
402 | * std::cout. |
---|
403 | */ |
---|
404 | //void print () const; |
---|
405 | }; |
---|
406 | |
---|
407 | class MinorValue |
---|
408 | { |
---|
409 | protected: |
---|
410 | /** |
---|
411 | * -1 iff cache is not used, otherwise the number of retrievals so far of |
---|
412 | * the current minor |
---|
413 | */ |
---|
414 | int _retrievals; |
---|
415 | |
---|
416 | /** |
---|
417 | * -1 iff cache is not used, otherwise the maximum number of potential |
---|
418 | * retrievals of this minor (e.g. when the minor would be kept in cache |
---|
419 | * forever) |
---|
420 | */ |
---|
421 | int _potentialRetrievals; |
---|
422 | |
---|
423 | /** |
---|
424 | * a store for the actual number of multiplications to compute the current |
---|
425 | * minor |
---|
426 | */ |
---|
427 | int _multiplications; |
---|
428 | |
---|
429 | /** |
---|
430 | * a store for the actual number of additions to compute the current minor |
---|
431 | */ |
---|
432 | int _additions; |
---|
433 | |
---|
434 | /** |
---|
435 | * a store for the accumulated number of multiplications to compute the |
---|
436 | * current minor; |
---|
437 | * This also includes all multiplications nested in sub-minors which may be |
---|
438 | * retrieved from a cache. (Thus, these nested operations do not need to be |
---|
439 | * performed again.) |
---|
440 | */ |
---|
441 | int _accumulatedMult; |
---|
442 | |
---|
443 | /** |
---|
444 | * a store for the accumulated number of additions to compute the current |
---|
445 | * minor; |
---|
446 | * This also includes all additions nested in sub-minors which may be |
---|
447 | * retrieved from a cache. (Thus, these nested operations do not need to be |
---|
448 | * performed again.) |
---|
449 | */ |
---|
450 | int _accumulatedSum; |
---|
451 | |
---|
452 | /** |
---|
453 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
454 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
455 | * induced ordering |
---|
456 | * on MinorValues has an impact on the caching behaviour in a given cache: |
---|
457 | * Greater MinorValues will be cached longer than lower ones.<br> |
---|
458 | * More explicitely, this means: Make the return value of this method |
---|
459 | * greater, and the given MinorValue will be cached longer when caching |
---|
460 | * strategy 1 is deployed.<br> |
---|
461 | * Rank measure 1 is equal to the number of actually performed |
---|
462 | * multiplications to compute \a mv. |
---|
463 | * @return an integer rank measure of \c this |
---|
464 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
465 | */ |
---|
466 | int rankMeasure1 () const; |
---|
467 | |
---|
468 | /** |
---|
469 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
470 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
471 | * induced ordering on MinorValues has an impact on the caching behaviour |
---|
472 | * in a given cache: Greater MinorValues will be cached longer than lower |
---|
473 | * ones.<br> |
---|
474 | * More explicitely, this means: Make the return value of this method |
---|
475 | * greater, and the given MinorValue will be cached longer when caching |
---|
476 | * strategy 1 is deployed.<br> |
---|
477 | * Rank measure 2 is equal to the number of accumulated multiplications to |
---|
478 | * compute the given MinorValue. This also includes all nested |
---|
479 | * multiplications which were performed to compute all sub-minors which |
---|
480 | * could be reused from cache. |
---|
481 | * @return an integer rank measure of \c this |
---|
482 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
483 | */ |
---|
484 | int rankMeasure2 () const; |
---|
485 | |
---|
486 | /** |
---|
487 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
488 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
489 | * induced ordering on MinorValues has an impact on the caching behaviour |
---|
490 | * in a given cache: Greater MinorValues will be cached longer than lower |
---|
491 | * ones.<br> |
---|
492 | * More explicitely, this means: Make the return value of this method |
---|
493 | * greater, and the given MinorValue will be cached longer when caching |
---|
494 | * strategy 1 is deployed.<br> |
---|
495 | * Rank measure 3 is equal to the number of actually performed |
---|
496 | * multiplications, weighted with the ratio of not yet performed retrievals |
---|
497 | * over the maximum number of retrievals. |
---|
498 | * @return an integer rank measure of \c this |
---|
499 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
500 | */ |
---|
501 | int rankMeasure3 () const; |
---|
502 | |
---|
503 | /** |
---|
504 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
505 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
506 | * induced ordering on MinorValues has an impact on the caching behaviour |
---|
507 | * in a given cache: Greater MinorValues will be cached longer than lower |
---|
508 | * ones.<br> |
---|
509 | * More explicitely, this means: Make the return value of this method |
---|
510 | * greater, and the given MinorValue will be cached longer when caching |
---|
511 | * strategy 1 is deployed.<br> |
---|
512 | * Rank measure 4 is equal to the number of actually performed |
---|
513 | * multiplications, multiplied with the number of not yet performed |
---|
514 | * retrievals. |
---|
515 | * @return an integer rank measure of \c this |
---|
516 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
517 | */ |
---|
518 | int rankMeasure4 () const; |
---|
519 | |
---|
520 | /** |
---|
521 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
522 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
523 | * induced ordering on MinorValues has an impact on the caching behaviour |
---|
524 | * in a given cache: Greater MinorValues will be cached longer than lower |
---|
525 | * ones.<br> |
---|
526 | * More explicitely, this means: Make the return value of this method |
---|
527 | * greater, and the given MinorValue will be cached longer when caching |
---|
528 | * strategy 1 is deployed.<br> |
---|
529 | * Rank measure 5 is equal to the number of not yet performed retrievals. |
---|
530 | * This strategy tends to cache MinorValues longer which have a high |
---|
531 | * maximum number of potential retrievals. |
---|
532 | * @return an integer rank measure of \c this |
---|
533 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
534 | */ |
---|
535 | int rankMeasure5 () const; |
---|
536 | |
---|
537 | /** |
---|
538 | * private store for the current value ranking strategy; |
---|
539 | * This member can be set using MinorValue::SetRankingStrategy (const int). |
---|
540 | */ |
---|
541 | STATIC_VAR int g_rankingStrategy; |
---|
542 | |
---|
543 | /** |
---|
544 | * Accessor for the static private field g_rankingStrategy. |
---|
545 | */ |
---|
546 | static int GetRankingStrategy(); |
---|
547 | public: |
---|
548 | /** |
---|
549 | * just to make the compiler happy |
---|
550 | */ |
---|
551 | bool operator== (const MinorValue& mv) const; |
---|
552 | |
---|
553 | /** |
---|
554 | * just to make the compiler happy |
---|
555 | */ |
---|
556 | bool operator< (const MinorValue& mv) const; |
---|
557 | |
---|
558 | /** |
---|
559 | * A method for retrieving the weight of a given MinorValue. |
---|
560 | * The implementation of Cache uses this function to determine the total |
---|
561 | * weight of an entire cache. As the user can instantiate Cache by |
---|
562 | * determining its maximum total weight |
---|
563 | * (see Cache::Cache(const int, const int)), |
---|
564 | * the definition of weight of a MinorValue |
---|
565 | * may have an impact on the behaviour of the cache. |
---|
566 | * @return the weight of a given instance of MinorValue |
---|
567 | * @see Cache::getWeight () const |
---|
568 | */ |
---|
569 | virtual int getWeight () const; |
---|
570 | |
---|
571 | /** |
---|
572 | * A method for accessing the number of retrievals of this minor. Multiple |
---|
573 | * retrievals will occur when computing large minors by means of cached |
---|
574 | * sub-minors. (Then, the latter ones may be retrieved multiple times.) |
---|
575 | * @return the number of retrievals of this minor |
---|
576 | * @see MinorValue::getPotentialRetrievals () const |
---|
577 | */ |
---|
578 | int getRetrievals () const; |
---|
579 | |
---|
580 | /** |
---|
581 | * A method for accessing the maximum number of potential retrievals of |
---|
582 | * this minor. Multiple retrievals will occur when computing large minors |
---|
583 | * by means of cached sub-minors. (Then, the latter ones may be retrieved |
---|
584 | * multiple times.) |
---|
585 | * @return the maximum number of potential retrievals of this minor |
---|
586 | * @see MinorValue::getRetrievals () const |
---|
587 | */ |
---|
588 | int getPotentialRetrievals () const; |
---|
589 | |
---|
590 | /** |
---|
591 | * A method for accessing the multiplications performed while computing |
---|
592 | * this minor. |
---|
593 | * Due to multiplication with zero entries of the underlying matrix, some |
---|
594 | * sub-minors may be irrelevant. In this case, the multiplications needed |
---|
595 | * to compute these sub-minors will not be counted (, as they need not be |
---|
596 | * performed). |
---|
597 | * Moreover, multiplications that were needed to compute cached sub-minors |
---|
598 | * will not be counted either, as the value of those sub-minors can be |
---|
599 | * directly retrieved from the cache. |
---|
600 | * @return the number of multiplications performed |
---|
601 | * @see MinorValue::getAccumulatedMultiplications () const |
---|
602 | */ |
---|
603 | int getMultiplications () const; |
---|
604 | |
---|
605 | /** |
---|
606 | * A method for accessing the multiplications performed while computing |
---|
607 | * this minor, including all nested multiplications. |
---|
608 | * Contrary to MinorValue::getMultiplications () const, this method will |
---|
609 | * also count multiplications needed to compute all cached sub-minors |
---|
610 | * (, although they need not be performed again in order to compute the |
---|
611 | * given instance of MinorValue). |
---|
612 | * @return the number of multiplications performed, including nested |
---|
613 | * multiplications |
---|
614 | * @see MinorValue::getMultiplications () const |
---|
615 | */ |
---|
616 | int getAccumulatedMultiplications () const; |
---|
617 | |
---|
618 | /** |
---|
619 | * A method for accessing the additions performed while computing this |
---|
620 | * minor. |
---|
621 | * Additions that were needed to compute cached sub-minors will not be |
---|
622 | * counted, as the value of those sub-minors can be directly retrieved |
---|
623 | * from the cache. |
---|
624 | * @return the number of additions performed |
---|
625 | * @see MinorValue::getAccumulatedAdditions () const |
---|
626 | */ |
---|
627 | int getAdditions () const; |
---|
628 | |
---|
629 | /** |
---|
630 | * A method for accessing the additions performed while computing this |
---|
631 | * minor, including all nested additions. |
---|
632 | * Contrary to MinorValue::getAdditions () const, this method will also |
---|
633 | * count additions needed to compute all cached sub-minors (, although |
---|
634 | * they need not be performed again in order to compute the given instance |
---|
635 | * of MinorValue). |
---|
636 | * @return the number of additions performed, including nested additions |
---|
637 | * @see MinorValue::getAdditions () const |
---|
638 | */ |
---|
639 | int getAccumulatedAdditions () const; |
---|
640 | |
---|
641 | /** |
---|
642 | * A method for incrementing the number of performed retrievals of \a this |
---|
643 | * instance of MinorValue.<br> |
---|
644 | * Note that, when calling MinorValue::incrementRetrievals () for some |
---|
645 | * instance \a mv of MinorValue which has been cached in a Cache under |
---|
646 | * MinorKey \a mk, the user should be careful: After incrementing the |
---|
647 | * number of retrievals for \a mv, the user should always put the value |
---|
648 | * again into cache, i.e. should perform |
---|
649 | * Cache::put (const KeyClass&, const ValueClass&) |
---|
650 | * with \a mk and the modified \a mv as arguments. This is due to the fact |
---|
651 | * that changing the number of performed retrievals of a MinorValue may |
---|
652 | * have an impact on its ranking in Cache. Only by calling |
---|
653 | * Cache::put (const KeyClass&, const ValueClass&) can the user ensure |
---|
654 | * that the pair (\a mk --> \a mv) will be correctly re-positioned within |
---|
655 | * the Cache. |
---|
656 | */ |
---|
657 | void incrementRetrievals (); |
---|
658 | |
---|
659 | /** |
---|
660 | * A method for obtaining a rank measure for theiven MinorValue.<br> |
---|
661 | * Rank measures are used to compare any two instances of MinorValue. The |
---|
662 | * induced ordering on MinorValues has an impact on the caching behaviour |
---|
663 | * of the underlying cache: Greater MinorValues will be cached longer than |
---|
664 | * lower ones.<br> |
---|
665 | * More explicitely, this means: Make the return value of this method |
---|
666 | * greater, and the given MinorValue will be cached longer.<br> |
---|
667 | * Internally, this method will call one of several implementations, |
---|
668 | * depending on the pre-defined caching strategy; see |
---|
669 | * MinorProcessor::SetCacheStrategy (const int). |
---|
670 | * @return an integer rank measure of \c this |
---|
671 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
672 | * @see MinorProcessor::SetCacheStrategy (const int) |
---|
673 | */ |
---|
674 | int getUtility () const; |
---|
675 | |
---|
676 | /** |
---|
677 | * A method for determining the value ranking strategy.<br> |
---|
678 | * This setting has a direct effect on how long the given MinorValue |
---|
679 | * will be cached in any cache that uses MinorValue to represent its |
---|
680 | * cached values. |
---|
681 | * @param rankingStrategy an int, so far one of 1, 2, ..., 5 |
---|
682 | */ |
---|
683 | static void SetRankingStrategy (const int rankingStrategy); |
---|
684 | |
---|
685 | /** |
---|
686 | * A method for providing a printable version of the represented MinorValue. |
---|
687 | * @return a printable version of the given instance as instance of class |
---|
688 | * string |
---|
689 | */ |
---|
690 | virtual std::string toString () const; |
---|
691 | |
---|
692 | /** |
---|
693 | * A method for printing a string representation of the given MinorValue |
---|
694 | * to std::cout. |
---|
695 | */ |
---|
696 | void print () const; |
---|
697 | }; |
---|
698 | |
---|
699 | /*! \class IntMinorValue |
---|
700 | \brief Class IntMinorValue is derived from MinorValue and can be used for |
---|
701 | representing values in a cache for sub-determinantes; see class Cache. |
---|
702 | |
---|
703 | As such, it is a realization of the template class ValueClass which is |
---|
704 | used in the declaration of class Cache. Following the documentation of |
---|
705 | class Cache, we need to implement at least the methods:<br> |
---|
706 | <c>bool IntMinorValue::operator< (const IntMinorValue& key),</c><br> |
---|
707 | <c>bool IntMinorValue::operator== (const IntMinorValue& key),</c><br> |
---|
708 | <c>int IntMinorValue::getWeight ().</c><br><br> |
---|
709 | The main purpose of IntMinorValue is to represent values of |
---|
710 | sub-determinantes of a pre-defined matrix. Class MinorKey is used to |
---|
711 | determine which rows and columns of this pre-defined matrix ought to |
---|
712 | belong to the respective sub-determinante of interest. So far, |
---|
713 | IntMinorValue is just an example implementation which assumes matrices |
---|
714 | with int entries, such that the result of any minor is again an int. |
---|
715 | \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch |
---|
716 | */ |
---|
717 | class IntMinorValue : public MinorValue |
---|
718 | { |
---|
719 | private: |
---|
720 | /** |
---|
721 | * a store for the actual value of the minor |
---|
722 | */ |
---|
723 | int _result; |
---|
724 | public: |
---|
725 | /** |
---|
726 | * A constructor for class MinorValue. |
---|
727 | * @param result the actual value of the represented minor |
---|
728 | * @param multiplications number of multiplications to compute \a this |
---|
729 | minor |
---|
730 | * @param additions number of additions to compute \a this minor |
---|
731 | * @param accumulatedMultiplications number of multiplications to compute |
---|
732 | \a this minor, including nested operations |
---|
733 | * @param accumulatedAdditions number of additions to compute \a this minor, |
---|
734 | including nested operations |
---|
735 | * @param retrievals number of times this minor has been retrieved from |
---|
736 | cache |
---|
737 | * @param potentialRetrievals maximum number of times this minor may be |
---|
738 | retrieved from cache |
---|
739 | */ |
---|
740 | IntMinorValue (const int result, const int multiplications, |
---|
741 | const int additions, |
---|
742 | const int accumulatedMultiplications, |
---|
743 | const int accumulatedAdditions, const int retrievals, |
---|
744 | const int potentialRetrievals); |
---|
745 | |
---|
746 | /** |
---|
747 | * Copy constructor |
---|
748 | */ |
---|
749 | IntMinorValue (const IntMinorValue& mv); |
---|
750 | |
---|
751 | /** |
---|
752 | * just to make the compiler happy |
---|
753 | */ |
---|
754 | IntMinorValue (); |
---|
755 | |
---|
756 | /** |
---|
757 | * Destructor |
---|
758 | */ |
---|
759 | virtual ~IntMinorValue (); |
---|
760 | |
---|
761 | /** |
---|
762 | * Accessor for the private field _result. |
---|
763 | * @result the result encoded in this class instance |
---|
764 | */ |
---|
765 | int getResult() const; |
---|
766 | |
---|
767 | /** |
---|
768 | * Accessor for the current weight of this class instance. |
---|
769 | * @result the current weight of this class instance |
---|
770 | */ |
---|
771 | int getWeight () const; |
---|
772 | |
---|
773 | /** |
---|
774 | * A method for providing a printable version of the represented MinorValue. |
---|
775 | * @return a printable version of the given instance as instance of class |
---|
776 | * string |
---|
777 | */ |
---|
778 | std::string toString () const; |
---|
779 | }; |
---|
780 | |
---|
781 | /*! \class PolyMinorValue |
---|
782 | \brief Class PolyMinorValue is derived from MinorValue and can be used for |
---|
783 | representing values in a cache for sub-determinantes; see class Cache. |
---|
784 | |
---|
785 | As such, it is a realization of the template class ValueClass which is |
---|
786 | used in the declaration of class Cache. Following the documentation of |
---|
787 | class Cache, we need to implement at least the methods:<br> |
---|
788 | <c>bool IntMinorValue::operator< (const IntMinorValue& key),</c><br> |
---|
789 | <c>bool IntMinorValue::operator== (const IntMinorValue& key),</c><br> |
---|
790 | <c>int IntMinorValue::getWeight ().</c><br><br> |
---|
791 | The main purpose of PolyMinorValue is to represent values of |
---|
792 | sub-determinantes of a pre-defined matrix. Class MinorKey is used to |
---|
793 | determine which rows and columns of this pre-defined matrix ought to |
---|
794 | belong to the respective sub-determinante of interest. PolyMinorValue is |
---|
795 | a special implementation which assumes matrices with polynomial entries, |
---|
796 | such that the result of any minor is again a polynomial. |
---|
797 | \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch |
---|
798 | */ |
---|
799 | class PolyMinorValue : public MinorValue |
---|
800 | { |
---|
801 | private: |
---|
802 | /** |
---|
803 | * a store for the actual value of the minor |
---|
804 | */ |
---|
805 | poly _result; |
---|
806 | public: |
---|
807 | /** |
---|
808 | * A constructor for class MinorValue. |
---|
809 | * @param result the actual value of the represented minor |
---|
810 | * @param multiplications number of multiplications to compute \a this |
---|
811 | minor |
---|
812 | * @param additions number of additions to compute \a this minor |
---|
813 | * @param accumulatedMultiplications number of multiplications to compute |
---|
814 | \a this minor, including nested operations |
---|
815 | * @param accumulatedAdditions number of additions to compute \a this |
---|
816 | minor, including nested operations |
---|
817 | * @param retrievals number of times this minor has been retrieved from |
---|
818 | cache |
---|
819 | * @param potentialRetrievals maximum number of times this minor may be |
---|
820 | retrieved from cache |
---|
821 | */ |
---|
822 | PolyMinorValue (const poly result, const int multiplications, |
---|
823 | const int additions, |
---|
824 | const int accumulatedMultiplications, |
---|
825 | const int accumulatedAdditions, const int retrievals, |
---|
826 | const int potentialRetrievals); |
---|
827 | |
---|
828 | /** |
---|
829 | * Copy constructor for creating a deep copy. |
---|
830 | */ |
---|
831 | PolyMinorValue (const PolyMinorValue& mv); |
---|
832 | |
---|
833 | /** |
---|
834 | * Assignment operator which creates a deep copy. |
---|
835 | */ |
---|
836 | void operator= (const PolyMinorValue& mv); |
---|
837 | |
---|
838 | /** |
---|
839 | * just to make the compiler happy |
---|
840 | */ |
---|
841 | PolyMinorValue (); |
---|
842 | |
---|
843 | /** |
---|
844 | * Destructor |
---|
845 | */ |
---|
846 | virtual ~PolyMinorValue (); |
---|
847 | |
---|
848 | /** |
---|
849 | * Accessor for the private field _result. |
---|
850 | * @result the result encoded in this class instance |
---|
851 | */ |
---|
852 | poly getResult() const; |
---|
853 | |
---|
854 | /** |
---|
855 | * Accessor for the current weight of this class instance. |
---|
856 | * @result the current weight of this class instance |
---|
857 | */ |
---|
858 | int getWeight () const; |
---|
859 | |
---|
860 | /** |
---|
861 | * A method for providing a printable version of the represented MinorValue. |
---|
862 | * @return a printable version of the given instance as instance of class |
---|
863 | * string |
---|
864 | */ |
---|
865 | std::string toString () const; |
---|
866 | }; |
---|
867 | |
---|
868 | #endif |
---|
869 | /* MINOR_H */ |
---|