My Project
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 299 of file MinorProcessor.h.

Constructor & Destructor Documentation

◆ IntMinorProcessor()

IntMinorProcessor::IntMinorProcessor ( )

A constructor for creating an instance.

Definition at line 290 of file MinorProcessor.cc.

291 {
292  _intMatrix = 0;
293 }
int * _intMatrix
private store for integer matrix entries

◆ ~IntMinorProcessor()

IntMinorProcessor::~IntMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 338 of file MinorProcessor.cc.

339 {
340  /* free memory of _intMatrix */
341  delete [] _intMatrix; _intMatrix = 0;
342 }

Member Function Documentation

◆ defineMatrix()

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 350 of file MinorProcessor.cc.

353 {
354  /* free memory of _intMatrix */
356 
357  _rows = numberOfRows;
358  _columns = numberOfColumns;
359 
360  /* allocate memory for new entries in _intMatrix */
361  int n = _rows * _columns;
362  _intMatrix = (int*)omAlloc(n*sizeof(int));
363 
364  /* copying values from one-dimensional method
365  parameter "matrix" */
366  for (int i = 0; i < n; i++)
367  _intMatrix[i] = matrix[i];
368 }
int i
Definition: cfEzgcd.cc:132
int _columns
private store for the number of columns in the underlying matrix
int _rows
private store for the number of rows in the underlying matrix
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:12

◆ getEntry()

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 653 of file MinorProcessor.cc.

655 {
656  return _intMatrix[rowIndex * _columns + columnIndex];
657 }

◆ getMinor() [1/2]

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 370 of file MinorProcessor.cc.

376 {
377  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
379  /* call a helper method which recursively computes the minor using the
380  cache c: */
381  return getMinorPrivateLaplace(dimension, _container, false, c,
382  characteristic, iSB);
383 }
BOOLEAN dimension(leftv res, leftv args)
Definition: bbcone.cc:757
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
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...

◆ getMinor() [2/2]

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 385 of file MinorProcessor.cc.

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

◆ getMinorPrivateBareiss()

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 computed
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 566 of file MinorProcessor.cc.

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

◆ getMinorPrivateLaplace() [1/2]

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 computed
mkthe representation of rows and columns of the minor to be computed
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 659 of file MinorProcessor.cc.

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

◆ getMinorPrivateLaplace() [2/2]

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 computed
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 bool multipleMinors, Cache<MinorKey, IntMinorValue>& c, int characteristic, const ideal& iSB)

Definition at line 449 of file MinorProcessor.cc.

454 {
455  assume(k > 0); /* k is the minor's dimension; the minor must be at least
456  1x1 */
457  /* The method works by recursion, and using Lapace's Theorem along the
458  row/column with the most zeros. */
459  if (k == 1)
460  {
462  if (characteristic != 0) e = e % characteristic;
463  if (iSB != 0) e = getReduction(e, iSB);
464  return IntMinorValue(e, 0, 0, 0, 0, -1, -1); /* "-1" is to signal that any
465  statistics about the number
466  of retrievals does not make
467  sense, as we do not use a
468  cache. */
469  }
470  else
471  {
472  /* Here, the minor must be 2x2 or larger. */
473  int b = getBestLine(k, mk); /* row or column with most
474  zeros */
475  int result = 0; /* This will contain the
476  value of the minor. */
477  int s = 0; int m = 0; int as = 0; int am = 0; /* counters for additions and
478  multiplications, ..."a*"
479  for accumulated operation
480  counters */
481  bool hadNonZeroEntry = false;
482  if (b >= 0)
483  {
484  /* This means that the best line is the row with absolute (0-based)
485  index b.
486  Using Laplace, the sign of the contributing minors must be iterating;
487  the initial sign depends on the relative index of b in minorRowKey: */
488  int sign = (mk.getRelativeRowIndex(b) % 2 == 0 ? 1 : -1);
489  for (int c = 0; c < k; c++) /* This iterates over all involved columns. */
490  {
491  int absoluteC = mk.getAbsoluteColumnIndex(c);
492  if (getEntry(b, absoluteC) != 0) /* Only then do we have to consider
493  this sub-determinante. */
494  {
495  hadNonZeroEntry = true;
496  /* Next MinorKey is mk with row b and column absoluteC omitted: */
497  MinorKey subMk = mk.getSubMinorKey(b, absoluteC);
498  IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk,
499  characteristic, iSB); /* recursive call */
500  m += mv.getMultiplications();
501  s += mv.getAdditions();
503  as += mv.getAccumulatedAdditions();
504  /* adding sub-determinante times matrix entry
505  times appropriate sign: */
506  result += sign * mv.getResult() * getEntry(b, absoluteC);
507 
508  if (characteristic != 0) result = result % characteristic;
509  s++; m++; as++, am++; /* This is for the last addition and
510  multiplication. */
511  }
512  sign = - sign; /* alternating the sign */
513  }
514  }
515  else
516  {
517  b = - b - 1;
518  /* This means that the best line is the column with absolute (0-based)
519  index b.
520  Using Laplace, the sign of the contributing minors must be iterating;
521  the initial sign depends on the relative index of b in
522  minorColumnKey: */
523  int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
524  for (int r = 0; r < k; r++) /* This iterates over all involved rows. */
525  {
526  int absoluteR = mk.getAbsoluteRowIndex(r);
527  if (getEntry(absoluteR, b) != 0) /* Only then do we have to consider
528  this sub-determinante. */
529  {
530  hadNonZeroEntry = true;
531  /* Next MinorKey is mk with row absoluteR and column b omitted. */
532  MinorKey subMk = mk.getSubMinorKey(absoluteR, b);
533  IntMinorValue mv = getMinorPrivateLaplace(k - 1, subMk, characteristic, iSB); /* recursive call */
534  m += mv.getMultiplications();
535  s += mv.getAdditions();
537  as += mv.getAccumulatedAdditions();
538  /* adding sub-determinante times matrix entry
539  times appropriate sign: */
540  result += sign * mv.getResult() * getEntry(absoluteR, b);
541  if (characteristic != 0) result = result % characteristic;
542  s++; m++; as++, am++; /* This is for the last addition and
543  multiplication. */
544  }
545  sign = - sign; /* alternating the sign */
546  }
547  }
548  if (hadNonZeroEntry)
549  {
550  s--; as--; /* first addition was 0 + ..., so we do not count it */
551  }
552  if (s < 0) s = 0; /* may happen when all subminors are zero and no
553  addition needs to be performed */
554  if (as < 0) as = 0; /* may happen when all subminors are zero and no
555  addition needs to be performed */
556  if (iSB != 0) result = getReduction(result, iSB);
557  IntMinorValue newMV(result, m, s, am, as, -1, -1);
558  /* "-1" is to signal that any statistics about the number of retrievals
559  does not make sense, as we do not use a cache. */
560  return newMV;
561  }
562 }
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1019
int getAdditions() const
A method for accessing the additions performed while computing this minor.
Definition: Minor.cc:888
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
Definition: Minor.cc:898
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
Definition: Minor.cc:883
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
Definition: Minor.cc:893

◆ getNextMinor() [1/2]

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 425 of file MinorProcessor.cc.

429 {
430  /* computation with cache */
431  return getMinorPrivateLaplace(_minorSize, _minor, true, c, characteristic,
432  iSB);
433 }
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...

◆ getNextMinor() [2/2]

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 409 of file MinorProcessor.cc.

412 {
413  /* call a helper method which computes the minor (without a cache): */
414  if (strcmp(algorithm, "Laplace") == 0)
415  return getMinorPrivateLaplace(_minorSize, _minor, characteristic, iSB);
416  else if (strcmp(algorithm, "Bareiss") == 0)
417  return getMinorPrivateBareiss(_minorSize, _minor, characteristic, iSB);
418  else assume(false);
419 
420  /* The following code is never reached and just there to make the
421  compiler happy: */
422  return IntMinorValue();
423 }

◆ isEntryZero()

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 344 of file MinorProcessor.cc.

346 {
347  return getEntry(absoluteRowIndex, absoluteColumnIndex) == 0;
348 }

◆ toString()

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 295 of file MinorProcessor.cc.

296 {
297  char h[32];
298  string t = "";
299  string s = "IntMinorProcessor:";
300  s += "\n matrix: ";
301  sprintf(h, "%d", _rows); s += h;
302  s += " x ";
303  sprintf(h, "%d", _columns); s += h;
304  for (int r = 0; r < _rows; r++)
305  {
306  s += "\n ";
307  for (int c = 0; c < _columns; c++)
308  {
309  sprintf(h, "%d", getEntry(r, c)); t = h;
310  for (int k = 0; k < int(4 - strlen(h)); k++) s += " ";
311  s += t;
312  }
313  }
314  int myIndexArray[500];
315  s += "\n considered submatrix has row indices: ";
316  _container.getAbsoluteRowIndices(myIndexArray);
317  for (int k = 0; k < _containerRows; k++)
318  {
319  if (k != 0) s += ", ";
320  sprintf(h, "%d", myIndexArray[k]); s += h;
321  }
322  s += " (first row of matrix has index 0)";
323  s += "\n considered submatrix has column indices: ";
324  _container.getAbsoluteColumnIndices(myIndexArray);
325  for (int k = 0; k < _containerColumns; k++)
326  {
327  if (k != 0) s += ", ";
328  sprintf(h, "%d", myIndexArray[k]); s += h;
329  }
330  s += " (first column of matrix has index 0)";
331  s += "\n size of considered minor(s): ";
332  sprintf(h, "%d", _minorSize); s += h;
333  s += "x";
334  s += h;
335  return s;
336 }
STATIC_VAR Poly * h
Definition: janet.cc:971

Field Documentation

◆ _intMatrix

int* IntMinorProcessor::_intMatrix
private

private store for integer matrix entries

Definition at line 305 of file MinorProcessor.h.


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