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

288 {
289  _intMatrix = 0;
290 }
int * _intMatrix
private store for integer matrix entries

◆ ~IntMinorProcessor()

IntMinorProcessor::~IntMinorProcessor ( )

A destructor for deleting an instance.

Definition at line 335 of file MinorProcessor.cc.

336 {
337  /* free memory of _intMatrix */
338  delete [] _intMatrix; _intMatrix = 0;
339 }

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

350 {
351  /* free memory of _intMatrix */
353 
354  _rows = numberOfRows;
355  _columns = numberOfColumns;
356 
357  /* allocate memory for new entries in _intMatrix */
358  int n = _rows * _columns;
359  _intMatrix = (int*)omAlloc(n*sizeof(int));
360 
361  /* copying values from one-dimensional method
362  parameter "matrix" */
363  for (int i = 0; i < n; i++)
364  _intMatrix[i] = matrix[i];
365 }
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 650 of file MinorProcessor.cc.

652 {
653  return _intMatrix[rowIndex * _columns + columnIndex];
654 }

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

373 {
374  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
376  /* call a helper method which recursively computes the minor using the
377  cache c: */
378  return getMinorPrivateLaplace(dimension, _container, false, c,
379  characteristic, iSB);
380 }
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 382 of file MinorProcessor.cc.

388 {
389  defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
391 
392  /* call a helper method which computes the minor (without a cache): */
393  if (strcmp(algorithm, "Laplace") == 0)
394  return getMinorPrivateLaplace(_minorSize, _container, characteristic,
395  iSB);
396  else if (strcmp(algorithm, "Bareiss") == 0)
397  return getMinorPrivateBareiss(_minorSize, _container, characteristic,
398  iSB);
399  else assume(false);
400 
401  /* The following code is never reached and just there to make the
402  compiler happy: */
403  return IntMinorValue();
404 }
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:387

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

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

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

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

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

426 {
427  /* computation with cache */
428  return getMinorPrivateLaplace(_minorSize, _minor, true, c, characteristic,
429  iSB);
430 }
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 406 of file MinorProcessor.cc.

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

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

343 {
344  return getEntry(absoluteRowIndex, absoluteColumnIndex) == 0;
345 }

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

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