Changeset 95a6f3 in git

Timestamp:

Oct 9, 2009, 3:46:30 PM (14 years ago)

Author:

Frank Seelisch <seelisch@…>

Branches:

(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')

Children:

60e4be265398f8004f3b093179a74b59f4fdcb74

Parents:

70f63ab39d1a6a435e42e041336a21e13c1269d9

Message:

more functionality: compute int minors modulo p


git-svn-id: file:///usr/local/Singular/svn/trunk@12182 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

Singular

Files:

• MinorProcessor.cc (modified) (10 diffs)
• MinorProcessor.h (modified) (6 diffs)
• TestMinors.cc (modified) (8 diffs)
• TestMinors.h (modified) (1 diff)
• extra.cc (modified) (3 diffs)

Singular/MinorProcessor.cc

@@ -270 +270 @@
 
 IntMinorValue IntMinorProcessor::getMinor(const int dimension, const int* rowIndices, const int* columnIndices,
-                                            Cache<MinorKey, IntMinorValue>& c) {
+                                            Cache<MinorKey, IntMinorValue>& c, const int characteristic) {
     defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
     _minorSize = dimension;
     // call a helper method which recursively computes the minor using the cache c:
-    return getMinorPrivate(dimension, _container, false, c);
-}
-
-IntMinorValue IntMinorProcessor::getMinor(const int dimension, const int* rowIndices, const int* columnIndices) {
+    return getMinorPrivate(dimension, _container, false, c, characteristic);
+}
+
+IntMinorValue IntMinorProcessor::getMinor(const int dimension, const int* rowIndices, const int* columnIndices, const int characteristic) {
     defineSubMatrix(dimension, rowIndices, dimension, columnIndices);
     _minorSize = dimension;
     // call a helper method which recursively computes the minor (without using a cache):
-    return getMinorPrivate(_minorSize, _container);
-}
-
-IntMinorValue IntMinorProcessor::getNextMinor() {
+    return getMinorPrivate(_minorSize, _container, characteristic);
+}
+
+IntMinorValue IntMinorProcessor::getNextMinor(const int characteristic) {
     // computation without cache
-    return getMinorPrivate(_minorSize, _minor);
-}
-
-IntMinorValue IntMinorProcessor::getNextMinor(Cache<MinorKey, IntMinorValue>& c) {
+    return getMinorPrivate(_minorSize, _minor, characteristic);
+}
+
+IntMinorValue IntMinorProcessor::getNextMinor(Cache<MinorKey, IntMinorValue>& c, const int characteristic) {
     // computation with cache
-    return getMinorPrivate(_minorSize, _minor, true, c);
-}
-
-IntMinorValue IntMinorProcessor::getMinorPrivate(const int k, const MinorKey& mk) {
+    return getMinorPrivate(_minorSize, _minor, true, c, characteristic);
+}
+
+IntMinorValue IntMinorProcessor::getMinorPrivate(const int k, const MinorKey& mk, const int characteristic) {
     assert(k > 0); // k is the minor's dimension; the minor must be at least 1x1
     // The method works by recursion, and using Lapace's Theorem along the row/column with the most zeros.
@@ -317 +317 @@
                 MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey when we omit row b and column absoluteC.
                 if (_matrix[b][absoluteC] != 0) { // Only then do we have to consider this sub-determinante.
-                    IntMinorValue mv = getMinorPrivate(k - 1, subMk);  // recursive call
+                    IntMinorValue mv = getMinorPrivate(k - 1, subMk, characteristic);  // recursive call
                     m += mv.getMultiplications();
                     s += mv.getAdditions();
@@ -324 +324 @@
                     result += sign * mv.getResult() * _matrix[b][absoluteC]; // adding sub-determinante times matrix entry
                                                                              // times appropriate sign
+                    if (characteristic != 0) result = result % characteristic;
                     s++; m++; as++, am++; // This is for the addition and multiplication in the previous line of code.
                 }
@@ -339 +340 @@
                 MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey when we omit row absoluteR and column b.
                 if (_matrix[absoluteR][b] != 0) { // Only then do we have to consider this sub-determinante.
-                    IntMinorValue mv = getMinorPrivate(k - 1, subMk);  // recursive call
+                    IntMinorValue mv = getMinorPrivate(k - 1, subMk, characteristic);  // recursive call
                     m += mv.getMultiplications();
                     s += mv.getAdditions();
@@ -346 +347 @@
                     result += sign * mv.getResult() * _matrix[absoluteR][b]; // adding sub-determinante times matrix entry
                                                                              // times appropriate sign
+                    if (characteristic != 0) result = result % characteristic;
                     s++; m++; as++, am++; // This is for the addition and multiplication in the previous line of code.
                 }
@@ -362 +364 @@
 
 IntMinorValue IntMinorProcessor::getMinorPrivate(const int k, const MinorKey& mk,
-                                                   const bool multipleMinors,
-                                                   Cache<MinorKey, IntMinorValue>& cch) {
+                                                 const bool multipleMinors,
+                                                 Cache<MinorKey, IntMinorValue>& cch,
+                                                 const int characteristic) {
     assert(k > 0); // k is the minor's dimension; the minor must be at least 1x1
     // The method works by recursion, and using Lapace's Theorem along the row/column with the most zeros.
@@ -392 +395 @@
                     }
                     else {
-                        mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch); // recursive call
+                        mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch, characteristic); // recursive call
                         // As this minor was not in the cache, we count the additions and
                         // multiplications that we needed to do in the recursive call:
@@ -403 +406 @@
                     result += sign * mv.getResult() * _matrix[b][absoluteC]; // adding sub-determinante times matrix entry
                                                                              // times appropriate sign
+                    if (characteristic != 0) result = result % characteristic;
                     s++; m++; as++; am++; // This is for the addition and multiplication in the previous line of code.
                 }
@@ -425 +429 @@
                     }
                     else {
-                        mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch); // recursive call
+                        mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch, characteristic); // recursive call
                         // As this minor was not in the cache, we count the additions and
                         // multiplications that we needed to do in the recursive call:
@@ -436 +440 @@
                     result += sign * mv.getResult() * _matrix[absoluteR][b]; // adding sub-determinante times matrix entry
                                                                              // times appropriate sign
+                    if (characteristic != 0) result = result % characteristic;
                     s++; m++; as++; am++; // This is for the addition and multiplication in the previous line of code.
                 }

Singular/MinorProcessor.h

@@ -237 +237 @@
         */
         IntMinorValue getMinorPrivate (const int k, const MinorKey& mk,
-                                        const bool multipleMinors,
-                                        Cache<MinorKey, IntMinorValue>& c);
+                                       const bool multipleMinors,
+                                       Cache<MinorKey, IntMinorValue>& c,
+                                       int characteristic);
 
         /**
@@ -250 +251 @@
         * @see MinorProcessor::getMinorPrivate (const int, const MinorKey&, const bool, Cache<MinorKey, MinorValue>&)
         */
-        IntMinorValue getMinorPrivate (const int k, const MinorKey& mk);
+        IntMinorValue getMinorPrivate (const int k, const MinorKey& mk, int characteristic);
     protected:
         bool isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const;
@@ -284 +285 @@
         * @see MinorProcessor::getMinor (const int, const int*, const int*, Cache<MinorKey, MinorValue>&)
         */
-        IntMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices);
+        IntMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices, const int characteristic);
 
         /**
@@ -299 +300 @@
         */
         IntMinorValue getMinor (const int dimension, const int* rowIndices, const int* columnIndices,
-                                 Cache<MinorKey, IntMinorValue>& c);
+                                 Cache<MinorKey, IntMinorValue>& c, const int characteristic);
 
         /**
@@ -311 +312 @@
         * @see MinorProcessor::hasNextMinor ()
         */
-        IntMinorValue getNextMinor ();
+        IntMinorValue getNextMinor (const int characteristic);
 
         /**
@@ -324 +325 @@
         * @see MinorProcessor::hasNextMinor ()
         */
-        IntMinorValue getNextMinor (Cache<MinorKey, IntMinorValue>& c);
+        IntMinorValue getNextMinor (Cache<MinorKey, IntMinorValue>& c, const int characteristic);
 
         /**

Singular/TestMinors.cc

@@ -69 +69 @@
   PrintS("\nweight of the cache equals the total number of monomials counted over");
   PrintS("\nall cached polynomials.)");
-  PrintS("\nFor this command, there will be no file or console outputs.\n\n");
+  PrintS("\nFor this command, there will be no file or console outputs.");
+  PrintS("\n\nType 'ideal i = system(\"minors\", m, k, strategy, nCache, wCache, ch);'");
+  PrintS("\nto obtain the ideal generated by all k x k non-zero minors of the");
+  PrintS("\ninteger matrix m modulo ch. (For the remaining parameters, see the");
+  PrintS("\nprevious call.)\n\n");
 }
 
@@ -409 +413 @@
 }
 
+ideal testAllIntMinorsAsIdeal(matrix mat, int minorSize, int strategy, int cacheEntries, int cacheWeight, int characteristic)
+{
+    // counters + auxiliary stuff
+  int totalMultiplications = 0;
+  int totalAdditions = 0;
+  int totalMultiplicationsAccumulated = 0;
+  int totalAdditionsAccumulated = 0;
+  char h[30];
+
+  int rowCount = mat->nrows;
+  int columnCount = mat->ncols;
+
+  int* myPolyMatrix = (int*)(mat->m);
+  IntMinorProcessor mp;
+  mp.defineMatrix(rowCount, columnCount, myPolyMatrix);
+
+  /* The next lines are for defining the sub-matrix of myPolyMatrix
+     from which we want to compute all k x k - minors.
+     In the given setting, we want the entire matrix to form the sub-matrix. */
+  int minorRows = rowCount;
+  int minorColumns = columnCount;
+  int myRowIndices[minorRows];  for (int i = 0; i < minorRows; i++) myRowIndices[i] = i;
+  int myColumnIndices[minorColumns]; for (int i = 0; i < minorColumns; i++) myColumnIndices[i] = i;
+
+  // setting sub-matrix and size of minors of interest within that sub-matrix:
+  mp.defineSubMatrix(minorRows, myRowIndices, minorColumns, myColumnIndices);
+  mp.setMinorSize(minorSize);
+
+  // containers for all upcoming results
+  IntMinorValue theMinor;
+  int theValue;
+  ideal iii = idInit(1, 0);
+
+  if (strategy == 0)
+  {
+    PrintLn(); PrintS("new code uses no cache");
+    // iteration over all minors of size "minorSize x minorSize"
+    while (mp.hasNextMinor()) {
+      // retrieving the minor:
+      theMinor = mp.getNextMinor(characteristic);
+      theValue = theMinor.getResult();
+      totalMultiplicationsAccumulated += theMinor.getAccumulatedMultiplications();
+      totalMultiplications += theMinor.getMultiplications();
+      totalAdditionsAccumulated += theMinor.getAccumulatedAdditions();
+      totalAdditions += theMinor.getAdditions();
+      idInsertPoly(iii, pISet(theValue)); // will include theValue only if it is not zero
+    }
+  }
+  else
+  {
+    PrintLn(); PrintS("new code uses cache with caching strategy ");
+    sprintf(h, "%d", strategy); PrintS(h);
+    MinorValue::SetRankingStrategy(strategy);
+    Cache<MinorKey, IntMinorValue> cch(cacheEntries, cacheWeight);
+    // iteration over all minors of size "minorSize x minorSize"
+    while (mp.hasNextMinor()) {
+      // retrieving the minor:
+      theMinor = mp.getNextMinor(cch, characteristic);
+      theValue = theMinor.getResult();
+      totalMultiplicationsAccumulated += theMinor.getAccumulatedMultiplications();
+      totalMultiplications += theMinor.getMultiplications();
+      totalAdditionsAccumulated += theMinor.getAccumulatedAdditions();
+      totalAdditions += theMinor.getAdditions();
+      idInsertPoly(iii, pISet(theValue)); // will include theValue only if it is not zero
+    }
+  }
+  idSkipZeroes(iii);  // remove zero generators (resulting from block-wise allocation of memory)
+
+  PrintLn(); PrintS("numbers of performed operations");
+  PrintLn(); PrintS("   multiplications: ");
+  sprintf(h, "%d", totalMultiplications); PrintS(h);
+  PrintLn(); PrintS("   additions: ");
+  sprintf(h, "%d", totalAdditions); PrintS(h);
+  PrintLn(); PrintS("   (multiplications without cache would be: ");
+  sprintf(h, "%d", totalMultiplicationsAccumulated); PrintS(h); PrintS(")");
+  PrintLn(); PrintS("   (additions without cache would be: ");
+  sprintf(h, "%d", totalAdditionsAccumulated); PrintS(h); PrintS(")");
+  PrintLn(); PrintLn();
+
+  return iii;
+}
+
 /**
 * A method for testing the computation of one minor; without and with cache, respectively.<br>
@@ -442 +528 @@
     prpr << "Results - " << testHeader << " - no cache";
     start = clock();
-    IntMinorValue mv = mp.getMinor(minorSize, myRowIndices, myColumnIndices);
+    IntMinorValue mv = mp.getMinor(minorSize, myRowIndices, myColumnIndices, 0);
     end = clock();
     ++prpr << "value of minor = " << mv.toString();
@@ -459 +545 @@
         IntMinorValue::SetRankingStrategy(strategy);
         start = clock();
-        mv = mp.getMinor(minorSize, myRowIndices, myColumnIndices, cch);
+        mv = mp.getMinor(minorSize, myRowIndices, myColumnIndices, cch, 0);
         end = clock();
 
@@ -526 +612 @@
     while (mp.hasNextMinor()) {
         // retrieving the minor:
-        theMinor = mp.getNextMinor();
+        theMinor = mp.getNextMinor(0);
         printTimeStart = clock();
 
@@ -587 +673 @@
         while (mp.hasNextMinor()) {
             // retrieving the minor:
-            theMinor = mp.getNextMinor(cch);
+            theMinor = mp.getNextMinor(cch, 0);
             printTimeStart = clock();
 
@@ -697 +783 @@
 
         // retrieving the minor:
-        theMinor = mp.getNextMinor();
+        theMinor = mp.getNextMinor(0);
         printTimeStart = clock();
         minorFound = (checkForEquality ? (theMinor.getResult() == targetMinor) : (theMinor.getResult() != targetMinor));
@@ -748 +834 @@
 
             // retrieving the minor:
-            theMinor = mp.getNextMinor(cch);
+            theMinor = mp.getNextMinor(cch, 0);
             printTimeStart = clock();
             minorFound = (checkForEquality ? (theMinor.getResult() == targetMinor) : (theMinor.getResult() != targetMinor));

Singular/TestMinors.h

@@ -12 +12 @@
                       int dumpMinors, int dumpResults, int dumpComplete, int dumpConsole);
 ideal testAllPolyMinorsAsIdeal(matrix m, int minorSize, int strategy, int cacheEntries, int cacheWeight);
+ideal testAllIntMinorsAsIdeal(matrix m, int minorSize, int strategy, int cacheEntries, int cacheWeight, int characteristic);
 void testStuff (const poly p);
 

Singular/extra.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR      *
 *****************************************/
-/* $Id: extra.cc,v 1.324 2009-10-09 09:05:18 seelisch Exp $ */
+/* $Id: extra.cc,v 1.325 2009-10-09 13:46:30 seelisch Exp $ */
 /*
 * ABSTRACT: general interface to internals of Singular ("system" command)
@@ -2147 +2147 @@
             // starts the computation of all k x k minors in the
             // provided matrix m (which is assumed to have polynomial
-            // entries) using a cache with 200 entries and a maximum total
-            // number of 10000 cached monomials;
+            // entries);
             // when calling this method, a ring must be declared before;
-            // there will be a run without using a cache; afterwards all 5
-            // caching strategies will be run
+            // there will be one run using a cache with specified properties
+          res->rtyp = IDEAL_CMD;
+          res->data = iii;
+        }
+        else if ((h->Typ() == MATRIX_CMD) &&
+                 (h->next->Typ() == INT_CMD) &&
+                 (h->next->next->Typ() == INT_CMD) &&
+                 (h->next->next->next->Typ() == INT_CMD) &&
+                 (h->next->next->next->next->Typ() == INT_CMD) &&
+                 (h->next->next->next->next->next->Typ() == INT_CMD) &&
+                 (h->next->next->next->next->next->next == NULL))
+        {
+          const matrix m           = (const matrix)h->Data();
+          const int k              = (const int)(long)h->next->Data();
+          const int strategy       = (const int)(long)h->next->next->Data();
+          const int cacheEntries   = (const int)(long)h->next->next->next->Data();
+          const int cacheWeight    = (const int)(long)h->next->next->next->next->Data();
+          const int characteristic = (const int)(long)h->next->next->next->next->next->Data();
+          ideal iii = testAllIntMinorsAsIdeal(m, k, strategy, cacheEntries, cacheWeight, characteristic);
+            // starts the computation of all k x k minors in the
+            // provided matrix m (which is assumed to have integer
+            // entries);
+            // when calling this method, a ring must be declared before;
+            // there will be one run using a cache with specified properties;
+            // the resulting minors will be computed modulo the given characteristic
           res->rtyp = IDEAL_CMD;
           res->data = iii;
@@ -2162 +2184 @@
                  (h->next->next->next->next->next->Typ() == INT_CMD) &&
                  (h->next->next->next->next->next->next->Typ() == INT_CMD) &&
-                 (h->next->next->next->next->next->next->next->Typ() == INT_CMD))
+                 (h->next->next->next->next->next->next->next->Typ() == INT_CMD) &&
+                 (h->next->next->next->next->next->next->next->next == NULL))
         {
           const matrix m           = (const matrix)h->Data();