source: git/Singular/MinorProcessor.h @ 665ca8

spielwiese
Last change on this file since 665ca8 was 411e002, checked in by Hans Schoenemann <hannes@…>, 13 years ago
format git-svn-id: file:///usr/local/Singular/svn/trunk@14092 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 34.9 KB
Line 
1#ifndef MINOR_PROCESSOR_H
2#define MINOR_PROCESSOR_H
3
4#include <Cache.h>
5#include <Minor.h>
6#include <assert.h>
7#include <string>
8
9/* write "##define COUNT_AND_PRINT_OPERATIONS x" if you want
10   to count all basic operations and have them printed when
11   one of the methods documented herein will be invoked;
12   otherwise, comment this line;
13   x = 1: only final counters (after computing ALL
14          specified minors) will be printed, i.e., no
15          intermediate results;
16   x = 2: print counters after the computation of each
17          minor; this will be much more information
18   x = 3: print also all intermediate matrices with the
19          numbers of monomials in each entry;
20          this will be much much more information */
21//#define COUNT_AND_PRINT_OPERATIONS 2
22
23void printCounters (char* prefix, bool resetToZero);
24
25/*! \class MinorProcessor
26    \brief Class MinorProcessor implements the key methods for computing one
27    or all sub-determinantes of a given size in a pre-defined matrix; either
28    without caching or by using a cache.
29
30    After defining the entire matrix (e.g. 10 x 14) using<br>
31    MinorProcessor::defineMatrix (const int, const int, const int*),<br>
32    the user may do two different things:<br>
33    1. He/she can simply compute a minor in this matrix using<br>
34    MinorProcessor::getMinor (const int, const int*, const int*,
35                              Cache<MinorKey, MinorValue>&), or<br>
36    MinorProcessor::getMinor (const int, const int*, const int*);<br>
37    depending on whether a cache shall or shall not be used, respectively.<br>
38    In the first case, the user simply provides all row and column indices of
39    the desired minor.
40    2. He/she may define a smaller sub-matrix (e.g. 8 x 7) using
41    MinorValue::defineSubMatrix (const int, const int*, const int, const int*).
42    Afterwards, he/she may compute all minors of an even smaller size (e.g.
43    5 x 5) that consist exclusively of rows and columns of this (8 x 7)
44    sub-matrix (inside the entire 10 x 14 matrix).<br>
45    The implementation at hand eases the iteration over all such minors. Also
46    in the second case there are both implementations, i.e., with and without
47    using a cache.<br><br>
48    MinorProcessor makes use of MinorKey, MinorValue, and Cache. The
49    implementation of all mentioned classes (MinorKey, MinorValue, and
50    MinorProcessor) is generic to allow for the use of different types of
51    keys and values.
52    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
53*/
54class MinorProcessor
55{
56  protected:
57    /**
58    * A static method for computing the maximum number of retrievals of a
59    * minor.<br>
60    * More concretely, we are given a matrix of size \c rows x \c columns. We
61    * furthermore assume that we have - as part of this matrix - a minor of
62    * size \c containerMinorSize x \c containerMinorSize. Now we are
63    * interested in the number of times a minor of yet smaller size
64    * \c minorSize x \c minorSize will be needed when we compute the
65    * containerMinor by Laplace's Theorem.<br>
66    * The method returns the combinatorial results for both cases:
67    * containerMinor is fixed within the matrix
68    * (<c>multipleMinors == false</c>), or it can vary inside the matrix
69    * (<c>multipleMinors == true</c>).<br>
70    * The notion is here that we want to cache the small minor of size
71    * \c minorSize x \c minorSize, i.e. compute it just once.
72    * @param rows the number of rows of the underlying matrix
73    * @param columns the number of columns of the underlying matrix
74    * @param containerMinorSize the size of the container minor
75    * @param minorSize the size of the small minor (which may be retrieved
76    *        multiple times)
77    * @param multipleMinors decides whether containerMinor is fixed within
78    *        the underlying matrix or not
79    * @return the number of times, the small minor will be needed when
80    *         computing one or all containerMinors
81    */
82    static int NumberOfRetrievals (const int rows, const int columns,
83                                   const int containerMinorSize,
84                                   const int minorSize,
85                                   const bool multipleMinors);
86    /**
87    * A static method for computing the binomial coefficient i over j.
88    * \par Assert
89    * The method checks whether <em>i >= j >= 0</em>.
90    * @param i a positive integer greater than or equal to \a j
91    * @param j a positive integer less than or equal to \a i, and greater
92    *        than or equal to \e 0.
93    * @return the binomial coefficient i over j
94    */
95    static int IOverJ (const int i, const int j);
96
97    /**
98    * A static method for computing the factorial of i.
99    * \par Assert
100    * The method checks whether <em>i >= 0</em>.
101    * @param i an integer greater than or equal to \a 0
102    * @return the factorial of i
103    */
104    static int Faculty (const int i);
105
106    /**
107    * A method for iterating through all possible subsets of \c k rows and
108    * \c k columns inside a pre-defined submatrix of a pre-defined matrix.<br>
109    * The method will set \c _rowKey and \c columnKey to represent the
110    * next possbile subsets of \c k rows and columns inside the submatrix
111    * determined by \c _globalRowKey and \c _globalColumnKey.<br>
112    * When first called, this method will just shift \c _rowKey and
113    * \c _columnKey to point to the first sensible choices. Every subsequent
114    * call will move to the next \c _columnKey until there is no next.
115    * In this situation, a next \c _rowKey will be set, and \c _columnKey
116    * again to the first possible choice.<br>
117    * Finally, in case there is also no next \c _rowkey, the method returns
118    * \c false. (Otherwise \c true is returned.)
119    * @param k the size of the minor / all minors of interest
120    * @return true iff there is a next possible choice of rows and columns
121    */
122    bool setNextKeys (const int k);
123
124    /**
125    * private store for the rows and columns of the container minor within
126    * the underlying matrix;
127    * \c _container will be used to fix a submatrix (e.g. 40 x 50) of a
128    * larger matrix (e.g. 70 x 100). This is usefull when we would like to
129    * compute all minors of a given size (e.g. 4 x 4) inside such a
130    * pre-defined submatrix.
131    */
132    MinorKey _container;
133
134    /**
135    * private store for the number of rows in the container minor;
136    * This is set by MinorProcessor::defineSubMatrix (const int, const int*,
137    *                                                 const int, const int*).
138    */
139    int _containerRows;
140
141    /**
142    * private store for the number of columns in the container minor;
143    * This is set by MinorProcessor::defineSubMatrix (const int, const int*,
144    *                                                 const int, const int*).
145    */
146    int _containerColumns;
147
148    /**
149    * private store for the rows and columns of the minor of interest;
150    * Usually, this minor will encode subsets of the rows and columns in
151    * _container.
152    */
153    MinorKey _minor;
154
155    /**
156    * private store for the dimension of the minor(s) of interest
157    */
158    int _minorSize;
159
160    /**
161    * private store for the number of rows in the underlying matrix
162    */
163    int _rows;
164
165    /**
166    * private store for the number of columns in the underlying matrix
167    */
168    int _columns;
169
170    /**
171    * A method for identifying the row or column with the most zeros.<br>
172    * Using Laplace's Theorem, a minor can more efficiently be computed when
173    * developing along this best line.
174    * The returned index \c bestIndex is 0-based within the pre-defined
175    * matrix. If some row has the most zeros, then the (0-based) row index is
176    * returned. If, contrarywise, some column has the most zeros, then
177    * <c>x = - 1 - c</c> where \c c is the column index, is returned.
178    * (Note that in this case \c c can be reconstructed by computing
179    * <c>c = - 1 - x</c>.)
180    * @param k the size of the minor / all minors of interest
181    * @param mk the representation of rows and columns of the minor of
182    *        interest
183    * @return an int encoding which row or column has the most zeros
184    */
185    int getBestLine (const int k, const MinorKey& mk) const;
186
187    /**
188    * A method for testing whether a matrix entry is zero.
189    * @param absoluteRowIndex the absolute (zero-based) row index
190    * @param absoluteColumnIndex the absolute (zero-based) column index
191    * @return true iff the specified matrix entry is zero
192    */
193    virtual bool isEntryZero (const int absoluteRowIndex,
194                              const int absoluteColumnIndex) const;
195  public:
196    /**
197    * The default constructor
198    */
199    MinorProcessor ();
200
201    /**
202     * A destructor for deleting an instance. We must make this destructor
203     * virtual so that destructors of all derived classes will automatically
204     * also call the destructor of the base class MinorProcessor.
205     */
206     virtual ~MinorProcessor ();
207
208    /**
209    * A method for defining a sub-matrix within a pre-defined matrix.
210    * @param numberOfRows the number of rows in the sub-matrix
211    * @param rowIndices an array with the (0-based) indices of rows inside
212    *        the pre-defined matrix
213    * @param numberOfColumns the number of columns in the sub-matrix
214    * @param columnIndices an array with the (0-based) indices of columns
215    *        inside the pre-defined matrix
216    * @see MinorValue::defineMatrix (const int, const int, const int*)
217    */
218    void defineSubMatrix (const int numberOfRows, const int* rowIndices,
219                          const int numberOfColumns, const int* columnIndices);
220
221    /**
222    * Sets the size of the minor(s) of interest.<br>
223    * This method needs to be performed before beginning to compute all minors
224    * of size \a minorSize inside a pre-defined submatrix of an underlying
225    * (also pre-defined) matrix.
226    * @param minorSize the size of the minor(s) of interest
227    * @see MinorValue::defineSubMatrix (const int, const int*, const int,
228    *                                   const int*)
229    */
230    void setMinorSize (const int minorSize);
231
232    /**
233    * A method for checking whether there is a next choice of rows and columns
234    * when iterating through all minors of a given size within a pre-defined
235    * sub-matrix of an underlying matrix.<br>
236    * The number of rows and columns has to be set before using
237    * MinorValue::setMinorSize(const int).<br>
238    * After calling MinorValue::hasNextMinor (), the current sets of rows and
239    * columns may be inspected using
240    * MinorValue::getCurrentRowIndices(int* const) const and
241    * MinorValue::getCurrentColumnIndices(int* const) const.
242    * @return true iff there is a next choice of rows and columns
243    * @see MinorProcessor::getMinor (const int, const int*, const int*)
244    * @see MinorValue::getCurrentRowIndices(int* const) const
245    * @see MinorValue::getCurrentColumnIndices(int* const) const
246    */
247    bool hasNextMinor ();
248
249    /**
250    * A method for obtaining the current set of rows corresponding to the
251    * current minor when iterating through all minors of a given size within
252    * a pre-defined sub-matrix of an underlying matrix.<br>
253    * This method should only be called after MinorProcessor::hasNextMinor ()
254    * had been called and yielded \c true.<br>
255    * The user of this method needs to know the number of rows in order to
256    * know which entries of the newly filled \c target will be valid.
257    * @param target an int array to be filled with the row indices
258    * @see MinorProcessor::hasNextMinor ()
259    */
260    void getCurrentRowIndices (int* const target) const;
261
262    /**
263    * A method for obtaining the current set of columns corresponding to the
264    * current minor when iterating through all minors of a given size within
265    * a pre-defined sub-matrix of an underlying matrix.<br>
266    * This method should only be called after MinorProcessor::hasNextMinor ()
267    * had been called and yielded \c true.<br>
268    * The user of this method needs to know the number of columns in order to
269    * know which entries of the newly filled \c target will be valid.
270    * @param target an int array to be filled with the column indices
271    * @see MinorProcessor::hasNextMinor ()
272    */
273    void getCurrentColumnIndices (int* const target) const;
274
275    /**
276    * A method for providing a printable version of the represented
277    * MinorProcessor.
278    * @return a printable version of the given instance as instance of class
279    * string
280    */
281    virtual string toString () const;
282
283    /**
284    * A method for printing a string representation of the given
285    * MinorProcessor to std::cout.
286    */
287    void print () const;
288};
289
290/*! \class IntMinorProcessor
291    \brief Class IntMinorProcessor is derived from class MinorProcessor.
292
293    This class implements the special case of integer matrices.
294    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
295*/
296class IntMinorProcessor : public MinorProcessor
297{
298  private:
299    /**
300    * private store for integer matrix entries
301    */
302    int* _intMatrix;
303
304    /**
305    * A method for retrieving the matrix entry.
306    * @param rowIndex the absolute (zero-based) row index
307    * @param columnIndex the absolute (zero-based) column index
308    * @return the specified matrix entry
309    */
310    int getEntry (const int rowIndex, const int columnIndex) const;
311
312    /**
313    * A method for computing the value of a minor, using a cache.<br>
314    * The sub-matrix is specified by \c mk. Computation works recursively
315    * using Laplace's Theorem. We always develop along the row or column with
316    * the most zeros; see
317    * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
318    * If an ideal is given, it is assumed to be a standard basis. In this case,
319    * all results will be reduced w.r.t. to this basis. Moreover, if the given
320    * characteristic is non-zero, all results will be computed modulo this
321    * characteristic.
322    * @param k the number of rows and columns in the minor to be comuted
323    * @param mk the representation of rows and columns of the minor to be
324    *        comuted
325    * @param multipleMinors decides whether we compute just one or all minors
326    *        of a specified size
327    * @param c a cache to be used for caching reusable sub-minors
328    * @param characteristic 0 or the characteristic of the underlying
329    *        coefficient ring/field
330    * @param iSB NULL or a standard basis
331    * @return an instance of MinorValue representing the value of the
332    *         corresponding minor
333    * @see MinorProcessor::getMinorPrivateLaplace (const int k,
334                                                   const MinorKey& mk,
335                                                   const int characteristic,
336                                                   const ideal& iSB)
337    */
338    IntMinorValue getMinorPrivateLaplace (const int k, const MinorKey& mk,
339                                          const bool multipleMinors,
340                                          Cache<MinorKey, IntMinorValue>& c,
341                                          int characteristic,
342                                          const ideal& iSB);
343
344    /**
345    * A method for computing the value of a minor, without using a cache.<br>
346    * The sub-matrix is specified by \c mk. Computation works recursively
347    * using Laplace's Theorem. We always develop along the row or column with
348    * the most zeros; see
349    * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
350    * If an ideal is given, it is assumed to be a standard basis. In this case,
351    * all results will be reduced w.r.t. to this basis. Moreover, if the given
352    * characteristic is non-zero, all results will be computed modulo this
353    * characteristic.
354    * @param k the number of rows and columns in the minor to be comuted
355    * @param mk the representation of rows and columns of the minor to be
356    *        comuted
357    * @param characteristic 0 or the characteristic of the underlying
358    *        coefficient ring/field
359    * @param iSB NULL or a standard basis
360    * @return an instance of MinorValue representing the value of the
361    *         corresponding minor
362    * @see MinorProcessor::getMinorPrivateLaplace (const int k,
363                                                   const MinorKey& mk,
364                                                   const bool multipleMinors,
365                                                   Cache<MinorKey,
366                                                         IntMinorValue>& c,
367                                                   int characteristic,
368                                                   const ideal& iSB)
369    */
370    IntMinorValue getMinorPrivateLaplace (const int k, const MinorKey& mk,
371                                          const int characteristic,
372                                          const ideal& iSB);
373
374    /**
375    * A method for computing the value of a minor using Bareiss's
376    * algorithm.<br>
377    * The sub-matrix is specified by \c mk.
378    * If an ideal is given, it is assumed to be a standard basis. In this
379    * case, all results will be reduced w.r.t. to this basis. Moreover, if the
380    * given characteristic is non-zero, all results will be computed modulo
381    * this characteristic.
382    * @param k the number of rows and columns in the minor to be comuted
383    * @param mk the representation of rows and columns of the minor to be
384    *        computed
385    * @param characteristic 0 or the characteristic of the underlying
386    *        coefficient ring/field
387    * @param iSB NULL or a standard basis
388    * @return an instance of MinorValue representing the value of the
389    *         corresponding minor
390    * @see MinorProcessor::getMinorPrivateLaplace (const int k,
391                                                   const MinorKey& mk,
392                                                   const int characteristic,
393                                                   const ideal& iSB)
394    */
395    IntMinorValue getMinorPrivateBareiss (const int k, const MinorKey& mk,
396                                          const int characteristic,
397                                          const ideal& iSB);
398  protected:
399    /**
400    * A method for testing whether a matrix entry is zero.
401    * @param absoluteRowIndex the absolute (zero-based) row index
402    * @param absoluteColumnIndex the absolute (zero-based) column index
403    * @return true iff the specified matrix entry is zero
404    */
405    bool isEntryZero (const int absoluteRowIndex,
406                      const int absoluteColumnIndex) const;
407  public:
408    /**
409    * A constructor for creating an instance.
410    */
411    IntMinorProcessor ();
412
413    /**
414    * A destructor for deleting an instance.
415    */
416    ~IntMinorProcessor ();
417
418    /**
419    * A method for defining a matrix with integer entries.
420    * @param numberOfRows the number of rows
421    * @param numberOfColumns the number of columns
422    * @param matrix the matrix entries in a linear array, i.e., from left to
423    *        right and top to bottom
424    * @see MinorValue::defineSubMatrix (const int, const int*, const int,
425    *                                   const int*)
426    */
427    void defineMatrix (const int numberOfRows, const int numberOfColumns,
428                       const int* matrix);
429
430    /**
431    * A method for computing the value of a minor without using a cache.<br>
432    * The sub-matrix is determined by \c rowIndices and \c columnIndices.
433    * Computation works either by Laplace's algorithm or by Bareiss's
434    * algorithm.<br>
435    * If an ideal is given, it is assumed to be a standard basis. In this
436    * case, all results will be reduced w.r.t. to this basis. Moreover, if the
437    * given characteristic is non-zero, all results will be computed modulo
438    * this characteristic.
439    * @param dimension the size of the minor to be computed
440    * @param rowIndices 0-based indices of the rows of the minor
441    * @param columnIndices 0-based indices of the column of the minor
442    * @param characteristic 0 or the characteristic of the underlying
443    *        coefficient ring/field
444    * @param iSB NULL or a standard basis
445    * @param algorithm either "Bareiss" or "Laplace"
446    * @return an instance of MinorValue representing the value of the
447    *         corresponding minor
448    * @see MinorProcessor::getMinor (const int dimension,
449                                     const int* rowIndices,
450                                     const int* columnIndices,
451                                     Cache<MinorKey, IntMinorValue>& c,
452                                     const int characteristic,
453                                     const ideal& iSB)
454    */
455    IntMinorValue getMinor (const int dimension, const int* rowIndices,
456                            const int* columnIndices,
457                            const int characteristic, const ideal& iSB,
458                            const char* algorithm);
459
460    /**
461    * A method for computing the value of a minor using a cache.<br>
462    * The sub-matrix is determined by \c rowIndices and \c columnIndices.
463    * Computation works by Laplace's algorithm together with caching of
464    * subdeterminants.<br>
465    * If an ideal is given, it is assumed to be a standard basis. In this case,
466    * all results will be reduced w.r.t. to this basis. Moreover, if the given
467    * characteristic is non-zero, all results will be computed modulo this
468    * characteristic.
469    * @param dimension the size of the minor to be computed
470    * @param rowIndices 0-based indices of the rows of the minor
471    * @param columnIndices 0-based indices of the column of the minor
472    * @param c the cache for storing subdeterminants
473    * @param characteristic 0 or the characteristic of the underlying
474    *        coefficient ring/field
475    * @param iSB NULL or a standard basis
476    * @return an instance of MinorValue representing the value of the
477    *         corresponding minor
478    * @see MinorProcessor::getMinor (const int dimension,
479                                     const int* rowIndices,
480                                     const int* columnIndices,
481                                     const int characteristic,
482                                     const ideal& iSB,
483                                     const char* algorithm)
484    */
485    IntMinorValue getMinor (const int dimension, const int* rowIndices,
486                            const int* columnIndices,
487                            Cache<MinorKey, IntMinorValue>& c,
488                            const int characteristic,  const ideal& iSB);
489
490    /**
491    * A method for obtaining the next minor when iterating
492    * through all minors of a given size within a pre-defined sub-matrix of an
493    * underlying matrix.<br>
494    * This method should only be called after MinorProcessor::hasNextMinor ()
495    * had been called and yielded \c true.<br>
496    * Computation works by Laplace's algorithm (without using a cache) or by
497    * Bareiss's algorithm.<br>
498    * If an ideal is given, it is assumed to be a standard basis. In this case,
499    * all results will be reduced w.r.t. to this basis. Moreover, if the given
500    * characteristic is non-zero, all results will be computed modulo this
501    * characteristic.
502    * @param characteristic 0 or the characteristic of the underlying
503    *        coefficient ring/field
504    * @param iSB NULL or a standard basis
505    * @param algorithm either "Bareiss" or "Laplace"
506    * @return the next minor
507    * @see IntMinorValue::getNextMinor (Cache<MinorKey, IntMinorValue>& c,
508    *                                   const int characteristic,
509    *                                   const ideal& iSB)
510    */
511    IntMinorValue getNextMinor (const int characteristic, const ideal& iSB,
512                                const char* algorithm);
513
514    /**
515    * A method for obtaining the next minor when iterating
516    * through all minors of a given size within a pre-defined sub-matrix of an
517    * underlying matrix.<br>
518    * This method should only be called after MinorProcessor::hasNextMinor ()
519    * had been called and yielded \c true.<br>
520    * Computation works using the cache \a c which may already contain useful
521    * results from previous calls of
522    * IntMinorValue::getNextMinor (Cache<MinorKey, IntMinorValue>& c,
523                                   const int characteristic,
524                                   const ideal& iSB).
525    * If an ideal is given, it is assumed to be a standard basis. In this case,
526    * all results will be reduced w.r.t. to this basis. Moreover, if the given
527    * characteristic is non-zero, all results will be computed modulo this
528    * characteristic.
529    * @param c the cache
530    * @param characteristic 0 or the characteristic of the underlying
531    *        coefficient ring/field
532    * @param iSB NULL or a standard basis
533    * @return the next minor
534    * @see IntMinorValue::getNextMinor (const int characteristic,
535    *                                   const ideal& iSB,
536    *                                   const char* algorithm)
537    */
538    IntMinorValue getNextMinor (Cache<MinorKey, IntMinorValue>& c,
539                                const int characteristic,
540                                const ideal& iSB);
541
542    /**
543    * A method for providing a printable version of the represented
544    * MinorProcessor.
545    * @return a printable version of the given instance as instance of class
546    *         string
547    */
548    string toString () const;
549};
550
551/*! \class PolyMinorProcessor
552    \brief Class PolyMinorProcessor is derived from class MinorProcessor.
553
554    This class implements the special case of polynomial matrices.
555    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
556*/
557class PolyMinorProcessor : public MinorProcessor
558{
559  private:
560    /**
561    * private store for polynomial matrix entries
562    */
563    poly* _polyMatrix;
564
565    /**
566    * A method for retrieving the matrix entry.
567    * @param rowIndex the absolute (zero-based) row index
568    * @param columnIndex the absolute (zero-based) column index
569    * @return the specified matrix entry
570    */
571    poly getEntry (const int rowIndex, const int columnIndex) const;
572
573    /**
574    * A method for computing the value of a minor, using a cache.<br>
575    * The sub-matrix is specified by \c mk. Computation works recursively
576    * using Laplace's Theorem. We always develop along the row or column with
577    * the most zeros; see
578    * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
579    * If an ideal is given, it is assumed to be a standard basis. In this case,
580    * all results will be reduced w.r.t. to this basis.
581    * @param k the number of rows and columns in the minor to be comuted
582    * @param mk the representation of rows and columns of the minor to be
583    *        comuted
584    * @param multipleMinors decides whether we compute just one or all minors
585    *        of a specified size
586    * @param c a cache to be used for caching reusable sub-minors
587    * @param iSB NULL or a standard basis
588    * @return an instance of MinorValue representing the value of the
589    *         corresponding minor
590    * @see MinorProcessor::getMinorPrivateLaplace (const int k,
591    *                                              const MinorKey& mk,
592    *                                              const ideal& iSB)
593    */
594    PolyMinorValue getMinorPrivateLaplace (const int k, const MinorKey& mk,
595                                           const bool multipleMinors,
596                                           Cache<MinorKey, PolyMinorValue>& c,
597                                           const ideal& iSB);
598
599    /**
600    * A method for computing the value of a minor, without using a cache.<br>
601    * The sub-matrix is specified by \c mk. Computation works recursively
602    * using Laplace's Theorem. We always develop along the row or column with
603    * the most zeros; see
604    * MinorProcessor::getBestLine (const int k, const MinorKey& mk).
605    * If an ideal is given, it is assumed to be a standard basis. In this case,
606    * all results will be reduced w.r.t. to this basis.
607    * @param k the number of rows and columns in the minor to be comuted
608    * @param mk the representation of rows and columns of the minor to be
609    *        comuted
610    * @param iSB NULL or a standard basis
611    * @return an instance of MinorValue representing the value of the
612    *         corresponding minor
613    * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&,
614    *                                       const bool,
615    *                                       Cache<MinorKey, MinorValue>&)
616    */
617    PolyMinorValue getMinorPrivateLaplace (const int k, const MinorKey& mk,
618                                           const ideal& iSB);
619
620    /**
621    * A method for computing the value of a minor, without using a cache.<br>
622    * The sub-matrix is specified by \c mk. Computation works
623    * using Bareiss's algorithm.
624    * If an ideal is given, it is assumed to be a standard basis. In this case,
625    * all results will be reduced w.r.t. to this basis.
626    * @param k the number of rows and columns in the minor to be comuted
627    * @param mk the representation of rows and columns of the minor to be
628    *        comuted
629    * @param iSB NULL or a standard basis
630    * @return an instance of MinorValue representing the value of the
631    *         corresponding minor
632    * @see MinorProcessor::getMinorPrivateLaplace (const int k,
633    *                                              const MinorKey& mk,
634    *                                              const ideal& iSB)
635    */
636    PolyMinorValue getMinorPrivateBareiss (const int k, const MinorKey& mk,
637                                           const ideal& iSB);
638  protected:
639    /**
640    * A method for testing whether a matrix entry is zero.
641    * @param absoluteRowIndex the absolute (zero-based) row index
642    * @param absoluteColumnIndex the absolute (zero-based) column index
643    * @return true iff the specified matrix entry is zero
644    */
645    bool isEntryZero (const int absoluteRowIndex,
646                      const int absoluteColumnIndex) const;
647  public:
648    /**
649    * A constructor for creating an instance.
650    */
651    PolyMinorProcessor ();
652
653    /**
654    * A destructor for deleting an instance.
655    */
656    ~PolyMinorProcessor ();
657
658    /**
659    * A method for defining a matrix with polynomial entries.
660    * @param numberOfRows the number of rows
661    * @param numberOfColumns the number of columns
662    * @param polyMatrix the matrix entries in a linear array, i.e., from left
663    *        to right and top to bottom
664    * @see MinorValue::defineSubMatrix (const int, const int*, const int,
665    *                                   const int*)
666    */
667    void defineMatrix (const int numberOfRows, const int numberOfColumns,
668                       const poly* polyMatrix);
669
670    /**
671    * A method for computing the value of a minor, without using a cache.<br>
672    * The sub-matrix is determined by \c rowIndices and \c columnIndices.
673    * Computation works either by Laplace's algorithm or by Bareiss's
674    * algorithm.<br>
675    * If an ideal is given, it is assumed to be a standard basis. In this case,
676    * all results will be reduced w.r.t. to this basis.
677    * @param dimension the size of the minor to be computed
678    * @param rowIndices 0-based indices of the rows of the minor
679    * @param columnIndices 0-based indices of the column of the minor
680    * @param algorithm either "Laplace" or "Bareiss"
681    * @param iSB NULL or a standard basis
682    * @return an instance of MinorValue representing the value of the
683    *         corresponding minor
684    * @see MinorProcessor::getMinor (const int dimension,
685    *                                const int* rowIndices,
686    *                                const int* columnIndices,
687    *                                Cache<MinorKey, PolyMinorValue>& c,
688    *                                const ideal& iSB)
689    */
690    PolyMinorValue getMinor (const int dimension, const int* rowIndices,
691                             const int* columnIndices, const char* algorithm,
692                             const ideal& iSB);
693
694    /**
695    * A method for computing the value of a minor, using a cache.<br>
696    * The sub-matrix is determined by \c rowIndices and \c columnIndices.
697    * Computation works recursively using Laplace's Theorem. We always develop
698    * along the row or column with most zeros; see
699    * MinorProcessor::getBestLine (const int, const int, const int).
700    * If an ideal is given, it is assumed to be a standard basis. In this case,
701    * all results will be reduced w.r.t. to this basis.
702    * @param dimension the size of the minor to be computed
703    * @param rowIndices 0-based indices of the rows of the minor
704    * @param columnIndices 0-based indices of the column of the minor
705    * @param c a cache to be used for caching reusable sub-minors
706    * @param iSB NULL or a standard basis
707    * @return an instance of MinorValue representing the value of the
708    *         corresponding minor
709    * @see MinorProcessor::(const int dimension, const int* rowIndices,
710    *                       const int* columnIndices, const char* algorithm,
711    *                       const ideal& iSB)
712    */
713    PolyMinorValue getMinor (const int dimension, const int* rowIndices,
714                             const int* columnIndices,
715                             Cache<MinorKey, PolyMinorValue>& c,
716                             const ideal& iSB);
717
718    /**
719    * A method for obtaining the next minor when iterating
720    * through all minors of a given size within a pre-defined sub-matrix of an
721    * underlying matrix.<br>
722    * This method should only be called after MinorProcessor::hasNextMinor ()
723    * had been called and yielded \c true.<br>
724    * Computation works either by Laplace's algorithm (without using a cache)
725    * or by Bareiss's algorithm.<br>
726    * If an ideal is given, it is assumed to be a standard basis. In this case,
727    * all results will be reduced w.r.t. to this basis.
728    * @param algorithm either "Laplace" or "Bareiss"
729    * @param iSB NULL or a standard basis
730    * @return true iff there is a next choice of rows and columns
731    * @see PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c,
732    *                                    const ideal& iSB)
733    */
734    PolyMinorValue getNextMinor (const char* algorithm, const ideal& iSB);
735
736    /**
737    * A method for obtaining the next minor when iterating
738    * through all minors of a given size within a pre-defined sub-matrix of an
739    * underlying matrix.<br>
740    * This method should only be called after MinorProcessor::hasNextMinor ()
741    * had been called and yielded \c true.<br>
742    * Computation works using Laplace's algorithm and a cache \a c which may
743    * already contain useful results from previous calls of
744    * PolyMinorValue::getNextMinor (Cache<MinorKey, PolyMinorValue>& c,
745    *                               const ideal& iSB).
746    * If an ideal is given, it is assumed to be a standard basis. In this case,
747    * all results will be reduced w.r.t. to this basis.
748    * @param iSB NULL or a standard basis
749    * @return the next minor
750    * @see PolyMinorValue::getNextMinor (const char* algorithm,
751    *                                    const ideal& iSB)
752    */
753    PolyMinorValue getNextMinor (Cache<MinorKey, PolyMinorValue>& c,
754                                 const ideal& iSB);
755
756    /**
757    * A method for providing a printable version of the represented
758    * MinorProcessor.
759    * @return a printable version of the given instance as instance of class
760    *         string
761    */
762    string toString () const;
763};
764
765#endif
766/* MINOR_PROCESSOR_H */
Note: See TracBrowser for help on using the repository browser.