001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018 package org.apache.commons.math.linear; 019 020 import junit.framework.Test; 021 import junit.framework.TestCase; 022 import junit.framework.TestSuite; 023 024 import org.apache.commons.math.TestUtils; 025 import org.apache.commons.math.fraction.Fraction; 026 import org.apache.commons.math.fraction.FractionField; 027 import org.apache.commons.math.linear.FieldLUDecomposition; 028 import org.apache.commons.math.linear.FieldLUDecompositionImpl; 029 import org.apache.commons.math.linear.FieldMatrix; 030 import org.apache.commons.math.linear.Array2DRowFieldMatrix; 031 import org.apache.commons.math.linear.InvalidMatrixException; 032 033 public class FieldLUDecompositionImplTest extends TestCase { 034 private Fraction[][] testData = { 035 { new Fraction(1), new Fraction(2), new Fraction(3)}, 036 { new Fraction(2), new Fraction(5), new Fraction(3)}, 037 { new Fraction(1), new Fraction(0), new Fraction(8)} 038 }; 039 private Fraction[][] testDataMinus = { 040 { new Fraction(-1), new Fraction(-2), new Fraction(-3)}, 041 { new Fraction(-2), new Fraction(-5), new Fraction(-3)}, 042 { new Fraction(-1), new Fraction(0), new Fraction(-8)} 043 }; 044 private Fraction[][] luData = { 045 { new Fraction(2), new Fraction(3), new Fraction(3) }, 046 { new Fraction(2), new Fraction(3), new Fraction(7) }, 047 { new Fraction(6), new Fraction(6), new Fraction(8) } 048 }; 049 050 // singular matrices 051 private Fraction[][] singular = { 052 { new Fraction(2), new Fraction(3) }, 053 { new Fraction(2), new Fraction(3) } 054 }; 055 private Fraction[][] bigSingular = { 056 { new Fraction(1), new Fraction(2), new Fraction(3), new Fraction(4) }, 057 { new Fraction(2), new Fraction(5), new Fraction(3), new Fraction(4) }, 058 { new Fraction(7), new Fraction(3), new Fraction(256), new Fraction(1930) }, 059 { new Fraction(3), new Fraction(7), new Fraction(6), new Fraction(8) } 060 }; // 4th row = 1st + 2nd 061 062 public FieldLUDecompositionImplTest(String name) { 063 super(name); 064 } 065 066 public static Test suite() { 067 TestSuite suite = new TestSuite(FieldLUDecompositionImplTest.class); 068 suite.setName("FieldLUDecompositionImpl Tests"); 069 return suite; 070 } 071 072 /** test dimensions */ 073 public void testDimensions() { 074 FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData); 075 FieldLUDecomposition<Fraction> LU = new FieldLUDecompositionImpl<Fraction>(matrix); 076 assertEquals(testData.length, LU.getL().getRowDimension()); 077 assertEquals(testData.length, LU.getL().getColumnDimension()); 078 assertEquals(testData.length, LU.getU().getRowDimension()); 079 assertEquals(testData.length, LU.getU().getColumnDimension()); 080 assertEquals(testData.length, LU.getP().getRowDimension()); 081 assertEquals(testData.length, LU.getP().getColumnDimension()); 082 083 } 084 085 /** test non-square matrix */ 086 public void testNonSquare() { 087 try { 088 new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 089 { Fraction.ZERO, Fraction.ZERO }, 090 { Fraction.ZERO, Fraction.ZERO }, 091 { Fraction.ZERO, Fraction.ZERO } 092 })); 093 } catch (InvalidMatrixException ime) { 094 // expected behavior 095 } catch (Exception e) { 096 fail("wrong exception caught"); 097 } 098 } 099 100 /** test PA = LU */ 101 public void testPAEqualLU() { 102 FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData); 103 FieldLUDecomposition<Fraction> lu = new FieldLUDecompositionImpl<Fraction>(matrix); 104 FieldMatrix<Fraction> l = lu.getL(); 105 FieldMatrix<Fraction> u = lu.getU(); 106 FieldMatrix<Fraction> p = lu.getP(); 107 TestUtils.assertEquals(p.multiply(matrix), l.multiply(u)); 108 109 matrix = new Array2DRowFieldMatrix<Fraction>(testDataMinus); 110 lu = new FieldLUDecompositionImpl<Fraction>(matrix); 111 l = lu.getL(); 112 u = lu.getU(); 113 p = lu.getP(); 114 TestUtils.assertEquals(p.multiply(matrix), l.multiply(u)); 115 116 matrix = new Array2DRowFieldMatrix<Fraction>(FractionField.getInstance(), 17, 17); 117 for (int i = 0; i < matrix.getRowDimension(); ++i) { 118 matrix.setEntry(i, i, Fraction.ONE); 119 } 120 lu = new FieldLUDecompositionImpl<Fraction>(matrix); 121 l = lu.getL(); 122 u = lu.getU(); 123 p = lu.getP(); 124 TestUtils.assertEquals(p.multiply(matrix), l.multiply(u)); 125 126 matrix = new Array2DRowFieldMatrix<Fraction>(singular); 127 lu = new FieldLUDecompositionImpl<Fraction>(matrix); 128 assertFalse(lu.getSolver().isNonSingular()); 129 assertNull(lu.getL()); 130 assertNull(lu.getU()); 131 assertNull(lu.getP()); 132 133 matrix = new Array2DRowFieldMatrix<Fraction>(bigSingular); 134 lu = new FieldLUDecompositionImpl<Fraction>(matrix); 135 assertFalse(lu.getSolver().isNonSingular()); 136 assertNull(lu.getL()); 137 assertNull(lu.getU()); 138 assertNull(lu.getP()); 139 140 } 141 142 /** test that L is lower triangular with unit diagonal */ 143 public void testLLowerTriangular() { 144 FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData); 145 FieldMatrix<Fraction> l = new FieldLUDecompositionImpl<Fraction>(matrix).getL(); 146 for (int i = 0; i < l.getRowDimension(); i++) { 147 assertEquals(Fraction.ONE, l.getEntry(i, i)); 148 for (int j = i + 1; j < l.getColumnDimension(); j++) { 149 assertEquals(Fraction.ZERO, l.getEntry(i, j)); 150 } 151 } 152 } 153 154 /** test that U is upper triangular */ 155 public void testUUpperTriangular() { 156 FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData); 157 FieldMatrix<Fraction> u = new FieldLUDecompositionImpl<Fraction>(matrix).getU(); 158 for (int i = 0; i < u.getRowDimension(); i++) { 159 for (int j = 0; j < i; j++) { 160 assertEquals(Fraction.ZERO, u.getEntry(i, j)); 161 } 162 } 163 } 164 165 /** test that P is a permutation matrix */ 166 public void testPPermutation() { 167 FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData); 168 FieldMatrix<Fraction> p = new FieldLUDecompositionImpl<Fraction>(matrix).getP(); 169 170 FieldMatrix<Fraction> ppT = p.multiply(p.transpose()); 171 FieldMatrix<Fraction> id = 172 new Array2DRowFieldMatrix<Fraction>(FractionField.getInstance(), 173 p.getRowDimension(), p.getRowDimension()); 174 for (int i = 0; i < id.getRowDimension(); ++i) { 175 id.setEntry(i, i, Fraction.ONE); 176 } 177 TestUtils.assertEquals(id, ppT); 178 179 for (int i = 0; i < p.getRowDimension(); i++) { 180 int zeroCount = 0; 181 int oneCount = 0; 182 int otherCount = 0; 183 for (int j = 0; j < p.getColumnDimension(); j++) { 184 final Fraction e = p.getEntry(i, j); 185 if (e.equals(Fraction.ZERO)) { 186 ++zeroCount; 187 } else if (e.equals(Fraction.ONE)) { 188 ++oneCount; 189 } else { 190 ++otherCount; 191 } 192 } 193 assertEquals(p.getColumnDimension() - 1, zeroCount); 194 assertEquals(1, oneCount); 195 assertEquals(0, otherCount); 196 } 197 198 for (int j = 0; j < p.getColumnDimension(); j++) { 199 int zeroCount = 0; 200 int oneCount = 0; 201 int otherCount = 0; 202 for (int i = 0; i < p.getRowDimension(); i++) { 203 final Fraction e = p.getEntry(i, j); 204 if (e.equals(Fraction.ZERO)) { 205 ++zeroCount; 206 } else if (e.equals(Fraction.ONE)) { 207 ++oneCount; 208 } else { 209 ++otherCount; 210 } 211 } 212 assertEquals(p.getRowDimension() - 1, zeroCount); 213 assertEquals(1, oneCount); 214 assertEquals(0, otherCount); 215 } 216 217 } 218 219 220 /** test singular */ 221 public void testSingular() { 222 FieldLUDecomposition<Fraction> lu = 223 new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(testData)); 224 assertTrue(lu.getSolver().isNonSingular()); 225 lu = new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(singular)); 226 assertFalse(lu.getSolver().isNonSingular()); 227 lu = new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(bigSingular)); 228 assertFalse(lu.getSolver().isNonSingular()); 229 } 230 231 /** test matrices values */ 232 public void testMatricesValues1() { 233 FieldLUDecomposition<Fraction> lu = 234 new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(testData)); 235 FieldMatrix<Fraction> lRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 236 { new Fraction(1), new Fraction(0), new Fraction(0) }, 237 { new Fraction(2), new Fraction(1), new Fraction(0) }, 238 { new Fraction(1), new Fraction(-2), new Fraction(1) } 239 }); 240 FieldMatrix<Fraction> uRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 241 { new Fraction(1), new Fraction(2), new Fraction(3) }, 242 { new Fraction(0), new Fraction(1), new Fraction(-3) }, 243 { new Fraction(0), new Fraction(0), new Fraction(-1) } 244 }); 245 FieldMatrix<Fraction> pRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 246 { new Fraction(1), new Fraction(0), new Fraction(0) }, 247 { new Fraction(0), new Fraction(1), new Fraction(0) }, 248 { new Fraction(0), new Fraction(0), new Fraction(1) } 249 }); 250 int[] pivotRef = { 0, 1, 2 }; 251 252 // check values against known references 253 FieldMatrix<Fraction> l = lu.getL(); 254 TestUtils.assertEquals(lRef, l); 255 FieldMatrix<Fraction> u = lu.getU(); 256 TestUtils.assertEquals(uRef, u); 257 FieldMatrix<Fraction> p = lu.getP(); 258 TestUtils.assertEquals(pRef, p); 259 int[] pivot = lu.getPivot(); 260 for (int i = 0; i < pivotRef.length; ++i) { 261 assertEquals(pivotRef[i], pivot[i]); 262 } 263 264 // check the same cached instance is returned the second time 265 assertTrue(l == lu.getL()); 266 assertTrue(u == lu.getU()); 267 assertTrue(p == lu.getP()); 268 269 } 270 271 /** test matrices values */ 272 public void testMatricesValues2() { 273 FieldLUDecomposition<Fraction> lu = 274 new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(luData)); 275 FieldMatrix<Fraction> lRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 276 { new Fraction(1), new Fraction(0), new Fraction(0) }, 277 { new Fraction(3), new Fraction(1), new Fraction(0) }, 278 { new Fraction(1), new Fraction(0), new Fraction(1) } 279 }); 280 FieldMatrix<Fraction> uRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 281 { new Fraction(2), new Fraction(3), new Fraction(3) }, 282 { new Fraction(0), new Fraction(-3), new Fraction(-1) }, 283 { new Fraction(0), new Fraction(0), new Fraction(4) } 284 }); 285 FieldMatrix<Fraction> pRef = new Array2DRowFieldMatrix<Fraction>(new Fraction[][] { 286 { new Fraction(1), new Fraction(0), new Fraction(0) }, 287 { new Fraction(0), new Fraction(0), new Fraction(1) }, 288 { new Fraction(0), new Fraction(1), new Fraction(0) } 289 }); 290 int[] pivotRef = { 0, 2, 1 }; 291 292 // check values against known references 293 FieldMatrix<Fraction> l = lu.getL(); 294 TestUtils.assertEquals(lRef, l); 295 FieldMatrix<Fraction> u = lu.getU(); 296 TestUtils.assertEquals(uRef, u); 297 FieldMatrix<Fraction> p = lu.getP(); 298 TestUtils.assertEquals(pRef, p); 299 int[] pivot = lu.getPivot(); 300 for (int i = 0; i < pivotRef.length; ++i) { 301 assertEquals(pivotRef[i], pivot[i]); 302 } 303 304 // check the same cached instance is returned the second time 305 assertTrue(l == lu.getL()); 306 assertTrue(u == lu.getU()); 307 assertTrue(p == lu.getP()); 308 309 } 310 311 }