Changeset 3029

Timestamp:

09/05/08 16:22:47 (3 months ago)

Author:

saunders

Message:

This upgraded test breaks solutions/minpoly.h when a small prime is used.

Files:

• trunk/linbox/tests/test-minpoly.C (modified) (10 diffs)

trunk/linbox/tests/test-minpoly.C

@@ -24 +24 @@
 
 #include "linbox/field/modular.h"
+#include "linbox/field/givaro-gfq.h"
 #include "linbox/blackbox/sparse.h"
 #include "linbox/util/commentator.h"
@@ -33 +34 @@
 using namespace LinBox;
 
+/* Test 0: Minimal polynomial of the zero matrix
+*/
+template <class Field, class Meth>
+static bool testZeroMinpoly (Field &F, size_t n, bool symmetrizing, const Meth& M) 
+{
+        commentator.start ("Testing zero minpoly", "testZeroMinpoly");
+        typedef vector <typename Field::Element> Polynomial;
+        Polynomial phi;
+        SparseMatrix<Field> A(F, n, n);
+        minpoly(phi, A, M);
+
+        ostream &report = commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_DESCRIPTION);
+        report << "Minimal polynomial is: ";
+        printPolynomial<Field, Polynomial> (F, report, phi);
+
+        bool ret;
+        if (phi.size () == 2 && F.isZero (phi[0]) && F.isOne(phi[1]) ) 
+                ret = true;
+        else 
+        {
+                commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
+                        << "ERROR: A = 0, should get x, got ";
+                printPolynomial<Field, Polynomial> (F, report, phi);
+                report << endl;
+                ret = false;
+        }
+        commentator.stop (MSG_STATUS (ret), (const char *) 0, "testZeroMinpoly");
+        return ret;
+}
+template <class Field>
+static bool testZeroMinpoly (Field &F, size_t n) 
+{
+        return testZeroMinpoly(F, n, false, Method::Wiedemann());
+}
+
 /* Test 1: Minimal polynomial of the identity matrix
  *
  * Construct the identity matrix and compute its minimal polynomial. Confirm
- * that the result is 1-x
+ * that the result is x-1
  *
  * F - Field over which to perform computations
@@ -54 +90 @@
         commentator.start ("Testing identity minpoly", "testIdentityMinpoly");
 
-        bool ret = true;
-
         typename Field::Element c0, c1;
 
@@ -71 +105 @@
         printPolynomial<Field, Polynomial> (F, report, phi);
 
+        bool ret;
+
         F.init (c0, -1);
         F.init (c1, 1);
 
-        if (phi.size () != 2 ||
-            !F.areEqual (phi[0], c0) ||
-            !F.areEqual (phi[1], c1)) {
+        if (phi.size () == 2 && F.areEqual (phi[0], c0) && F.areEqual (phi[1], c1)) 
+                ret = true;
+        else {
                 ret = false;
                 commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
-                        << "ERROR: Minimal polynomial is incorrect" << endl;
+                        << "ERROR: A = I, should get x-1, got ";
+                printPolynomial<Field, Polynomial> (F, report, phi);
         }
 
@@ -114 +151 @@
         commentator.start ("Testing nilpotent minpoly", "testNilpotentMinpoly");
 
-        bool ret = true;
+        bool ret;
         bool lowerTermsCorrect = true;
 
@@ -136 +173 @@
                         lowerTermsCorrect = false;
 
-        if (phi.size () != n + 1 || !F.isOne (phi[n]) || !lowerTermsCorrect) {
+        if (phi.size () == n + 1 && F.isOne (phi[n]) && lowerTermsCorrect)
+                ret = true;
+        else {
                 ret = false;
                 commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
-                        << "ERROR: Minimal polynomial is incorrect" << endl;
+                        << "ERROR: A^n = 0, should get x^" << n <<", got ";
+                printPolynomial (F, report, phi);
         }
 
@@ -232 +272 @@
                 if (!iter_passed)
                         commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
-                                << "ERROR: Output vector was incorrect" << endl;
+                                << "ERROR: A = rand, purported-minpoly(A) is not zero." << endl;
                 commentator.stop ("done");
                 commentator.progress ();
@@ -248 +288 @@
 {
     return testRandomMinpoly(F, iterations, A_stream, v_stream, Method::Wiedemann());
+}
+
+/* Test 4: test gram matrix.
+     A test of behaviour with self-orthogonal rows and cols.
+
+         Gram matrix is 1's offdiagonal and 0's on diagonal.  Self orthogonality when characteristic | n-1.
+
+         Arg m is ignored. 
+         if p := characteristic is small then size is p+1 and minpoly is x^2 + x
+         (because A^2 = (p-1)A).
+         if p is large, size is 2 and minpoly is x^2 -1.
+*/
+template <class Field, class Meth>
+static bool testGramMinpoly (Field &F, size_t m, bool symmetrizing, const Meth& M) 
+{
+        commentator.start ("Testing gram minpoly", "testGramMinpoly");
+        typedef vector <typename Field::Element> Polynomial;
+        integer n;
+        F.characteristic(n); n += 1;
+        if (n > 30) n = 2;
+        Polynomial phi;
+        typename Field::Element one, zero, neg1; F.init(one, 1); F.init(zero, 0); F.init(neg1); F.neg(neg1, one);
+        DenseMatrix<Field> A(F, n, n);
+        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) A.setEntry(i, j, one);
+        for (int i = 0; i < n; ++i) A.setEntry(i, i, zero);
+        minpoly(phi, A, M);
+
+        ostream &report = commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_DESCRIPTION);
+        report << "Minimal polynomial is: ";
+        printPolynomial<Field, Polynomial> (F, report, phi);
+
+        bool ret;
+        if (n == 2)
+                if ( phi.size() == 3 && F.areEqual(phi[0], neg1) && F.isZero(phi[1]) && F.isOne(phi[2]))
+                        ret = true;
+                else
+                {
+                        commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
+                                << "ERROR: A = gram, should get x^2 - x, got ";
+                        printPolynomial<Field, Polynomial> (F, report, phi);
+                        ret = false;
+                }
+        else 
+                if (phi.size() == 3 && F.isZero(phi[0]) && F.isOne(phi[1]) && F.isOne(phi[2]))
+                        ret = true;
+                else
+                {
+                        commentator.report (Commentator::LEVEL_IMPORTANT, INTERNAL_ERROR)
+                                << "ERROR: A = gram, should get x^2 + x, got ";
+                        printPolynomial<Field, Polynomial> (F, report, phi);
+                        ret = false;
+                }
+                commentator.stop (MSG_STATUS (ret), (const char *) 0, "testGramMinpoly");
+                return ret;
+}
+
+template <class Field>
+static bool testGramMinpoly (Field &F, size_t n) 
+{
+        return testGramMinpoly(F, n, false, Method::Wiedemann());
 }
 
@@ -272 +372 @@
 
         parseArguments (argc, argv, args);
-
-// /////////////// finite field part //////////////////
-        typedef Modular<LinBox::uint32> Field;
-        typedef vector<Field::Element> DenseVector;
-        typedef SparseMatrix<Field>::Row SparseVector;
-        //typedef pair<vector<size_t>, vector<Field::Element> > SparseVector;
-        Field F (q);
-        srand (time (NULL));
-
         commentator.getMessageClass (TIMING_MEASURE).setMaxDepth (10);
         commentator.getMessageClass (INTERNAL_DESCRIPTION).setMaxDepth (10);
         commentator.getMessageClass (INTERNAL_DESCRIPTION).setMaxDetailLevel (Commentator::LEVEL_UNIMPORTANT);
 
+// /////////////// finite field part //////////////////
+        if (q > 5 && q % 2 != 0 && q % 3 != 0 && q % 5 != 0 )
+        {
+        typedef Modular<LinBox::uint32> Field;
+        Field F (q);
+        srand (time (NULL));
+
         commentator.start("Wiedemann prime field minpoly test suite", "Wminpoly");
-        RandomDenseStream<Field, DenseVector, NonzeroRandIter<Field> >
-                v_stream (F, NonzeroRandIter<Field> (F, Field::RandIter (F)), n, numVectors);
-        RandomSparseStream<Field, SparseVector, NonzeroRandIter<Field> >
-                A_stream (F, NonzeroRandIter<Field> (F, Field::RandIter (F)), (double) k / (double) n, n, n);
 
         //no symmetrizing
+        if (!testZeroMinpoly      (F, n)) pass = false;
         if (!testIdentityMinpoly  (F, n)) pass = false;
         if (!testNilpotentMinpoly (F, n)) pass = false;
-        if (!testRandomMinpoly    (F, iterations, A_stream, v_stream)) pass = false;
+        //if (!testRandomMinpoly    (F, n)) pass = false;
+        if (!testGramMinpoly      (F, n)) pass = false;
 
         // symmetrizing
+        //if (!testZeroMinpoly            (F, n, true)) pass = false;
         if (!testIdentityMinpoly  (F, n, true)) pass = false;
+        //if (!testNilpotentMinpoly (F, n, true)) pass = false;
+        //if (!testRandomMinpoly    (F, n, true)) pass = false;
+        //if (!testGramMinpoly      (F, n, true)) pass = false;
         //need other tests...
 
         commentator.stop("Wiedemann prime field minpoly test suite");
-
+        }else{
+
+        int p;  
+        if (q % 2 == 0) p = 2;
+        if (q % 3 == 0) p = 3;
+        if (q % 5 == 0) p = 5;
+        int e = 0;  do {++e; q = q/p; } while (q > 1);
+        typedef GivaroGfq Field;
+        Field F (p, e);
+        srand (time (NULL));
+
+        commentator.start("Wiedemann non-prime field minpoly test suite", "Wminpoly");
+
+        //no symmetrizing
+        if (!testZeroMinpoly      (F, n)) pass = false;
+        if (!testIdentityMinpoly  (F, n)) pass = false;
+        if (!testNilpotentMinpoly (F, n)) pass = false;
+        //if (!testRandomMinpoly    (F, n)) pass = false;
+        if (!testGramMinpoly      (F, n)) pass = false;
+
+        // symmetrizing
+        //if (!testZeroMinpoly            (F, n, true)) pass = false;
+        if (!testIdentityMinpoly  (F, n, true)) pass = false;
+        //if (!testNilpotentMinpoly (F, n, true)) pass = false;
+        //if (!testRandomMinpoly    (F, n, true)) pass = false;
+        //if (!testGramMinpoly      (F, n, true)) pass = false;
+        //need other tests...
+
+        commentator.stop("Wiedemann non-prime field minpoly test suite");
+        }
+
+#if 0
         commentator.start("Hybrid prime field minpoly test suite", "Hminpoly");
         if (!testIdentityMinpoly  (F, n, false,  Method::Hybrid())) pass = false;
@@ -362 +493 @@
         commentator.stop("Elimination integer minpoly test suite");
 
+#endif
         return pass ? 0 : -1;
 }