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 <coeffs/modulop.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

§ arrayIsNumberArray()

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

Definition at line 46 of file MinorInterface.cc.

49 {
50  int n = 0; if (currRing != 0) n = currRing->N;
51  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
52  zeroCounter = 0;
53  bool result = true;
54 
55  for (int i = 0; i < length; i++)
56  {
57  nfPolyArray[i] = pCopy(polyArray[i]);
58  if (iSB != 0) nfPolyArray[i] = kNF(iSB, currRing->qideal, nfPolyArray[i]);
59  if (nfPolyArray[i] == NULL)
60  {
61  intArray[i] = 0;
62  zeroCounter++;
63  }
64  else
65  {
66  bool isConstant = true;
67  for (int j = 1; j <= n; j++)
68  if (pGetExp(nfPolyArray[i], j) > 0)
69  isConstant = false;
70  if (!isConstant) result = false;
71  else
72  {
73  intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing->cf);
74  if (characteristic != 0) intArray[i] = intArray[i] % characteristic;
75  if (intArray[i] == 0) zeroCounter++;
76  }
77  }
78  }
79  return result;
80 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
int rChar(ring r)
Definition: ring.cc:684
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:10
#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:551
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:168

§ currRingIsOverField()

bool currRingIsOverField ( )

Definition at line 30 of file MinorInterface.cc.

31 {
32  if (rField_is_Ring_PtoM(currRing)) return false;
33  if (rField_is_Ring_2toM(currRing)) return false;
34  if (rField_is_Ring_ModN(currRing)) return false;
35  if (rField_is_Ring_Z(currRing)) return false;
36  return true;
37 }
static BOOLEAN rField_is_Ring_PtoM(const ring r)
Definition: ring.h:471
static BOOLEAN rField_is_Ring_ModN(const ring r)
Definition: ring.h:468
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
static BOOLEAN rField_is_Ring_2toM(const ring r)
Definition: ring.h:465
static BOOLEAN rField_is_Ring_Z(const ring r)
Definition: ring.h:474

§ currRingIsOverIntegralDomain()

bool currRingIsOverIntegralDomain ( )

Definition at line 22 of file MinorInterface.cc.

23 {
24  if (rField_is_Ring_PtoM(currRing)) return false;
25  if (rField_is_Ring_2toM(currRing)) return false;
26  if (rField_is_Ring_ModN(currRing)) return false;
27  return true;
28 }
static BOOLEAN rField_is_Ring_PtoM(const ring r)
Definition: ring.h:471
static BOOLEAN rField_is_Ring_ModN(const ring r)
Definition: ring.h:468
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
static BOOLEAN rField_is_Ring_2toM(const ring r)
Definition: ring.h:465

§ getMinorIdeal()

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 252 of file MinorInterface.cc.

255 {
256  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
257  to enable faster computations in the case of matrices which contain
258  only numbers. But so far, this method is not yet usable as it replaces
259  the numbers by ints which may result in overflows during computations
260  of minors. */
261  int rowCount = mat->nrows;
262  int columnCount = mat->ncols;
263  poly* myPolyMatrix = (poly*)(mat->m);
264  int length = rowCount * columnCount;
265  poly* nfPolyMatrix = new poly[length];
266  ideal iii; /* the ideal to be filled and returned */
267 
268  /* copy all polynomials and reduce them w.r.t. iSB
269  (if iSB is present, i.e., not the NULL pointer) */
270  for (int i = 0; i < length; i++)
271  {
272  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
273  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
274  nfPolyMatrix[i]);
275  }
276 
277  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
278  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
279  {
280  /* In this case, we call an optimized procedure, dating back to
281  Wilfried Pohl. It may be used whenever
282  - all minors are requested,
283  - requested minors need not be mutually distinct, and
284  - coefficients come from a field (i.e., the ring Z is not
285  allowed for this implementation). */
286  iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
287  iSB));
288  }
289  else
290  {
291  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
292  k, algorithm, iSB, allDifferent);
293  }
294 
295  /* clean up */
296  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
297  delete [] nfPolyMatrix;
298 
299  return iii;
300 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
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:10
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:1744
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:474
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168

§ getMinorIdeal_Int()

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 88 of file MinorInterface.cc.

92 {
93  /* setting up a MinorProcessor for matrices with integer entries: */
95  mp.defineMatrix(rowCount, columnCount, intMatrix);
96  int *myRowIndices=new int[rowCount];
97  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
98  int *myColumnIndices=new int[columnCount];
99  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
100  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
101  mp.setMinorSize(minorSize);
102 
103  /* containers for all upcoming results: */
104  IntMinorValue theMinor;
105  // int value = 0;
106  int collectedMinors = 0;
107  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
108 
109  /* the ideal to be returned: */
110  ideal iii = idInit(1);
111 
112  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
113  omitting zero minors */
114  bool duplicatesOk = (allDifferent ? false : true);
115  int kk = ((k < 0) ? -k : k); /* absolute value of k */
116 
117  /* looping over all minors: */
118  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
119  {
120  /* retrieving the next minor: */
121  theMinor = mp.getNextMinor(characteristic, i, algorithm);
122  poly f = NULL;
123  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
124  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
125  collectedMinors++;
126  }
127 
128  /* before we return the result, let's omit zero generators
129  in iii which come after the computed minors */
130  ideal jjj;
131  if (collectedMinors == 0) jjj = idInit(1);
132  else jjj = idCopyFirstK(iii, collectedMinors);
133  idDelete(&iii);
134  delete[] myColumnIndices;
135  delete[] myRowIndices;
136  return jjj;
137 }
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
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:10
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:77
static ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
#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:295
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.

§ getMinorIdeal_Poly()

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 143 of file MinorInterface.cc.

147 {
148  /* setting up a MinorProcessor for matrices with polynomial entries: */
150  mp.defineMatrix(rowCount, columnCount, polyMatrix);
151  int *myRowIndices=new int[rowCount];
152  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
153  int *myColumnIndices=new int[columnCount];
154  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
155  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
156  mp.setMinorSize(minorSize);
157 
158  /* containers for all upcoming results: */
159  PolyMinorValue theMinor;
160  poly f = NULL;
161  int collectedMinors = 0;
162 
163  /* the ideal to be returned: */
164  ideal iii = idInit(1);
165 
166  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
167  requested, omitting zero minors */
168  bool duplicatesOk = (allDifferent ? false : true);
169  int kk = ((k < 0) ? -k : k); /* absolute value of k */
170 #ifdef COUNT_AND_PRINT_OPERATIONS
171  printCounters ("starting", true);
172  int qqq = 0;
173 #endif
174  /* looping over all minors: */
175  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
176  {
177  /* retrieving the next minor: */
178  theMinor = mp.getNextMinor(algorithm, i);
179 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
180  qqq++;
181  Print("after %d", qqq);
182  printCounters ("-th minor", false);
183 #endif
184  f = theMinor.getResult();
185  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
186  zeroOk, duplicatesOk))
187  collectedMinors++;
188  }
189 #ifdef COUNT_AND_PRINT_OPERATIONS
190  printCounters ("ending", true);
191 #endif
192 
193  /* before we return the result, let's omit zero generators
194  in iii which come after the computed minors */
195  idKeepFirstK(iii, collectedMinors);
196  delete[] myColumnIndices;
197  delete[] myRowIndices;
198  return(iii);
199 }
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:2531
#define Print
Definition: emacs.cc:83
Class PolyMinorProcessor is derived from class MinorProcessor.
int k
Definition: cfEzgcd.cc:93
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1103
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...
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:77
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:168

§ getMinorIdeal_toBeDone()

ideal getMinorIdeal_toBeDone ( const matrix  mat,
const int  minorSize,
const int  k,
const char *  algorithm,
const ideal  i,
const bool  allDifferent 
)

Definition at line 201 of file MinorInterface.cc.

204 {
205  int rowCount = mat->nrows;
206  int columnCount = mat->ncols;
207  poly* myPolyMatrix = (poly*)(mat->m);
208  ideal iii; /* the ideal to be filled and returned */
209  int zz = 0;
210 
211  /* divert to special implementations for pure number matrices and actual
212  polynomial matrices: */
213  int* myIntMatrix = new int [rowCount * columnCount];
214  poly* nfPolyMatrix = new poly[rowCount * columnCount];
215  if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount,
216  myIntMatrix, nfPolyMatrix, zz))
217  iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k,
218  algorithm, i, allDifferent);
219  else
220  {
221  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
222  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
223  {
224  /* In this case, we call an optimized procedure, dating back to
225  Wilfried Pohl. It may be used whenever
226  - all minors are requested,
227  - requested minors need not be mutually distinct, and
228  - coefficients come from a field (i.e., Z is also not allowed
229  for this implementation). */
230  iii = (i == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize, i));
231  }
232  else
233  {
234  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
235  k, algorithm, i, allDifferent);
236  }
237  }
238 
239  /* clean up */
240  delete [] myIntMatrix;
241  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
242  delete [] nfPolyMatrix;
243 
244  return iii;
245 }
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:10
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:1744
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:474
#define pDelete(p_ptr)
Definition: polys.h:169
polyrec * poly
Definition: hilb.h:10

§ getMinorIdealCache()

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 463 of file MinorInterface.cc.

467 {
468  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
469  to enable faster computations in the case of matrices which contain
470  only numbers. But so far, this method is not yet usable as it replaces
471  the numbers by ints which may result in overflows during computations
472  of minors. */
473  int rowCount = mat->nrows;
474  int columnCount = mat->ncols;
475  poly* myPolyMatrix = (poly*)(mat->m);
476  int length = rowCount * columnCount;
477  poly* nfPolyMatrix = new poly[length];
478  ideal iii; /* the ideal to be filled and returned */
479 
480  /* copy all polynomials and reduce them w.r.t. iSB
481  (if iSB is present, i.e., not the NULL pointer) */
482  for (int i = 0; i < length; i++)
483  {
484  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
485  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
486  nfPolyMatrix[i]);
487  }
488 
489  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
490  minorSize, k, iSB, cacheStrategy,
491  cacheN, cacheW, allDifferent);
492 
493  /* clean up */
494  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
495  delete [] nfPolyMatrix;
496 
497  return iii;
498 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2971
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:10
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:169
polyrec * poly
Definition: hilb.h:10
#define pCopy(p)
return a copy of the poly
Definition: polys.h:168

§ getMinorIdealCache_Int()

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 308 of file MinorInterface.cc.

313 {
314  /* setting up a MinorProcessor for matrices with integer entries: */
316  mp.defineMatrix(rowCount, columnCount, intMatrix);
317  int *myRowIndices=new int[rowCount];
318  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
319  int *myColumnIndices=new int[columnCount];
320  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
321  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
322  mp.setMinorSize(minorSize);
323  MinorValue::SetRankingStrategy(cacheStrategy);
324  Cache<MinorKey, IntMinorValue> cch(cacheN, cacheW);
325 
326  /* containers for all upcoming results: */
327  IntMinorValue theMinor;
328  // int value = 0;
329  int collectedMinors = 0;
330  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
331 
332  /* the ideal to be returned: */
333  ideal iii = idInit(1);
334 
335  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
336  requested, omitting zero minors */
337  bool duplicatesOk = (allDifferent ? false : true);
338  int kk = ((k < 0) ? -k : k); /* absolute value of k */
339 
340  /* looping over all minors: */
341  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
342  {
343  /* retrieving the next minor: */
344  theMinor = mp.getNextMinor(cch, characteristic, i);
345  poly f = NULL;
346  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
347  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
348  collectedMinors++;
349  }
350 
351  /* before we return the result, let's omit zero generators
352  in iii which come after the computed minors */
353  ideal jjj;
354  if (collectedMinors == 0) jjj = idInit(1);
355  else jjj = idCopyFirstK(iii, collectedMinors);
356  idDelete(&iii);
357  delete[] myColumnIndices;
358  delete[] myRowIndices;
359  return jjj;
360 }
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
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:10
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:77
static ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
#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:295
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.

§ getMinorIdealCache_Poly()

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 366 of file MinorInterface.cc.

371 {
372  /* setting up a MinorProcessor for matrices with polynomial entries: */
374  mp.defineMatrix(rowCount, columnCount, polyMatrix);
375  int *myRowIndices=new int[rowCount];
376  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
377  int *myColumnIndices=new int[columnCount];
378  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
379  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
380  mp.setMinorSize(minorSize);
381  MinorValue::SetRankingStrategy(cacheStrategy);
382  Cache<MinorKey, PolyMinorValue> cch(cacheN, cacheW);
383 
384  /* containers for all upcoming results: */
385  PolyMinorValue theMinor;
386  poly f = NULL;
387  int collectedMinors = 0;
388 
389  /* the ideal to be returned: */
390  ideal iii = idInit(1);
391 
392  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
393  requested, omitting zero minors */
394  bool duplicatesOk = (allDifferent ? false : true);
395  int kk = ((k < 0) ? -k : k); /* absolute value of k */
396 #ifdef COUNT_AND_PRINT_OPERATIONS
397  printCounters ("starting", true);
398  int qqq = 0;
399 #endif
400  /* looping over all minors: */
401  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
402  {
403  /* retrieving the next minor: */
404  theMinor = mp.getNextMinor(cch, i);
405 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
406  qqq++;
407  Print("after %d", qqq);
408  printCounters ("-th minor", false);
409 #endif
410  f = theMinor.getResult();
411  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
412  duplicatesOk))
413  collectedMinors++;
414  }
415 #ifdef COUNT_AND_PRINT_OPERATIONS
416  printCounters ("ending", true);
417 #endif
418 
419  /* before we return the result, let's omit zero generators
420  in iii which come after the computed minors */
421  ideal jjj;
422  if (collectedMinors == 0) jjj = idInit(1);
423  else jjj = idCopyFirstK(iii, collectedMinors);
424  idDelete(&iii);
425  delete[] myColumnIndices;
426  delete[] myRowIndices;
427  return jjj;
428 }
#define Print
Definition: emacs.cc:83
Class PolyMinorProcessor is derived from class MinorProcessor.
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition: Minor.cc:910
int k
Definition: cfEzgcd.cc:93
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1103
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...
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:77
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
static ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:22
#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:168

§ getMinorIdealCache_toBeDone()

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 430 of file MinorInterface.cc.

434 {
435  int rowCount = mat->nrows;
436  int columnCount = mat->ncols;
437  poly* myPolyMatrix = (poly*)(mat->m);
438  ideal iii; /* the ideal to be filled and returned */
439  int zz = 0;
440 
441  /* divert to special implementation when myPolyMatrix has only number
442  entries: */
443  int* myIntMatrix = new int [rowCount * columnCount];
444  poly* nfPolyMatrix = new poly[rowCount * columnCount];
445  if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount,
446  myIntMatrix, nfPolyMatrix, zz))
447  iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount,
448  minorSize, k, iSB, cacheStrategy, cacheN,
449  cacheW, allDifferent);
450  else
451  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
452  minorSize, k, iSB, cacheStrategy, cacheN,
453  cacheW, allDifferent);
454 
455  /* clean up */
456  delete [] myIntMatrix;
457  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
458  delete [] nfPolyMatrix;
459 
460  return iii;
461 }
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:169
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)

§ getMinorIdealHeuristic()

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 500 of file MinorInterface.cc.

503 {
504  int vars = 0; if (currRing != 0) vars = currRing->N;
505  int rowCount = mat->nrows;
506  int columnCount = mat->ncols;
507 
508  /* here comes the heuristic, as of 29 January 2010:
509 
510  integral domain and minorSize <= 2 -> Bareiss
511  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
512  field case and minorSize >= 3 and vars = 3
513  and c in {2, 3, ..., 32749} -> Bareiss
514 
515  otherwise:
516  if not all minors are requested -> Laplace, no Caching
517  otherwise:
518  minorSize >= 3 and vars <= 4 and
519  (rowCount over minorSize)*(columnCount over minorSize) >= 100
520  -> Laplace with Caching
521  minorSize >= 3 and vars >= 5 and
522  (rowCount over minorSize)*(columnCount over minorSize) >= 40
523  -> Laplace with Caching
524 
525  otherwise: -> Laplace, no Caching
526  */
527 
528  bool b = false; /* Bareiss */
529  bool l = false; /* Laplace without caching */
530  // bool c = false; /* Laplace with caching */
532  { /* the field case or ring Z */
533  if (minorSize <= 2) b = true;
534  else if (vars <= 2) b = true;
535  else if (currRingIsOverField() && (vars == 3)
536  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
537  b = true;
538  }
539  if (!b)
540  { /* the non-Bareiss cases */
541  if (k != 0) /* this means, not all minors are requested */ l = true;
542  else
543  { /* k == 0, i.e., all minors are requested */
544  int minorCount = binom(rowCount, minorSize);
545  minorCount *= binom(columnCount, minorSize);
546  // if ((minorSize >= 3) && (vars <= 4)
547  // && (minorCount >= 100)) c = true;
548  // else if ((minorSize >= 3) && (vars >= 5)
549  // && (minorCount >= 40)) c = true;
550  /*else*/ l = true;
551  }
552  }
553 
554  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
555  allDifferent);
556  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
557  allDifferent);
558  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
559  3, 200, 100000, allDifferent);
560 }
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:10
int nrows
Definition: matpol.h:21
#define NV_MAX_PRIME
Definition: modulop.h:21
bool currRingIsOverField()
const poly b
Definition: syzextra.cc:213
int binom(int n, int r)
int l
Definition: cfEzgcd.cc:94