My Project
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  zeroCounter = 0;
35  bool result = true;
36 
37  for (int i = 0; i < length; i++)
38  {
39  nfPolyArray[i] = pCopy(polyArray[i]);
40  if (iSB != NULL)
41  {
42  poly tmp = kNF(iSB, currRing->qideal, nfPolyArray[i]);
43  pDelete(&nfPolyArray[i]);
44  nfPolyArray[i]=tmp;
45  }
46  if (nfPolyArray[i] == NULL)
47  {
48  intArray[i] = 0;
49  zeroCounter++;
50  }
51  else
52  {
53  bool isConstant = true;
54  for (int j = 1; j <= n; j++)
55  if (pGetExp(nfPolyArray[i], j) > 0)
56  isConstant = false;
57  if (!isConstant) result = false;
58  else
59  {
60  intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing->cf);
61  if (intArray[i] == 0) zeroCounter++;
62  }
63  }
64  }
65  return result;
66 }
int i
Definition: cfEzgcd.cc:132
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:544
return result
Definition: facAbsBiFact.cc:75
int j
Definition: facHensel.cc:110
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3182
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define NULL
Definition: omList.c:12
VAR 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:186
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185

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

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

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

78 {
79  /* setting up a MinorProcessor for matrices with integer entries: */
81  mp.defineMatrix(rowCount, columnCount, intMatrix);
82  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
83  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
84  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
85  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
86  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
87  mp.setMinorSize(minorSize);
88 
89  /* containers for all upcoming results: */
90  IntMinorValue theMinor;
91  // int value = 0;
92  int collectedMinors = 0;
93  int characteristic = 0; if (currRing != 0) characteristic = rChar(currRing);
94 
95  /* the ideal to be returned: */
96  ideal iii = idInit(1);
97 
98  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
99  omitting zero minors */
100  bool duplicatesOk = (allDifferent ? false : true);
101  int kk = ABS(k); /* absolute value of k */
102 
103  /* looping over all minors: */
104  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
105  {
106  /* retrieving the next minor: */
107  theMinor = mp.getNextMinor(characteristic, i, algorithm);
108  poly f = NULL;
109  if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
110  if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
111  collectedMinors++;
112  }
113 
114  /* before we return the result, let's omit zero generators
115  in iii which come after the computed minors */
116  ideal jjj;
117  if (collectedMinors == 0) jjj = idInit(1);
118  else jjj = idCopyFirstK(iii, collectedMinors);
119  idDelete(&iii);
120  omFree(myColumnIndices);
121  omFree(myRowIndices);
122  return jjj;
123 }
static int ABS(int v)
Definition: auxiliary.h:112
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:312
int rChar(ring r)
Definition: ring.cc:713
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35

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

133 {
134  /* setting up a MinorProcessor for matrices with polynomial entries: */
136  mp.defineMatrix(rowCount, columnCount, polyMatrix);
137  int *myRowIndices=(int*)omAlloc(rowCount*sizeof(int));
138  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
139  int *myColumnIndices=(int*)omAlloc(columnCount*sizeof(int));
140  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
141  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
142  mp.setMinorSize(minorSize);
143 
144  /* containers for all upcoming results: */
145  PolyMinorValue theMinor;
146  poly f = NULL;
147  int collectedMinors = 0;
148 
149  /* the ideal to be returned: */
150  ideal iii = idInit(1);
151 
152  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
153  requested, omitting zero minors */
154  bool duplicatesOk = (allDifferent ? false : true);
155  int kk = ABS(k); /* absolute value of k */
156 #ifdef COUNT_AND_PRINT_OPERATIONS
157  printCounters ("starting", true);
158  int qqq = 0;
159 #endif
160  /* looping over all minors: */
161  while (mp.hasNextMinor() && ((kk == 0) || (collectedMinors < kk)))
162  {
163  /* retrieving the next minor: */
164  theMinor = mp.getNextMinor(algorithm, i);
165 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 1)
166  qqq++;
167  Print("after %d", qqq);
168  printCounters ("-th minor", false);
169 #endif
170  f = theMinor.getResult();
171  if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
172  zeroOk, duplicatesOk))
173  collectedMinors++;
174  }
175 #ifdef COUNT_AND_PRINT_OPERATIONS
176  printCounters ("ending", true);
177 #endif
178 
179  /* before we return the result, let's omit zero generators
180  in iii which come after the computed minors */
181  idKeepFirstK(iii, collectedMinors);
182  omFree(myColumnIndices);
183  omFree(myRowIndices);
184  return(iii);
185 }
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:2924

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

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

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

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

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

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

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

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

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