X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=test%2Fjalview%2Fmath%2FSparseMatrixTest.java;fp=test%2Fjalview%2Fmath%2FSparseMatrixTest.java;h=3c2ccaa21f8aac9f889c34cf1246e11c2b8e44d8;hb=9f70ff4b6d193b340031997634c9e3602486bc8e;hp=0000000000000000000000000000000000000000;hpb=76844c43faeeeba369deaf42f1998ca0fb33d956;p=jalview.git diff --git a/test/jalview/math/SparseMatrixTest.java b/test/jalview/math/SparseMatrixTest.java new file mode 100644 index 0000000..3c2ccaa --- /dev/null +++ b/test/jalview/math/SparseMatrixTest.java @@ -0,0 +1,416 @@ +package jalview.math; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertFalse; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.fail; + +import java.util.Random; + +import org.testng.annotations.Test; +import org.testng.internal.junit.ArrayAsserts; + +public class SparseMatrixTest +{ + final static double DELTA = 0.0001d; + + Random r = new Random(1729); + + @Test(groups = "Functional") + public void testConstructor() + { + MatrixI m1 = new SparseMatrix( + new double[][] { { 2, 0, 4 }, { 0, 6, 0 } }); + assertEquals(m1.getValue(0, 0), 2d); + assertEquals(m1.getValue(0, 1), 0d); + assertEquals(m1.getValue(0, 2), 4d); + assertEquals(m1.getValue(1, 0), 0d); + assertEquals(m1.getValue(1, 1), 6d); + assertEquals(m1.getValue(1, 2), 0d); + } + + @Test(groups = "Functional") + public void testTranspose() + { + MatrixI m1 = new SparseMatrix( + new double[][] { { 2, 0, 4 }, { 5, 6, 0 } }); + MatrixI m2 = m1.transpose(); + assertTrue(m2 instanceof SparseMatrix); + assertEquals(m2.height(), 3); + assertEquals(m2.width(), 2); + assertEquals(m2.getValue(0, 0), 2d); + assertEquals(m2.getValue(0, 1), 5d); + assertEquals(m2.getValue(1, 0), 0d); + assertEquals(m2.getValue(1, 1), 6d); + assertEquals(m2.getValue(2, 0), 4d); + assertEquals(m2.getValue(2, 1), 0d); + } + @Test(groups = "Functional") + public void testPreMultiply() + { + MatrixI m1 = new SparseMatrix(new double[][] { { 2, 3, 4 } }); // 1x3 + MatrixI m2 = new SparseMatrix(new double[][] { { 5 }, { 6 }, { 7 } }); // 3x1 + + /* + * 1x3 times 3x1 is 1x1 + * 2x5 + 3x6 + 4*7 = 56 + */ + MatrixI m3 = m2.preMultiply(m1); + assertFalse(m3 instanceof SparseMatrix); + assertEquals(m3.height(), 1); + assertEquals(m3.width(), 1); + assertEquals(m3.getValue(0, 0), 56d); + + /* + * 3x1 times 1x3 is 3x3 + */ + m3 = m1.preMultiply(m2); + assertEquals(m3.height(), 3); + assertEquals(m3.width(), 3); + assertEquals(m3.getValue(0, 0), 10d); + assertEquals(m3.getValue(0, 1), 15d); + assertEquals(m3.getValue(0, 2), 20d); + assertEquals(m3.getValue(1, 0), 12d); + assertEquals(m3.getValue(1, 1), 18d); + assertEquals(m3.getValue(1, 2), 24d); + assertEquals(m3.getValue(2, 0), 14d); + assertEquals(m3.getValue(2, 1), 21d); + assertEquals(m3.getValue(2, 2), 28d); + } + + @Test( + groups = "Functional", + expectedExceptions = { IllegalArgumentException.class }) + public void testPreMultiply_tooManyColumns() + { + Matrix m1 = new SparseMatrix( + new double[][] { { 2, 3, 4 }, { 3, 4, 5 } }); // 2x3 + + /* + * 2x3 times 2x3 invalid operation - + * multiplier has more columns than multiplicand has rows + */ + m1.preMultiply(m1); + fail("Expected exception"); + } + + @Test( + groups = "Functional", + expectedExceptions = { IllegalArgumentException.class }) + public void testPreMultiply_tooFewColumns() + { + Matrix m1 = new SparseMatrix( + new double[][] { { 2, 3, 4 }, { 3, 4, 5 } }); // 2x3 + + /* + * 3x2 times 3x2 invalid operation - + * multiplier has more columns than multiplicand has row + */ + m1.preMultiply(m1); + fail("Expected exception"); + } + + @Test(groups = "Functional") + public void testPostMultiply() + { + /* + * Square matrices + * (2 3) . (10 100) + * (4 5) (1000 10000) + * = + * (3020 30200) + * (5040 50400) + */ + MatrixI m1 = new SparseMatrix(new double[][] { { 2, 3 }, { 4, 5 } }); + MatrixI m2 = new SparseMatrix(new double[][] { { 10, 100 }, + { 1000, 10000 } }); + MatrixI m3 = m1.postMultiply(m2); + assertEquals(m3.getValue(0, 0), 3020d); + assertEquals(m3.getValue(0, 1), 30200d); + assertEquals(m3.getValue(1, 0), 5040d); + assertEquals(m3.getValue(1, 1), 50400d); + + /* + * also check m2.preMultiply(m1) - should be same as m1.postMultiply(m2) + */ + MatrixI m4 = m2.preMultiply(m1); + assertMatricesMatch(m3, m4, 0.00001d); + + /* + * m1 has more rows than columns + * (2).(10 100 1000) = (20 200 2000) + * (3) (30 300 3000) + */ + m1 = new SparseMatrix(new double[][] { { 2 }, { 3 } }); + m2 = new SparseMatrix(new double[][] { { 10, 100, 1000 } }); + m3 = m1.postMultiply(m2); + assertEquals(m3.height(), 2); + assertEquals(m3.width(), 3); + assertEquals(m3.getValue(0, 0), 20d); + assertEquals(m3.getValue(0, 1), 200d); + assertEquals(m3.getValue(0, 2), 2000d); + assertEquals(m3.getValue(1, 0), 30d); + assertEquals(m3.getValue(1, 1), 300d); + assertEquals(m3.getValue(1, 2), 3000d); + + m4 = m2.preMultiply(m1); + assertMatricesMatch(m3, m4, 0.00001d); + + /* + * m1 has more columns than rows + * (2 3 4) . (5 4) = (56 25) + * (6 3) + * (7 2) + * [0, 0] = 2*5 + 3*6 + 4*7 = 56 + * [0, 1] = 2*4 + 3*3 + 4*2 = 25 + */ + m1 = new SparseMatrix(new double[][] { { 2, 3, 4 } }); + m2 = new SparseMatrix(new double[][] { { 5, 4 }, { 6, 3 }, { 7, 2 } }); + m3 = m1.postMultiply(m2); + assertEquals(m3.height(), 1); + assertEquals(m3.width(), 2); + assertEquals(m3.getValue(0, 0), 56d); + assertEquals(m3.getValue(0, 1), 25d); + + /* + * and check premultiply equivalent + */ + m4 = m2.preMultiply(m1); + assertMatricesMatch(m3, m4, 0.00001d); + } + + @Test(groups = "Timing") + public void testSign() + { + assertEquals(Matrix.sign(-1, -2), -1d); + assertEquals(Matrix.sign(-1, 2), 1d); + assertEquals(Matrix.sign(-1, 0), 1d); + assertEquals(Matrix.sign(1, -2), -1d); + assertEquals(Matrix.sign(1, 2), 1d); + assertEquals(Matrix.sign(1, 0), 1d); + } + + /** + * Verify that the results of method tred() are the same for SparseMatrix as + * they are for Matrix (i.e. a regression test rather than an absolute test of + * correctness of results) + */ + @Test(groups = "Functional") + public void testTred_matchesMatrix() + { + /* + * make a pseudo-random symmetric matrix as required for tred/tqli + */ + int rows = 10; + int cols = rows; + double[][] d = getSparseValues(rows, cols, 3); + + /* + * make a copy of the values so m1, m2 are not + * sharing arrays! + */ + double[][] d1 = new double[rows][cols]; + for (int row = 0; row < rows; row++) + { + for (int col = 0; col < cols; col++) + { + d1[row][col] = d[row][col]; + } + } + Matrix m1 = new Matrix(d); + Matrix m2 = new SparseMatrix(d1); + assertMatricesMatch(m1, m2, 0.00001d); // sanity check + m1.tred(); + m2.tred(); + assertMatricesMatch(m1, m2, 0.00001d); + } + + private void assertMatricesMatch(MatrixI m1, MatrixI m2, double delta) + { + if (m1.height() != m2.height()) + { + fail("height mismatch"); + } + if (m1.width() != m2.width()) + { + fail("width mismatch"); + } + for (int row = 0; row < m1.height(); row++) + { + for (int col = 0; col < m1.width(); col++) + { + double v2 = m2.getValue(row, col); + double v1 = m1.getValue(row, col); + if (Math.abs(v1 - v2) > DELTA) + { + fail(String.format("At [%d, %d] %f != %f", row, col, v1, v2)); + } + } + } + ArrayAsserts.assertArrayEquals(m1.getD(), m2.getD(), delta); + ArrayAsserts.assertArrayEquals(m1.getE(), m2.getE(), 0.00001d); + } + + @Test + public void testGetValue() + { + double[][] d = new double[][] { { 0, 0, 1, 0, 0 }, { 2, 3, 0, 0, 0 }, + { 4, 0, 0, 0, 5 } }; + MatrixI m = new SparseMatrix(d); + for (int row = 0; row < 3; row++) + { + for (int col = 0; col < 5; col++) + { + assertEquals(m.getValue(row, col), d[row][col], + String.format("At [%d, %d]", row, col)); + } + } + } + + /** + * Verify that the results of method tqli() are the same for SparseMatrix as + * they are for Matrix (i.e. a regression test rather than an absolute test of + * correctness of results) + * + * @throws Exception + */ + @Test(groups = "Functional") + public void testTqli_matchesMatrix() throws Exception + { + /* + * make a pseudo-random symmetric matrix as required for tred + */ + int rows = 6; + int cols = rows; + double[][] d = getSparseValues(rows, cols, 3); + + /* + * make a copy of the values so m1, m2 are not + * sharing arrays! + */ + double[][] d1 = new double[rows][cols]; + for (int row = 0; row < rows; row++) + { + for (int col = 0; col < cols; col++) + { + d1[row][col] = d[row][col]; + } + } + Matrix m1 = new Matrix(d); + Matrix m2 = new SparseMatrix(d1); + + // have to do tred() before doing tqli() + m1.tred(); + m2.tred(); + assertMatricesMatch(m1, m2, 0.00001d); + + m1.tqli(); + m2.tqli(); + assertMatricesMatch(m1, m2, 0.00001d); + } + + /** + * Helper method to make values for a sparse, pseudo-random symmetric matrix + * + * @param rows + * @param cols + * @param occupancy + * one in 'occupancy' entries will be non-zero + * @return + */ + public double[][] getSparseValues(int rows, int cols, int occupancy) + { + /* + * generate whole number values between -12 and +12 + * (to mimic score matrices used in Jalview) + */ + double[][] d = new double[rows][cols]; + int m = 0; + for (int i = 0; i < rows; i++) + { + if (++m % occupancy == 0) + { + d[i][i] = r.nextInt() % 13; // diagonal + } + for (int j = 0; j < i; j++) + { + if (++m % occupancy == 0) + { + d[i][j] = r.nextInt() % 13; + d[j][i] = d[i][j]; + } + } + } + return d; + + } + + /** + * Test that verifies that the result of preMultiply is a SparseMatrix if more + * than 80% zeroes, else a Matrix + */ + @Test(groups = "Functional") + public void testPreMultiply_sparseProduct() + { + MatrixI m1 = new SparseMatrix(new double[][] { { 1 }, { 0 }, { 0 }, + { 0 }, { 0 } }); // 5x1 + MatrixI m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 1 } }); // 1x4 + + /* + * m1.m2 makes a row of 4 1's, and 4 rows of zeros + * 20% non-zero so not 'sparse' + */ + MatrixI m3 = m2.preMultiply(m1); + assertFalse(m3 instanceof SparseMatrix); + + /* + * replace a 1 with a 0 in the product: + * it is now > 80% zero so 'sparse' + */ + m2 = new SparseMatrix(new double[][] { { 1, 1, 1, 0 } }); + m3 = m2.preMultiply(m1); + assertTrue(m3 instanceof SparseMatrix); + } + + @Test(groups = "Functional") + public void testFillRatio() + { + SparseMatrix m1 = new SparseMatrix(new double[][] { { 2, 0, 4, 1, 0 }, + { 0, 6, 0, 0, 0 } }); + assertEquals(m1.getFillRatio(), 0.4f); + } + + /** + * Verify that the results of method tred() are the same if the calculation is + * redone + */ + @Test(groups = "Functional") + public void testTred_reproducible() + { + /* + * make a pseudo-random symmetric matrix as required for tred/tqli + */ + int rows = 10; + int cols = rows; + double[][] d = getSparseValues(rows, cols, 3); + + /* + * make a copy of the values so m1, m2 are not + * sharing arrays! + */ + double[][] d1 = new double[rows][cols]; + for (int row = 0; row < rows; row++) + { + for (int col = 0; col < cols; col++) + { + d1[row][col] = d[row][col]; + } + } + Matrix m1 = new SparseMatrix(d); + Matrix m2 = new SparseMatrix(d1); + assertMatricesMatch(m1, m2, 1.0e16); // sanity check + m1.tred(); + m2.tred(); + assertMatricesMatch(m1, m2, 0.00001d); + } +} \ No newline at end of file