1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 package org.hipparchus.linear;
24
25 import org.hipparchus.exception.LocalizedCoreFormats;
26 import org.hipparchus.exception.MathIllegalArgumentException;
27 import org.hipparchus.fraction.Fraction;
28 import org.junit.Assert;
29 import org.junit.Test;
30
31 public class LUDecompositionTest {
32 private double[][] testData = {
33 { 1.0, 2.0, 3.0},
34 { 2.0, 5.0, 3.0},
35 { 1.0, 0.0, 8.0}
36 };
37 private double[][] testDataMinus = {
38 { -1.0, -2.0, -3.0},
39 { -2.0, -5.0, -3.0},
40 { -1.0, 0.0, -8.0}
41 };
42 private double[][] luData = {
43 { 2.0, 3.0, 3.0 },
44 { 0.0, 5.0, 7.0 },
45 { 6.0, 9.0, 8.0 }
46 };
47
48
49 private double[][] singular = {
50 { 2.0, 3.0 },
51 { 2.0, 3.0 }
52 };
53 private double[][] bigSingular = {
54 { 1.0, 2.0, 3.0, 4.0 },
55 { 2.0, 5.0, 3.0, 4.0 },
56 { 7.0, 3.0, 256.0, 1930.0 },
57 { 3.0, 7.0, 6.0, 8.0 }
58 };
59
60 private static final double entryTolerance = 10e-16;
61
62 private static final double normTolerance = 10e-14;
63
64
65 @Test
66 public void testDimensions() {
67 RealMatrix matrix = MatrixUtils.createRealMatrix(testData);
68 LUDecomposition LU = new LUDecomposition(matrix);
69 Assert.assertEquals(testData.length, LU.getL().getRowDimension());
70 Assert.assertEquals(testData.length, LU.getL().getColumnDimension());
71 Assert.assertEquals(testData.length, LU.getU().getRowDimension());
72 Assert.assertEquals(testData.length, LU.getU().getColumnDimension());
73 Assert.assertEquals(testData.length, LU.getP().getRowDimension());
74 Assert.assertEquals(testData.length, LU.getP().getColumnDimension());
75
76 }
77
78
79 @Test
80 public void testNonSquare() {
81 try {
82 new LUDecomposition(MatrixUtils.createRealMatrix(new double[3][2]));
83 Assert.fail("Expecting MathIllegalArgumentException");
84 } catch (MathIllegalArgumentException ime) {
85 Assert.assertEquals(LocalizedCoreFormats.NON_SQUARE_MATRIX, ime.getSpecifier());
86 }
87 }
88
89
90 @Test
91 public void testPAEqualLU() {
92 RealMatrix matrix = MatrixUtils.createRealMatrix(testData);
93 LUDecomposition lu = new LUDecomposition(matrix);
94 RealMatrix l = lu.getL();
95 RealMatrix u = lu.getU();
96 RealMatrix p = lu.getP();
97 double norm = l.multiply(u).subtract(p.multiply(matrix)).getNorm1();
98 Assert.assertEquals(0, norm, normTolerance);
99
100 matrix = MatrixUtils.createRealMatrix(testDataMinus);
101 lu = new LUDecomposition(matrix);
102 l = lu.getL();
103 u = lu.getU();
104 p = lu.getP();
105 norm = l.multiply(u).subtract(p.multiply(matrix)).getNorm1();
106 Assert.assertEquals(0, norm, normTolerance);
107
108 matrix = MatrixUtils.createRealIdentityMatrix(17);
109 lu = new LUDecomposition(matrix);
110 l = lu.getL();
111 u = lu.getU();
112 p = lu.getP();
113 norm = l.multiply(u).subtract(p.multiply(matrix)).getNorm1();
114 Assert.assertEquals(0, norm, normTolerance);
115
116 matrix = MatrixUtils.createRealMatrix(singular);
117 lu = new LUDecomposition(matrix);
118 Assert.assertFalse(lu.getSolver().isNonSingular());
119 Assert.assertNull(lu.getL());
120 Assert.assertNull(lu.getU());
121 Assert.assertNull(lu.getP());
122
123 matrix = MatrixUtils.createRealMatrix(bigSingular);
124 lu = new LUDecomposition(matrix);
125 Assert.assertFalse(lu.getSolver().isNonSingular());
126 Assert.assertNull(lu.getL());
127 Assert.assertNull(lu.getU());
128 Assert.assertNull(lu.getP());
129
130 }
131
132
133 @Test
134 public void testLLowerTriangular() {
135 RealMatrix matrix = MatrixUtils.createRealMatrix(testData);
136 RealMatrix l = new LUDecomposition(matrix).getL();
137 for (int i = 0; i < l.getRowDimension(); i++) {
138 Assert.assertEquals(l.getEntry(i, i), 1, entryTolerance);
139 for (int j = i + 1; j < l.getColumnDimension(); j++) {
140 Assert.assertEquals(l.getEntry(i, j), 0, entryTolerance);
141 }
142 }
143 }
144
145
146 @Test
147 public void testUUpperTriangular() {
148 RealMatrix matrix = MatrixUtils.createRealMatrix(testData);
149 RealMatrix u = new LUDecomposition(matrix).getU();
150 for (int i = 0; i < u.getRowDimension(); i++) {
151 for (int j = 0; j < i; j++) {
152 Assert.assertEquals(u.getEntry(i, j), 0, entryTolerance);
153 }
154 }
155 }
156
157
158 @Test
159 public void testPPermutation() {
160 RealMatrix matrix = MatrixUtils.createRealMatrix(testData);
161 RealMatrix p = new LUDecomposition(matrix).getP();
162
163 RealMatrix ppT = p.multiplyTransposed(p);
164 RealMatrix id = MatrixUtils.createRealIdentityMatrix(p.getRowDimension());
165 Assert.assertEquals(0, ppT.subtract(id).getNorm1(), normTolerance);
166
167 for (int i = 0; i < p.getRowDimension(); i++) {
168 int zeroCount = 0;
169 int oneCount = 0;
170 int otherCount = 0;
171 for (int j = 0; j < p.getColumnDimension(); j++) {
172 final double e = p.getEntry(i, j);
173 if (e == 0) {
174 ++zeroCount;
175 } else if (e == 1) {
176 ++oneCount;
177 } else {
178 ++otherCount;
179 }
180 }
181 Assert.assertEquals(p.getColumnDimension() - 1, zeroCount);
182 Assert.assertEquals(1, oneCount);
183 Assert.assertEquals(0, otherCount);
184 }
185
186 for (int j = 0; j < p.getColumnDimension(); j++) {
187 int zeroCount = 0;
188 int oneCount = 0;
189 int otherCount = 0;
190 for (int i = 0; i < p.getRowDimension(); i++) {
191 final double e = p.getEntry(i, j);
192 if (e == 0) {
193 ++zeroCount;
194 } else if (e == 1) {
195 ++oneCount;
196 } else {
197 ++otherCount;
198 }
199 }
200 Assert.assertEquals(p.getRowDimension() - 1, zeroCount);
201 Assert.assertEquals(1, oneCount);
202 Assert.assertEquals(0, otherCount);
203 }
204
205 }
206
207
208 @Test
209 public void testSingular() {
210 final RealMatrix m = MatrixUtils.createRealMatrix(testData);
211 LUDecomposition lu = new LUDecomposition(m);
212 Assert.assertTrue(lu.getSolver().isNonSingular());
213 Assert.assertEquals(-1.0, lu.getDeterminant(), 1.0e-15);
214 lu = new LUDecomposition(m.getSubMatrix(0, 1, 0, 1));
215 Assert.assertTrue(lu.getSolver().isNonSingular());
216 Assert.assertEquals(+1.0, lu.getDeterminant(), 1.0e-15);
217 lu = new LUDecomposition(MatrixUtils.createRealMatrix(singular));
218 Assert.assertFalse(lu.getSolver().isNonSingular());
219 Assert.assertEquals(0.0, lu.getDeterminant(), 1.0e-15);
220 lu = new LUDecomposition(MatrixUtils.createRealMatrix(bigSingular));
221 Assert.assertFalse(lu.getSolver().isNonSingular());
222 Assert.assertEquals(0.0, lu.getDeterminant(), 1.0e-15);
223 try {
224 lu.getSolver().solve(new ArrayRealVector(new double[] { 1, 1, 1, 1 }));
225 Assert.fail("an exception should have been thrown");
226 } catch (MathIllegalArgumentException miae) {
227 Assert.assertEquals(LocalizedCoreFormats.SINGULAR_MATRIX, miae.getSpecifier());
228 }
229 }
230
231
232 @Test
233 public void testMatricesValues1() {
234 LUDecomposition lu =
235 new LUDecomposition(MatrixUtils.createRealMatrix(testData));
236 RealMatrix lRef = MatrixUtils.createRealMatrix(new double[][] {
237 { 1.0, 0.0, 0.0 },
238 { 0.5, 1.0, 0.0 },
239 { 0.5, 0.2, 1.0 }
240 });
241 RealMatrix uRef = MatrixUtils.createRealMatrix(new double[][] {
242 { 2.0, 5.0, 3.0 },
243 { 0.0, -2.5, 6.5 },
244 { 0.0, 0.0, 0.2 }
245 });
246 RealMatrix pRef = MatrixUtils.createRealMatrix(new double[][] {
247 { 0.0, 1.0, 0.0 },
248 { 0.0, 0.0, 1.0 },
249 { 1.0, 0.0, 0.0 }
250 });
251 int[] pivotRef = { 1, 2, 0 };
252
253
254 RealMatrix l = lu.getL();
255 Assert.assertEquals(0, l.subtract(lRef).getNorm1(), 1.0e-13);
256 RealMatrix u = lu.getU();
257 Assert.assertEquals(0, u.subtract(uRef).getNorm1(), 1.0e-13);
258 RealMatrix p = lu.getP();
259 Assert.assertEquals(0, p.subtract(pRef).getNorm1(), 1.0e-13);
260 int[] pivot = lu.getPivot();
261 for (int i = 0; i < pivotRef.length; ++i) {
262 Assert.assertEquals(pivotRef[i], pivot[i]);
263 }
264
265
266 Assert.assertTrue(l == lu.getL());
267 Assert.assertTrue(u == lu.getU());
268 Assert.assertTrue(p == lu.getP());
269
270 }
271
272
273 @Test
274 public void testMatricesValues2() {
275 LUDecomposition lu =
276 new LUDecomposition(MatrixUtils.createRealMatrix(luData));
277 RealMatrix lRef = MatrixUtils.createRealMatrix(new double[][] {
278 { 1.0, 0.0, 0.0 },
279 { 0.0, 1.0, 0.0 },
280 { 1.0 / 3.0, 0.0, 1.0 }
281 });
282 RealMatrix uRef = MatrixUtils.createRealMatrix(new double[][] {
283 { 6.0, 9.0, 8.0 },
284 { 0.0, 5.0, 7.0 },
285 { 0.0, 0.0, 1.0 / 3.0 }
286 });
287 RealMatrix pRef = MatrixUtils.createRealMatrix(new double[][] {
288 { 0.0, 0.0, 1.0 },
289 { 0.0, 1.0, 0.0 },
290 { 1.0, 0.0, 0.0 }
291 });
292 int[] pivotRef = { 2, 1, 0 };
293
294
295 RealMatrix l = lu.getL();
296 Assert.assertEquals(0, l.subtract(lRef).getNorm1(), 1.0e-13);
297 RealMatrix u = lu.getU();
298 Assert.assertEquals(0, u.subtract(uRef).getNorm1(), 1.0e-13);
299 RealMatrix p = lu.getP();
300 Assert.assertEquals(0, p.subtract(pRef).getNorm1(), 1.0e-13);
301 int[] pivot = lu.getPivot();
302 for (int i = 0; i < pivotRef.length; ++i) {
303 Assert.assertEquals(pivotRef[i], pivot[i]);
304 }
305
306
307 Assert.assertTrue(l == lu.getL());
308 Assert.assertTrue(u == lu.getU());
309 Assert.assertTrue(p == lu.getP());
310 }
311
312 @Test
313 public void testSolve() {
314 LUDecomposition lu =
315 new LUDecomposition(new Array2DRowRealMatrix(testData));
316 DecompositionSolver solver = lu.getSolver();
317 RealVector solution = solver.solve(new ArrayRealVector(new double[] {
318 new Fraction(1, 2).doubleValue(), new Fraction(2, 3).doubleValue(), new Fraction(3,4).doubleValue()
319 }));
320 Assert.assertEquals(testData.length, solution.getDimension());
321 Assert.assertEquals(new Fraction(-31, 12).doubleValue(), solution.getEntry(0), 1.0e-14);
322 Assert.assertEquals(new Fraction( 11, 12).doubleValue(), solution.getEntry(1), 1.0e-14);
323 Assert.assertEquals(new Fraction( 5, 12).doubleValue(), solution.getEntry(2), 1.0e-14);
324 Assert.assertEquals(testData.length, solver.getRowDimension());
325 Assert.assertEquals(testData[0].length, solver.getColumnDimension());
326 try {
327 solver.solve(new ArrayRealVector(new double[] { 1, 1 }));
328 Assert.fail("an exception should have been thrown");
329 } catch (MathIllegalArgumentException miae) {
330 Assert.assertEquals(LocalizedCoreFormats.DIMENSIONS_MISMATCH, miae.getSpecifier());
331 }
332 }
333
334 }