View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.math4.legacy.linear;
19  
20  import org.junit.Test;
21  import org.junit.Assert;
22  import org.apache.commons.math4.legacy.TestUtils;
23  import org.apache.commons.math4.legacy.core.dfp.Dfp;
24  
25  public class FieldLUDecompositionTest {
26      private Dfp[][] testData = {
27              { Dfp25.of(1), Dfp25.of(2), Dfp25.of(3)},
28              { Dfp25.of(2), Dfp25.of(5), Dfp25.of(3)},
29              { Dfp25.of(1), Dfp25.of(0), Dfp25.of(8)}
30      };
31      private Dfp[][] testDataMinus = {
32              { Dfp25.of(-1), Dfp25.of(-2), Dfp25.of(-3)},
33              { Dfp25.of(-2), Dfp25.of(-5), Dfp25.of(-3)},
34              { Dfp25.of(-1),  Dfp25.of(0), Dfp25.of(-8)}
35      };
36      private Dfp[][] luData = {
37              { Dfp25.of(2), Dfp25.of(3), Dfp25.of(3) },
38              { Dfp25.of(2), Dfp25.of(3), Dfp25.of(7) },
39              { Dfp25.of(6), Dfp25.of(6), Dfp25.of(8) }
40      };
41  
42      // singular matrices
43      private Dfp[][] singular = {
44              { Dfp25.of(2), Dfp25.of(3) },
45              { Dfp25.of(2), Dfp25.of(3) }
46      };
47      private Dfp[][] bigSingular = {
48              { Dfp25.of(1), Dfp25.of(2),   Dfp25.of(3),    Dfp25.of(4) },
49              { Dfp25.of(2), Dfp25.of(5),   Dfp25.of(3),    Dfp25.of(4) },
50              { Dfp25.of(7), Dfp25.of(3), Dfp25.of(256), Dfp25.of(1930) },
51              { Dfp25.of(3), Dfp25.of(7),   Dfp25.of(6),    Dfp25.of(8) }
52      }; // 4th row = 1st + 2nd
53  
54      /** test dimensions */
55      @Test
56      public void testDimensions() {
57          FieldMatrix<Dfp> matrix =
58              new Array2DRowFieldMatrix<>(Dfp25.getField(), testData);
59          FieldLUDecomposition<Dfp> LU = new FieldLUDecomposition<>(matrix);
60          Assert.assertEquals(testData.length, LU.getL().getRowDimension());
61          Assert.assertEquals(testData.length, LU.getL().getColumnDimension());
62          Assert.assertEquals(testData.length, LU.getU().getRowDimension());
63          Assert.assertEquals(testData.length, LU.getU().getColumnDimension());
64          Assert.assertEquals(testData.length, LU.getP().getRowDimension());
65          Assert.assertEquals(testData.length, LU.getP().getColumnDimension());
66      }
67  
68      /** test non-square matrix */
69      @Test
70      public void testNonSquare() {
71          try {
72              // we don't use Dfp25.getField() for testing purposes
73              new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(new Dfp[][] {
74                      { Dfp25.ZERO, Dfp25.ZERO },
75                      { Dfp25.ZERO, Dfp25.ZERO },
76                      { Dfp25.ZERO, Dfp25.ZERO }
77              }));
78              Assert.fail("Expected NonSquareMatrixException");
79          } catch (NonSquareMatrixException ime) {
80              // expected behavior
81          }
82      }
83  
84      /** test PA = LU */
85      @Test
86      public void testPAEqualLU() {
87          FieldMatrix<Dfp> matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), testData);
88          FieldLUDecomposition<Dfp> lu = new FieldLUDecomposition<>(matrix);
89          FieldMatrix<Dfp> l = lu.getL();
90          FieldMatrix<Dfp> u = lu.getU();
91          FieldMatrix<Dfp> p = lu.getP();
92          TestUtils.assertEquals(p.multiply(matrix), l.multiply(u));
93  
94          matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), testDataMinus);
95          lu = new FieldLUDecomposition<>(matrix);
96          l = lu.getL();
97          u = lu.getU();
98          p = lu.getP();
99          TestUtils.assertEquals(p.multiply(matrix), l.multiply(u));
100 
101         matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), 17, 17);
102         for (int i = 0; i < matrix.getRowDimension(); ++i) {
103             matrix.setEntry(i, i, Dfp25.ONE);
104         }
105         lu = new FieldLUDecomposition<>(matrix);
106         l = lu.getL();
107         u = lu.getU();
108         p = lu.getP();
109         TestUtils.assertEquals(p.multiply(matrix), l.multiply(u));
110 
111         matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), singular);
112         lu = new FieldLUDecomposition<>(matrix);
113         Assert.assertFalse(lu.getSolver().isNonSingular());
114         Assert.assertNull(lu.getL());
115         Assert.assertNull(lu.getU());
116         Assert.assertNull(lu.getP());
117 
118         matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), bigSingular);
119         lu = new FieldLUDecomposition<>(matrix);
120         Assert.assertFalse(lu.getSolver().isNonSingular());
121         Assert.assertNull(lu.getL());
122         Assert.assertNull(lu.getU());
123         Assert.assertNull(lu.getP());
124     }
125 
126     /** test that L is lower triangular with unit diagonal */
127     @Test
128     public void testLLowerTriangular() {
129         FieldMatrix<Dfp> matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), testData);
130         FieldMatrix<Dfp> l = new FieldLUDecomposition<>(matrix).getL();
131         for (int i = 0; i < l.getRowDimension(); i++) {
132             Assert.assertEquals(Dfp25.ONE, l.getEntry(i, i));
133             for (int j = i + 1; j < l.getColumnDimension(); j++) {
134                 Assert.assertEquals(Dfp25.ZERO, l.getEntry(i, j));
135             }
136         }
137     }
138 
139     /** test that U is upper triangular */
140     @Test
141     public void testUUpperTriangular() {
142         FieldMatrix<Dfp> matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), testData);
143         FieldMatrix<Dfp> u = new FieldLUDecomposition<>(matrix).getU();
144         for (int i = 0; i < u.getRowDimension(); i++) {
145             for (int j = 0; j < i; j++) {
146                 Assert.assertEquals(Dfp25.ZERO, u.getEntry(i, j));
147             }
148         }
149     }
150 
151     /** test that P is a permutation matrix */
152     @Test
153     public void testPPermutation() {
154         FieldMatrix<Dfp> matrix = new Array2DRowFieldMatrix<>(Dfp25.getField(), testData);
155         FieldMatrix<Dfp> p   = new FieldLUDecomposition<>(matrix).getP();
156 
157         FieldMatrix<Dfp> ppT = p.multiply(p.transpose());
158         FieldMatrix<Dfp> id  =
159             new Array2DRowFieldMatrix<>(Dfp25.getField(),
160                                           p.getRowDimension(), p.getRowDimension());
161         for (int i = 0; i < id.getRowDimension(); ++i) {
162             id.setEntry(i, i, Dfp25.ONE);
163         }
164         TestUtils.assertEquals(id, ppT);
165 
166         for (int i = 0; i < p.getRowDimension(); i++) {
167             int zeroCount  = 0;
168             int oneCount   = 0;
169             int otherCount = 0;
170             for (int j = 0; j < p.getColumnDimension(); j++) {
171                 final Dfp e = p.getEntry(i, j);
172                 if (e.equals(Dfp25.ZERO)) {
173                     ++zeroCount;
174                 } else if (e.equals(Dfp25.ONE)) {
175                     ++oneCount;
176                 } else {
177                     ++otherCount;
178                 }
179             }
180             Assert.assertEquals(p.getColumnDimension() - 1, zeroCount);
181             Assert.assertEquals(1, oneCount);
182             Assert.assertEquals(0, otherCount);
183         }
184 
185         for (int j = 0; j < p.getColumnDimension(); j++) {
186             int zeroCount  = 0;
187             int oneCount   = 0;
188             int otherCount = 0;
189             for (int i = 0; i < p.getRowDimension(); i++) {
190                 final Dfp e = p.getEntry(i, j);
191                 if (e.equals(Dfp25.ZERO)) {
192                     ++zeroCount;
193                 } else if (e.equals(Dfp25.ONE)) {
194                     ++oneCount;
195                 } else {
196                     ++otherCount;
197                 }
198             }
199             Assert.assertEquals(p.getRowDimension() - 1, zeroCount);
200             Assert.assertEquals(1, oneCount);
201             Assert.assertEquals(0, otherCount);
202         }
203     }
204 
205 
206     /** test singular */
207     @Test
208     public void testSingular() {
209         FieldLUDecomposition<Dfp> lu =
210             new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(Dfp25.getField(), testData));
211         Assert.assertTrue(lu.getSolver().isNonSingular());
212         lu = new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(Dfp25.getField(), singular));
213         Assert.assertFalse(lu.getSolver().isNonSingular());
214         lu = new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(Dfp25.getField(), bigSingular));
215         Assert.assertFalse(lu.getSolver().isNonSingular());
216     }
217 
218     /** test matrices values */
219     @Test
220     public void testMatricesValues1() {
221        FieldLUDecomposition<Dfp> lu =
222             new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(Dfp25.getField(), testData));
223         FieldMatrix<Dfp> lRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
224                 { Dfp25.of(1), Dfp25.of(0), Dfp25.of(0) },
225                 { Dfp25.of(2), Dfp25.of(1), Dfp25.of(0) },
226                 { Dfp25.of(1), Dfp25.of(-2), Dfp25.of(1) }
227         });
228         FieldMatrix<Dfp> uRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
229                 { Dfp25.of(1),  Dfp25.of(2), Dfp25.of(3) },
230                 { Dfp25.of(0), Dfp25.of(1), Dfp25.of(-3) },
231                 { Dfp25.of(0),  Dfp25.of(0), Dfp25.of(-1) }
232         });
233         FieldMatrix<Dfp> pRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
234                 { Dfp25.of(1), Dfp25.of(0), Dfp25.of(0) },
235                 { Dfp25.of(0), Dfp25.of(1), Dfp25.of(0) },
236                 { Dfp25.of(0), Dfp25.of(0), Dfp25.of(1) }
237         });
238         int[] pivotRef = { 0, 1, 2 };
239 
240         // check values against known references
241         FieldMatrix<Dfp> l = lu.getL();
242         TestUtils.assertEquals(lRef, l);
243         FieldMatrix<Dfp> u = lu.getU();
244         TestUtils.assertEquals(uRef, u);
245         FieldMatrix<Dfp> p = lu.getP();
246         TestUtils.assertEquals(pRef, p);
247         int[] pivot = lu.getPivot();
248         for (int i = 0; i < pivotRef.length; ++i) {
249             Assert.assertEquals(pivotRef[i], pivot[i]);
250         }
251 
252         // check the same cached instance is returned the second time
253         Assert.assertSame(l, lu.getL());
254         Assert.assertSame(u, lu.getU());
255         Assert.assertSame(p, lu.getP());
256     }
257 
258     /** test matrices values */
259     @Test
260     public void testMatricesValues2() {
261        FieldLUDecomposition<Dfp> lu =
262             new FieldLUDecomposition<>(new Array2DRowFieldMatrix<>(Dfp25.getField(), luData));
263         FieldMatrix<Dfp> lRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
264                 { Dfp25.of(1), Dfp25.of(0), Dfp25.of(0) },
265                 { Dfp25.of(3), Dfp25.of(1), Dfp25.of(0) },
266                 { Dfp25.of(1), Dfp25.of(0), Dfp25.of(1) }
267         });
268         FieldMatrix<Dfp> uRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
269                 { Dfp25.of(2), Dfp25.of(3), Dfp25.of(3)    },
270                 { Dfp25.of(0), Dfp25.of(-3), Dfp25.of(-1)  },
271                 { Dfp25.of(0), Dfp25.of(0), Dfp25.of(4) }
272         });
273         FieldMatrix<Dfp> pRef = new Array2DRowFieldMatrix<>(Dfp25.getField(), new Dfp[][] {
274                 { Dfp25.of(1), Dfp25.of(0), Dfp25.of(0) },
275                 { Dfp25.of(0), Dfp25.of(0), Dfp25.of(1) },
276                 { Dfp25.of(0), Dfp25.of(1), Dfp25.of(0) }
277         });
278         int[] pivotRef = { 0, 2, 1 };
279 
280         // check values against known references
281         FieldMatrix<Dfp> l = lu.getL();
282         TestUtils.assertEquals(lRef, l);
283         FieldMatrix<Dfp> u = lu.getU();
284         TestUtils.assertEquals(uRef, u);
285         FieldMatrix<Dfp> p = lu.getP();
286         TestUtils.assertEquals(pRef, p);
287         int[] pivot = lu.getPivot();
288         for (int i = 0; i < pivotRef.length; ++i) {
289             Assert.assertEquals(pivotRef[i], pivot[i]);
290         }
291 
292         // check the same cached instance is returned the second time
293         Assert.assertSame(l, lu.getL());
294         Assert.assertSame(u, lu.getU());
295         Assert.assertSame(p, lu.getP());
296     }
297 
298     @Test
299     public void testConstructorWithBigReal() {
300         BigReal[][] leftMatrixData = new BigReal[][]{
301                 {new BigReal(1), new BigReal(0), new BigReal(0), new BigReal(0)},
302                 {new BigReal(1), new BigReal(0), new BigReal(1), new BigReal(0)},
303                 {new BigReal(1), new BigReal(1), new BigReal(0), new BigReal(0)},
304                 {new BigReal(1), new BigReal(1), new BigReal(1), new BigReal(1)},
305         };
306 
307         FieldMatrix<BigReal> matrix = MatrixUtils.createFieldMatrix(leftMatrixData);
308         FieldLUDecomposition<BigReal> lu = new FieldLUDecomposition<>(matrix);
309         Assert.assertEquals(new BigReal(-1), lu.getDeterminant());
310         Assert.assertArrayEquals(new int[]{0, 2, 1, 3}, lu.getPivot());
311     }
312 }