MinorProcessor.h
Go to the documentation of this file.
1 #ifndef MINOR_PROCESSOR_H
2 #define MINOR_PROCESSOR_H
3 
6 
7 struct spolyrec; typedef struct spolyrec polyrec; typedef polyrec* poly;
8 struct ip_sring; typedef struct ip_sring* ring; typedef struct ip_sring const* const_ring;
9 
10 struct 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 
29 void 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 */
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  */
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  */
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  */
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  */
160 
161  /**
162  * private store for the dimension of the minor(s) of interest
163  */
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 */
303 {
304  private:
305  /**
306  * private store for integer matrix entries
307  */
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,
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  */
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,
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  */
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 */
564 {
565  private:
566  /**
567  * private store for polynomial matrix entries
568  */
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,
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  */
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,
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  */
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 */
Class MinorProcessor implements the key methods for computing one or all sub-determinantes of a given...
static int IOverJ(const int i, const int j)
A static method for computing the binomial coefficient i over j.
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.
void print() const
A method for printing a string representation of the given MinorProcessor to std::cout.
int _rows
private store for the number of rows in the underlying matrix
virtual std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
#define string
Definition: libparse.cc:1250
Definition: ring.h:255
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
int _columns
private store for the number of columns in the underlying matrix
int k
Definition: cfEzgcd.cc:93
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
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.
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:717
MinorProcessor()
The default constructor.
int _minorSize
private store for the dimension of the minor(s) of interest
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
int * _intMatrix
private store for integer matrix entries
bool setNextKeys(const int k)
A method for iterating through all possible subsets of k rows and k columns inside a pre-defined subm...
int j
Definition: myNF.cc:70
void getCurrentRowIndices(int *const target) const
A method for obtaining the current set of rows corresponding to the current minor when iterating thro...
static int Faculty(const int i)
A static method for computing the factorial of i.
virtual bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
int i
Definition: cfEzgcd.cc:123
void getCurrentColumnIndices(int *const target) const
A method for obtaining the current set of columns corresponding to the current minor when iterating t...
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:799
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
BOOLEAN dimension(leftv res, leftv args)
Definition: bbcone.cc:713
The following sip_sideal structure has many different uses thoughout Singular. Basic use-cases for it...
Definition: simpleideals.h:18
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
Definition: Minor.h:39
polyrec * poly
Definition: MinorProcessor.h:7
void printCounters(char *prefix, bool resetToZero)
poly * _polyMatrix
private store for polynomial matrix entries
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
Class IntMinorProcessor is derived from class MinorProcessor.
#define const
Definition: fegetopt.c:41
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
polyrec * poly
Definition: hilb.h:10
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.
virtual ~MinorProcessor()
A destructor for deleting an instance.