My Project
Loading...
Searching...
No Matches
MinorProcessor.h
Go to the documentation of this file.
1#ifndef MINOR_PROCESSOR_H
2#define MINOR_PROCESSOR_H
3
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
26void 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 possible 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 useful 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 */
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 */
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 computed
326 * @param mk the representation of rows and columns of the minor to be
327 * computed
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 computed
358 * @param mk the representation of rows and columns of the minor to be
359 * computed
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 computed
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 */
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 computed
585 * @param mk the representation of rows and columns of the minor to be
586 * computed
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 computed
611 * @param mk the representation of rows and columns of the minor to be
612 * computed
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 computed
630 * @param mk the representation of rows and columns of the minor to be
631 * computed
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:132
int k
Definition: cfEzgcd.cc:99
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:110
Compatibility layer for legacy polynomial operations (over currRing)