test/jalview/math/SparseMatrixTest.java

   1 package jalview.math;
   2
   3 import static org.testng.Assert.assertEquals;
   4 import static org.testng.Assert.assertFalse;
   5 import static org.testng.Assert.assertTrue;
   6 import static org.testng.Assert.fail;
   7
   8 import java.util.Random;
   9
  10 import org.testng.annotations.Test;
  11 import org.testng.internal.junit.ArrayAsserts;
  12
  13 public class SparseMatrixTest
  14 {
  15   final static double DELTA = 0.0001d;
  16
  17   Random r = new Random(1729);
  18
  19   @Test(groups = "Functional")
  20   public void testConstructor()
  21   {
  22     MatrixI m1 = new SparseMatrix(
  23             new double[][] { { 2, 0, 4 }, { 0, 6, 0 } });
  24     assertEquals(m1.getValue(0, 0), 2d);
  25     assertEquals(m1.getValue(0, 1), 0d);
  26     assertEquals(m1.getValue(0, 2), 4d);
  27     assertEquals(m1.getValue(1, 0), 0d);
  28     assertEquals(m1.getValue(1, 1), 6d);
  29     assertEquals(m1.getValue(1, 2), 0d);
  30   }
  31
  32   @Test(groups = "Functional")
  33   public void testTranspose()
  34   {
  35     MatrixI m1 = new SparseMatrix(
  36             new double[][] { { 2, 0, 4 }, { 5, 6, 0 } });
  37     MatrixI m2 = m1.transpose();
  38     assertTrue(m2 instanceof SparseMatrix);
  39     assertEquals(m2.height(), 3);
  40     assertEquals(m2.width(), 2);
  41     assertEquals(m2.getValue(0, 0), 2d);
  42     assertEquals(m2.getValue(0, 1), 5d);
  43     assertEquals(m2.getValue(1, 0), 0d);
  44     assertEquals(m2.getValue(1, 1), 6d);
  45     assertEquals(m2.getValue(2, 0), 4d);
  46     assertEquals(m2.getValue(2, 1), 0d);
  47   }
  48   @Test(groups = "Functional")
  49   public void testPreMultiply()
  50   {
  51     MatrixI m1 = new SparseMatrix(new double[][] { { 2, 3, 4 } }); // 1x3
  52     MatrixI m2 = new SparseMatrix(new double[][] { { 5 }, { 6 }, { 7 } }); // 3x1
  53
  54     /*
  55      * 1x3 times 3x1 is 1x1
  56      * 2x5 + 3x6 + 4*7 =  56
  57      */
  58     MatrixI m3 = m2.preMultiply(m1);
  59     assertFalse(m3 instanceof SparseMatrix);
  60     assertEquals(m3.height(), 1);
  61     assertEquals(m3.width(), 1);
  62     assertEquals(m3.getValue(0, 0), 56d);
  63
  64     /*
  65      * 3x1 times 1x3 is 3x3
  66      */
  67     m3 = m1.preMultiply(m2);
  68     assertEquals(m3.height(), 3);
  69     assertEquals(m3.width(), 3);
  70     assertEquals(m3.getValue(0, 0), 10d);
  71     assertEquals(m3.getValue(0, 1), 15d);
  72     assertEquals(m3.getValue(0, 2), 20d);
  73     assertEquals(m3.getValue(1, 0), 12d);
  74     assertEquals(m3.getValue(1, 1), 18d);
  75     assertEquals(m3.getValue(1, 2), 24d);
  76     assertEquals(m3.getValue(2, 0), 14d);
  77     assertEquals(m3.getValue(2, 1), 21d);
  78     assertEquals(m3.getValue(2, 2), 28d);
  79   }
  80
  81   @Test(
  82     groups = "Functional",
  83     expectedExceptions = { IllegalArgumentException.class })
  84   public void testPreMultiply_tooManyColumns()
  85   {
  86     Matrix m1 = new SparseMatrix(
  87             new double[][] { { 2, 3, 4 }, { 3, 4, 5 } }); // 2x3
  88
  89     /*
  90      * 2x3 times 2x3 invalid operation -
  91      * multiplier has more columns than multiplicand has rows
  92      */
  93     m1.preMultiply(m1);
  94     fail("Expected exception");
  95   }
  96
  97   @Test(
  98     groups = "Functional",
  99     expectedExceptions = { IllegalArgumentException.class })
 100   public void testPreMultiply_tooFewColumns()
 101   {
 102     Matrix m1 = new SparseMatrix(
 103             new double[][] { { 2, 3, 4 }, { 3, 4, 5 } }); // 2x3
 104
 105     /*
 106      * 3x2 times 3x2 invalid operation -
 107      * multiplier has more columns than multiplicand has row
 108      */
 109     m1.preMultiply(m1);
 110     fail("Expected exception");
 111   }
 112
 113   @Test(groups = "Functional")
 114   public void testPostMultiply()
 115   {
 116     /*
 117      * Square matrices
 118      * (2 3) . (10   100)
 119      * (4 5)   (1000 10000)
 120      * =
 121      * (3020 30200)
 122      * (5040 50400)
 123      */
 124     MatrixI m1 = new SparseMatrix(new double[][] { { 2, 3 }, { 4, 5 } });
 125     MatrixI m2 = new SparseMatrix(new double[][] { { 10, 100 },
 126         { 1000, 10000 } });
 127     MatrixI m3 = m1.postMultiply(m2);
 128     assertEquals(m3.getValue(0, 0), 3020d);
 129     assertEquals(m3.getValue(0, 1), 30200d);
 130     assertEquals(m3.getValue(1, 0), 5040d);
 131     assertEquals(m3.getValue(1, 1), 50400d);
 132
 133     /*
 134      * also check m2.preMultiply(m1) - should be same as m1.postMultiply(m2)
 135      */
 136     MatrixI m4 = m2.preMultiply(m1);
 137     assertMatricesMatch(m3, m4, 0.00001d);
 138
 139     /*
 140      * m1 has more rows than columns
 141      * (2).(10 100 1000) = (20 200 2000)
 142      * (3)                 (30 300 3000)
 143      */
 144     m1 = new SparseMatrix(new double[][] { { 2 }, { 3 } });
 145     m2 = new SparseMatrix(new double[][] { { 10, 100, 1000 } });
 146     m3 = m1.postMultiply(m2);
 147     assertEquals(m3.height(), 2);
 148     assertEquals(m3.width(), 3);
 149     assertEquals(m3.getValue(0, 0), 20d);
 150     assertEquals(m3.getValue(0, 1), 200d);
 151     assertEquals(m3.getValue(0, 2), 2000d);
 152     assertEquals(m3.getValue(1, 0), 30d);
 153     assertEquals(m3.getValue(1, 1), 300d);
 154     assertEquals(m3.getValue(1, 2), 3000d);
 155
 156     m4 = m2.preMultiply(m1);
 157     assertMatricesMatch(m3, m4, 0.00001d);
 158
 159     /*
 160      * m1 has more columns than rows
 161      * (2 3 4) . (5 4) = (56 25)
 162      *           (6 3)
 163      *           (7 2)
 164      * [0, 0] = 2*5 + 3*6 + 4*7 = 56
 165      * [0, 1] = 2*4 + 3*3 + 4*2 = 25
 166      */
 167     m1 = new SparseMatrix(new double[][] { { 2, 3, 4 } });
 168     m2 = new SparseMatrix(new double[][] { { 5, 4 }, { 6, 3 }, { 7, 2 } });
 169     m3 = m1.postMultiply(m2);
 170     assertEquals(m3.height(), 1);
 171     assertEquals(m3.width(), 2);
 172     assertEquals(m3.getValue(0, 0), 56d);
 173     assertEquals(m3.getValue(0, 1), 25d);
 174
 175     /*
 176      * and check premultiply equivalent
 177      */
 178     m4 = m2.preMultiply(m1);
 179     assertMatricesMatch(m3, m4, 0.00001d);
 180   }
 181
 182   @Test(groups = "Timing")
 183   public void testSign()
 184   {
 185     assertEquals(Matrix.sign(-1, -2), -1d);
 186     assertEquals(Matrix.sign(-1, 2), 1d);
 187     assertEquals(Matrix.sign(-1, 0), 1d);
 188     assertEquals(Matrix.sign(1, -2), -1d);
 189     assertEquals(Matrix.sign(1, 2), 1d);
 190     assertEquals(Matrix.sign(1, 0), 1d);
 191   }
 192
 193   /**
 194    * Verify that the results of method tred() are the same for SparseMatrix as
 195    * they are for Matrix (i.e. a regression test rather than an absolute test of
 196    * correctness of results)
 197    */
 198   @Test(groups = "Functional")
 199   public void testTred_matchesMatrix()
 200   {
 201     /*
 202      * make a pseudo-random symmetric matrix as required for tred/tqli
 203      */
 204     int rows = 10;
 205     int cols = rows;
 206     double[][] d = getSparseValues(rows, cols, 3);
 207
 208     /*
 209      * make a copy of the values so m1, m2 are not
 210      * sharing arrays!
 211      */
 212     double[][] d1 = new double[rows][cols];
 213     for (int row = 0; row < rows; row++)
 214     {
 215       for (int col = 0; col < cols; col++)
 216       {
 217         d1[row][col] = d[row][col];
 218       }
 219     }
 220     Matrix m1 = new Matrix(d);
 221     Matrix m2 = new SparseMatrix(d1);
 222     assertMatricesMatch(m1, m2, 0.00001d); // sanity check
 223     m1.tred();
 224     m2.tred();
 225     assertMatricesMatch(m1, m2, 0.00001d);
 226   }
 227
 228   private void assertMatricesMatch(MatrixI m1, MatrixI m2, double delta)
 229   {
 230     if (m1.height() != m2.height())
 231     {
 232       fail("height mismatch");
 233     }
 234     if (m1.width() != m2.width())
 235     {
 236       fail("width mismatch");
 237     }
 238     for (int row = 0; row < m1.height(); row++)
 239     {
 240       for (int col = 0; col < m1.width(); col++)
 241       {
 242         double v2 = m2.getValue(row, col);
 243         double v1 = m1.getValue(row, col);
 244         if (Math.abs(v1 - v2) > DELTA)
 245         {
 246           fail(String.format("At [%d, %d] %f != %f", row, col, v1, v2));
 247         }
 248       }
 249     }
 250     ArrayAsserts.assertArrayEquals(m1.getD(), m2.getD(), delta);
 251     ArrayAsserts.assertArrayEquals(m1.getE(), m2.getE(), 0.00001d);
 252   }
 253
 254   @Test
 255   public void testGetValue()
 256   {
 257     double[][] d = new double[][] { { 0, 0, 1, 0, 0 }, { 2, 3, 0, 0, 0 },
 258         { 4, 0, 0, 0, 5 } };
 259     MatrixI m = new SparseMatrix(d);
 260     for (int row = 0; row < 3; row++)
 261     {
 262       for (int col = 0; col < 5; col++)
 263       {
 264         assertEquals(m.getValue(row, col), d[row][col],
 265                 String.format("At [%d, %d]", row, col));
 266       }
 267     }
 268   }
 269
 270   /**
 271    * Verify that the results of method tqli() are the same for SparseMatrix as
 272    * they are for Matrix (i.e. a regression test rather than an absolute test of
 273    * correctness of results)
 274    *
 275    * @throws Exception
 276    */
 277   @Test(groups = "Functional")
 278   public void testTqli_matchesMatrix() throws Exception
 279   {
 280     /*
 281      * make a pseudo-random symmetric matrix as required for tred
 282      */
 283     int rows = 6;
 284     int cols = rows;
 285     double[][] d = getSparseValues(rows, cols, 3);
 286
 287     /*
 288      * make a copy of the values so m1, m2 are not
 289      * sharing arrays!
 290      */
 291     double[][] d1 = new double[rows][cols];
 292     for (int row = 0; row < rows; row++)
 293     {
 294       for (int col = 0; col < cols; col++)
 295       {
 296         d1[row][col] = d[row][col];
 297       }
 298     }
 299     Matrix m1 = new Matrix(d);
 300     Matrix m2 = new SparseMatrix(d1);
 301
 302     // have to do tred() before doing tqli()
 303     m1.tred();
 304     m2.tred();
 305     assertMatricesMatch(m1, m2, 0.00001d);
 306
 307     m1.tqli();
 308     m2.tqli();
 309     assertMatricesMatch(m1, m2, 0.00001d);
 310   }
 311
 312   /**
 313    * Helper method to make values for a sparse, pseudo-random symmetric matrix
 314    *
 315    * @param rows
 316    * @param cols
 317    * @param occupancy
 318    *          one in 'occupancy' entries will be non-zero
 319    * @return
 320    */
 321   public double[][] getSparseValues(int rows, int cols, int occupancy)
 322   {
 323     /*
 324      * generate whole number values between -12 and +12
 325      * (to mimic score matrices used in Jalview)
 326      */
 327     double[][] d = new double[rows][cols];
 328     int m = 0;
 329     for (int i = 0; i < rows; i++)
 330     {
 331       if (++m % occupancy == 0)
 332       {
 333         d[i][i] = r.nextInt() % 13; // diagonal
 334       }
 335       for (int j = 0; j < i; j++)
 336       {
 337         if (++m % occupancy == 0)
 338         {
 339           d[i][j] = r.nextInt() % 13;
 340           d[j][i] = d[i][j];
 341         }
 342       }
 343     }
 344     return d;
 345
 346   }
 347
 348   /**
 349    * Test that verifies that the result of preMultiply is a SparseMatrix if more
 350    * than 80% zeroes, else a Matrix
 351    */
 352   @Test(groups = "Functional")
 353   public void testPreMultiply_sparseProduct()
 354   {
 355     MatrixI m1 = new SparseMatrix(new double[][] { { 1 }, { 0 }, { 0 },
 356         { 0 }, { 0 } }); // 5x1
 357     MatrixI m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 1 } }); // 1x4
 358
 359     /*
 360      * m1.m2 makes a row of 4 1's, and 4 rows of zeros
 361      * 20% non-zero so not 'sparse'
 362      */
 363     MatrixI m3 = m2.preMultiply(m1);
 364     assertFalse(m3 instanceof SparseMatrix);
 365
 366     /*
 367      * replace a 1 with a 0 in the product:
 368      * it is now > 80% zero so 'sparse'
 369      */
 370     m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 0 } });
 371     m3 = m2.preMultiply(m1);
 372     assertTrue(m3 instanceof SparseMatrix);
 373   }
 374
 375   @Test(groups = "Functional")
 376   public void testFillRatio()
 377   {
 378     SparseMatrix m1 = new SparseMatrix(new double[][] { { 2, 0, 4, 1, 0 },
 379     { 0, 6, 0, 0, 0 } });
 380     assertEquals(m1.getFillRatio(), 0.4f);
 381   }
 382
 383   /**
 384    * Verify that the results of method tred() are the same if the calculation is
 385    * redone
 386    */
 387   @Test(groups = "Functional")
 388   public void testTred_reproducible()
 389   {
 390     /*
 391      * make a pseudo-random symmetric matrix as required for tred/tqli
 392      */
 393     int rows = 10;
 394     int cols = rows;
 395     double[][] d = getSparseValues(rows, cols, 3);
 396
 397     /*
 398      * make a copy of the values so m1, m2 are not
 399      * sharing arrays!
 400      */
 401     double[][] d1 = new double[rows][cols];
 402     for (int row = 0; row < rows; row++)
 403     {
 404       for (int col = 0; col < cols; col++)
 405       {
 406         d1[row][col] = d[row][col];
 407       }
 408     }
 409     Matrix m1 = new SparseMatrix(d);
 410     Matrix m2 = new SparseMatrix(d1);
 411     assertMatricesMatch(m1, m2, 1.0e16); // sanity check
 412     m1.tred();
 413     m2.tred();
 414     assertMatricesMatch(m1, m2, 0.00001d);
 415   }
 416 }