source: git/Singular/MinorProcessor.h @ 95a6f3

spielwiese
Last change on this file since 95a6f3 was 95a6f3, checked in by Frank Seelisch <seelisch@…>, 14 years ago
more functionality: compute int minors modulo p git-svn-id: file:///usr/local/Singular/svn/trunk@12182 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 24.3 KB
Line 
1#ifndef MINOR_PROCESSOR_H
2#define MINOR_PROCESSOR_H
3
4#ifdef HAVE_MINOR
5
6#include <Cache.h>
7#include <Minor.h>
8#include <assert.h>
9#include <string>
10
11/*! \class MinorProcessor
12    \brief Class MinorProcessor implements the key methods for computing one or all sub-determinantes of
13    a given size in a pre-defined matrix; either without cache or using a cache.
14
15    After defining the entire matrix (e.g. 10 x 14) using<br>
16    MinorProcessor::defineMatrix (const int, const int, const int*),<br>
17    the user may do two different things:<br>
18    1. He/she can simply compute a minor in this matrix using<br>
19    MinorProcessor::getMinor (const int, const int*, const int*, Cache<MinorKey, MinorValue>&), or<br>
20    MinorProcessor::getMinor (const int, const int*, const int*);<br>
21    depending on whether a cache shall or shall not be used, respectively.<br>
22    In this first alternative, the user simply provides all row and column indices of the minor.
23    2. He/she may define a smaller sub-matrix (e.g. 8 x 7) using
24    MinorValue::defineSubMatrix (const int, const int*, const int, const int*).
25    Afterwards, he/she may compute all minors of an even smaller size (e.g. 5 x 5) that consist exclusively of rows and
26    columns of this (8 x 7) sub-matrix (inside the entire 10 x 14 matrix).<br>
27    The implementation at hand eases the iteration over all such minors. Also in the
28    second case there are both implementations, i.e., with and without the usage of a cache.<br><br>
29    MinorProcessor makes use of MinorKey, MinorValue, and Cache. Therefore, it only works for matrices with integer
30    entries. But the implementation of all mentioned classes (MinorKey, MinorValue, and MinorProcessor) is in this
31    respect generic enough to quickly replace integer matrix entries by any other kind of objects (which only need
32    to implement binary addition and multiplication).<br>
33    Elements of any ring, such as polynomial rings, are canonical choices for such objects.
34    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
35*/
36class MinorProcessor {
37    protected:
38        /**
39        * A static method for computing the maximum number of retrievals of a minor.<br>
40        * More concretely, we are given a matrix of size \c rows x \c columns. We furthermore assume that
41        * we have - as part of this matrix - a minor of size \c containerMinorSize x \c containerMinorSize.
42        * Now we are interested in the number of times a minor of yet smaller size \c minorSize x \c minorSize
43        * will be needed when we compute the containerMinor by Laplace's Theorem.<br>
44        * The method returns the combinatorial results for both cases: containerMinor is fixed within the
45        * matrix (<c>multipleMinors == false</c>), or it can vary inside the matrix (<c>multipleMinors == true</c>).<br>
46        * The notion is here that we want to cache the small minor of size \c minorSize x \c minorSize, i.e.
47        * compute it just once.
48        * @param rows the number of rows of the underlying matrix
49        * @param columns the number of columns of the underlying matrix
50        * @param containerMinorSize the size of the container minor
51        * @param minorSize the size of the small minor (which may be retrieved multiple times)
52        * @param multipleMinors decides whether containerMinor is fixed within the underlying matrix or not
53        * @return the number of times, the small minor will be needed when computing one or all containerMinors
54        */
55        static int NumberOfRetrievals (const int rows, const int columns, const int containerMinorSize,
56                                       const int minorSize, const bool multipleMinors);
57        /**
58        * A static method for computing the binomial coefficient i over j.
59        * \par Assert
60        * The method checks whether <em>i >= j >= 0</em>.
61        * @param i a positive integer greater than or equal to \a j
62        * @param j a positive integer less than or equal to \a i, and greater than or equal to \e 0.
63        * @return the binomial coefficient i over j
64        */
65        static int IOverJ (const int i, const int j);
66
67        /**
68        * A static method for computing the factorial of i.
69        * \par Assert
70        * The method checks whether <em>i >= 0</em>.
71        * @param i an integer greater than or equal to \a 0
72        * @return the factorial of i
73        */
74        static int Faculty (const int i);
75
76        /**
77        * A method for iterating through all possible subsets of \c k rows and \c k columns inside a pre-defined
78        * submatrix of a pre-defined matrix.<br>
79        * The method will set \c _rowKey and \c columnKey to represent the
80        * next possbile subsets of \c k rows and columns inside the submatrix
81        * determined by \c _globalRowKey and \c _globalColumnKey.<br>
82        * When first called, this method will just shift \c _rowKey and \c _columnKey to point to the first
83        * sensible choices. Every subsequent call will move to the next \c _columnKey until there is no next.
84        * In this situation, a next \c _rowKey will be set, and \c _columnKey again to the first possible choice.<br>
85        * Finally, in case there is also no next \c _rowkey, the method returns \c false. (Otherwise \c true is returned.)
86        * @param k the size of the minor / all minors of interest
87        * @return true iff there is a next possible choice of rows and columns
88        */
89        bool setNextKeys (const int k);
90
91        /**
92        * private store for the rows and columns of the container minor within the underlying matrix;
93        * \c _container will be used to fix a submatrix (e.g. 40 x 50) of a larger matrix (e.g. 70 x 100).
94        * This is usefull when we would like to compute all minors of a given size (e.g. 4 x 4) inside
95        * such a pre-defined submatrix.
96        */
97        MinorKey _container;
98
99        /**
100        * private store for the number of rows in the container minor;
101        * This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*).
102        */
103        int _containerRows;
104
105        /**
106        * private store for the number of columns in the container minor;
107        * This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*).
108        */
109        int _containerColumns;
110
111        /**
112        * private store for the rows and columns of the minor of interest;
113        * Usually, this minor will encode subsets of the rows and columns in _container.
114        */
115        MinorKey _minor;
116
117        /**
118        * private store for the dimension of the minor(s) of interest
119        */
120        int _minorSize;
121
122        /**
123        * private store for the number of rows in the underlying matrix
124        */
125        int _rows;
126
127        /**
128        * private store for the number of column in the underlying matrix
129        */
130        int _columns;
131       
132        /**
133        * A method for identifying the row or column with the most zeros.<br>
134        * Using Laplace's Theorem, a minor can more efficiently be computed when developing along this best line.
135        * The returned index \c bestIndex is 0-based within the pre-defined matrix. If some row has the most zeros,
136        * then the (0-based) row index is returned. If, contrarywise, some column has the most zeros, then
137        * <c>x = - 1 - c</c> where \c c is the column index, is returned. (Note that in this case \c c can be
138        * reconstructed by computing <c>c = - 1 - x</c>.)
139        * @param k the size of the minor / all minors of interest
140        * @param mk the representation of rows and columns of the minor of interest
141        * @return an int encoding which row or column has the most zeros
142        */
143        int getBestLine (const int k, const MinorKey& mk) const;
144       
145        virtual bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const;
146    public:
147        MinorProcessor ();
148        /**
149        * A method for defining a sub-matrix within a pre-defined matrix.
150        * @param numberOfRows the number of rows in the sub-matrix
151        * @param rowIndices an array with the (0-based) indices of rows inside the pre-defined matrix
152        * @param numberOfColumns the number of columns in the sub-matrix
153        * @param columnIndices an array with the (0-based) indices of columns inside the pre-defined matrix
154        * @see MinorValue::defineMatrix (const int, const int, const int*)
155        */
156        void defineSubMatrix (const int numberOfRows, const int* rowIndices,
157                              const int numberOfColumns, const int* columnIndices);
158
159        /**
160        * Sets the size of the minor(s) of interest.<br>
161        * This method needs to be performed before beginning to compute all minors of size \a minorSize
162        * inside a pre-defined submatrix of an underlying (also pre-defined) matrix.
163        * @param minorSize the size of the minor(s) of interest
164        * @see MinorValue::defineSubMatrix (const int, const int*, const int, const int*)
165        */
166        void setMinorSize (const int minorSize);
167
168        /**
169        * A method for checking whether there is a next choice of rows and columns when iterating
170        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
171        * The number of rows and columns has to be set before using
172        * MinorValue::setMinorSize(const int).<br>
173        * After calling MinorValue::hasNextMinor (), the current sets of rows and columns may be
174        * inspected using MinorValue::getCurrentRowIndices(int* const) const and
175        * MinorValue::getCurrentColumnIndices(int* const) const.
176        * @return true iff there is a next choice of rows and columns
177        * @see MinorProcessor::getMinor (const int, const int*, const int*)
178        * @see MinorValue::getCurrentRowIndices(int* const) const
179        * @see MinorValue::getCurrentColumnIndices(int* const) const
180        */
181        bool hasNextMinor ();
182
183        /**
184        * A method for obtaining the current set of rows corresponding to the current minor when iterating
185        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
186        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
187        * \c true.<br>
188        * The user of this method needs to know the number of rows in order to know which entries of the
189        * newly filled \c target will be valid.
190        * @param target an int array to be filled with the row indices
191        * @see MinorProcessor::hasNextMinor ()
192        */
193        void getCurrentRowIndices (int* const target) const;
194
195        /**
196        * A method for obtaining the current set of columns corresponding to the current minor when iterating
197        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
198        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
199        * \c true.<br>
200        * The user of this method needs to know the number of columns in order to know which entries of the
201        * newly filled \c target will be valid.
202        * @param target an int array to be filled with the column indices
203        * @see MinorProcessor::hasNextMinor ()
204        */
205        void getCurrentColumnIndices (int* const target) const;
206
207        /**
208        * A method for providing a printable version of the represented MinorProcessor.
209        * @return a printable version of the given instance as instance of class string
210        */
211        virtual string toString () const;
212
213        /**
214        * A method for printing a string representation of the given MinorProcessor to std::cout.
215        */
216        void print () const;
217};
218
219class IntMinorProcessor : public MinorProcessor {
220    private:
221        /**
222        * private store for integer matrix entries; \c _matrix[r][c] is the entry in row \c r and column \c c
223        */
224        int** _matrix;
225
226        /**
227        * A method for computing the value of a minor, using a cache.<br>
228        * The sub-matrix is specified by \c mk. Computation works recursively
229        * using Laplace's Theorem. We always develop along the row or column with the most zeros; see
230        * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
231        * @param k the number of rows and columns in the minor to be comuted
232        * @param mk the representation of rows and columns of the minor to be comuted
233        * @param multipleMinors decides whether we compute just one or all minors of a specified size
234        * @param c a cache to be used for caching reusable sub-minors
235        * @return an instance of MinorValue representing the value of the corresponding minor
236        * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&)
237        */
238        IntMinorValue getMinorPrivate (const int k, const MinorKey& mk,
239                                       const bool multipleMinors,
240                                       Cache<MinorKey, IntMinorValue>& c,
241                                       int characteristic);
242
243        /**
244        * A method for computing the value of a minor, without using a cache.<br>
245        * The sub-matrix is specified by \c mk. Computation works recursively
246        * using Laplace's Theorem. We always develop along the row or column with the most zeros; see
247        * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
248        * @param k the number of rows and columns in the minor to be comuted
249        * @param mk the representation of rows and columns of the minor to be comuted
250        * @return an instance of MinorValue representing the value of the corresponding minor
251        * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&, const bool, Cache<MinorKey, MinorValue>&)
252        */
253        IntMinorValue getMinorPrivate (const int k, const MinorKey& mk, int characteristic);
254    protected:
255        bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const;
256    public:
257        /**
258        * A constructor for creating an instance.
259        */
260        IntMinorProcessor ();
261
262        /**
263        * A destructor for deleting an instance.
264        */
265        ~IntMinorProcessor ();
266
267        /**
268        * A method for defining a matrix with integer entries.
269        * @param numberOfRows the number of rows
270        * @param numberOfColumns the number of columns
271        * @param matrix the matrix entries in a linear array, i.e., from left to right and top to bottom
272        * @see MinorValue::defineSubMatrix (const int, const int*, const int, const int*)
273        */
274        void defineMatrix (const int numberOfRows, const int numberOfColumns, const int* matrix);
275
276        /**
277        * A method for computing the value of a minor, without using a cache.<br>
278        * The sub-matrix is determined by \c rowIndices and \c columnIndices. Computation works recursively
279        * using Laplace's Theorem. We always develop along the row or column with most zeros; see
280        * MinorProcessor::getBestLine (const int, const int, const int).
281        * @param dimension the size of the minor to be computed
282        * @param rowIndices 0-based indices of the rows of the minor
283        * @param columnIndices 0-based indices of the column of the minor
284        * @return an instance of MinorValue representing the value of the corresponding minor
285        * @see MinorProcessor::getMinor (const int, const int*, const int*, Cache<MinorKey, MinorValue>&)
286        */
287        IntMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices, const int characteristic);
288
289        /**
290        * A method for computing the value of a minor, using a cache.<br>
291        * The sub-matrix is determined by \c rowIndices and \c columnIndices. Computation works recursively
292        * using Laplace's Theorem. We always develop along the row or column with most zeros; see
293        * MinorProcessor::getBestLine (const int, const int, const int).
294        * @param dimension the size of the minor to be computed
295        * @param rowIndices 0-based indices of the rows of the minor
296        * @param columnIndices 0-based indices of the column of the minor
297        * @param c a cache to be used for caching reusable sub-minors
298        * @return an instance of MinorValue representing the value of the corresponding minor
299        * @see MinorProcessor::getMinor (const int, const int*, const int*)
300        */
301        IntMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices,
302                                 Cache<MinorKey, IntMinorValue>& c, const int characteristic);
303
304        /**
305        * A method for obtaining the next minor when iterating
306        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
307        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
308        * \c true.<br>
309        * Computation works without using a cache.
310        * @return true iff there is a next choice of rows and columns
311        * @see MinorProcessor::getMinor (const int, const int*, const int*)
312        * @see MinorProcessor::hasNextMinor ()
313        */
314        IntMinorValue getNextMinor (const int characteristic);
315
316        /**
317        * A method for obtaining the next minor when iterating
318        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
319        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
320        * \c true.<br>
321        * Computation works using the cache \a c which may already contain useful results from previous
322        * calls of MinorValue::getNextMinor (Cache<MinorKey, MinorValue>&).
323        * @return the next minor
324        * @see MinorProcessor::getMinor (const int, const int*, const int*)
325        * @see MinorProcessor::hasNextMinor ()
326        */
327        IntMinorValue getNextMinor (Cache<MinorKey, IntMinorValue>& c, const int characteristic);
328
329        /**
330        * A method for providing a printable version of the represented MinorProcessor.
331        * @return a printable version of the given instance as instance of class string
332        */
333        string toString () const;
334};
335
336class PolyMinorProcessor : public MinorProcessor {
337    private:
338        /**
339        * private store for polynomial matrix entries; \c _matrix[r][c] is the entry in row \c r and column \c c
340        */
341        poly** _polyMatrix;
342
343        /**
344        * A method for computing the value of a minor, using a cache.<br>
345        * The sub-matrix is specified by \c mk. Computation works recursively
346        * using Laplace's Theorem. We always develop along the row or column with the most zeros; see
347        * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
348        * @param k the number of rows and columns in the minor to be comuted
349        * @param mk the representation of rows and columns of the minor to be comuted
350        * @param multipleMinors decides whether we compute just one or all minors of a specified size
351        * @param c a cache to be used for caching reusable sub-minors
352        * @return an instance of MinorValue representing the value of the corresponding minor
353        * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&)
354        */
355        PolyMinorValue getMinorPrivate (const int k, const MinorKey& mk,
356                                        const bool multipleMinors,
357                                        Cache<MinorKey, PolyMinorValue>& c);
358
359        /**
360        * A method for computing the value of a minor, without using a cache.<br>
361        * The sub-matrix is specified by \c mk. Computation works recursively
362        * using Laplace's Theorem. We always develop along the row or column with the most zeros; see
363        * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
364        * @param k the number of rows and columns in the minor to be comuted
365        * @param mk the representation of rows and columns of the minor to be comuted
366        * @return an instance of MinorValue representing the value of the corresponding minor
367        * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&, const bool, Cache<MinorKey, MinorValue>&)
368        */
369        PolyMinorValue getMinorPrivate (const int k, const MinorKey& mk);
370    protected:
371        bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const;
372    public:
373        /**
374        * A constructor for creating an instance.
375        */
376        PolyMinorProcessor ();
377
378        /**
379        * A destructor for deleting an instance.
380        */
381        ~PolyMinorProcessor ();
382
383        /**
384        * A method for defining a matrix with integer entries.
385        * @param numberOfRows the number of rows
386        * @param numberOfColumns the number of columns
387        * @param matrix the matrix entries in a linear array, i.e., from left to right and top to bottom
388        * @see MinorValue::defineSubMatrix (const int, const int*, const int, const int*)
389        */
390        void defineMatrix (const int numberOfRows, const int numberOfColumns, const poly* polyMatrix);
391
392        /**
393        * A method for computing the value of a minor, without using a cache.<br>
394        * The sub-matrix is determined by \c rowIndices and \c columnIndices. Computation works recursively
395        * using Laplace's Theorem. We always develop along the row or column with most zeros; see
396        * MinorProcessor::getBestLine (const int, const int, const int).
397        * @param dimension the size of the minor to be computed
398        * @param rowIndices 0-based indices of the rows of the minor
399        * @param columnIndices 0-based indices of the column of the minor
400        * @return an instance of MinorValue representing the value of the corresponding minor
401        * @see MinorProcessor::getMinor (const int, const int*, const int*, Cache<MinorKey, MinorValue>&)
402        */
403        PolyMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices);
404
405        /**
406        * A method for computing the value of a minor, using a cache.<br>
407        * The sub-matrix is determined by \c rowIndices and \c columnIndices. Computation works recursively
408        * using Laplace's Theorem. We always develop along the row or column with most zeros; see
409        * MinorProcessor::getBestLine (const int, const int, const int).
410        * @param dimension the size of the minor to be computed
411        * @param rowIndices 0-based indices of the rows of the minor
412        * @param columnIndices 0-based indices of the column of the minor
413        * @param c a cache to be used for caching reusable sub-minors
414        * @return an instance of MinorValue representing the value of the corresponding minor
415        * @see MinorProcessor::getMinor (const int, const int*, const int*)
416        */
417        PolyMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices,
418                                 Cache<MinorKey, PolyMinorValue>& c);
419
420        /**
421        * A method for obtaining the next minor when iterating
422        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
423        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
424        * \c true.<br>
425        * Computation works without using a cache.
426        * @return true iff there is a next choice of rows and columns
427        * @see MinorProcessor::getMinor (const int, const int*, const int*)
428        * @see MinorProcessor::hasNextMinor ()
429        */
430        PolyMinorValue getNextMinor ();
431
432        /**
433        * A method for obtaining the next minor when iterating
434        * through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.<br>
435        * This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded
436        * \c true.<br>
437        * Computation works using the cache \a c which may already contain useful results from previous
438        * calls of MinorValue::getNextMinor (Cache<MinorKey, MinorValue>&).
439        * @return the next minor
440        * @see MinorProcessor::getMinor (const int, const int*, const int*)
441        * @see MinorProcessor::hasNextMinor ()
442        */
443        PolyMinorValue getNextMinor (Cache<MinorKey, PolyMinorValue>& c);
444
445        /**
446        * A method for providing a printable version of the represented MinorProcessor.
447        * @return a printable version of the given instance as instance of class string
448        */
449        string toString () const;
450};
451
452#endif // HAVE_MINOR
453
454#endif
455/* MINOR_PROCESSOR_H */
Note: See TracBrowser for help on using the repository browser.