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 }