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    }