Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes
IntMinorProcessor Class Reference

Class IntMinorProcessor is derived from class MinorProcessor. More...

#include <MinorProcessor.h>

Public Member Functions

 IntMinorProcessor ()
 A constructor for creating an instance. More...
 
 ~IntMinorProcessor ()
 A destructor for deleting an instance. More...
 
void defineMatrix (const int numberOfRows, const int numberOfColumns, const int *matrix)
 A method for defining a matrix with integer entries. More...
 
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. More...
 
IntMinorValue getMinor (const int dimension, const int *rowIndices, const int *columnIndices, Cache< MinorKey, IntMinorValue > &c, const int characteristic, const ideal &iSB)
 A method for computing the value of a minor using a cache. More...
 
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-defined sub-matrix of an underlying matrix. More...
 
IntMinorValue getNextMinor (Cache< MinorKey, IntMinorValue > &c, const int characteristic, const ideal &iSB)
 A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
std::string toString () const
 A method for providing a printable version of the represented MinorProcessor. More...
 
- Public Member Functions inherited from MinorProcessor
 MinorProcessor ()
 The default constructor. More...
 
virtual ~MinorProcessor ()
 A destructor for deleting an instance. More...
 
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. More...
 
void setMinorSize (const int minorSize)
 Sets the size of the minor(s) of interest. More...
 
bool hasNextMinor ()
 A method for checking whether there is a next choice of rows and columns when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void getCurrentRowIndices (int *const target) const
 A method for obtaining the current set of rows corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void getCurrentColumnIndices (int *const target) const
 A method for obtaining the current set of columns corresponding to the current minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix. More...
 
void print () const
 A method for printing a string representation of the given MinorProcessor to std::cout. More...
 

Protected Member Functions

bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
 A method for testing whether a matrix entry is zero. More...
 
- Protected Member Functions inherited from MinorProcessor
bool setNextKeys (const int k)
 A method for iterating through all possible subsets of k rows and k columns inside a pre-defined submatrix of a pre-defined matrix. More...
 
int getBestLine (const int k, const MinorKey &mk) const
 A method for identifying the row or column with the most zeros. More...
 

Private Member Functions

int getEntry (const int rowIndex, const int columnIndex) const
 A method for retrieving the matrix entry. More...
 
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. More...
 
IntMinorValue getMinorPrivateLaplace (const int k, const MinorKey &mk, const int characteristic, const ideal &iSB)
 A method for computing the value of a minor, without using a cache. More...
 
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. More...
 

Private Attributes

int * _intMatrix
 private store for integer matrix entries More...
 

Additional Inherited Members

- Static Protected Member Functions inherited from MinorProcessor
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. More...
 
static int IOverJ (const int i, const int j)
 A static method for computing the binomial coefficient i over j. More...
 
static int Faculty (const int i)
 A static method for computing the factorial of i. More...
 
- Protected Attributes inherited from MinorProcessor
MinorKey _container
 private store for the rows and columns of the container minor within the underlying matrix; _container will be used to fix a submatrix (e.g. More...
 
int _containerRows
 private store for the number of rows in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*). More...
 
int _containerColumns
 private store for the number of columns in the container minor; This is set by MinorProcessor::defineSubMatrix (const int, const int*, const int, const int*). More...
 
MinorKey _minor
 private store for the rows and columns of the minor of interest; Usually, this minor will encode subsets of the rows and columns in _container. More...
 
int _minorSize
 private store for the dimension of the minor(s) of interest More...
 
int _rows
 private store for the number of rows in the underlying matrix More...
 
int _columns
 private store for the number of columns in the underlying matrix More...
 

Detailed Description

Class IntMinorProcessor is derived from class MinorProcessor.

This class implements the special case of integer matrices.

Author
Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch

Definition at line 302 of file MinorProcessor.h.

Constructor & Destructor Documentation

IntMinorProcessor::IntMinorProcessor ( )

A constructor for creating an instance.

Definition at line 288 of file MinorProcessor.cc.

289 {
290  _intMatrix = 0;
291 }
int * _intMatrix
private store for integer matrix entries
IntMinorProcessor::~IntMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 336 of file MinorProcessor.cc.

337 {
338  /* free memory of _intMatrix */
339  delete [] _intMatrix; _intMatrix = 0;
340 }
int * _intMatrix
private store for integer matrix entries

Member Function Documentation

void IntMinorProcessor::defineMatrix ( const int  numberOfRows,
const int  numberOfColumns,
const int *  matrix 
)

A method for defining a matrix with integer entries.

Parameters
numberOfRowsthe number of rows
numberOfColumnsthe number of columns
matrixthe matrix entries in a linear array, i.e., from left to right and top to bottom
See also
MinorValue::defineSubMatrix (const int, const int*, const int, const int*)

Definition at line 348 of file MinorProcessor.cc.

351 {
352  /* free memory of _intMatrix */
353  delete [] _intMatrix; _intMatrix = 0;
354 
355  _rows = numberOfRows;
356  _columns = numberOfColumns;
357 
358  /* allocate memory for new entries in _intMatrix */
359  int n = _rows * _columns;
360  _intMatrix = new int[n];
361 
362  /* copying values from one-dimensional method
363  parameter "matrix" */
364  for (int i = 0; i < n; i++)
365  _intMatrix[i] = matrix[i];
366 }
int _rows
private store for the number of rows in the underlying matrix
int _columns
private store for the number of columns in the underlying matrix
int * _intMatrix
private store for integer matrix entries
int i
Definition: cfEzgcd.cc:123
int IntMinorProcessor::getEntry ( const int  rowIndex,
const int  columnIndex 
) const
private

A method for retrieving the matrix entry.

Parameters
rowIndexthe absolute (zero-based) row index
columnIndexthe absolute (zero-based) column index
Returns
the specified matrix entry

Definition at line 649 of file MinorProcessor.cc.

651 {
652  return _intMatrix[rowIndex * _columns + columnIndex];
653 }
int _columns
private store for the number of columns in the underlying matrix
int * _intMatrix
private store for integer matrix entries
IntMinorValue IntMinorProcessor::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.


The sub-matrix is determined by rowIndices and columnIndices. Computation works either by Laplace's algorithm or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
dimensionthe size of the minor to be computed
rowIndices0-based indices of the rows of the minor
columnIndices0-based indices of the column of the minor
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
algorithmeither "Bareiss" or "Laplace"
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinor (const int dimension, const int* rowIndices, const int* columnIndices, Cache<MinorKey, IntMinorValue>& c, const int characteristic, const ideal& iSB)

Definition at line 383 of file MinorProcessor.cc.

389 {
390  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
392 
393  /* call a helper method which computes the minor (without a cache): */
394  if (strcmp(algorithm, "Laplace") == 0)
395  return getMinorPrivateLaplace(_minorSize, _container, characteristic,
396  iSB);
397  else if (strcmp(algorithm, "Bareiss") == 0)
398  return getMinorPrivateBareiss(_minorSize, _container, characteristic,
399  iSB);
400  else assume(false);
401 
402  /* The following code is never reached and just there to make the
403  compiler happy: */
404  return IntMinorValue();
405 }
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.
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:717
int _minorSize
private store for the dimension of the minor(s) of interest
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&#39;s algorithm.
#define assume(x)
Definition: mod2.h:405
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:701
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.
IntMinorValue IntMinorProcessor::getMinor ( const int  dimension,
const int *  rowIndices,
const int *  columnIndices,
Cache< MinorKey, IntMinorValue > &  c,
const int  characteristic,
const ideal &  iSB 
)

A method for computing the value of a minor using a cache.


The sub-matrix is determined by rowIndices and columnIndices. Computation works by Laplace's algorithm together with caching of subdeterminants.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
dimensionthe size of the minor to be computed
rowIndices0-based indices of the rows of the minor
columnIndices0-based indices of the column of the minor
cthe cache for storing subdeterminants
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinor (const int dimension, const int* rowIndices, const int* columnIndices, const int characteristic, const ideal& iSB, const char* algorithm)

Definition at line 368 of file MinorProcessor.cc.

374 {
375  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
377  /* call a helper method which recursively computes the minor using the
378  cache c: */
379  return getMinorPrivateLaplace(dimension, _container, false, c,
380  characteristic, iSB);
381 }
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 _minorSize
private store for the dimension of the minor(s) of interest
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:701
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.
IntMinorValue IntMinorProcessor::getMinorPrivateBareiss ( const int  k,
const MinorKey mk,
const int  characteristic,
const ideal &  iSB 
)
private

A method for computing the value of a minor using Bareiss's algorithm.


The sub-matrix is specified by mk. If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be computed
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const int characteristic, const ideal& iSB)

Definition at line 564 of file MinorProcessor.cc.

569 {
570  assume(k > 0); /* k is the minor's dimension; the minor must be at least
571  1x1 */
572  int *theRows=new int[k]; mk.getAbsoluteRowIndices(theRows);
573  int *theColumns=new int[k]; mk.getAbsoluteColumnIndices(theColumns);
574  /* the next line provides the return value for the case k = 1 */
575  int e = getEntry(theRows[0], theColumns[0]);
576  if (characteristic != 0) e = e % characteristic;
577  if (iSB != 0) e = getReduction(e, iSB);
578  IntMinorValue mv(e, 0, 0, 0, 0, -1, -1);
579  if (k > 1)
580  {
581  /* the matrix to perform Bareiss with */
582  long *tempMatrix=new long[k * k];
583  /* copy correct set of entries from _intMatrix to tempMatrix */
584  int i = 0;
585  for (int r = 0; r < k; r++)
586  for (int c = 0; c < k; c++)
587  {
588  e = getEntry(theRows[r], theColumns[c]);
589  if (characteristic != 0) e = e % characteristic;
590  tempMatrix[i++] = e;
591  }
592  /* Bareiss algorithm operating on tempMatrix which is at least 2x2 */
593  int sign = 1; /* This will store the correct sign resulting
594  from permuting the rows of tempMatrix. */
595  int *rowPermutation=new int[k];
596  /* This is for storing the permutation of rows
597  resulting from searching for a non-zero
598  pivot element. */
599  for (int i = 0; i < k; i++) rowPermutation[i] = i;
600  int divisor = 1; /* the Bareiss divisor */
601  for (int r = 0; r <= k - 2; r++)
602  {
603  /* look for a non-zero entry in column r: */
604  int i = r;
605  while ((i < k) && (tempMatrix[rowPermutation[i] * k + r] == 0))
606  i++;
607  if (i == k)
608  /* There is no non-zero entry; hence the minor is zero. */
609  return IntMinorValue(0, 0, 0, 0, 0, -1, -1);
610  if (i != r)
611  {
612  /* We swap the rows with indices r and i: */
613  int j = rowPermutation[i];
614  rowPermutation[i] = rowPermutation[r];
615  rowPermutation[r] = j;
616  /* Now we know that tempMatrix[rowPermutation[r] * k + r] is not zero.
617  But carefull; we have to negate the sign, as there is always an odd
618  number of row transpositions to swap two given rows of a matrix. */
619  sign = -sign;
620  }
621  if (r >= 1) divisor = tempMatrix[rowPermutation[r - 1] * k + r - 1];
622  for (int rr = r + 1; rr < k; rr++)
623  for (int cc = r + 1; cc < k; cc++)
624  {
625  e = rowPermutation[rr] * k + cc;
626  /* Attention: The following may cause an overflow and
627  thus a wrong result: */
628  tempMatrix[e] = tempMatrix[e] * tempMatrix[rowPermutation[r] * k + r]
629  - tempMatrix[rowPermutation[r] * k + cc]
630  * tempMatrix[rowPermutation[rr] * k + r];
631  /* The following is, by theory, always a division without
632  remainder: */
633  tempMatrix[e] = tempMatrix[e] / divisor;
634  if (characteristic != 0)
635  tempMatrix[e] = tempMatrix[e] % characteristic;
636  }
637  delete[] rowPermutation;
638  delete[] tempMatrix;
639  }
640  int theValue = sign * tempMatrix[rowPermutation[k - 1] * k + k - 1];
641  if (iSB != 0) theValue = getReduction(theValue, iSB);
642  mv = IntMinorValue(theValue, 0, 0, 0, 0, -1, -1);
643  }
644  delete [] theRows;
645  delete [] theColumns;
646  return mv;
647 }
int getReduction(const int i, const ideal &iSB)
int k
Definition: cfEzgcd.cc:93
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:717
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:405
int i
Definition: cfEzgcd.cc:123
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
Definition: Minor.cc:206
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey. ...
Definition: Minor.cc:185
int sign(const CanonicalForm &a)
IntMinorValue IntMinorProcessor::getMinorPrivateLaplace ( const int  k,
const MinorKey mk,
const bool  multipleMinors,
Cache< MinorKey, IntMinorValue > &  c,
int  characteristic,
const ideal &  iSB 
)
private

A method for computing the value of a minor, using a cache.


The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be comuted
multipleMinorsdecides whether we compute just one or all minors of a specified size
ca cache to be used for caching reusable sub-minors
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const int characteristic, const ideal& iSB)

Definition at line 655 of file MinorProcessor.cc.

660 {
661  assume(k > 0); /* k is the minor's dimension; the minor must be at least
662  1x1 */
663  /* The method works by recursion, and using Lapace's Theorem along
664  the row/column with the most zeros. */
665  if (k == 1)
666  {
668  if (characteristic != 0) e = e % characteristic;
669  if (iSB != 0) e = getReduction(e, iSB);
670  return IntMinorValue(e, 0, 0, 0, 0, -1, -1);
671  /* we set "-1" as, for k == 1, we do not have any cache retrievals */
672  }
673  else
674  {
675  int b = getBestLine(k, mk); /* row or column with
676  most zeros */
677  int result = 0; /* This will contain the
678  value of the minor. */
679  int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions
680  and multiplications,
681  ..."a*" for
682  accumulated operation
683  counters */
684  IntMinorValue mv(0, 0, 0, 0, 0, 0, 0); /* for storing all
685  intermediate minors */
686  bool hadNonZeroEntry = false;
687  if (b >= 0)
688  {
689  /* This means that the best line is the row with absolute (0-based)
690  index b.
691  Using Laplace, the sign of the contributing minors must be
692  iterating; the initial sign depends on the relative index of b
693  in minorRowKey: */
694  int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
695  for (int c = 0; c < k; c++) /* This iterates over all involved
696  columns. */
697  {
698  int absoluteC = mk.getAbsoluteColumnIndex(c);
699  if (getEntry(b, absoluteC) != 0) /* Only then do we have to consider
700  this sub-determinante. */
701  {
702  hadNonZeroEntry = true;
703  /* Next MinorKey is mk with row b and column absoluteC omitted. */
704  MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
705  if (cch.hasKey(subMk))
706  { /* trying to find the result in the cache */
707  mv = cch.getValue(subMk);
708  mv.incrementRetrievals(); /* once more, we made use of the cached
709  value for key mk */
710  cch.put(subMk, mv); /* We need to do this with "put", as the
711  (altered) number of retrievals may have
712  an impact on the internal ordering among
713  the cached entries. */
714  }
715  else
716  {
717  mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch,
718  characteristic, iSB); /* recursive call */
719  /* As this minor was not in the cache, we count the additions
720  and multiplications that we needed to perform in the
721  recursive call: */
722  m += mv.getMultiplications();
723  s += mv.getAdditions();
724  }
725  /* In any case, we count all nested operations in the accumulative
726  counters: */
727  am += mv.getAccumulatedMultiplications();
728  as += mv.getAccumulatedAdditions();
729  /* adding sub-determinante times matrix entry times appropriate
730  sign */
731  result += sign * mv.getResult() * getEntry(b, absoluteC);
732  if (characteristic != 0) result = result % characteristic;
733  s++; m++; as++; am++; /* This is for the last addition and
734  multiplication. */
735  }
736  sign = - sign; /* alternating the sign */
737  }
738  }
739  else
740  {
741  b = - b - 1;
742  /* This means that the best line is the column with absolute (0-based)
743  index b.
744  Using Laplace, the sign of the contributing minors must be iterating;
745  the initial sign depends on the relative index of b in
746  minorColumnKey: */
747  int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
748  for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
749  {
750  int absoluteR = mk.getAbsoluteRowIndex(r);
751  if (getEntry(absoluteR, b) != 0) /* Only then do we have to consider
752  this sub-determinante. */
753  {
754  hadNonZeroEntry = true;
755  /* Next MinorKey is mk with row absoluteR and column b omitted. */
756  MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
757  if (cch.hasKey(subMk))
758  { /* trying to find the result in the cache */
759  mv = cch.getValue(subMk);
760  mv.incrementRetrievals(); /* once more, we made use of the cached
761  value for key mk */
762  cch.put(subMk, mv); /* We need to do this with "put", as the
763  (altered) number of retrievals may have an
764  impact on the internal ordering among the
765  cached entries. */
766  }
767  else
768  {
769  mv = getMinorPrivateLaplace(k - 1, subMk, multipleMinors, cch, characteristic, iSB); /* recursive call */
770  /* As this minor was not in the cache, we count the additions and
771  multiplications that we needed to do in the recursive call: */
772  m += mv.getMultiplications();
773  s += mv.getAdditions();
774  }
775  /* In any case, we count all nested operations in the accumulative
776  counters: */
777  am += mv.getAccumulatedMultiplications();
778  as += mv.getAccumulatedAdditions();
779  /* adding sub-determinante times matrix entry times appropriate
780  sign: */
781  result += sign * mv.getResult() * getEntry(absoluteR, b);
782  if (characteristic != 0) result = result % characteristic;
783  s++; m++; as++; am++; /* This is for the last addition and
784  multiplication. */
785  }
786  sign = - sign; /* alternating the sign */
787  }
788  }
789  /* Let's cache the newly computed minor: */
790  int potentialRetrievals = NumberOfRetrievals(_containerRows,
792  _minorSize, k,
793  multipleMinors);
794  if (hadNonZeroEntry)
795  {
796  s--; as--; /* first addition was 0 + ..., so we do not count it */
797  }
798  if (s < 0) s = 0; /* may happen when all subminors are zero and no
799  addition needs to be performed */
800  if (as < 0) as = 0; /* may happen when all subminors are zero and no
801  addition needs to be performed */
802  if (iSB != 0) result = getReduction(result, iSB);
803  IntMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
804  cch.put(mk, newMV); /* Here's the actual put inside the cache. */
805  return newMV;
806  }
807 }
int getReduction(const int i, const ideal &iSB)
const CanonicalForm int s
Definition: facAbsFact.cc:55
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 _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this...
Definition: Minor.cc:121
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...
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
Definition: Minor.cc:347
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
int _minorSize
private store for the dimension of the minor(s) of interest
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
Definition: Minor.cc:259
const ring r
Definition: syzextra.cc:208
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
#define assume(x)
Definition: mod2.h:405
int m
Definition: cfEzgcd.cc:119
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
Definition: Minor.cc:227
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this...
Definition: Minor.cc:153
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
Definition: Minor.h:39
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
const poly b
Definition: syzextra.cc:213
return result
Definition: facAbsBiFact.cc:76
int sign(const CanonicalForm &a)
IntMinorValue IntMinorProcessor::getMinorPrivateLaplace ( const int  k,
const MinorKey mk,
const int  characteristic,
const ideal &  iSB 
)
private

A method for computing the value of a minor, without using a cache.


The sub-matrix is specified by mk. Computation works recursively using Laplace's Theorem. We always develop along the row or column with the most zeros; see MinorProcessor::getBestLine (const int k, const MinorKey& mk). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
kthe number of rows and columns in the minor to be comuted
mkthe representation of rows and columns of the minor to be comuted
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
Returns
an instance of MinorValue representing the value of the corresponding minor
See also
MinorProcessor::getMinorPrivateLaplace (const int k, const MinorKey& mk, const bool multipleMinors, Cache<MinorKey, IntMinorValue>& c, int characteristic, const ideal& iSB)

Definition at line 447 of file MinorProcessor.cc.

452 {
453  assume(k > 0); /* k is the minor's dimension; the minor must be at least
454  1x1 */
455  /* The method works by recursion, and using Lapace's Theorem along the
456  row/column with the most zeros. */
457  if (k == 1)
458  {
460  if (characteristic != 0) e = e % characteristic;
461  if (iSB != 0) e = getReduction(e, iSB);
462  return IntMinorValue(e, 0, 0, 0, 0, -1, -1); /* "-1" is to signal that any
463  statistics about the number
464  of retrievals does not make
465  sense, as we do not use a
466  cache. */
467  }
468  else
469  {
470  /* Here, the minor must be 2x2 or larger. */
471  int b = getBestLine(k, mk); /* row or column with most
472  zeros */
473  int result = 0; /* This will contain the
474  value of the minor. */
475  int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions and
476  multiplications, ..."a*"
477  for accumulated operation
478  counters */
479  bool hadNonZeroEntry = false;
480  if (b >= 0)
481  {
482  /* This means that the best line is the row with absolute (0-based)
483  index b.
484  Using Laplace, the sign of the contributing minors must be iterating;
485  the initial sign depends on the relative index of b in minorRowKey: */
486  int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
487  for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
488  {
489  int absoluteC = mk.getAbsoluteColumnIndex(c);
490  if (getEntry(b, absoluteC) != 0) /* Only then do we have to consider
491  this sub-determinante. */
492  {
493  hadNonZeroEntry = true;
494  /* Next MinorKey is mk with row b and column absoluteC omitted: */
495  MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
496  IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk,
497  characteristic, iSB); /* recursive call */
498  m += mv.getMultiplications();
499  s += mv.getAdditions();
501  as += mv.getAccumulatedAdditions();
502  /* adding sub-determinante times matrix entry
503  times appropriate sign: */
504  result += sign * mv.getResult() * getEntry(b, absoluteC);
505 
506  if (characteristic != 0) result = result % characteristic;
507  s++; m++; as++, am++; /* This is for the last addition and
508  multiplication. */
509  }
510  sign = - sign; /* alternating the sign */
511  }
512  }
513  else
514  {
515  b = - b - 1;
516  /* This means that the best line is the column with absolute (0-based)
517  index b.
518  Using Laplace, the sign of the contributing minors must be iterating;
519  the initial sign depends on the relative index of b in
520  minorColumnKey: */
521  int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
522  for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
523  {
524  int absoluteR = mk.getAbsoluteRowIndex(r);
525  if (getEntry(absoluteR, b) != 0) /* Only then do we have to consider
526  this sub-determinante. */
527  {
528  hadNonZeroEntry = true;
529  /* Next MinorKey is mk with row absoluteR and column b omitted. */
530  MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
531  IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, characteristic, iSB); /* recursive call */
532  m += mv.getMultiplications();
533  s += mv.getAdditions();
535  as += mv.getAccumulatedAdditions();
536  /* adding sub-determinante times matrix entry
537  times appropriate sign: */
538  result += sign * mv.getResult() * getEntry(absoluteR, b);
539  if (characteristic != 0) result = result % characteristic;
540  s++; m++; as++, am++; /* This is for the last addition and
541  multiplication. */
542  }
543  sign = - sign; /* alternating the sign */
544  }
545  }
546  if (hadNonZeroEntry)
547  {
548  s--; as--; /* first addition was 0 + ..., so we do not count it */
549  }
550  if (s < 0) s = 0; /* may happen when all subminors are zero and no
551  addition needs to be performed */
552  if (as < 0) as = 0; /* may happen when all subminors are zero and no
553  addition needs to be performed */
554  if (iSB != 0) result = getReduction(result, iSB);
555  IntMinorValue newMV(result, m, s, am, as, -1, -1);
556  /* "-1" is to signal that any statistics about the number of retrievals
557  does not make sense, as we do not use a cache. */
558  return newMV;
559  }
560 }
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
Definition: Minor.cc:894
int getReduction(const int i, const ideal &iSB)
const CanonicalForm int s
Definition: facAbsFact.cc:55
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 getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
Definition: Minor.cc:899
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this...
Definition: Minor.cc:121
int k
Definition: cfEzgcd.cc:93
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
Definition: Minor.cc:347
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:717
int getAdditions() const
A method for accessing the additions performed while computing this minor.
Definition: Minor.cc:889
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
Definition: Minor.cc:259
const ring r
Definition: syzextra.cc:208
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
#define assume(x)
Definition: mod2.h:405
int m
Definition: cfEzgcd.cc:119
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
Definition: Minor.cc:227
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this...
Definition: Minor.cc:153
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
Definition: Minor.cc:884
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
Definition: Minor.h:39
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
const poly b
Definition: syzextra.cc:213
return result
Definition: facAbsBiFact.cc:76
int sign(const CanonicalForm &a)
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
IntMinorValue IntMinorProcessor::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-defined sub-matrix of an underlying matrix.


This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works by Laplace's algorithm (without using a cache) or by Bareiss's algorithm.
If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
algorithmeither "Bareiss" or "Laplace"
Returns
the next minor
See also
IntMinorValue::getNextMinor (Cache<MinorKey, IntMinorValue>& c, const int characteristic, const ideal& iSB)

Definition at line 407 of file MinorProcessor.cc.

410 {
411  /* call a helper method which computes the minor (without a cache): */
412  if (strcmp(algorithm, "Laplace") == 0)
413  return getMinorPrivateLaplace(_minorSize, _minor, characteristic, iSB);
414  else if (strcmp(algorithm, "Bareiss") == 0)
415  return getMinorPrivateBareiss(_minorSize, _minor, characteristic, iSB);
416  else assume(false);
417 
418  /* The following code is never reached and just there to make the
419  compiler happy: */
420  return IntMinorValue();
421 }
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.
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:717
int _minorSize
private store for the dimension of the minor(s) of interest
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&#39;s algorithm.
#define assume(x)
Definition: mod2.h:405
IntMinorValue IntMinorProcessor::getNextMinor ( Cache< MinorKey, IntMinorValue > &  c,
const int  characteristic,
const ideal &  iSB 
)

A method for obtaining the next minor when iterating through all minors of a given size within a pre-defined sub-matrix of an underlying matrix.


This method should only be called after MinorProcessor::hasNextMinor () had been called and yielded true.
Computation works using the cache c which may already contain useful results from previous calls of IntMinorValue::getNextMinor (Cache<MinorKey, IntMinorValue>& c, const int characteristic, const ideal& iSB). If an ideal is given, it is assumed to be a standard basis. In this case, all results will be reduced w.r.t. to this basis. Moreover, if the given characteristic is non-zero, all results will be computed modulo this characteristic.

Parameters
cthe cache
characteristic0 or the characteristic of the underlying coefficient ring/field
iSBNULL or a standard basis
Returns
the next minor
See also
IntMinorValue::getNextMinor (const int characteristic, const ideal& iSB, const char* algorithm)

Definition at line 423 of file MinorProcessor.cc.

427 {
428  /* computation with cache */
429  return getMinorPrivateLaplace(_minorSize, _minor, true, c, characteristic,
430  iSB);
431 }
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.
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
int _minorSize
private store for the dimension of the minor(s) of interest
bool IntMinorProcessor::isEntryZero ( const int  absoluteRowIndex,
const int  absoluteColumnIndex 
) const
protectedvirtual

A method for testing whether a matrix entry is zero.

Parameters
absoluteRowIndexthe absolute (zero-based) row index
absoluteColumnIndexthe absolute (zero-based) column index
Returns
true iff the specified matrix entry is zero

Reimplemented from MinorProcessor.

Definition at line 342 of file MinorProcessor.cc.

344 {
345  return getEntry(absoluteRowIndex, absoluteColumnIndex) == 0;
346 }
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
string IntMinorProcessor::toString ( ) const
virtual

A method for providing a printable version of the represented MinorProcessor.

Returns
a printable version of the given instance as instance of class string

Reimplemented from MinorProcessor.

Definition at line 293 of file MinorProcessor.cc.

294 {
295  char h[32];
296  string t = "";
297  string s = "IntMinorProcessor:";
298  s += "\n matrix: ";
299  sprintf(h, "%d", _rows); s += h;
300  s += " x ";
301  sprintf(h, "%d", _columns); s += h;
302  for (int r = 0; r < _rows; r++)
303  {
304  s += "\n ";
305  for (int c = 0; c < _columns; c++)
306  {
307  sprintf(h, "%d", getEntry(r, c)); t = h;
308  for (int k = 0; k < int(4 - strlen(h)); k++) s += " ";
309  s += t;
310  }
311  }
312  int myIndexArray[500];
313  s += "\n considered submatrix has row indices: ";
314  _container.getAbsoluteRowIndices(myIndexArray);
315  for (int k = 0; k < _containerRows; k++)
316  {
317  if (k != 0) s += ", ";
318  sprintf(h, "%d", myIndexArray[k]); s += h;
319  }
320  s += " (first row of matrix has index 0)";
321  s += "\n considered submatrix has column indices: ";
322  _container.getAbsoluteColumnIndices(myIndexArray);
323  for (int k = 0; k < _containerColumns; k++)
324  {
325  if (k != 0) s += ", ";
326  sprintf(h, "%d", myIndexArray[k]); s += h;
327  }
328  s += " (first column of matrix has index 0)";
329  s += "\n size of considered minor(s): ";
330  sprintf(h, "%d", _minorSize); s += h;
331  s += "x";
332  s += h;
333  return s;
334 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
int _rows
private store for the number of rows in the underlying matrix
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...
int _minorSize
private store for the dimension of the minor(s) of interest
const ring r
Definition: syzextra.cc:208
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
Definition: Minor.cc:206
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey. ...
Definition: Minor.cc:185
static Poly * h
Definition: janet.cc:978

Field Documentation

int* IntMinorProcessor::_intMatrix
private

private store for integer matrix entries

Definition at line 308 of file MinorProcessor.h.


The documentation for this class was generated from the following files: