1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.math.linearalgebra; 22 23 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.almostEquals; 24 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.diagonal; 25 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.minus; 26 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.normF; 27 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.times; 28 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.timesTranspose; 29 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.transpose; 30 import static de.lmu.ifi.dbs.elki.math.linearalgebra.VMath.transposeTimes; 31 import static org.junit.Assert.assertEquals; 32 import static org.junit.Assert.assertTrue; 33 34 import org.junit.Test; 35 36 import de.lmu.ifi.dbs.elki.math.MathUtil; 37 38 /** 39 * Simple unit test for eigenvalue decomposition. 40 * 41 * @author Erich Schubert 42 */ 43 public class EigenvalueDecompositionTest { 44 @Test testToyExample()45 public void testToyExample() { 46 double[][] evs = { { 0.5, MathUtil.SQRT3 / 2 }, { -MathUtil.SQRT3 / 2, 0.5 } }; 47 double[][] lam = { { 4, 0 }, { 0, 9 } }, lam2 = { { 9, 0 }, { 0, 4 } }; 48 testBasics(timesTranspose(times(evs, lam), evs)); 49 testBasics(timesTranspose(times(evs, lam2), evs)); 50 } 51 testBasics(double[][] s)52 private EigenvalueDecomposition testBasics(double[][] s) { 53 EigenvalueDecomposition ev = new EigenvalueDecomposition(s); 54 double[][] evec = transpose(ev.getV()); // Eigenvectors are in transpose! 55 double[] eval = ev.getRealEigenvalues(); 56 double[][] diag = ev.getD(); 57 assertTrue("Diagonal does not agree with eigenvalues.", almostEquals(diagonal(eval), diag, 1e-15)); 58 59 // Try reconstruction of the original matrix: 60 // Note that we transposed V above! 61 double[][] r = times(transposeTimes(evec, diag), evec); 62 assertTrue("Not a proper decomposition.", almostEquals(s, r, 0.)); 63 64 for(int i = 0; i < eval.length; i++) { 65 assertTrue("Negative eigenvalue.", eval[i] >= 0); 66 // Check that the matrix multiplication and eigenvalue do the same thing. 67 assertTrue("Not an eigenvector.", almostEquals(times(evec[i], eval[i]), times(s, evec[i]))); 68 } 69 return ev; 70 } 71 72 /** 73 * Test added in Jama 1.0.3, causing an infinite loop. 74 */ 75 @Test(timeout = 60000) testJama103()76 public void testJama103() { 77 double[][] badeigs = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 1, 0, 0, 1 }, { 1, 0, 1, 0, 1 } }; 78 new EigenvalueDecomposition(badeigs); 79 } 80 81 @Test testAsymmetric()82 public void testAsymmetric() { 83 double[][] a = transpose(new double[][] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }); 84 EigenvalueDecomposition ev = new EigenvalueDecomposition(a); 85 double[][] v = ev.getV(), d = ev.getD(); 86 assertEquals("Asymmetric decomposition", 0., normF(minus(times(a, v), times(v, d))), 1e-13); 87 } 88 } 89