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);
 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);
 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);
 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     // TODO why does this fail for rows > 9??
 205     int rows = 9;
 206     int cols = rows;
 207     double[][] d = getSparseValues(rows, cols, 3);
 208
 209     /*
 210      * make a copy of the values so m1, m2 are not
 211      * sharing arrays!
 212      */
 213     double[][] d1 = new double[rows][cols];
 214     for (int row = 0; row < rows; row++)
 215     {
 216       for (int col = 0; col < cols; col++)
 217       {
 218         d1[row][col] = d[row][col];
 219       }
 220     }
 221     Matrix m1 = new Matrix(d);
 222     Matrix m2 = new SparseMatrix(d1);
 223     assertMatricesMatch(m1, m2); // sanity check
 224     m1.tred();
 225     m2.tred();
 226     assertMatricesMatch(m1, m2);
 227   }
 228
 229   private void assertMatricesMatch(MatrixI m1, MatrixI m2)
 230   {
 231     if (m1.height() != m2.height())
 232     {
 233       fail("height mismatch");
 234     }
 235     if (m1.width() != m2.width())
 236     {
 237       fail("width mismatch");
 238     }
 239     for (int row = 0; row < m1.height(); row++)
 240     {
 241       for (int col = 0; col < m1.width(); col++)
 242       {
 243         double v2 = m2.getValue(row, col);
 244         double v1 = m1.getValue(row, col);
 245         if (Math.abs(v1 - v2) > DELTA)
 246         {
 247           fail(String.format("At [%d, %d] %f != %f", row, col, v1, v2));
 248         }
 249       }
 250     }
 251     ArrayAsserts.assertArrayEquals(m1.getD(), m2.getD(), 0.00001d);
 252     ArrayAsserts.assertArrayEquals(m1.getE(), m2.getE(), 0.00001d);
 253   }
 254
 255   @Test
 256   public void testGetValue()
 257   {
 258     double[][] d = new double[][] { { 0, 0, 1, 0, 0 }, { 2, 3, 0, 0, 0 },
 259         { 4, 0, 0, 0, 5 } };
 260     MatrixI m = new SparseMatrix(d);
 261     for (int row = 0; row < 3; row++)
 262     {
 263       for (int col = 0; col < 5; col++)
 264       {
 265         assertEquals(m.getValue(row, col), d[row][col],
 266                 String.format("At [%d, %d]", row, col));
 267       }
 268     }
 269   }
 270
 271   /**
 272    * Verify that the results of method tqli() are the same for SparseMatrix as
 273    * they are for Matrix (i.e. a regression test rather than an absolute test of
 274    * correctness of results)
 275    *
 276    * @throws Exception
 277    */
 278   @Test(groups = "Functional")
 279   public void testTqli_matchesMatrix() throws Exception
 280   {
 281     /*
 282      * make a pseudo-random symmetric matrix as required for tred
 283      */
 284     int rows = 6;
 285     int cols = rows;
 286     double[][] d = getSparseValues(rows, cols, 3);
 287
 288     /*
 289      * make a copy of the values so m1, m2 are not
 290      * sharing arrays!
 291      */
 292     double[][] d1 = new double[rows][cols];
 293     for (int row = 0; row < rows; row++)
 294     {
 295       for (int col = 0; col < cols; col++)
 296       {
 297         d1[row][col] = d[row][col];
 298       }
 299     }
 300     Matrix m1 = new Matrix(d);
 301     Matrix m2 = new SparseMatrix(d1);
 302
 303     // have to do tred() before doing tqli()
 304     m1.tred();
 305     m2.tred();
 306     assertMatricesMatch(m1, m2);
 307
 308     m1.tqli();
 309     m2.tqli();
 310     assertMatricesMatch(m1, m2);
 311   }
 312
 313   /**
 314    * Helper method to make values for a sparse, pseudo-random symmetric matrix
 315    *
 316    * @param rows
 317    * @param cols
 318    * @param occupancy
 319    *          one in 'occupancy' entries will be non-zero
 320    * @return
 321    */
 322   public double[][] getSparseValues(int rows, int cols, int occupancy)
 323   {
 324     /*
 325      * generate whole number values between -12 and +12
 326      * (to mimic score matrices used in Jalview)
 327      */
 328     double[][] d = new double[rows][cols];
 329     int m = 0;
 330     for (int i = 0; i < rows; i++)
 331     {
 332       if (++m % occupancy == 0)
 333       {
 334         d[i][i] = r.nextInt() % 13; // diagonal
 335       }
 336       for (int j = 0; j < i; j++)
 337       {
 338         if (++m % occupancy == 0)
 339         {
 340           d[i][j] = r.nextInt() % 13;
 341           d[j][i] = d[i][j];
 342         }
 343       }
 344     }
 345     return d;
 346
 347   }
 348
 349   /**
 350    * Test that verifies that the result of preMultiply is a SparseMatrix if more
 351    * than 80% zeroes, else a Matrix
 352    */
 353   @Test(groups = "Functional")
 354   public void testPreMultiply_sparseProduct()
 355   {
 356     MatrixI m1 = new SparseMatrix(new double[][] { { 1 }, { 0 }, { 0 },
 357         { 0 }, { 0 } }); // 5x1
 358     MatrixI m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 1 } }); // 1x4
 359
 360     /*
 361      * m1.m2 makes a row of 4 1's, and 4 rows of zeros
 362      * 20% non-zero so not 'sparse'
 363      */
 364     MatrixI m3 = m2.preMultiply(m1);
 365     assertFalse(m3 instanceof SparseMatrix);
 366
 367     /*
 368      * replace a 1 with a 0 in the product:
 369      * it is now > 80% zero so 'sparse'
 370      */
 371     m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 0 } });
 372     m3 = m2.preMultiply(m1);
 373     assertTrue(m3 instanceof SparseMatrix);
 374   }
 375
 376   @Test(groups = "Functional")
 377   public void testFillRatio()
 378   {
 379     SparseMatrix m1 = new SparseMatrix(new double[][] { { 2, 0, 4, 1, 0 },
 380     { 0, 6, 0, 0, 0 } });
 381     assertEquals(m1.getFillRatio(), 0.4f);
 382   }
 383
 384   /**
 385    * Verify that the results of method tred() are the same if the calculation is
 386    * redone
 387    */
 388   @Test(groups = "Functional")
 389   public void testTred_reproducible()
 390   {
 391     /*
 392      * make a pseudo-random symmetric matrix as required for tred/tqli
 393      */
 394     int rows = 10;
 395     int cols = rows;
 396     double[][] d = getSparseValues(rows, cols, 3);
 397
 398     /*
 399      * make a copy of the values so m1, m2 are not
 400      * sharing arrays!
 401      */
 402     double[][] d1 = new double[rows][cols];
 403     for (int row = 0; row < rows; row++)
 404     {
 405       for (int col = 0; col < cols; col++)
 406       {
 407         d1[row][col] = d[row][col];
 408       }
 409     }
 410     Matrix m1 = new SparseMatrix(d);
 411     Matrix m2 = new SparseMatrix(d1);
 412     assertMatricesMatch(m1, m2); // sanity check
 413     m1.tred();
 414     m2.tred();
 415     assertMatricesMatch(m1, m2);
 416   }
 417 }