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