 |
My Project
debian-1:4.1.1-p2+ds-4build1
|
Go to the documentation of this file.
18 #ifdef COUNT_AND_PRINT_OPERATIONS
21 long addsPolyForDiv = 0;
23 long multsPolyForDiv = 0;
26 long multsMonForDiv = 0;
28 long savedMultsMFD = 0;
38 printf(
"%s [p+p(div) | p*p(div) | m*m(div, -save) | m/m ]", prefix);
39 printf(
" = [%ld(%ld) | %ld(%ld) | %ld(%d, -%ld) | %ld]\n",
40 addsPoly, addsPolyForDiv, multsPoly, multsPolyForDiv,
41 multsMon, multsMonForDiv, savedMultsMFD, divsMon);
44 multsMon = 0; addsPoly = 0; multsPoly = 0; divsMon = 0;
45 savedMultsMFD = 0; multsMonForDiv = 0; addsPolyForDiv = 0;
66 int numberOfZeros = 0;
67 int bestIndex = 100000;
68 int maxNumberOfZeros = -1;
70 for (
int r = 0; r <
k; r++)
75 for (
int c = 0; c <
k; c++)
78 if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
80 if (numberOfZeros > maxNumberOfZeros)
83 bestIndex = absoluteR;
84 maxNumberOfZeros = numberOfZeros;
87 for (
int c = 0; c <
k; c++)
91 for (
int r = 0; r <
k; r++)
94 if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
96 if (numberOfZeros > maxNumberOfZeros)
101 bestIndex = - absoluteC - 1;
102 maxNumberOfZeros = numberOfZeros;
110 _minorSize = minorSize;
116 return setNextKeys(_minorSize);
121 return _minor.getAbsoluteRowIndices(target);
126 return _minor.getAbsoluteColumnIndices(target);
130 const int* rowIndices,
131 const int numberOfColumns,
132 const int* columnIndices)
141 _containerRows = numberOfRows;
142 int highestRowIndex = rowIndices[numberOfRows - 1];
143 int rowBlockCount = (highestRowIndex / 32) + 1;
144 unsigned *rowBlocks=(
unsigned*)
omAlloc(rowBlockCount*
sizeof(
unsigned));
145 for (
int i = 0;
i < rowBlockCount;
i++) rowBlocks[
i] = 0;
146 for (
int i = 0;
i < numberOfRows;
i++)
148 int blockIndex = rowIndices[
i] / 32;
149 int offset = rowIndices[
i] % 32;
150 rowBlocks[blockIndex] += (1 <<
offset);
153 _containerColumns = numberOfColumns;
154 int highestColumnIndex = columnIndices[numberOfColumns - 1];
155 int columnBlockCount = (highestColumnIndex / 32) + 1;
156 unsigned *columnBlocks=(
unsigned*)
omAlloc0(columnBlockCount*
sizeof(
unsigned));
157 for (
int i = 0;
i < numberOfColumns;
i++)
159 int blockIndex = columnIndices[
i] / 32;
160 int offset = columnIndices[
i] % 32;
161 columnBlocks[blockIndex] += (1 <<
offset);
164 _container.set(rowBlockCount, rowBlocks, columnBlockCount, columnBlocks);
174 if (_minor.compare(
MinorKey(0, 0, 0, 0)) == 0)
178 _minor.selectFirstRows(
k, _container);
179 _minor.selectFirstColumns(
k, _container);
182 else if (_minor.selectNextColumns(
k, _container))
188 else if (_minor.selectNextRows(
k, _container))
193 _minor.selectFirstColumns(
k, _container);
222 if (
j == 0 ||
i ==
j)
return 1;
243 const int containerMinorSize,
245 const bool multipleMinors)
259 result = IOverJ(rows - minorSize, containerMinorSize - minorSize)
260 * IOverJ(columns - minorSize, containerMinorSize - minorSize)
261 * Faculty(containerMinorSize - minorSize);
269 result = Faculty(containerMinorSize - minorSize);
278 _containerColumns(0),
296 string s =
"IntMinorProcessor:";
301 for (
int r = 0; r <
_rows; r++)
307 for (
int k = 0;
k < int(4 - strlen(
h));
k++)
s +=
" ";
311 int myIndexArray[500];
312 s +=
"\n considered submatrix has row indices: ";
316 if (
k != 0)
s +=
", ";
317 sprintf(
h,
"%d", myIndexArray[
k]);
s +=
h;
319 s +=
" (first row of matrix has index 0)";
320 s +=
"\n considered submatrix has column indices: ";
324 if (
k != 0)
s +=
", ";
325 sprintf(
h,
"%d", myIndexArray[
k]);
s +=
h;
327 s +=
" (first column of matrix has index 0)";
328 s +=
"\n size of considered minor(s): ";
342 const int absoluteColumnIndex)
const
344 return getEntry(absoluteRowIndex, absoluteColumnIndex) == 0;
348 const int numberOfColumns,
354 _rows = numberOfRows;
363 for (
int i = 0;
i < n;
i++)
368 const int* rowIndices,
369 const int* columnIndices,
371 const int characteristic,
379 characteristic, iSB);
383 const int* rowIndices,
384 const int* columnIndices,
385 const int characteristic,
387 const char* algorithm)
393 if (strcmp(algorithm,
"Laplace") == 0)
396 else if (strcmp(algorithm,
"Bareiss") == 0)
408 const char* algorithm)
411 if (strcmp(algorithm,
"Laplace") == 0)
413 else if (strcmp(algorithm,
"Bareiss") == 0)
424 const int characteristic,
436 if (
i == 0)
return 0;
449 const int characteristic,
459 if (characteristic != 0) e = e % characteristic;
474 int s = 0;
int m = 0;
int as = 0;
int am = 0;
478 bool hadNonZeroEntry =
false;
486 for (
int c = 0; c <
k; c++)
492 hadNonZeroEntry =
true;
496 characteristic, iSB);
505 if (characteristic != 0)
result =
result % characteristic;
506 s++;
m++; as++, am++;
521 for (
int r = 0; r <
k; r++)
527 hadNonZeroEntry =
true;
538 if (characteristic != 0)
result =
result % characteristic;
539 s++;
m++; as++, am++;
566 const int characteristic,
571 int *theRows=(
int*)
omAlloc(
k*
sizeof(
int));
573 int *theColumns=(
int*)
omAlloc(
k*
sizeof(
int));
576 int e =
getEntry(theRows[0], theColumns[0]);
577 if (characteristic != 0) e = e % characteristic;
583 long *tempMatrix=(
long*)
omAlloc(
k *
k *
sizeof(
long));
586 for (
int r = 0; r <
k; r++)
587 for (
int c = 0; c <
k; c++)
589 e =
getEntry(theRows[r], theColumns[c]);
590 if (characteristic != 0) e = e % characteristic;
596 int *rowPermutation=(
int*)
omAlloc(
k*
sizeof(
int));
600 for (
int i = 0;
i <
k;
i++) rowPermutation[
i] =
i;
602 for (
int r = 0; r <=
k - 2; r++)
606 while ((
i <
k) && (tempMatrix[rowPermutation[
i] *
k + r] == 0))
614 int j = rowPermutation[
i];
615 rowPermutation[
i] = rowPermutation[r];
616 rowPermutation[r] =
j;
622 if (r >= 1) divisor = tempMatrix[rowPermutation[r - 1] *
k + r - 1];
623 for (
int rr = r + 1; rr <
k; rr++)
624 for (
int cc = r + 1; cc <
k; cc++)
626 e = rowPermutation[rr] *
k + cc;
629 tempMatrix[e] = tempMatrix[e] * tempMatrix[rowPermutation[r] *
k + r]
630 - tempMatrix[rowPermutation[r] *
k + cc]
631 * tempMatrix[rowPermutation[rr] *
k + r];
634 tempMatrix[e] = tempMatrix[e] / divisor;
635 if (characteristic != 0)
636 tempMatrix[e] = tempMatrix[e] % characteristic;
641 int theValue =
sign * tempMatrix[rowPermutation[
k - 1] *
k +
k - 1];
651 const int columnIndex)
const
658 const bool multipleMinors,
660 const int characteristic,
const ideal& iSB)
669 if (characteristic != 0) e = e % characteristic;
680 int s = 0;
int m = 0;
int as = 0;
int am = 0;
687 bool hadNonZeroEntry =
false;
696 for (
int c = 0; c <
k; c++)
703 hadNonZeroEntry =
true;
719 characteristic, iSB);
733 if (characteristic != 0)
result =
result % characteristic;
734 s++;
m++; as++; am++;
749 for (
int r = 0; r <
k; r++)
755 hadNonZeroEntry =
true;
783 if (characteristic != 0)
result =
result % characteristic;
784 s++;
m++; as++; am++;
816 const int columnIndex)
const
822 const int absoluteColumnIndex)
const
824 return getEntry(absoluteRowIndex, absoluteColumnIndex) ==
NULL;
831 string s =
"PolyMinorProcessor:";
836 int myIndexArray[500];
837 s +=
"\n considered submatrix has row indices: ";
841 if (
k != 0)
s +=
", ";
842 sprintf(
h,
"%d", myIndexArray[
k]);
s +=
h;
844 s +=
" (first row of matrix has index 0)";
845 s +=
"\n considered submatrix has column indices: ";
849 if (
k != 0)
s +=
", ";
850 sprintf(
h,
"%d", myIndexArray[
k]);
s +=
h;
852 s +=
" (first column of matrix has index 0)";
853 s +=
"\n size of considered minor(s): ";
864 for (
int i = 0;
i < n;
i++)
870 const int numberOfColumns,
871 const poly* polyMatrix)
875 for (
int i = 0;
i < n;
i++)
879 _rows = numberOfRows;
888 for (
int i = 0;
i < n;
i++)
893 const int* rowIndices,
894 const int* columnIndices,
906 const int* rowIndices,
907 const int* columnIndices,
908 const char* algorithm,
914 if (strcmp(algorithm,
"Laplace") == 0)
916 else if (strcmp(algorithm,
"Bareiss") == 0)
930 if (strcmp(algorithm,
"Laplace") == 0)
932 else if (strcmp(algorithm,
"Bareiss") == 0)
974 int s = 0;
int m = 0;
int as = 0;
int am = 0;
978 bool hadNonZeroEntry =
false;
986 for (
int c = 0; c <
k; c++)
992 hadNonZeroEntry =
true;
1006 #ifdef COUNT_AND_PRINT_OPERATIONS
1011 s++;
m++; as++, am++;
1026 for (
int r = 0; r <
k; r++)
1032 hadNonZeroEntry =
true;
1046 #ifdef COUNT_AND_PRINT_OPERATIONS
1051 s++;
m++; as++, am++;
1057 if (hadNonZeroEntry)
1060 #ifdef COUNT_AND_PRINT_OPERATIONS
1086 const bool multipleMinors,
1098 0, 0, 0, 0, -1, -1);
1108 int s = 0;
int m = 0;
int as = 0;
int am = 0;
1112 bool hadNonZeroEntry =
false;
1121 for (
int c = 0; c <
k; c++)
1127 hadNonZeroEntry =
true;
1160 #ifdef COUNT_AND_PRINT_OPERATIONS
1165 s++;
m++; as++; am++;
1180 for (
int r = 0; r <
k; r++)
1186 hadNonZeroEntry =
true;
1218 #ifdef COUNT_AND_PRINT_OPERATIONS
1223 s++;
m++; as++; am++;
1235 if (hadNonZeroEntry)
1238 #ifdef COUNT_AND_PRINT_OPERATIONS
1264 poly a = f1; poly
b = f2;
1268 b = f1; a = f2; bLen = aLen;
1288 #ifdef COUNT_AND_PRINT_OPERATIONS
1322 number &c5,
int p5Len)
1324 #ifdef COUNT_AND_PRINT_OPERATIONS
1351 while (bucketLm !=
NULL)
1362 #ifdef COUNT_AND_PRINT_OPERATIONS
1364 multsMonForDiv += p5Len;
1376 helperPoly = bucketLm;
1377 helperPoly->next = p1;
1394 int *theRows=(
int*)
omAlloc(
k*
sizeof(
int));
1396 int *theColumns=(
int*)
omAlloc(
k*
sizeof(
int));
1401 0, 0, 0, 0, -1, -1);
1409 poly* tempMatrix = (poly*)
omAlloc(
k *
k *
sizeof(poly));
1412 for (
int r = 0; r <
k; r++)
1413 for (
int c = 0; c <
k; c++)
1419 int *rowPermutation=(
int*)
omAlloc(
k*
sizeof(
int));
1423 for (
int i = 0;
i <
k;
i++) rowPermutation[
i] =
i;
1424 poly divisor =
NULL;
1425 int divisorLength = 0;
1427 for (
int r = 0; r <=
k - 2; r++)
1431 int minComplexity = -1;
int complexity = 0;
int bestRow = -1;
1433 for (
int i = r;
i <
k;
i++)
1435 pp = tempMatrix[rowPermutation[
i] *
k + r];
1438 if (minComplexity == -1)
1446 while ((
pp !=
NULL) && (complexity < minComplexity))
1450 if (complexity < minComplexity)
1452 minComplexity = complexity;
1456 if (minComplexity <= 1)
break;
1465 pNormalize(tempMatrix[rowPermutation[bestRow] *
k + r]);
1469 int j = rowPermutation[bestRow];
1470 rowPermutation[bestRow] = rowPermutation[r];
1471 rowPermutation[r] =
j;
1477 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
1478 poly
w =
NULL;
int wl = 0;
1479 printf(
"matrix after %d steps:\n", r);
1480 for (
int u = 0; u <
k; u++)
1482 for (
int v = 0;
v <
k;
v++)
1484 if ((
v < r) && (u >
v))
1488 w = tempMatrix[rowPermutation[u] *
k +
v];
1499 divisor = tempMatrix[rowPermutation[r - 1] *
k + r - 1];
1501 divisorLength =
pLength(divisor);
1504 for (
int rr = r + 1; rr <
k; rr++)
1505 for (
int cc = r + 1; cc <
k; cc++)
1509 tempMatrix[rowPermutation[r] *
k + r],
1510 tempMatrix[rowPermutation[r] *
k + cc],
1511 tempMatrix[rowPermutation[rr] *
k + r]);
1514 tempMatrix[rowPermutation[r] *
k + r],
1515 tempMatrix[rowPermutation[r] *
k + cc],
1516 tempMatrix[rowPermutation[rr] *
k + r],
1517 divisor, divisorLC, divisorLength);
1520 #if (defined COUNT_AND_PRINT_OPERATIONS) && (COUNT_AND_PRINT_OPERATIONS > 2)
1521 poly
w =
NULL;
int wl = 0;
1522 printf(
"matrix after %d steps:\n",
k - 1);
1523 for (
int u = 0; u <
k; u++)
1525 for (
int v = 0;
v <
k;
v++)
1527 if ((
v <
k - 1) && (u >
v))
1531 w = tempMatrix[rowPermutation[u] *
k +
v];
1539 poly
result = tempMatrix[rowPermutation[
k - 1] *
k +
k - 1];
1540 tempMatrix[rowPermutation[
k - 1] *
k +
k - 1]=
NULL;
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
IntMinorValue getMinorPrivateLaplace(const int k, const MinorKey &mk, const bool multipleMinors, Cache< MinorKey, IntMinorValue > &c, int characteristic, const ideal &iSB)
A method for computing the value of a minor, using a cache.
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
std::string toString(const gfan::ZCone *const c)
MinorProcessor()
The default constructor.
poly * _polyMatrix
private store for polynomial matrix entries
std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
void setMinorSize(const int minorSize)
Sets the size of the minor(s) of interest.
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
virtual ~MinorProcessor()
A destructor for deleting an instance.
bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
IntMinorValue getMinor(const int dimension, const int *rowIndices, const int *columnIndices, const int characteristic, const ideal &iSB, const char *algorithm)
A method for computing the value of a minor without using a cache.
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this.
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.
PolyMinorValue getMinor(const int dimension, const int *rowIndices, const int *columnIndices, const char *algorithm, const ideal &iSB)
A method for computing the value of a minor, without using a cache.
ValueClass getValue(const KeyClass &key) const
Returns the value for a given key.
std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
PolyMinorProcessor()
A constructor for creating an instance.
const poly kBucketGetLm(kBucket_pt bucket)
int getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
MinorKey _container
private store for the rows and columns of the container minor within the underlying matrix; _containe...
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
static unsigned pLength(poly a)
virtual bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
poly getEntry(const int rowIndex, const int columnIndex) const
A method for retrieving the matrix entry.
IntMinorValue getMinorPrivateBareiss(const int k, const MinorKey &mk, const int characteristic, const ideal &iSB)
A method for computing the value of a minor using Bareiss's algorithm.
void kBucketDestroy(kBucket_pt *bucket_pt)
static void addOperationBucket(poly f1, poly f2, kBucket_pt bucket)
void PrintS(const char *s)
void printCounters(char *prefix, bool resetToZero)
#define omFreeSize(addr, size)
bool hasKey(const KeyClass &key) const
Checks whether the cache contains a pair (k --> v) such that k equals the given key.
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
int _rows
private store for the number of rows in the underlying matrix
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-...
PolyMinorValue getMinorPrivateLaplace(const int k, const MinorKey &mk, const bool multipleMinors, Cache< MinorKey, PolyMinorValue > &c, const ideal &iSB)
A method for computing the value of a minor, using a cache.
static int NumberOfRetrievals(const int rows, const int columns, const int containerMinorSize, const int minorSize, const bool multipleMinors)
A static method for computing the maximum number of retrievals of a minor.
int * _intMatrix
private store for integer matrix entries
MinorKey _minor
private store for the rows and columns of the minor of interest; Usually, this minor will encode subs...
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l)
static poly pp_Mult_qq(poly p, poly q, const ring r)
int getReduction(const int i, const ideal &iSB)
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
int _containerRows
private store for the number of rows in the container minor; This is set by MinorProcessor::defineSub...
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
void defineMatrix(const int numberOfRows, const int numberOfColumns, const poly *polyMatrix)
A method for defining a matrix with polynomial entries.
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
PolyMinorValue getMinorPrivateBareiss(const int k, const MinorKey &mk, const ideal &iSB)
A method for computing the value of a minor, without using a cache.
void elimOperationBucket(poly &p1, poly &p2, poly &p3, poly &p4, poly &p5, number &c5, int p5Len)
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.
poly getResult() const
Accessor for the private field _result.
static int IOverJ(const int i, const int j)
A static method for computing the binomial coefficient i over j.
int _minorSize
private store for the dimension of the minor(s) of interest
BOOLEAN dimension(leftv res, leftv args)
static void p_Delete(poly *p, const ring r)
static poly p_Add_q(poly p, poly q, const ring r)
bool hasNextMinor()
A method for checking whether there is a next choice of rows and columns when iterating through all m...
IntMinorProcessor()
A constructor for creating an instance.
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
bool setNextKeys(const int k)
A method for iterating through all possible subsets of k rows and k columns inside a pre-defined subm...
int getBestLine(const int k, const MinorKey &mk) const
A method for identifying the row or column with the most zeros.
int getAdditions() const
A method for accessing the additions performed while computing this minor.
void getCurrentRowIndices(int *const target) const
A method for obtaining the current set of rows corresponding to the current minor when iterating thro...
bool isEntryZero(const int absoluteRowIndex, const int absoluteColumnIndex) const
A method for testing whether a matrix entry is zero.
~PolyMinorProcessor()
A destructor for deleting an instance.
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
int _containerColumns
private store for the number of columns in the container minor; This is set by MinorProcessor::define...
void defineMatrix(const int numberOfRows, const int numberOfColumns, const int *matrix)
A method for defining a matrix with integer entries.
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 ....
bool put(const KeyClass &key, const ValueClass &value)
Inserts the pair (key --> value) in the cache.
const Variable & v
< [in] a sqrfree bivariate poly
void print() const
A method for printing a string representation of the given MinorProcessor to std::cout.
static void elimOperationBucketNoDiv(poly &p1, poly p2, poly p3, poly p4)
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
const CanonicalForm int s
int getResult() const
Accessor for the private field _result.
void getCurrentColumnIndices(int *const target) const
A method for obtaining the current set of columns corresponding to the current minor when iterating t...
#define pCopy(p)
return a copy of the poly
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this.
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
static int Faculty(const int i)
A static method for computing the factorial of i.
static poly p_Mult_q(poly p, poly q, const ring r)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
~IntMinorProcessor()
A destructor for deleting an instance.
virtual std::string toString() const
A method for providing a printable version of the represented MinorProcessor.
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey.
static poly pReverse(poly p)
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-...
int _columns
private store for the number of columns in the underlying matrix