My Project
Loading...
Searching...
No Matches
Functions
MinorInterface.h File Reference
#include "polys/monomials/ring.h"
#include "kernel/polys.h"

Go to the source code of this file.

Functions

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. More...
 
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. More...
 
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. More...
 

Function Documentation

◆ 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 i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int j
Definition: facHensel.cc:110
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
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
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#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 pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define rField_is_Ring(R)
Definition: ring.h:485

◆ 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)

◆ 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