check/time_lw_M2.cpp

   1 /** @file time_lw_M2.cpp
   2  *
   3  *  Test M2 from the paper "Comparison of Polynomial-Oriented CAS" by Robert H.
   4  *  Lewis and Michael Wester. */
   5
   6 /*
   7  *  GiNaC Copyright (C) 1999-2010 Johannes Gutenberg University Mainz, Germany
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  22  */
  23
  24 #include "ginac.h"
  25 #include "timer.h"
  26 using namespace GiNaC;
  27
  28 #include <iostream>
  29 using namespace std;
  30
  31 static const bool do_test = false;  // set to true in order to run this beast
  32
  33 static unsigned test()
  34 {
  35         // Determinant of a sparse matrix that comes up in graph theory:
  36         symbol x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5");
  37         symbol x6("x6"), x7("x7"), x8("x8"), x9("x9"), xA("xA");
  38         ex w[101][21] = {
  39             { 1, 1, 1, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
  40             { 2, 2, 1, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
  41             { 3, 3, 1, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
  42             { 4, 4, 1, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
  43             { 5, 5, 1, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
  44             { 6, 6, 1, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
  45             { 7, 7, 1, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
  46             { 8, 8, 1, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
  47             { 9, 9, 1, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
  48             {10, 10, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  49             {11, 2, xA, 11, 1, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
  50             {12, 3, xA, 12, 1, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
  51             {13, 4, xA, 13, 1, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
  52             {14, 5, xA, 14, 1, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
  53             {15, 6, xA, 15, 1, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
  54             {16, 7, xA, 16, 1, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
  55             {17, 8, xA, 17, 1, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
  56             {18, 9, xA, 18, 1, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
  57             {19, 10, xA, 19, 1, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
  58             {20, 20, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  59             {21, 2, xA, 12, x9, 21, 1, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
  60             {22, 3, xA, 13, x9, 22, 1, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
  61             {23, 4, xA, 14, x9, 23, 1, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
  62             {24, 5, xA, 15, x9, 24, 1, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
  63             {25, 6, xA, 16, x9, 25, 1, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
  64             {26, 7, xA, 17, x9, 26, 1, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
  65             {27, 8, xA, 18, x9, 27, 1, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
  66             {28, 9, xA, 19, x9, 28, 1, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
  67             {29, 10, xA, 20, x9, 29, 1, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
  68             {30, 30, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  69             {31, 2, xA, 12, x9, 22, x8, 31, 1, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
  70             {32, 3, xA, 13, x9, 23, x8, 32, 1, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
  71             {33, 4, xA, 14, x9, 24, x8, 33, 1, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
  72             {34, 5, xA, 15, x9, 25, x8, 34, 1, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
  73             {35, 6, xA, 16, x9, 26, x8, 35, 1, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
  74             {36, 7, xA, 17, x9, 27, x8, 36, 1, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
  75             {37, 8, xA, 18, x9, 28, x8, 37, 1, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
  76             {38, 9, xA, 19, x9, 29, x8, 38, 1, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
  77             {39, 10, xA, 20, x9, 30, x8, 39, 1, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
  78             {40, 40, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  79             {41, 2, xA, 12, x9, 22, x8, 32, x7, 41, 1, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
  80             {42, 3, xA, 13, x9, 23, x8, 33, x7, 42, 1, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
  81             {43, 4, xA, 14, x9, 24, x8, 34, x7, 43, 1, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
  82             {44, 5, xA, 15, x9, 25, x8, 35, x7, 44, 1, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
  83             {45, 6, xA, 16, x9, 26, x8, 36, x7, 45, 1, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
  84             {46, 7, xA, 17, x9, 27, x8, 37, x7, 46, 1, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
  85             {47, 8, xA, 18, x9, 28, x8, 38, x7, 47, 1, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
  86             {48, 9, xA, 19, x9, 29, x8, 39, x7, 48, 1, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
  87             {49, 10, xA, 20, x9, 30, x8, 40, x7, 49, 1, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
  88             {50, 50, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  89             {51, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 51, 1, 62, x4, 72, x3, 82, x2, 92, x1 },
  90             {52, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 52, 1, 63, x4, 73, x3, 83, x2, 93, x1 },
  91             {53, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 53, 1, 64, x4, 74, x3, 84, x2, 94, x1 },
  92             {54, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 54, 1, 65, x4, 75, x3, 85, x2, 95, x1 },
  93             {55, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 55, 1, 66, x4, 76, x3, 86, x2, 96, x1 },
  94             {56, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 56, 1, 67, x4, 77, x3, 87, x2, 97, x1 },
  95             {57, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 57, 1, 68, x4, 78, x3, 88, x2, 98, x1 },
  96             {58, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 58, 1, 69, x4, 79, x3, 89, x2, 99, x1 },
  97             {59, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 59, 1, 70, x4, 80, x3, 90, x2, 100, x1 },
  98             {60, 60, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
  99             {61, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 61, 1, 72, x3, 82, x2, 92, x1 },
 100             {62, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 62, 1, 73, x3, 83, x2, 93, x1 },
 101             {63, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 63, 1, 74, x3, 84, x2, 94, x1 },
 102             {64, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 64, 1, 75, x3, 85, x2, 95, x1 },
 103             {65, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 65, 1, 76, x3, 86, x2, 96, x1 },
 104             {66, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 66, 1, 77, x3, 87, x2, 97, x1 },
 105             {67, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 67, 1, 78, x3, 88, x2, 98, x1 },
 106             {68, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 68, 1, 79, x3, 89, x2, 99, x1 },
 107             {69, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 69, 1, 80, x3, 90, x2, 100, x1 },
 108             {70, 70, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
 109             {71, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 71, 1, 82, x2, 92, x1 },
 110             {72, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 72, 1, 83, x2, 93, x1 },
 111             {73, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 73, 1, 84, x2, 94, x1 },
 112             {74, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 74, 1, 85, x2, 95, x1 },
 113             {75, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 75, 1, 86, x2, 96, x1 },
 114             {76, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 76, 1, 87, x2, 97, x1 },
 115             {77, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 77, 1, 88, x2, 98, x1 },
 116             {78, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 78, 1, 89, x2, 99, x1 },
 117             {79, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 79, 1, 90, x2, 100, x1 },
 118             {80, 80, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
 119             {81, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 81, 1, 92, x1 },
 120             {82, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 82, 1, 93, x1 },
 121             {83, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 83, 1, 94, x1 },
 122             {84, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 84, 1, 95, x1 },
 123             {85, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 85, 1, 96, x1 },
 124             {86, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 86, 1, 97, x1 },
 125             {87, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 87, 1, 98, x1 },
 126             {88, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 88, 1, 99, x1 },
 127             {89, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 89, 1, 100, x1 },
 128             {90, 90, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
 129             {91, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 91, 1 },
 130             {92, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 92, 1 },
 131             {93, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 93, 1 },
 132             {94, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 94, 1 },
 133             {95, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 95, 1 },
 134             {96, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 96, 1 },
 135             {97, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 97, 1 },
 136             {98, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 98, 1 },
 137             {99, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 99, 1 },
 138             {100, 100, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
 139             {101, 1, xA, 11, x9, 21, x8, 31, x7, 41, x6, 51, x5, 61, x4, 71, x3, 81, x2, 91, x1}
 140         };
 141         matrix m(101,101);
 142         for (unsigned r=0; r<101; ++r) {
 143                 for (unsigned c=0; c<10; ++c) {
 144                         m.set(r,
 145                               unsigned(ex_to<numeric>(w[r][2*c+1]).to_int()-1),
 146                               w[r][2*c+2]);
 147                 }
 148         }
 149         ex det = m.determinant();
 150         if (det.nops()!=85228) {
 151                 clog << "The determinant was miscalculated." << endl;
 152                 return 1;
 153         }
 154         return 0;
 155 }
 156
 157 unsigned time_lw_M2()
 158 {
 159         unsigned result = 0;
 160         unsigned count = 0;
 161         timer piaget;
 162         double time = .0;
 163
 164         cout << "timing Lewis-Wester test M2 (101x101 sparse, det)" << flush;
 165
 166         if (do_test) {
 167                 piaget.start();
 168                 // correct for very small times:
 169                 do {
 170                         result = test();
 171                         ++count;
 172                 } while ((time=piaget.read())<0.1 && !result);
 173                 cout << '.' << flush;
 174                 cout << time/count << 's' << endl;
 175         } else {
 176                 cout << " disabled" << endl;
 177         }
 178
 179         return result;
 180 }
 181
 182 extern void randomify_symbol_serials();
 183
 184 int main(int argc, char** argv)
 185 {
 186         randomify_symbol_serials();
 187         cout << setprecision(2) << showpoint;
 188         return time_lw_M2();
 189 }