- Finally: the test M1 from Lewis and Wester works.

diff --git a/check/Makefile.am b/check/Makefile.am
index a877fdb5f335af9bf642a3e1ae019a649666877f..7b24a57837771d369b181a4d67b851b5125b19d7 100644 (file)
--- a/check/Makefile.am
+++ b/check/Makefile.am
@@ -12,7 +12,7 @@ checks_LDADD = ../ginac/libginac.la
 times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp \
   time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp \
   time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp \
 times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp \
   time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp \
   time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp \

-  time_lw_H.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp \
+  time_lw_H.cpp time_lw_M1.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp \

   timer.cpp times.cpp times.h
 times_LDADD = ../ginac/libginac.la
 INCLUDES = -I$(srcdir)/../ginac
   timer.cpp times.cpp times.h
 times_LDADD = ../ginac/libginac.la
 INCLUDES = -I$(srcdir)/../ginac

diff --git a/check/Makefile.in b/check/Makefile.in
index 3a7cd3b62de837bfdb62201203161457f995dc3c..b3f8dd5b2391f8de46d0a5d8e42f1690dfdae5b1 100644 (file)
--- a/check/Makefile.in
+++ b/check/Makefile.in
@@ -111,7 +111,7 @@ exams_LDADD = ../ginac/libginac.la
 checks_SOURCES = check_numeric.cpp check_inifcns.cpp check_matrices.cpp   check_lsolve.cpp genex.cpp checks.cpp checks.h
 
 checks_LDADD = ../ginac/libginac.la
 checks_SOURCES = check_numeric.cpp check_inifcns.cpp check_matrices.cpp   check_lsolve.cpp genex.cpp checks.cpp checks.h
 
 checks_LDADD = ../ginac/libginac.la

-times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp   time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp   time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp   time_lw_H.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp   timer.cpp times.cpp times.h
+times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp   time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp   time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp   time_lw_H.cpp time_lw_M1.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp   timer.cpp times.cpp times.h

 
 times_LDADD = ../ginac/libginac.la
 INCLUDES = -I$(srcdir)/../ginac
 
 times_LDADD = ../ginac/libginac.la
 INCLUDES = -I$(srcdir)/../ginac


@@ -137,8 +137,8 @@ checks_DEPENDENCIES =  ../ginac/libginac.la
 checks_LDFLAGS = 
 times_OBJECTS =  time_dennyfliegner.o time_gammaseries.o \
 time_vandermonde.o time_toeplitz.o time_lw_A.o time_lw_B.o time_lw_C.o \
 checks_LDFLAGS = 
 times_OBJECTS =  time_dennyfliegner.o time_gammaseries.o \
 time_vandermonde.o time_toeplitz.o time_lw_A.o time_lw_B.o time_lw_C.o \

-time_lw_D.o time_lw_E.o time_lw_F.o time_lw_G.o time_lw_H.o time_lw_O.o \
-time_lw_P.o time_lw_Pprime.o timer.o times.o
+time_lw_D.o time_lw_E.o time_lw_F.o time_lw_G.o time_lw_H.o \
+time_lw_M1.o time_lw_O.o time_lw_P.o time_lw_Pprime.o timer.o times.o

 times_DEPENDENCIES =  ../ginac/libginac.la
 times_LDFLAGS = 
 CXXFLAGS = @CXXFLAGS@
 times_DEPENDENCIES =  ../ginac/libginac.la
 times_LDFLAGS = 
 CXXFLAGS = @CXXFLAGS@


@@ -167,9 +167,10 @@ DEP_FILES =  .deps/check_inifcns.P .deps/check_lsolve.P \
 .deps/exams.P .deps/genex.P .deps/time_dennyfliegner.P \
 .deps/time_gammaseries.P .deps/time_lw_A.P .deps/time_lw_B.P \
 .deps/time_lw_C.P .deps/time_lw_D.P .deps/time_lw_E.P .deps/time_lw_F.P \
 .deps/exams.P .deps/genex.P .deps/time_dennyfliegner.P \
 .deps/time_gammaseries.P .deps/time_lw_A.P .deps/time_lw_B.P \
 .deps/time_lw_C.P .deps/time_lw_D.P .deps/time_lw_E.P .deps/time_lw_F.P \

-.deps/time_lw_G.P .deps/time_lw_H.P .deps/time_lw_O.P .deps/time_lw_P.P \
-.deps/time_lw_Pprime.P .deps/time_toeplitz.P .deps/time_vandermonde.P \
-.deps/timer.P .deps/times.P
+.deps/time_lw_G.P .deps/time_lw_H.P .deps/time_lw_M1.P \
+.deps/time_lw_O.P .deps/time_lw_P.P .deps/time_lw_Pprime.P \
+.deps/time_toeplitz.P .deps/time_vandermonde.P .deps/timer.P \
+.deps/times.P

 SOURCES = $(exams_SOURCES) $(checks_SOURCES) $(times_SOURCES)
 OBJECTS = $(exams_OBJECTS) $(checks_OBJECTS) $(times_OBJECTS)
 
 SOURCES = $(exams_SOURCES) $(checks_SOURCES) $(times_SOURCES)
 OBJECTS = $(exams_OBJECTS) $(checks_OBJECTS) $(times_OBJECTS)
 

diff --git a/check/time_lw_M1.cpp b/check/time_lw_M1.cpp
new file mode 100644 (file)
index 0000000..d3dabe6
--- /dev/null
+++ b/check/time_lw_M1.cpp
@@ -0,0 +1,136 @@
+/** @file time_lw_M1.cpp
+ *
+ *  Test M1 from the paper "Comparison of Polynomial-Oriented CAS" by Robert H.
+ *  Lewis and Michael Wester. */
+
+/*
+ *  GiNaC Copyright (C) 1999-2000 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include "times.h"
+
+static unsigned test(void)
+{
+    // Determinant of a sparse matrix that comes up in graph theory:
+    symbol x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5");
+    ex w[26][11] = {
+        { 1,  1,  1,  7, x4, 12, x3, 17, x2, 22, x1},
+        { 2,  2,  1,  8, x4, 13, x3, 18, x2, 23, x1},
+        { 3,  3,  1,  9, x4, 14, x3, 19, x2, 24, x1},
+        { 4,  4,  1, 10, x4, 15, x3, 20, x2, 25, x1},
+        { 5,  5,  1, 26,  1,  1,  0,  1,  0,  1, 0 },
+        { 6,  2, x5,  6,  1, 12, x3, 17, x2, 22, x1},
+        { 7,  3, x5,  7,  1, 13, x3, 18, x2, 23, x1},
+        { 8,  4, x5,  8,  1, 14, x3, 19, x2, 24, x1},
+        { 9,  5, x5,  9,  1, 15, x3, 20, x2, 25, x1},
+        {10, 10,  1, 26,  1,  1,  0,  1,  0,  1, 0 },
+        {11,  2, x5,  7, x4, 11,  1, 17, x2, 22, x1},
+        {12,  3, x5,  8, x4, 12,  1, 18, x2, 23, x1},
+        {13,  4, x5,  9, x4, 13,  1, 19, x2, 24, x1},
+        {14,  5, x5, 10, x4, 14,  1, 20, x2, 25, x1},
+        {15, 15,  1, 26,  1,  1,  0,  1,  0,  1, 0 },
+        {16,  2, x5,  7, x4, 12, x3, 16,  1, 22, x1},
+        {17,  3, x5,  8, x4, 13, x3, 17,  1, 23, x1},
+        {18,  4, x5,  9, x4, 14, x3, 18,  1, 24, x1},
+        {19,  5, x5, 10, x4, 15, x3, 19,  1, 25, x1},
+        {20, 20,  1, 26,  1,  1,  0,  1,  0,  1, 0 },
+        {21,  2, x5,  7, x4, 12, x3, 17, x2, 21, 1 },
+        {22,  3, x5,  8, x4, 13, x3, 18, x2, 22, 1 },
+        {23,  4, x5,  9, x4, 14, x3, 19, x2, 23, 1 },
+        {24,  5, x5, 10, x4, 15, x3, 20, x2, 24, 1 },
+        {25, 25,  1, 26,  1,  1,  0,  1,  0,  1, 0 },
+        {26,  1, x5,  6, x4, 11, x3, 16, x2, 21, x1}
+    };
+    matrix m(26,26);
+    for (unsigned r=0; r<26; ++r) {
+        for (unsigned c=0; c<5; ++c) {
+            m.set(r,
+                  unsigned(ex_to_numeric(w[r][2*c+1]).to_int()-1),
+                  w[r][2*c+2]);
+        }
+    }
+    ex det = m.determinant();
+    // The result should have been:
+    ex cmp = -12*pow(x1*x5,2)*x4-12*x1*pow(x2*x4,2)-12*x3*pow(x4*x5,2)
+        -pow(x5,3)*pow(x4,2)-12*x1*pow(x4*x5,2)-12*x2*pow(x4*x5,2)
+        -pow(x4,3)*pow(x5,2)-2*pow(x5,3)*x4*x3-2*pow(x4,3)*x5*x3
+        -36*x3*x1*pow(x5,2)*x4-36*x3*x1*pow(x4,2)*x5-12*pow(x3*x5,2)*x4
+        -12*pow(x3*x4,2)*x5-36*x3*x2*pow(x5,2)*x4-36*x3*x2*pow(x4,2)*x5
+        -36*x1*x5*pow(x3,2)*x4-36*x2*x5*pow(x3,2)*x4-12*x1*pow(x3*x5,2)
+        -12*x1*pow(x3*x4,2)-pow(x3,3)*pow(x5,2)-pow(x3,3)*pow(x4,2)
+        -2*pow(x3,3)*x5*x4-12*x2*pow(x3*x5,2)-12*x2*pow(x3*x4,2)
+        -12*x1*pow(x2*x5,2)-12*pow(x2*x5,2)*x4-12*pow(x2*x4,2)*x5
+        -12*pow(x2*x5,2)*x3-12*pow(x2*x4,2)*x3-12*pow(x2*x3,2)*x5
+        -12*pow(x2*x3,2)*x4-pow(x3,2)*pow(x5,3)-pow(x3,2)*pow(x4,3)
+        -2*pow(x5,3)*x4*x2-2*pow(x4,3)*x5*x2-2*x3*pow(x5,3)*x2
+        -2*x3*pow(x4,3)*x2-2*pow(x3,3)*x5*x2-2*pow(x3,3)*x4*x2
+        -2*pow(x2,3)*x5*x4-36*x2*x1*pow(x5,2)*x4-36*x2*x1*pow(x4,2)*x5
+        -120*x2*x1*x5*x4*x3-36*x2*x1*pow(x5,2)*x3-36*x2*x1*pow(x4,2)*x3
+        -36*x2*x1*pow(x3,2)*x5-36*x2*x1*pow(x3,2)*x4-36*pow(x2,2)*x5*x4*x3
+        -36*pow(x1,2)*x5*x4*x3-12*pow(x1*x5,2)*x3-12*pow(x1*x4,2)*x3
+        -12*pow(x1*x3,2)*x5-12*pow(x1*x3,2)*x4-12*pow(x1*x5,2)*x2
+        -12*pow(x1*x4,2)*x2-12*pow(x1*x3,2)*x2-12*pow(x1*x2,2)*x5
+        -12*pow(x1*x2,2)*x4-12*pow(x1*x2,2)*x3-pow(x2,2)*pow(x5,3)
+        -pow(x2,2)*pow(x4,3)-pow(x2,2)*pow(x3,3)-36*x1*x5*pow(x2,2)*x4
+        -36*x1*x5*pow(x2,2)*x3-36*x1*x4*pow(x2,2)*x3-36*x2*pow(x1,2)*x5*x4
+        -pow(x2,3)*pow(x5,2)-pow(x2,3)*pow(x4,2)-pow(x2,3)*pow(x3,2)
+        -2*pow(x2,3)*x5*x3-2*pow(x2,3)*x4*x3-12*x1*pow(x2*x3,2)
+        -12*pow(x1*x4,2)*x5-pow(x1,3)*pow(x5,2)-pow(x1,3)*pow(x4,2)
+        -pow(x1,3)*pow(x3,2)-pow(x1,3)*pow(x2,2)-pow(x1,2)*pow(x5,3)
+        -pow(x1,2)*pow(x4,3)-pow(x1,2)*pow(x3,3)-pow(x1,2)*pow(x2,3)
+        -36*x2*x3*pow(x1,2)*x5-36*x2*x3*pow(x1,2)*x4-2*pow(x5,3)*x4*x1
+        -2*pow(x4,3)*x5*x1-2*x3*pow(x5,3)*x1-2*x3*pow(x4,3)*x1
+        -2*pow(x3,3)*x5*x1-2*pow(x3,3)*x4*x1-2*x2*pow(x5,3)*x1
+        -2*x2*pow(x4,3)*x1-2*x2*pow(x3,3)*x1-2*pow(x2,3)*x5*x1
+        -2*pow(x2,3)*x4*x1-2*pow(x2,3)*x3*x1-2*pow(x1,3)*x5*x4
+        -2*pow(x1,3)*x5*x3-2*pow(x1,3)*x5*x2-2*pow(x1,3)*x4*x3
+        -2*pow(x1,3)*x4*x2-2*pow(x1,3)*x3*x2;
+    if (det!=cmp) {
+        clog << "The determinant was miscalculated" << endl;
+        return 1;
+    }
+    return 0;
+}
+
+unsigned time_lw_M1(void)
+{
+    unsigned result = 0;
+    unsigned count = 0;
+    timer rolex;
+    double time = .0;
+    
+    cout << "timing Lewis-Wester test M1 (26x26 sparse, det)" << flush;
+    clog << "-------Lewis-Wester test M1 (26x26 sparse, det)" << endl;
+    
+    rolex.start();
+    // correct for very small times:
+    do {
+        result = test();
+        ++count;
+    } while ((time=rolex.read())<0.1 && !result);
+    cout << '.' << flush;
+    
+    if (!result) {
+        cout << " passed ";
+        clog << "(no output)" << endl;
+    } else {
+        cout << " failed ";
+    }
+    cout << int(1000*(time/count))*0.001 << 's' << endl;
+    
+    return result;
+}

diff --git a/check/times.cpp b/check/times.cpp
index 5628aa4cfb64cd502c3f5e0d209bdaf828115b50..f5642862b47f678edba343d9b5c0bde8b1db0a34 100644 (file)
--- a/check/times.cpp
+++ b/check/times.cpp
@@ -30,120 +30,112 @@ int main()
     unsigned result = 0;
     
     try {
     unsigned result = 0;
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_dennyfliegner();
+        result += time_dennyfliegner();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_gammaseries();
+        result += time_gammaseries();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_vandermonde();
+        result += time_vandermonde();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_toeplitz();
+        result += time_toeplitz();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_A();
+        result += time_lw_A();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_B();
+        result += time_lw_B();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_C();
+        result += time_lw_C();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_D();
+        result += time_lw_D();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_E();
+        result += time_lw_E();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_F();
+        result += time_lw_F();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_G();
+        result += time_lw_G();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_H();
+        result += time_lw_H();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_O();
+        result += time_lw_M1();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_P();
+        result += time_lw_O();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     }
     
     try {

-        for (int i=0; i<1; ++i)
-            result += time_lw_Pprime();
+        result += time_lw_P();
+    } catch (const exception &e) {
+        cout << "Error: caught exception " << e.what() << endl;
+        ++result;
+    }
+    
+    try {
+        result += time_lw_Pprime();

     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;
     } catch (const exception &e) {
         cout << "Error: caught exception " << e.what() << endl;
         ++result;

diff --git a/check/times.h b/check/times.h
index 26a33552f50b6be94acbb0e0c0d82c9966f05ec7..24cfc77670af633fc96253978197cc3153e68fc3 100644 (file)
--- a/check/times.h
+++ b/check/times.h
@@ -59,6 +59,7 @@ unsigned time_lw_E();
 unsigned time_lw_F();
 unsigned time_lw_G();
 unsigned time_lw_H();
 unsigned time_lw_F();
 unsigned time_lw_G();
 unsigned time_lw_H();

+unsigned time_lw_M1();

 unsigned time_lw_O();
 unsigned time_lw_P();
 unsigned time_lw_Pprime();
 unsigned time_lw_O();
 unsigned time_lw_P();
 unsigned time_lw_Pprime();

diff --git a/check/times.ref b/check/times.ref
index 1ae35418c3e90a41bbe228693dbf45f44a0b3227..d47cb6d30df698f03fb30ac28e0251870fe00bd5 100644 (file)
--- a/check/times.ref
+++ b/check/times.ref
@@ -22,6 +22,8 @@
 (no output)
 -------Lewis-Wester test H (det of 80x80 Hilbert)
 (no output)
 (no output)
 -------Lewis-Wester test H (det of 80x80 Hilbert)
 (no output)

+-------Lewis-Wester test M1 (26x26 sparse, det)
+(no output)

 -------Lewis-Wester test O1 (three 15x15 dets)
 (no output)
 -------Lewis-Wester test P (det of sparse rank 101)
 -------Lewis-Wester test O1 (three 15x15 dets)
 (no output)
 -------Lewis-Wester test P (det of sparse rank 101)