My Project
Minor.h
Go to the documentation of this file.
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  */
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  */
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 
408 {
409  protected:
410  /**
411  * -1 iff cache is not used, otherwise the number of retrievals so far of
412  * the current minor
413  */
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  */
422 
423  /**
424  * a store for the actual number of multiplications to compute the current
425  * minor
426  */
428 
429  /**
430  * a store for the actual number of additions to compute the current minor
431  */
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  */
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  */
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  */
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 */
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 */
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:718
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1019
int _result
a store for the actual value of the minor
Definition: Minor.h:723
std::string toString() const
A method for providing a printable version of the represented MinorValue.
Definition: Minor.cc:1024
int getWeight() const
Accessor for the current weight of this class instance.
Definition: Minor.cc:980
virtual ~IntMinorValue()
Destructor.
Definition: Minor.cc:1015
IntMinorValue()
just to make the compiler happy
Definition: Minor.cc:1004
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.
Definition: Minor.h:40
MinorKey(const int lengthOfRowArray=0, const unsigned int *const rowKey=NULL, const int lengthOfColumnArray=0, const unsigned int *const columnKey=NULL)
A constructor for class MinorKey.
Definition: Minor.cc:84
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:302
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:287
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
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
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
~MinorKey()
A destructor for deleting an instance.
Definition: Minor.cc:104
bool operator==(const MinorKey &) const
just to make the compiler happy
Definition: Minor.cc:443
bool operator<(const MinorKey &) const
just to make the compiler happy
Definition: Minor.cc:451
void reset()
A method for deleting all entries of _rowKey and _columnKey.
Definition: Minor.cc:13
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
void selectFirstColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
Definition: Minor.cc:498
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
Definition: Minor.cc:343
void setColumnKey(const int blockIndex, const unsigned int columnKey)
A method for setting the blockIndex-th element of _columnKey.
Definition: Minor.cc:406
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
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
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
void setRowKey(const int blockIndex, const unsigned int rowKey)
A method for setting the blockIndex-th element of _rowKey.
Definition: Minor.cc:401
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:297
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
Definition: Minor.cc:223
bool selectNextRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
Definition: Minor.cc:538
MinorKey & operator=(const MinorKey &)
just to make the compiler happy
Definition: Minor.cc:39
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
Definition: Minor.cc:255
std::string toString() const
A method for providing a printable version of the represented MinorKey.
Definition: Minor.cc:800
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:412
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
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:292
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
Class MinorProcessor implements the key methods for computing one or all sub-determinantes of a given...
int getPotentialRetrievals() const
A method for accessing the maximum number of potential retrievals of this minor.
Definition: Minor.cc:878
int _additions
a store for the actual number of additions to compute the current minor
Definition: Minor.h:432
int rankMeasure4() const
A method for obtaining a rank measure for the given MinorValue.
Definition: Minor.cc:963
int getAdditions() const
A method for accessing the additions performed while computing this minor.
Definition: Minor.cc:888
int _potentialRetrievals
-1 iff cache is not used, otherwise the maximum number of potential retrievals of this minor (e....
Definition: Minor.h:421
int _accumulatedMult
a store for the accumulated number of multiplications to compute the current minor; This also include...
Definition: Minor.h:441
int rankMeasure2() const
A method for obtaining a rank measure for the given MinorValue.
Definition: Minor.cc:946
int _accumulatedSum
a store for the accumulated number of additions to compute the current minor; This also includes all ...
Definition: Minor.h:450
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
Definition: Minor.cc:898
int rankMeasure5() const
A method for obtaining a rank measure for the given MinorValue.
Definition: Minor.cc:972
STATIC_VAR int g_rankingStrategy
private store for the current value ranking strategy; This member can be set using MinorValue::SetRan...
Definition: Minor.h:541
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
Definition: Minor.cc:883
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition: Minor.cc:909
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
Definition: Minor.cc:873
bool operator==(const MinorValue &mv) const
just to make the compiler happy
Definition: Minor.cc:848
int rankMeasure3() const
A method for obtaining a rank measure for the given MinorValue.
Definition: Minor.cc:953
virtual int getWeight() const
A method for retrieving the weight of a given MinorValue.
Definition: Minor.cc:840
int _multiplications
a store for the actual number of multiplications to compute the current minor
Definition: Minor.h:427
int getUtility() const
A method for obtaining a rank measure for theiven MinorValue.
Definition: Minor.cc:926
int getRetrievals() const
A method for accessing the number of retrievals of this minor.
Definition: Minor.cc:868
int rankMeasure1() const
A method for obtaining a rank measure for the given MinorValue.
Definition: Minor.cc:940
int _retrievals
-1 iff cache is not used, otherwise the number of retrievals so far of the current minor
Definition: Minor.h:414
virtual std::string toString() const
A method for providing a printable version of the represented MinorValue.
Definition: Minor.cc:854
static int GetRankingStrategy()
Accessor for the static private field g_rankingStrategy.
Definition: Minor.cc:919
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
Definition: Minor.cc:893
bool operator<(const MinorValue &mv) const
just to make the compiler happy
Definition: Minor.cc:862
void print() const
A method for printing a string representation of the given MinorValue to std::cout.
Definition: Minor.cc:903
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:800
PolyMinorValue()
just to make the compiler happy
Definition: Minor.cc:1086
void operator=(const PolyMinorValue &mv)
Assignment operator which creates a deep copy.
Definition: Minor.cc:1159
virtual ~PolyMinorValue()
Destructor.
Definition: Minor.cc:1097
std::string toString() const
A method for providing a printable version of the represented MinorValue.
Definition: Minor.cc:1114
int getWeight() const
Accessor for the current weight of this class instance.
Definition: Minor.cc:1107
poly _result
a store for the actual value of the minor
Definition: Minor.h:805
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1102
return result
Definition: facAbsBiFact.cc:75
#define STATIC_VAR
Definition: globaldefs.h:7
#define string
Definition: libparse.cc:1252
#define NULL
Definition: omList.c:12
Compatiblity layer for legacy polynomial operations (over currRing)