source: git/Singular/MinorProcessor.h @ 894604

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