Functions
MinorInterface.cc File Reference
#include <kernel/mod2.h>
#include <kernel/linear_algebra/MinorInterface.h>
#include <kernel/linear_algebra/MinorProcessor.h>
#include <polys/simpleideals.h>
#include <kernel/polys.h>
#include <kernel/structs.h>
#include <kernel/GBEngine/kstd1.h>
#include <kernel/ideals.h>

Go to the source code of this file.

Functions

bool currRingIsOverIntegralDomain ()
 
bool currRingIsOverField ()
 
bool arrayIsNumberArray (const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
 
ideal getMinorIdeal_Int (const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
 
ideal getMinorIdeal_Poly (const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
 
ideal getMinorIdeal_toBeDone (const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
 
ideal getMinorIdeal (const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal iSB, const bool allDifferent)
 Returns the specified set of minors (= subdeterminantes) of the given matrix. More...
 
ideal getMinorIdealCache_Int (const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
 
ideal getMinorIdealCache_Poly (const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
 
ideal getMinorIdealCache_toBeDone (const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
 
ideal getMinorIdealCache (const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
 Returns the specified set of minors (= subdeterminantes) of the given matrix. More...
 
ideal getMinorIdealHeuristic (const matrix mat, const int minorSize, const int k, const ideal iSB, const bool allDifferent)
 Returns the specified set of minors (= subdeterminantes) of the given matrix. More...
 

Function Documentation

bool arrayIsNumberArray ( const poly polyArray,
const ideal  iSB,
const int  length,
int *  intArray,
poly nfPolyArray,
int &  zeroCounter 
)

Definition at line 45 of file MinorInterface.cc.

48 {
49  int n = 0; if (currRing != 0) n = currRing->N;
50  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
51  zeroCounter = 0;
52  bool result = true;
53 
54  for (int i = 0; i < length; i++)
55  {
56  nfPolyArray[i] = pCopy(polyArray[i]);
57  if (iSB != 0) nfPolyArray[i] = kNF(iSB, currRing->qideal, nfPolyArray[i]);
58  if (nfPolyArray[i] == NULL)
59  {
60  intArray[i] = 0;
61  zeroCounter++;
62  }
63  else
64  {
65  bool isConstant = true;
66  for (int j = 1; j <= n; j++)
67  if (pGetExp(nfPolyArray[i], j) > 0)
68  isConstant = false;
69  if (!isConstant) result = false;
70  else
71  {
72  intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing->cf);
73  if (characteristic != 0) intArray[i] = intArray[i] % characteristic;
74  if (intArray[i] == 0) zeroCounter++;
75  }
76  }
77  }
78  return result;
79 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
int rChar(ring r)
Definition: ring.cc:684
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ...
Definition: coeffs.h:548
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
return result
Definition: facAbsBiFact.cc:76
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
bool currRingIsOverField ( )

Definition at line 29 of file MinorInterface.cc.

30 {
31  if (rField_is_Ring_PtoM(currRing)) return false;
32  if (rField_is_Ring_2toM(currRing)) return false;
33  if (rField_is_Ring_ModN(currRing)) return false;
34  if (rField_is_Ring_Z(currRing)) return false;
35  return true;
36 }
static BOOLEAN rField_is_Ring_PtoM(const ring r)
Definition: ring.h:431
static BOOLEAN rField_is_Ring_ModN(const ring r)
Definition: ring.h:428
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static BOOLEAN rField_is_Ring_2toM(const ring r)
Definition: ring.h:425
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:434
bool currRingIsOverIntegralDomain ( )

Definition at line 21 of file MinorInterface.cc.

22 {
23  if (rField_is_Ring_PtoM(currRing)) return false;
24  if (rField_is_Ring_2toM(currRing)) return false;
25  if (rField_is_Ring_ModN(currRing)) return false;
26  return true;
27 }
static BOOLEAN rField_is_Ring_PtoM(const ring r)
Definition: ring.h:431
static BOOLEAN rField_is_Ring_ModN(const ring r)
Definition: ring.h:428
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static BOOLEAN rField_is_Ring_2toM(const ring r)
Definition: ring.h:425
ideal getMinorIdeal ( const matrix  m,
const int  minorSize,
const int  k,
const char *  algorithm,
const ideal  i,
const bool  allDifferent 
)

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
algorithm must be one of "Bareiss" and "Laplace".
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
algorithmthe algorithm to be used for the computation
iNULL or an ideal which encodes a standard basis
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 251 of file MinorInterface.cc.

254 {
255  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
256  to enable faster computations in the case of matrices which contain
257  only numbers. But so far, this method is not yet usable as it replaces
258  the numbers by ints which may result in overflows during computations
259  of minors. */
260  int rowCount = mat->nrows;
261  int columnCount = mat->ncols;
262  poly* myPolyMatrix = (poly*)(mat->m);
263  int length = rowCount * columnCount;
264  poly* nfPolyMatrix = new poly[length];
265  ideal iii; /* the ideal to be filled and returned */
266 
267  /* copy all polynomials and reduce them w.r.t. iSB
268  (if iSB is present, i.e., not the NULL pointer) */
269  for (int i = 0; i < length; i++)
270  {
271  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
272  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
273  nfPolyMatrix[i]);
274  }
275 
276  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
277  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
278  {
279  /* In this case, we call an optimized procedure, dating back to
280  Wilfried Pohl. It may be used whenever
281  - all minors are requested,
282  - requested minors need not be mutually distinct, and
283  - coefficients come from a field (i.e., the ring Z is not
284  allowed for this implementation). */
285  iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
286  iSB));
287  }
288  else
289  {
290  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
291  k, algorithm, iSB, allDifferent);
292  }
293 
294  /* clean up */
295  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
296  delete [] nfPolyMatrix;
297 
298  return iii;
299 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
int ncols
Definition: matpol.h:22
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
poly * m
Definition: matpol.h:19
int nrows
Definition: matpol.h:21
int j
Definition: myNF.cc:70
ideal idMinors(matrix a, int ar, ideal R)
compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R ...
Definition: ideals.cc:1794
int i
Definition: cfEzgcd.cc:123
ideal getMinorIdeal_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:434
#define pDelete(p_ptr)
Definition: polys.h:157
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
ideal getMinorIdeal_Int ( const int *  intMatrix,
const int  rowCount,
const int  columnCount,
const int  minorSize,
const int  k,
const char *  algorithm,
const ideal  i,
const bool  allDifferent 
)

Definition at line 87 of file MinorInterface.cc.

91 {
92  /* setting up a MinorProcessor for matrices with integer entries: */
94  mp.defineMatrix(rowCount, columnCount, intMatrix);
95  int *myRowIndices=new int[rowCount];
96  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
97  int *myColumnIndices=new int[columnCount];
98  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
99  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
100  mp.setMinorSize(minorSize);
101 
102  /* containers for all upcoming results: */
103  IntMinorValue theMinor;
104  // int value = 0;
105  int collectedMinors = 0;
106  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
107 
108  /* the ideal to be returned: */
109  ideal iii = idInit(1);
110 
111  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
112  omitting zero minors */
113  bool duplicatesOk = (allDifferent ? false : true);
114  int kk = ((k < 0) ? -k : k); /* absolute value of k */
115 
116  /* looping over all minors: */
117  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
118  {
119  /* retrieving the next minor: */
120  theMinor = mp.getNextMinor(characteristic, i, algorithm);
121  poly f = NULL;
122  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
123  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
124  collectedMinors++;
125  }
126 
127  /* before we return the result, let's omit zero generators
128  in iii which come after the computed minors */
129  ideal jjj;
130  if (collectedMinors == 0) jjj = idInit(1);
131  else jjj = idCopyFirstK(iii, collectedMinors);
132  idDelete(&iii);
133  delete[] myColumnIndices;
134  delete[] myRowIndices;
135  return jjj;
136 }
int rChar(ring r)
Definition: ring.cc:684
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
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
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-...
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
BOOLEAN idInsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
Definition: ideals.h:90
#define NULL
Definition: omList.c:10
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
Class IntMinorProcessor is derived from class MinorProcessor.
void defineMatrix(const int numberOfRows, const int numberOfColumns, const int *matrix)
A method for defining a matrix with integer entries.
polyrec * poly
Definition: hilb.h:10
#define pISet(i)
Definition: polys.h:283
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
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.
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
ideal getMinorIdeal_Poly ( const poly polyMatrix,
const int  rowCount,
const int  columnCount,
const int  minorSize,
const int  k,
const char *  algorithm,
const ideal  i,
const bool  allDifferent 
)

Definition at line 142 of file MinorInterface.cc.

146 {
147  /* setting up a MinorProcessor for matrices with polynomial entries: */
149  mp.defineMatrix(rowCount, columnCount, polyMatrix);
150  int *myRowIndices=new int[rowCount];
151  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
152  int *myColumnIndices=new int[columnCount];
153  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
154  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
155  mp.setMinorSize(minorSize);
156 
157  /* containers for all upcoming results: */
158  PolyMinorValue theMinor;
159  poly f = NULL;
160  int collectedMinors = 0;
161 
162  /* the ideal to be returned: */
163  ideal iii = idInit(1);
164 
165  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
166  requested, omitting zero minors */
167  bool duplicatesOk = (allDifferent ? false : true);
168  int kk = ((k < 0) ? -k : k); /* absolute value of k */
169 #ifdef COUNT_AND_PRINT_OPERATIONS
170  printCounters ("starting", true);
171  int qqq = 0;
172 #endif
173  /* looping over all minors: */
174  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
175  {
176  /* retrieving the next minor: */
177  theMinor = mp.getNextMinor(algorithm, i);
178 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
179  qqq++;
180  Print("after %d", qqq);
181  printCounters ("-th minor", false);
182 #endif
183  f = theMinor.getResult();
184  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
185  zeroOk, duplicatesOk))
186  collectedMinors++;
187  }
188 #ifdef COUNT_AND_PRINT_OPERATIONS
189  printCounters ("ending", true);
190 #endif
191 
192  /* before we return the result, let's omit zero generators
193  in iii which come after the computed minors */
194  idKeepFirstK(iii, collectedMinors);
195  delete[] myColumnIndices;
196  delete[] myRowIndices;
197  return(iii);
198 }
void idKeepFirstK(ideal id, const int k)
keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero...
Definition: ideals.cc:2581
#define Print
Definition: emacs.cc:83
Class PolyMinorProcessor is derived from class MinorProcessor.
int k
Definition: cfEzgcd.cc:93
PolyMinorValue getNextMinor(const char *algorithm, const ideal &iSB)
A method for obtaining the next minor when iterating through all minors of a given size within a pre-...
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1103
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:799
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
BOOLEAN idInsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
Definition: ideals.h:90
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
#define NULL
Definition: omList.c:10
void printCounters(char *prefix, bool resetToZero)
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
polyrec * poly
Definition: hilb.h:10
void defineSubMatrix(const int numberOfRows, const int *rowIndices, const int numberOfColumns, const int *columnIndices)
A method for defining a sub-matrix within a pre-defined matrix.
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
ideal getMinorIdeal_toBeDone ( const matrix  mat,
const int  minorSize,
const int  k,
const char *  algorithm,
const ideal  i,
const bool  allDifferent 
)

Definition at line 200 of file MinorInterface.cc.

203 {
204  int rowCount = mat->nrows;
205  int columnCount = mat->ncols;
206  poly* myPolyMatrix = (poly*)(mat->m);
207  ideal iii; /* the ideal to be filled and returned */
208  int zz = 0;
209 
210  /* divert to special implementations for pure number matrices and actual
211  polynomial matrices: */
212  int* myIntMatrix = new int [rowCount * columnCount];
213  poly* nfPolyMatrix = new poly[rowCount * columnCount];
214  if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount,
215  myIntMatrix, nfPolyMatrix, zz))
216  iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k,
217  algorithm, i, allDifferent);
218  else
219  {
220  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
221  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
222  {
223  /* In this case, we call an optimized procedure, dating back to
224  Wilfried Pohl. It may be used whenever
225  - all minors are requested,
226  - requested minors need not be mutually distinct, and
227  - coefficients come from a field (i.e., Z is also not allowed
228  for this implementation). */
229  iii = (i == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize, i));
230  }
231  else
232  {
233  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
234  k, algorithm, i, allDifferent);
235  }
236  }
237 
238  /* clean up */
239  delete [] myIntMatrix;
240  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
241  delete [] nfPolyMatrix;
242 
243  return iii;
244 }
int ncols
Definition: matpol.h:22
ideal getMinorIdeal_Int(const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
int k
Definition: cfEzgcd.cc:93
bool arrayIsNumberArray(const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
poly * m
Definition: matpol.h:19
int nrows
Definition: matpol.h:21
int j
Definition: myNF.cc:70
ideal idMinors(matrix a, int ar, ideal R)
compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R ...
Definition: ideals.cc:1794
int i
Definition: cfEzgcd.cc:123
ideal getMinorIdeal_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const char *algorithm, const ideal i, const bool allDifferent)
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:434
#define pDelete(p_ptr)
Definition: polys.h:157
polyrec * poly
Definition: hilb.h:10
ideal getMinorIdealCache ( const matrix  m,
const int  minorSize,
const int  k,
const ideal  i,
const int  cacheStrategy,
const int  cacheN,
const int  cacheW,
const bool  allDifferent 
)

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
The underlying algorithm is Laplace's algorithm with caching of certain subdeterminantes. The caching strategy can be set; see int MinorValue::getUtility () const in Minor.cc. cacheN is the maximum number of cached polynomials (=subdeterminantes); cacheW the maximum weight of the cache during all computations.
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
iNULL or an ideal which encodes a standard basis
cacheStrategyone of {1, .., 5}; see Minor.cc
cacheNmaximum number of cached polynomials (=subdeterminantes)
cacheWmaximum weight of the cache
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 462 of file MinorInterface.cc.

466 {
467  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
468  to enable faster computations in the case of matrices which contain
469  only numbers. But so far, this method is not yet usable as it replaces
470  the numbers by ints which may result in overflows during computations
471  of minors. */
472  int rowCount = mat->nrows;
473  int columnCount = mat->ncols;
474  poly* myPolyMatrix = (poly*)(mat->m);
475  int length = rowCount * columnCount;
476  poly* nfPolyMatrix = new poly[length];
477  ideal iii; /* the ideal to be filled and returned */
478 
479  /* copy all polynomials and reduce them w.r.t. iSB
480  (if iSB is present, i.e., not the NULL pointer) */
481  for (int i = 0; i < length; i++)
482  {
483  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
484  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
485  nfPolyMatrix[i]);
486  }
487 
488  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
489  minorSize, k, iSB, cacheStrategy,
490  cacheN, cacheW, allDifferent);
491 
492  /* clean up */
493  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
494  delete [] nfPolyMatrix;
495 
496  return iii;
497 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
int ncols
Definition: matpol.h:22
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
poly * m
Definition: matpol.h:19
int nrows
Definition: matpol.h:21
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
ideal getMinorIdealCache_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
#define pDelete(p_ptr)
Definition: polys.h:157
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
ideal getMinorIdealCache_Int ( const int *  intMatrix,
const int  rowCount,
const int  columnCount,
const int  minorSize,
const int  k,
const ideal  i,
const int  cacheStrategy,
const int  cacheN,
const int  cacheW,
const bool  allDifferent 
)

Definition at line 307 of file MinorInterface.cc.

312 {
313  /* setting up a MinorProcessor for matrices with integer entries: */
315  mp.defineMatrix(rowCount, columnCount, intMatrix);
316  int *myRowIndices=new int[rowCount];
317  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
318  int *myColumnIndices=new int[columnCount];
319  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
320  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
321  mp.setMinorSize(minorSize);
322  MinorValue::SetRankingStrategy(cacheStrategy);
323  Cache<MinorKey, IntMinorValue> cch(cacheN, cacheW);
324 
325  /* containers for all upcoming results: */
326  IntMinorValue theMinor;
327  // int value = 0;
328  int collectedMinors = 0;
329  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
330 
331  /* the ideal to be returned: */
332  ideal iii = idInit(1);
333 
334  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
335  requested, omitting zero minors */
336  bool duplicatesOk = (allDifferent ? false : true);
337  int kk = ((k < 0) ? -k : k); /* absolute value of k */
338 
339  /* looping over all minors: */
340  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
341  {
342  /* retrieving the next minor: */
343  theMinor = mp.getNextMinor(cch, characteristic, i);
344  poly f = NULL;
345  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
346  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
347  collectedMinors++;
348  }
349 
350  /* before we return the result, let's omit zero generators
351  in iii which come after the computed minors */
352  ideal jjj;
353  if (collectedMinors == 0) jjj = idInit(1);
354  else jjj = idCopyFirstK(iii, collectedMinors);
355  idDelete(&iii);
356  delete[] myColumnIndices;
357  delete[] myRowIndices;
358  return jjj;
359 }
int rChar(ring r)
Definition: ring.cc:684
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition: Minor.cc:910
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
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
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-...
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
BOOLEAN idInsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
Definition: ideals.h:90
#define NULL
Definition: omList.c:10
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
Class IntMinorProcessor is derived from class MinorProcessor.
void defineMatrix(const int numberOfRows, const int numberOfColumns, const int *matrix)
A method for defining a matrix with integer entries.
polyrec * poly
Definition: hilb.h:10
#define pISet(i)
Definition: polys.h:283
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
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.
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
ideal getMinorIdealCache_Poly ( const poly polyMatrix,
const int  rowCount,
const int  columnCount,
const int  minorSize,
const int  k,
const ideal  i,
const int  cacheStrategy,
const int  cacheN,
const int  cacheW,
const bool  allDifferent 
)

Definition at line 365 of file MinorInterface.cc.

370 {
371  /* setting up a MinorProcessor for matrices with polynomial entries: */
373  mp.defineMatrix(rowCount, columnCount, polyMatrix);
374  int *myRowIndices=new int[rowCount];
375  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
376  int *myColumnIndices=new int[columnCount];
377  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
378  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
379  mp.setMinorSize(minorSize);
380  MinorValue::SetRankingStrategy(cacheStrategy);
381  Cache<MinorKey, PolyMinorValue> cch(cacheN, cacheW);
382 
383  /* containers for all upcoming results: */
384  PolyMinorValue theMinor;
385  poly f = NULL;
386  int collectedMinors = 0;
387 
388  /* the ideal to be returned: */
389  ideal iii = idInit(1);
390 
391  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
392  requested, omitting zero minors */
393  bool duplicatesOk = (allDifferent ? false : true);
394  int kk = ((k < 0) ? -k : k); /* absolute value of k */
395 #ifdef COUNT_AND_PRINT_OPERATIONS
396  printCounters ("starting", true);
397  int qqq = 0;
398 #endif
399  /* looping over all minors: */
400  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
401  {
402  /* retrieving the next minor: */
403  theMinor = mp.getNextMinor(cch, i);
404 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
405  qqq++;
406  Print("after %d", qqq);
407  printCounters ("-th minor", false);
408 #endif
409  f = theMinor.getResult();
410  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
411  duplicatesOk))
412  collectedMinors++;
413  }
414 #ifdef COUNT_AND_PRINT_OPERATIONS
415  printCounters ("ending", true);
416 #endif
417 
418  /* before we return the result, let's omit zero generators
419  in iii which come after the computed minors */
420  ideal jjj;
421  if (collectedMinors == 0) jjj = idInit(1);
422  else jjj = idCopyFirstK(iii, collectedMinors);
423  idDelete(&iii);
424  delete[] myColumnIndices;
425  delete[] myRowIndices;
426  return jjj;
427 }
#define Print
Definition: emacs.cc:83
Class PolyMinorProcessor is derived from class MinorProcessor.
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition: Minor.cc:910
int k
Definition: cfEzgcd.cc:93
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
PolyMinorValue getNextMinor(const char *algorithm, const ideal &iSB)
A method for obtaining the next minor when iterating through all minors of a given size within a pre-...
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1103
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:799
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
BOOLEAN idInsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
Definition: ideals.h:90
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
#define NULL
Definition: omList.c:10
void printCounters(char *prefix, bool resetToZero)
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
polyrec * poly
Definition: hilb.h:10
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
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.
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
ideal getMinorIdealCache_toBeDone ( const matrix  mat,
const int  minorSize,
const int  k,
const ideal  iSB,
const int  cacheStrategy,
const int  cacheN,
const int  cacheW,
const bool  allDifferent 
)

Definition at line 429 of file MinorInterface.cc.

433 {
434  int rowCount = mat->nrows;
435  int columnCount = mat->ncols;
436  poly* myPolyMatrix = (poly*)(mat->m);
437  ideal iii; /* the ideal to be filled and returned */
438  int zz = 0;
439 
440  /* divert to special implementation when myPolyMatrix has only number
441  entries: */
442  int* myIntMatrix = new int [rowCount * columnCount];
443  poly* nfPolyMatrix = new poly[rowCount * columnCount];
444  if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount,
445  myIntMatrix, nfPolyMatrix, zz))
446  iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount,
447  minorSize, k, iSB, cacheStrategy, cacheN,
448  cacheW, allDifferent);
449  else
450  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
451  minorSize, k, iSB, cacheStrategy, cacheN,
452  cacheW, allDifferent);
453 
454  /* clean up */
455  delete [] myIntMatrix;
456  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
457  delete [] nfPolyMatrix;
458 
459  return iii;
460 }
int ncols
Definition: matpol.h:22
int k
Definition: cfEzgcd.cc:93
bool arrayIsNumberArray(const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
poly * m
Definition: matpol.h:19
int nrows
Definition: matpol.h:21
int j
Definition: myNF.cc:70
ideal getMinorIdealCache_Poly(const poly *polyMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
#define pDelete(p_ptr)
Definition: polys.h:157
polyrec * poly
Definition: hilb.h:10
ideal getMinorIdealCache_Int(const int *intMatrix, const int rowCount, const int columnCount, const int minorSize, const int k, const ideal i, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
ideal getMinorIdealHeuristic ( const matrix  m,
const int  minorSize,
const int  k,
const ideal  i,
const bool  allDifferent 
)

Returns the specified set of minors (= subdeterminantes) of the given matrix.

These minors form the set of generators of the ideal which is actually returned.
If k == 0, all non-zero minors will be computed. For k > 0, only the first k non-zero minors (to some fixed ordering among all minors) will be computed. Use k < 0 to compute the first |k| minors (including zero minors).
The algorithm is heuristically chosen among "Bareiss", "Laplace", and Laplace with caching (of subdeterminants).
i must be either NULL or an ideal capturing a standard basis. In the later case all minors will be reduced w.r.t. i. If allDifferent is true, each minor will be included as generator in the resulting ideal only once; otherwise as often as it occurs as minor value during the computation.

Parameters
mthe matrix from which to compute minors
minorSizethe size of the minors to be computed
kthe number of minors to be computed
iNULL or an ideal which encodes a standard basis
allDifferentif true each minor is considered only once
Returns
the ideal which has as generators the specified set of minors

Definition at line 499 of file MinorInterface.cc.

502 {
503  int vars = 0; if (currRing != 0) vars = currRing->N;
504  int rowCount = mat->nrows;
505  int columnCount = mat->ncols;
506 
507  /* here comes the heuristic, as of 29 January 2010:
508 
509  integral domain and minorSize <= 2 -> Bareiss
510  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
511  field case and minorSize >= 3 and vars = 3
512  and c in {2, 3, ..., 32003} -> Bareiss
513 
514  otherwise:
515  if not all minors are requested -> Laplace, no Caching
516  otherwise:
517  minorSize >= 3 and vars <= 4 and
518  (rowCount over minorSize)*(columnCount over minorSize) >= 100
519  -> Laplace with Caching
520  minorSize >= 3 and vars >= 5 and
521  (rowCount over minorSize)*(columnCount over minorSize) >= 40
522  -> Laplace with Caching
523 
524  otherwise: -> Laplace, no Caching
525  */
526 
527  bool b = false; /* Bareiss */
528  bool l = false; /* Laplace without caching */
529  // bool c = false; /* Laplace with caching */
531  { /* the field case or ring Z */
532  if (minorSize <= 2) b = true;
533  else if (vars <= 2) b = true;
534  else if (currRingIsOverField() && (vars == 3)
535  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= 32003))
536  b = true;
537  }
538  if (!b)
539  { /* the non-Bareiss cases */
540  if (k != 0) /* this means, not all minors are requested */ l = true;
541  else
542  { /* k == 0, i.e., all minors are requested */
543  int minorCount = binom(rowCount, minorSize);
544  minorCount *= binom(columnCount, minorSize);
545  // if ((minorSize >= 3) && (vars <= 4)
546  // && (minorCount >= 100)) c = true;
547  // else if ((minorSize >= 3) && (vars >= 5)
548  // && (minorCount >= 40)) c = true;
549  /*else*/ l = true;
550  }
551  }
552 
553  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
554  allDifferent);
555  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
556  allDifferent);
557  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
558  3, 200, 100000, allDifferent);
559 }
ideal getMinorIdeal(const matrix mat, const int minorSize, const int k, const char *algorithm, const ideal iSB, const bool allDifferent)
Returns the specified set of minors (= subdeterminantes) of the given matrix.
bool currRingIsOverIntegralDomain()
int ncols
Definition: matpol.h:22
ideal getMinorIdealCache(const matrix mat, const int minorSize, const int k, const ideal iSB, const int cacheStrategy, const int cacheN, const int cacheW, const bool allDifferent)
Returns the specified set of minors (= subdeterminantes) of the given matrix.
int k
Definition: cfEzgcd.cc:93
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
int nrows
Definition: matpol.h:21
bool currRingIsOverField()
const poly b
Definition: syzextra.cc:213
int binom(int n, int r)
int l
Definition: cfEzgcd.cc:94