JAL-3070 allow SequenceI.findPositions(0,column+1) to return range between 1 and...
[jalview.git] / 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 }