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