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.math.linear;
19  
20  import junit.framework.Test;
21  import junit.framework.TestCase;
22  import junit.framework.TestSuite;
23  
24  import org.apache.commons.math.TestUtils;
25  import org.apache.commons.math.fraction.Fraction;
26  import org.apache.commons.math.fraction.FractionField;
27  import org.apache.commons.math.linear.FieldLUDecomposition;
28  import org.apache.commons.math.linear.FieldLUDecompositionImpl;
29  import org.apache.commons.math.linear.FieldMatrix;
30  import org.apache.commons.math.linear.Array2DRowFieldMatrix;
31  import org.apache.commons.math.linear.InvalidMatrixException;
32  
33  public class FieldLUDecompositionImplTest extends TestCase {
34      private Fraction[][] testData = {
35              { new Fraction(1), new Fraction(2), new Fraction(3)},
36              { new Fraction(2), new Fraction(5), new Fraction(3)},
37              { new Fraction(1), new Fraction(0), new Fraction(8)}
38      };
39      private Fraction[][] testDataMinus = {
40              { new Fraction(-1), new Fraction(-2), new Fraction(-3)},
41              { new Fraction(-2), new Fraction(-5), new Fraction(-3)},
42              { new Fraction(-1),  new Fraction(0), new Fraction(-8)}
43      };
44      private Fraction[][] luData = {
45              { new Fraction(2), new Fraction(3), new Fraction(3) },
46              { new Fraction(2), new Fraction(3), new Fraction(7) },
47              { new Fraction(6), new Fraction(6), new Fraction(8) }
48      };
49      
50      // singular matrices
51      private Fraction[][] singular = {
52              { new Fraction(2), new Fraction(3) },
53              { new Fraction(2), new Fraction(3) }
54      };
55      private Fraction[][] bigSingular = {
56              { new Fraction(1), new Fraction(2),   new Fraction(3),    new Fraction(4) },
57              { new Fraction(2), new Fraction(5),   new Fraction(3),    new Fraction(4) },
58              { new Fraction(7), new Fraction(3), new Fraction(256), new Fraction(1930) },
59              { new Fraction(3), new Fraction(7),   new Fraction(6),    new Fraction(8) }
60      }; // 4th row = 1st + 2nd
61  
62      public FieldLUDecompositionImplTest(String name) {
63          super(name);
64      }
65  
66      public static Test suite() {
67          TestSuite suite = new TestSuite(FieldLUDecompositionImplTest.class);
68          suite.setName("FieldLUDecompositionImpl Tests");
69          return suite;
70      }
71  
72      /** test dimensions */
73      public void testDimensions() {
74          FieldMatrix<Fraction> matrix = new Array2DRowFieldMatrix<Fraction>(testData);
75          FieldLUDecomposition<Fraction> LU = new FieldLUDecompositionImpl<Fraction>(matrix);
76          assertEquals(testData.length, LU.getL().getRowDimension());
77          assertEquals(testData.length, LU.getL().getColumnDimension());
78          assertEquals(testData.length, LU.getU().getRowDimension());
79          assertEquals(testData.length, LU.getU().getColumnDimension());
80          assertEquals(testData.length, LU.getP().getRowDimension());
81          assertEquals(testData.length, LU.getP().getColumnDimension());
82  
83      }
84  
85      /** test non-square matrix */
86      public void testNonSquare() {
87          try {
88              new FieldLUDecompositionImpl<Fraction>(new Array2DRowFieldMatrix<Fraction>(new Fraction[][] {
89                      { Fraction.ZERO, Fraction.ZERO },
90                      { Fraction.ZERO, Fraction.ZERO },
91                      { Fraction.ZERO, Fraction.ZERO }
92              }));
93          } catch (InvalidMatrixException ime) {
94              // expected behavior
95          } catch (Exception e) {
96              fail("wrong exception caught");
97          }
98      }
99  
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 }