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:686
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  if (iSB != NULL)
271  {
272  for (int i = 0; i < length; i++)
273  {
274  nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
275  }
276  }
277  else
278  {
279  for (int i = 0; i < length; i++)
280  {
281  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
282  }
283  }
284 
285  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
286  && (!rField_is_Ring_Z(currRing)) && (!allDifferent))
287  {
288  /* In this case, we call an optimized procedure, dating back to
289  Wilfried Pohl. It may be used whenever
290  - all minors are requested,
291  - requested minors need not be mutually distinct, and
292  - coefficients come from a field (i.e., the ring Z is not
293  allowed for this implementation). */
294  iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
295  iSB));
296  }
297  else
298  {
299  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
300  k, algorithm, iSB, allDifferent);
301  }
302 
303  /* clean up */
304  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
305  delete [] nfPolyMatrix;
306 
307  return iii;
308 }
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:1745
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
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:29
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1020
int rChar(ring r)
Definition: ring.cc:686
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
return false
Definition: cfModGcd.cc:84
FILE * f
Definition: checklibs.c:9
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:75
static ideal idCopyFirstK(const ideal ide, const int k)
Definition: ideals.h:20
#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:294
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:2532
#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
return false
Definition: cfModGcd.cc:84
FILE * f
Definition: checklibs.c:9
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:75
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:1745
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 471 of file MinorInterface.cc.

475 {
476  /* Note that this method should be replaced by getMinorIdealCache_toBeDone,
477  to enable faster computations in the case of matrices which contain
478  only numbers. But so far, this method is not yet usable as it replaces
479  the numbers by ints which may result in overflows during computations
480  of minors. */
481  int rowCount = mat->nrows;
482  int columnCount = mat->ncols;
483  poly* myPolyMatrix = (poly*)(mat->m);
484  int length = rowCount * columnCount;
485  poly* nfPolyMatrix = new poly[length];
486  ideal iii; /* the ideal to be filled and returned */
487 
488  /* copy all polynomials and reduce them w.r.t. iSB
489  (if iSB is present, i.e., not the NULL pointer) */
490  for (int i = 0; i < length; i++)
491  {
492  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
493  if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
494  nfPolyMatrix[i]);
495  }
496 
497  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
498  minorSize, k, iSB, cacheStrategy,
499  cacheN, cacheW, allDifferent);
500 
501  /* clean up */
502  for (int j = 0; j < length; j++) pDelete(&nfPolyMatrix[j]);
503  delete [] nfPolyMatrix;
504 
505  return iii;
506 }
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 316 of file MinorInterface.cc.

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

379 {
380  /* setting up a MinorProcessor for matrices with polynomial entries: */
382  mp.defineMatrix(rowCount, columnCount, polyMatrix);
383  int *myRowIndices=new int[rowCount];
384  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
385  int *myColumnIndices=new int[columnCount];
386  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
387  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
388  mp.setMinorSize(minorSize);
389  MinorValue::SetRankingStrategy(cacheStrategy);
390  Cache<MinorKey, PolyMinorValue> cch(cacheN, cacheW);
391 
392  /* containers for all upcoming results: */
393  PolyMinorValue theMinor;
394  poly f = NULL;
395  int collectedMinors = 0;
396 
397  /* the ideal to be returned: */
398  ideal iii = idInit(1);
399 
400  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
401  requested, omitting zero minors */
402  bool duplicatesOk = (allDifferent ? false : true);
403  int kk = ((k < 0) ? -k : k); /* absolute value of k */
404 #ifdef COUNT_AND_PRINT_OPERATIONS
405  printCounters ("starting", true);
406  int qqq = 0;
407 #endif
408  /* looping over all minors: */
409  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
410  {
411  /* retrieving the next minor: */
412  theMinor = mp.getNextMinor(cch, i);
413 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
414  qqq++;
415  Print("after %d", qqq);
416  printCounters ("-th minor", false);
417 #endif
418  f = theMinor.getResult();
419  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
420  duplicatesOk))
421  collectedMinors++;
422  }
423 #ifdef COUNT_AND_PRINT_OPERATIONS
424  printCounters ("ending", true);
425 #endif
426 
427  /* before we return the result, let's omit zero generators
428  in iii which come after the computed minors */
429  ideal jjj;
430  if (collectedMinors == 0) jjj = idInit(1);
431  else jjj = idCopyFirstK(iii, collectedMinors);
432  idDelete(&iii);
433  delete[] myColumnIndices;
434  delete[] myRowIndices;
435  return jjj;
436 }
#define Print
Definition: emacs.cc:83
Class PolyMinorProcessor is derived from class MinorProcessor.
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
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
return false
Definition: cfModGcd.cc:84
FILE * f
Definition: checklibs.c:9
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:75
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:20
#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 438 of file MinorInterface.cc.

442 {
443  int rowCount = mat->nrows;
444  int columnCount = mat->ncols;
445  poly* myPolyMatrix = (poly*)(mat->m);
446  ideal iii; /* the ideal to be filled and returned */
447  int zz = 0;
448 
449  /* divert to special implementation when myPolyMatrix has only number
450  entries: */
451  int* myIntMatrix = new int [rowCount * columnCount];
452  poly* nfPolyMatrix = new poly[rowCount * columnCount];
453  if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount,
454  myIntMatrix, nfPolyMatrix, zz))
455  iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount,
456  minorSize, k, iSB, cacheStrategy, cacheN,
457  cacheW, allDifferent);
458  else
459  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
460  minorSize, k, iSB, cacheStrategy, cacheN,
461  cacheW, allDifferent);
462 
463  /* clean up */
464  delete [] myIntMatrix;
465  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
466  delete [] nfPolyMatrix;
467 
468  return iii;
469 }
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 508 of file MinorInterface.cc.

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