My Project  UNKNOWN_GIT_VERSION
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 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 29 of file MinorInterface.cc.

32 {
33  int n = 0; if (currRing != 0) n = currRing->N;
34  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
35  zeroCounter = 0;
36  bool result = true;
37 
38  for (int i = 0; i < length; i++)
39  {
40  nfPolyArray[i] = pCopy(polyArray[i]);
41  if (iSB != NULL)
42  {
43  poly tmp = kNF(iSB, currRing->qideal, nfPolyArray[i]);
44  pDelete(&nfPolyArray[i]);
45  nfPolyArray[i]=tmp;
46  }
47  if (nfPolyArray[i] == NULL)
48  {
49  intArray[i] = 0;
50  zeroCounter++;
51  }
52  else
53  {
54  bool isConstant = true;
55  for (int j = 1; j <= n; j++)
56  if (pGetExp(nfPolyArray[i], j) > 0)
57  isConstant = false;
58  if (!isConstant) result = false;
59  else
60  {
61  intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing->cf);
62  if (characteristic != 0) intArray[i] = intArray[i] % characteristic;
63  if (intArray[i] == 0) zeroCounter++;
64  }
65  }
66  }
67  return result;
68 }
int i
Definition: cfEzgcd.cc:125
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:547
return result
Definition: facAbsBiFact.cc:76
int j
Definition: facHensel.cc:105
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2822
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:45
#define NULL
Definition: omList.c:10
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pDelete(p_ptr)
Definition: polys.h:181
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pCopy(p)
return a copy of the poly
Definition: polys.h:180
int rChar(ring r)
Definition: ring.cc:686

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

243 {
244  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
245  to enable faster computations in the case of matrices which contain
246  only numbers. But so far, this method is not yet usable as it replaces
247  the numbers by ints which may result in overflows during computations
248  of minors. */
249  int rowCount = mat->nrows;
250  int columnCount = mat->ncols;
251  poly* myPolyMatrix = (poly*)(mat->m);
252  int length = rowCount * columnCount;
253  ideal iii; /* the ideal to be filled and returned */
254 
255  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
256  && (!rField_is_Ring(currRing)) && (!allDifferent))
257  {
258  /* In this case, we call an optimized procedure, dating back to
259  Wilfried Pohl. It may be used whenever
260  - all minors are requested,
261  - requested minors need not be mutually distinct, and
262  - coefficients come from a field (i.e., the ring Z is not
263  allowed for this implementation). */
264  iii = (iSB == NULL ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
265  iSB));
266  }
267  else
268  {
269  /* copy all polynomials and reduce them w.r.t. iSB
270  (if iSB is present, i.e., not the NULL pointer) */
271 
272  poly* nfPolyMatrix = (poly*)omAlloc(length*sizeof(poly));
273  if (iSB != NULL)
274  {
275  for (int i = 0; i < length; i++)
276  {
277  nfPolyMatrix[i] = kNF(iSB, currRing->qideal,myPolyMatrix[i]);
278  }
279  }
280  else
281  {
282  for (int i = 0; i < length; i++)
283  {
284  nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
285  }
286  }
287  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
288  k, algorithm, iSB, allDifferent);
289 
290  /* clean up */
291  for (int j = length-1; j>=0; j--) pDelete(&nfPolyMatrix[j]);
292  omFree(nfPolyMatrix);
293  }
294 
295  return iii;
296 }
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)
int k
Definition: cfEzgcd.cc:92
int nrows
Definition: matpol.h:20
int ncols
Definition: matpol.h:21
poly * m
Definition: matpol.h:18
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:2010
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:475

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

80 {
81  /* setting up a MinorProcessor for matrices with integer entries: */
83  mp.defineMatrix(rowCount, columnCount, intMatrix);
84  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
85  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
86  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
87  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
88  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
89  mp.setMinorSize(minorSize);
90 
91  /* containers for all upcoming results: */
92  IntMinorValue theMinor;
93  // int value = 0;
94  int collectedMinors = 0;
95  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
96 
97  /* the ideal to be returned: */
98  ideal iii = idInit(1);
99 
100  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
101  omitting zero minors */
102  bool duplicatesOk = (allDifferent ? false : true);
103  int kk = ABS(k); /* absolute value of k */
104 
105  /* looping over all minors: */
106  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
107  {
108  /* retrieving the next minor: */
109  theMinor = mp.getNextMinor(characteristic, i, algorithm);
110  poly f = NULL;
111  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
112  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
113  collectedMinors++;
114  }
115 
116  /* before we return the result, let's omit zero generators
117  in iii which come after the computed minors */
118  ideal jjj;
119  if (collectedMinors == 0) jjj = idInit(1);
120  else jjj = idCopyFirstK(iii, collectedMinors);
121  idDelete(&iii);
122  omFree(myColumnIndices);
123  omFree(myRowIndices);
124  return jjj;
125 }
static int ABS(int v)
Definition: auxiliary.h:110
return false
Definition: cfModGcd.cc:84
FILE * f
Definition: checklibs.c:9
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.
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-...
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
Definition: Minor.h:718
int getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1019
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
void defineSubMatrix(const int numberOfRows, const int *rowIndices, const int numberOfColumns, const int *columnIndices)
A method for defining a sub-matrix within a pre-defined matrix.
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
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 pISet(i)
Definition: polys.h:306
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37

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

135 {
136  /* setting up a MinorProcessor for matrices with polynomial entries: */
138  mp.defineMatrix(rowCount, columnCount, polyMatrix);
139  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
140  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
141  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
142  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
143  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
144  mp.setMinorSize(minorSize);
145 
146  /* containers for all upcoming results: */
147  PolyMinorValue theMinor;
148  poly f = NULL;
149  int collectedMinors = 0;
150 
151  /* the ideal to be returned: */
152  ideal iii = idInit(1);
153 
154  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
155  requested, omitting zero minors */
156  bool duplicatesOk = (allDifferent ? false : true);
157  int kk = ABS(k); /* absolute value of k */
158 #ifdef COUNT_AND_PRINT_OPERATIONS
159  printCounters ("starting", true);
160  int qqq = 0;
161 #endif
162  /* looping over all minors: */
163  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
164  {
165  /* retrieving the next minor: */
166  theMinor = mp.getNextMinor(algorithm, i);
167 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
168  qqq++;
169  Print("after %d", qqq);
170  printCounters ("-th minor", false);
171 #endif
172  f = theMinor.getResult();
173  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
174  zeroOk, duplicatesOk))
175  collectedMinors++;
176  }
177 #ifdef COUNT_AND_PRINT_OPERATIONS
178  printCounters ("ending", true);
179 #endif
180 
181  /* before we return the result, let's omit zero generators
182  in iii which come after the computed minors */
183  idKeepFirstK(iii, collectedMinors);
184  omFree(myColumnIndices);
185  omFree(myRowIndices);
186  return(iii);
187 }
void printCounters(char *prefix, bool resetToZero)
Class PolyMinorProcessor is derived from class MinorProcessor.
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-...
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
Definition: Minor.h:800
poly getResult() const
Accessor for the private field _result.
Definition: Minor.cc:1102
#define Print
Definition: emacs.cc:80
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:2802

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

192 {
193  int rowCount = mat->nrows;
194  int columnCount = mat->ncols;
195  poly* myPolyMatrix = (poly*)(mat->m);
196  ideal iii; /* the ideal to be filled and returned */
197  int zz = 0;
198 
199  /* divert to special implementations for pure number matrices and actual
200  polynomial matrices: */
201  int* myIntMatrix = (int*)omAlloc(rowCount * columnCount *sizeof(int));
202  poly* nfPolyMatrix = (poly*)omAlloc(rowCount * columnCount *sizeof(poly));
203  if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount,
204  myIntMatrix, nfPolyMatrix, zz))
205  iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k,
206  algorithm, i, allDifferent);
207  else
208  {
209  if ((k == 0) && (strcmp(algorithm, "Bareiss") == 0)
210  && (!rField_is_Z(currRing)) && (!allDifferent))
211  {
212  /* In this case, we call an optimized procedure, dating back to
213  Wilfried Pohl. It may be used whenever
214  - all minors are requested,
215  - requested minors need not be mutually distinct, and
216  - coefficients come from a field (i.e., Z is also not allowed
217  for this implementation). */
218  iii = (i == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize, i));
219  }
220  else
221  {
222  iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
223  k, algorithm, i, allDifferent);
224  }
225  }
226 
227  /* clean up */
228  omFree(myIntMatrix);
229  for (int j = 0; j < rowCount * columnCount; j++) pDelete(&nfPolyMatrix[j]);
230  omFree(nfPolyMatrix);
231 
232  return iii;
233 }
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)
bool arrayIsNumberArray(const poly *polyArray, const ideal iSB, const int length, int *intArray, poly *nfPolyArray, int &zeroCounter)
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:500

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

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

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

309 {
310  /* setting up a MinorProcessor for matrices with integer entries: */
312  mp.defineMatrix(rowCount, columnCount, intMatrix);
313  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
314  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
315  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
316  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
317  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
318  mp.setMinorSize(minorSize);
319  MinorValue::SetRankingStrategy(cacheStrategy);
320  Cache<MinorKey, IntMinorValue> cch(cacheN, cacheW);
321 
322  /* containers for all upcoming results: */
323  IntMinorValue theMinor;
324  // int value = 0;
325  int collectedMinors = 0;
326  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
327 
328  /* the ideal to be returned: */
329  ideal iii = idInit(1);
330 
331  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
332  requested, omitting zero minors */
333  bool duplicatesOk = (allDifferent ? false : true);
334  int kk = ABS(k); /* absolute value of k */
335 
336  /* looping over all minors: */
337  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
338  {
339  /* retrieving the next minor: */
340  theMinor = mp.getNextMinor(cch, characteristic, i);
341  poly f = NULL;
342  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
343  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
344  collectedMinors++;
345  }
346 
347  /* before we return the result, let's omit zero generators
348  in iii which come after the computed minors */
349  ideal jjj;
350  if (collectedMinors == 0) jjj = idInit(1);
351  else jjj = idCopyFirstK(iii, collectedMinors);
352  idDelete(&iii);
353  omFree(myColumnIndices);
354  omFree(myRowIndices);
355  return jjj;
356 }
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:69
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
Definition: Minor.cc:909

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

367 {
368  /* setting up a MinorProcessor for matrices with polynomial entries: */
370  mp.defineMatrix(rowCount, columnCount, polyMatrix);
371  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
372  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
373  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
374  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
375  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
376  mp.setMinorSize(minorSize);
377  MinorValue::SetRankingStrategy(cacheStrategy);
378  Cache<MinorKey, PolyMinorValue> cch(cacheN, cacheW);
379 
380  /* containers for all upcoming results: */
381  PolyMinorValue theMinor;
382  poly f = NULL;
383  int collectedMinors = 0;
384 
385  /* the ideal to be returned: */
386  ideal iii = idInit(1);
387 
388  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
389  requested, omitting zero minors */
390  bool duplicatesOk = (allDifferent ? false : true);
391  int kk = ABS(k); /* absolute value of k */
392 #ifdef COUNT_AND_PRINT_OPERATIONS
393  printCounters ("starting", true);
394  int qqq = 0;
395 #endif
396  /* looping over all minors: */
397  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
398  {
399  /* retrieving the next minor: */
400  theMinor = mp.getNextMinor(cch, i);
401 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
402  qqq++;
403  Print("after %d", qqq);
404  printCounters ("-th minor", false);
405 #endif
406  f = theMinor.getResult();
407  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
408  duplicatesOk))
409  collectedMinors++;
410  }
411 #ifdef COUNT_AND_PRINT_OPERATIONS
412  printCounters ("ending", true);
413 #endif
414 
415  /* before we return the result, let's omit zero generators
416  in iii which come after the computed minors */
417  ideal jjj;
418  if (collectedMinors == 0) jjj = idInit(1);
419  else jjj = idCopyFirstK(iii, collectedMinors);
420  idDelete(&iii);
421  omFree(myColumnIndices);
422  omFree(myRowIndices);
423  return jjj;
424 }

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

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

500 {
501  int vars = currRing->N;
502 
503  /* here comes the heuristic, as of 29 January 2010:
504 
505  integral domain and minorSize <= 2 -> Bareiss
506  integral domain and minorSize >= 3 and vars <= 2 -> Bareiss
507  field case and minorSize >= 3 and vars = 3
508  and c in {2, 3, ..., 32749} -> Bareiss
509 
510  otherwise:
511  if not all minors are requested -> Laplace, no Caching
512  otherwise:
513  minorSize >= 3 and vars <= 4 and
514  (rowCount over minorSize)*(columnCount over minorSize) >= 100
515  -> Laplace with Caching
516  minorSize >= 3 and vars >= 5 and
517  (rowCount over minorSize)*(columnCount over minorSize) >= 40
518  -> Laplace with Caching
519 
520  otherwise: -> Laplace, no Caching
521  */
522 
523  bool b = false; /* Bareiss */
524  bool l = false; /* Laplace without caching */
525  // bool c = false; /* Laplace with caching */
527  { /* the field case or ring Z */
528  if (minorSize <= 2) b = true;
529  else if (vars <= 2) b = true;
530  else if ((!rField_is_Ring(currRing)) && (vars == 3)
531  && (currRing->cf->ch >= 2) && (currRing->cf->ch <= NV_MAX_PRIME))
532  b = true;
533  }
534  if (!b)
535  { /* the non-Bareiss cases */
536  if (k != 0) /* this means, not all minors are requested */ l = true;
537  else
538  { /* k == 0, i.e., all minors are requested */
539  l = true;
540  }
541  }
542 
543  if (b) return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
544  allDifferent);
545  else if (l) return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
546  allDifferent);
547  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
548  3, 200, 100000, allDifferent);
549 }
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.
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.
int l
Definition: cfEzgcd.cc:93
CanonicalForm b
Definition: cfModGcd.cc:4044
#define NV_MAX_PRIME
Definition: modulop.h:29
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:478