Author: luc
Date: Thu Dec 4 07:46:44 2008
New Revision: 723361
URL: http://svn.apache.org/viewvc?rev=723361&view=rev
Log:
added (at least!) a first implementation of singular value decomposition.
JIRA: MATH-157, MATH-220, MATH-233
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
(with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
(with props)
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecomposition.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecomposition.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecomposition.java?rev=723361&r1=723360&r2=723361&view=diff
==============================================================================
---
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecomposition.java
(original)
+++
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecomposition.java
Thu Dec 4 07:46:44 2008
@@ -17,7 +17,6 @@
package org.apache.commons.math.linear;
-import org.apache.commons.math.ConvergenceException;
/**
* An interface to classes that implement an algorithm to calculate the
@@ -34,8 +33,6 @@
* <li><code>solve</code> methods have been added (in the
superinterface),</li>
* <li>a [EMAIL PROTECTED] DecompositionSolver#decompose(RealMatrix)
decompose(RealMatrix)}
* method has been added (in the superinterface),</li>
- * <li>a [EMAIL PROTECTED] #decompose(RealMatrix, int)
decompose(RealMatrix), int)} method
- * has been added,</li>
* <li>a [EMAIL PROTECTED] DecompositionSolver#isNonSingular()
isNonSingular} method has
* been added (in the superinterface),</li>
* <li>a [EMAIL PROTECTED] DecompositionSolver#getInverse() getInverse}
method has been
@@ -55,41 +52,42 @@
public interface SingularValueDecomposition extends DecompositionSolver {
/**
- * Decompose a matrix to find its largest singular values.
- * @param matrix matrix to decompose
- * @param maxSingularValues maximal number of singular values to compute
- * @exception InvalidMatrixException (wrapping a [EMAIL PROTECTED]
ConvergenceException}
- * if algorithm fails to converge
- */
- void decompose(RealMatrix matrix, int maxSingularValues)
- throws InvalidMatrixException;
-
- /**
* Returns the matrix U of the decomposition.
* <p>U is an orthogonal matrix, i.e. its transpose is also its
inverse.</p>
* @return the U matrix
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
+ * @see #getUT()
*/
RealMatrix getU() throws IllegalStateException;
/**
+ * Returns the transpose of the matrix U of the decomposition.
+ * <p>U is an orthogonal matrix, i.e. its transpose is also its
inverse.</p>
+ * @return the U matrix (or null if decomposed matrix is singular)
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
+ * @see #getU()
+ */
+ RealMatrix getUT() throws IllegalStateException;
+
+ /**
* Returns the diagonal matrix Σ of the decomposition.
- * <p>Σ is a diagonal matrix.</p>
+ * <p>Σ is a diagonal matrix. The singular values are provided in
+ * non-increasing order, for compatibility with Jama.</p>
* @return the Σ matrix
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
*/
RealMatrix getS() throws IllegalStateException;
/**
- * Returns the diagonal elements of the matrix Σ of the
decomposition.
+ * Returns the diagonal elements of the matrix Σ of the
decomposition.
+ * <p>The singular values are provided in non-increasing order, for
+ * compatibility with Jama.</p>
* @return the diagonal elements of the Σ matrix
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
*/
double[] getSingularValues() throws IllegalStateException;
@@ -97,30 +95,38 @@
* Returns the matrix V of the decomposition.
* <p>V is an orthogonal matrix, i.e. its transpose is also its
inverse.</p>
* @return the V matrix (or null if decomposed matrix is singular)
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
+ * @see #getVT()
*/
RealMatrix getV() throws IllegalStateException;
/**
+ * Returns the transpose of the matrix V of the decomposition.
+ * <p>V is an orthogonal matrix, i.e. its transpose is also its
inverse.</p>
+ * @return the V matrix (or null if decomposed matrix is singular)
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
+ * @see #getV()
+ */
+ RealMatrix getVT() throws IllegalStateException;
+
+ /**
* Returns the L<sub>2</sub> norm of the matrix.
* <p>The L<sub>2</sub> norm is max(|A × u|<sub>2</sub> /
* |u|<sub>2</sub>), where |.|<sub>2</sub> denotes the vectorial 2-norm
* (i.e. the traditional euclidian norm).</p>
* @return norm
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
*/
double getNorm() throws IllegalStateException;
/**
* Return the condition number of the matrix.
* @return condition number of the matrix
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
*/
double getConditionNumber() throws IllegalStateException;
@@ -131,9 +137,8 @@
* terms is max(m,n) × ulp(s<sub>1</sub>) where ulp(s<sub>1</sub>)
* is the least significant bit of the largest singular value.</p>
* @return effective numerical matrix rank
- * @exception IllegalStateException if neither [EMAIL PROTECTED]
- * DecompositionSolver#decompose(RealMatrix) decompose} nor [EMAIL
PROTECTED]
- * #decompose(RealMatrix, int)} have not been called
+ * @exception IllegalStateException if [EMAIL PROTECTED]
+ * DecompositionSolver#decompose(RealMatrix) decompose} has not been called
*/
int getRank() throws IllegalStateException;
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java?rev=723361&view=auto
==============================================================================
---
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
(added)
+++
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
Thu Dec 4 07:46:44 2008
@@ -0,0 +1,435 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math.linear;
+
+import org.apache.commons.math.ConvergenceException;
+import org.apache.commons.math.MathRuntimeException;
+
+/**
+ * Calculates the Singular Value Decomposition of a matrix.
+ * <p>The Singular Value Decomposition of matrix A is a set of three matrices:
+ * U, Σ and V such that A = U × Σ × V<sup>T</sup>.
+ * Let A be an m × n matrix, then U is an m × m orthogonal matrix,
+ * Σ is a m × n diagonal matrix with positive diagonal elements,
+ * and V is an n × n orthogonal matrix.</p>
+ *
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class SingularValueDecompositionImpl implements
SingularValueDecomposition {
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = -2357152028714378552L;
+
+ /** Number of rows of the initial matrix. */
+ private int m;
+
+ /** Number of columns of the initial matrix. */
+ private int n;
+
+ /** Transformer to bidiagonal. */
+ private BiDiagonalTransformer transformer;
+
+ /** Main diagonal of the bidiagonal matrix. */
+ private double[] mainBidiagonal;
+
+ /** Secondary diagonal of the bidiagonal matrix. */
+ private double[] secondaryBidiagonal;
+
+ /** Main diagonal of the tridiagonal matrix. */
+ double[] mainTridiagonal;
+
+ /** Secondary diagonal of the tridiagonal matrix. */
+ double[] secondaryTridiagonal;
+
+ /** Eigen decomposition of the tridiagonal matrix. */
+ private EigenDecomposition eigenDecomposition;
+
+ /** Singular values. */
+ private double[] singularValues;
+
+ /** Cached value of U. */
+ private RealMatrix cachedU;
+
+ /** Cached value of U<sup>T</sup>. */
+ private RealMatrix cachedUt;
+
+ /** Cached value of S. */
+ private RealMatrix cachedS;
+
+ /** Cached value of V. */
+ private RealMatrix cachedV;
+
+ /** Cached value of V<sup>T</sup>. */
+ private RealMatrix cachedVt;
+
+ /**
+ * Build a new instance.
+ * <p>Note that [EMAIL PROTECTED] #decompose(RealMatrix)}
<strong>must</strong> be called
+ * before any of the [EMAIL PROTECTED] #getU()}, [EMAIL PROTECTED]
#getS()}, [EMAIL PROTECTED] #getV()},
+ * [EMAIL PROTECTED] #getSingularValues()}, [EMAIL PROTECTED] #getNorm()},
[EMAIL PROTECTED] #getConditionNumber()},
+ * [EMAIL PROTECTED] #getRank()}, [EMAIL PROTECTED] #solve(double[])},
[EMAIL PROTECTED] #solve(RealMatrix)},
+ * [EMAIL PROTECTED] #solve(RealVector)} or [EMAIL PROTECTED]
#solve(RealVectorImpl)} methods can be
+ * called.</p>
+ * @see #decompose(RealMatrix)
+ */
+ public SingularValueDecompositionImpl() {
+ }
+
+ /**
+ * Calculates the Singular Value Decomposition of the given matrix.
+ * <p>Calling this constructor is equivalent to first call the no-arguments
+ * constructor and then call [EMAIL PROTECTED] #decompose(RealMatrix)}.</p>
+ * @param matrix The matrix to decompose.
+ * @exception InvalidMatrixException (wrapping a [EMAIL PROTECTED]
ConvergenceException}
+ * if algorithm fails to converge
+ */
+ public SingularValueDecompositionImpl(RealMatrix matrix)
+ throws InvalidMatrixException {
+ decompose(matrix);
+ }
+
+ /** [EMAIL PROTECTED] */
+ public void decompose(final RealMatrix matrix) {
+
+ m = matrix.getRowDimension();
+ n = matrix.getColumnDimension();
+
+ cachedU = null;
+ cachedS = null;
+ cachedV = null;
+ cachedVt = null;
+
+ // transform the matrix to bidiagonal
+ transformer = new BiDiagonalTransformer(matrix);
+ mainBidiagonal = transformer.getMainDiagonalRef();
+ secondaryBidiagonal = transformer.getSecondaryDiagonalRef();
+
+ // compute Bt.B (if upper diagonal) or B.Bt (if lower diagonal)
+ mainTridiagonal = new double[mainBidiagonal.length];
+ secondaryTridiagonal = new double[mainBidiagonal.length - 1];
+ double a = mainBidiagonal[0];
+ mainTridiagonal[0] = a * a;
+ for (int i = 1; i < mainBidiagonal.length; ++i) {
+ final double b = secondaryBidiagonal[i - 1];
+ secondaryTridiagonal[i - 1] = a * b;
+ a = mainBidiagonal[i];
+ mainTridiagonal[i] = a * a + b * b;
+ }
+
+ // compute singular values
+ eigenDecomposition = new EigenDecompositionImpl(mainTridiagonal,
secondaryTridiagonal);
+ singularValues = eigenDecomposition.getEigenvalues();
+ for (int i = 0; i < singularValues.length; ++i) {
+ singularValues[i] = Math.sqrt(singularValues[i]);
+ }
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getU()
+ throws InvalidMatrixException {
+
+ if (cachedU == null) {
+
+ checkDecomposed();
+
+ if (m >= n) {
+ // the tridiagonal matrix is Bt.B, where B is upper bidiagonal
+ final double[][] eData = eigenDecomposition.getV().getData();
+ final double[][] iData = new double[m][];
+ double[] ei1 = eData[0];
+ iData[0] = ei1;
+ for (int i = 0; i < n - 1; ++i) {
+ // compute Bt.E.S^(-1) where E is the eigenvectors matrix
+ // we reuse the array from matrix E to store the result
+ final double[] ei0 = ei1;
+ ei1 = eData[i + 1];
+ iData[i + 1] = ei1;
+ for (int j = 0; j < n; ++j) {
+ ei0[j] = (mainBidiagonal[i] * ei0[j] +
+ secondaryBidiagonal[i] * ei1[j]) /
singularValues[j];
+ }
+ }
+ // last row
+ final double lastMain = mainBidiagonal[n - 1];
+ for (int j = 0; j < n; ++j) {
+ ei1[j] *= lastMain / singularValues[j];
+ }
+ for (int i = n; i < m; ++i) {
+ iData[i] = new double[n];
+ }
+ cachedU =
+ transformer.getU().multiply(new RealMatrixImpl(iData,
false));
+ } else {
+ // the tridiagonal matrix is B.Bt, where B is lower bidiagonal
+ cachedU =
transformer.getU().multiply(eigenDecomposition.getV());
+ }
+
+ }
+
+ // return the cached matrix
+ return cachedU;
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getUT()
+ throws InvalidMatrixException {
+
+ if (cachedUt == null) {
+ cachedUt = getU().transpose();
+ }
+
+ // return the cached matrix
+ return cachedUt;
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getS()
+ throws InvalidMatrixException {
+
+ if (cachedS == null) {
+
+ checkDecomposed();
+
+ final int p = singularValues.length;
+ final double[][] sData = new double[p][p];
+ for (int i = 0; i < p; ++i) {
+ sData[i][i] = singularValues[i];
+ }
+
+ // cache the matrix for subsequent calls
+ cachedS = new RealMatrixImpl(sData, false);
+
+ }
+ return cachedS;
+ }
+
+ /** [EMAIL PROTECTED] */
+ public double[] getSingularValues()
+ throws InvalidMatrixException {
+ checkDecomposed();
+ return singularValues.clone();
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getV()
+ throws InvalidMatrixException {
+
+ if (cachedV == null) {
+
+ checkDecomposed();
+
+ if (m >= n) {
+ // the tridiagonal matrix is Bt.B, where B is upper bidiagonal
+ cachedV =
transformer.getV().multiply(eigenDecomposition.getV());
+ } else {
+ // the tridiagonal matrix is B.Bt, where B is lower bidiagonal
+ final double[][] eData = eigenDecomposition.getV().getData();
+ final double[][] iData = new double[n][];
+ double[] ei1 = eData[0];
+ iData[0] = ei1;
+ for (int i = 0; i < m - 1; ++i) {
+ // compute Bt.E.S^(-1) where E is the eigenvectors matrix
+ // we reuse the array from matrix E to store the result
+ final double[] ei0 = ei1;
+ ei1 = eData[i + 1];
+ iData[i + 1] = ei1;
+ for (int j = 0; j < m; ++j) {
+ ei0[j] = (mainBidiagonal[i] * ei0[j] +
+ secondaryBidiagonal[i] * ei1[j]) /
singularValues[j];
+ }
+ }
+ // last row
+ final double lastMain = mainBidiagonal[m - 1];
+ for (int j = 0; j < m; ++j) {
+ ei1[j] *= lastMain / singularValues[j];
+ }
+ for (int i = m; i < n; ++i) {
+ iData[i] = new double[m];
+ }
+ cachedV =
+ transformer.getV().multiply(new RealMatrixImpl(iData,
false));
+ }
+
+ }
+
+ // return the cached matrix
+ return cachedV;
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getVT()
+ throws InvalidMatrixException {
+
+ if (cachedVt == null) {
+ cachedVt = getV().transpose();
+ }
+
+ // return the cached matrix
+ return cachedVt;
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public double getNorm()
+ throws InvalidMatrixException {
+ checkDecomposed();
+ return singularValues[0];
+ }
+
+ /** [EMAIL PROTECTED] */
+ public double getConditionNumber()
+ throws InvalidMatrixException {
+ checkDecomposed();
+ return singularValues[0] / singularValues[singularValues.length - 1];
+ }
+
+ /** [EMAIL PROTECTED] */
+ public int getRank()
+ throws IllegalStateException {
+
+ checkDecomposed();
+
+ final double threshold = Math.max(m, n) * Math.ulp(singularValues[0]);
+
+ for (int i = singularValues.length - 1; i >= 0; --i) {
+ if (singularValues[i] > threshold) {
+ return i + 1;
+ }
+ }
+ return 0;
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public boolean isNonSingular()
+ throws IllegalStateException {
+ return getRank() == singularValues.length;
+ }
+
+ /** [EMAIL PROTECTED] */
+ public double[] solve(final double[] b)
+ throws IllegalArgumentException, InvalidMatrixException {
+
+ checkDecomposed();
+
+ if (b.length != m) {
+ throw new IllegalArgumentException("constant vector has wrong
length");
+ }
+
+ final double[] w = getUT().operate(b);
+ for (int i = 0; i < singularValues.length; ++i) {
+ final double si = singularValues[i];
+ if (si == 0) {
+ throw new SingularMatrixException();
+ }
+ w[i] /= si;
+ }
+ return getV().operate(w);
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealVector solve(final RealVector b)
+ throws IllegalArgumentException, InvalidMatrixException {
+ try {
+ return solve((RealVectorImpl) b);
+ } catch (ClassCastException cce) {
+
+ checkDecomposed();
+
+ if (b.getDimension() != m) {
+ throw new IllegalArgumentException("constant vector has wrong
length");
+ }
+
+ final RealVector w = getUT().operate(b);
+ for (int i = 0; i < singularValues.length; ++i) {
+ final double si = singularValues[i];
+ if (si == 0) {
+ throw new SingularMatrixException();
+ }
+ w.set(i, w.getEntry(i) / si);
+ }
+ return getV().operate(w);
+
+ }
+ }
+
+ /** Solve the linear equation A × X = B.
+ * <p>The A matrix is implicit here. It is </p>
+ * @param b right-hand side of the equation A × X = B
+ * @return a vector X such that A × X = B
+ * @throws IllegalArgumentException if matrices dimensions don't match
+ * @throws InvalidMatrixException if decomposed matrix is singular
+ */
+ public RealVectorImpl solve(final RealVectorImpl b)
+ throws IllegalArgumentException, InvalidMatrixException {
+ return new RealVectorImpl(solve(b.getDataRef()), false);
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix solve(final RealMatrix b)
+ throws IllegalArgumentException, InvalidMatrixException {
+
+ checkDecomposed();
+
+ if (b.getRowDimension() != m) {
+ throw new IllegalArgumentException("Incorrect row dimension");
+ }
+
+ final RealMatrixImpl w = (RealMatrixImpl) getUT().multiply(b);
+ final double[][] wData = w.getDataRef();
+ for (int i = 0; i < singularValues.length; ++i) {
+ final double si = singularValues[i];
+ if (si == 0) {
+ throw new SingularMatrixException();
+ }
+ final double inv = 1.0 / si;
+ final double[] wi = wData[i];
+ for (int j = 0; j < b.getColumnDimension(); ++j) {
+ wi[j] *= inv;
+ }
+ }
+ return getV().multiply(w);
+
+ }
+
+ /** [EMAIL PROTECTED] */
+ public RealMatrix getInverse()
+ throws IllegalStateException, InvalidMatrixException {
+ checkDecomposed();
+ return
solve(MatrixUtils.createRealIdentityMatrix(singularValues.length));
+ }
+
+ /**
+ * Check if [EMAIL PROTECTED] #decompose(RealMatrix)} has been called.
+ * @exception IllegalStateException if [EMAIL PROTECTED]
#decompose(RealMatrix) decompose}
+ * has not been called
+ */
+ private void checkDecomposed()
+ throws IllegalStateException {
+ if (singularValues == null) {
+ throw MathRuntimeException.createIllegalStateException("no matrix
have been decomposed yet", null);
+ }
+ }
+
+}
Propchange:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/proper/math/trunk/src/java/org/apache/commons/math/linear/SingularValueDecompositionImpl.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=723361&r1=723360&r2=723361&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Thu Dec 4 07:46:44 2008
@@ -78,8 +78,8 @@
</action>
<action dev="luc" type="add" issue="MATH-220">
Added JAMA-like interfaces for eigen/singular problems. The
implementation
- of eigen-decomposition is based on the very quick dqd/dqds algorithms
and some
- parts of the MRRR algorithm. This leads to very fast and accurate
solutions.
+ are based on the very quick dqd/dqds algorithms and some parts of the
MRRR
+ algorithm. This leads to very fast and accurate solutions.
</action>
<action dev="luc" type="add" issue="MATH-220" >
Added JAMA-like interfaces for decomposition algorithms. These
interfaces
Added:
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java?rev=723361&view=auto
==============================================================================
---
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
(added)
+++
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
Thu Dec 4 07:46:44 2008
@@ -0,0 +1,332 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math.linear;
+
+import java.util.Random;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+public class SingularValueDecompositionImplTest extends TestCase {
+
+ private double[][] testSquare = {
+ { 24.0 / 25.0, 43.0 / 25.0 },
+ { 57.0 / 25.0, 24.0 / 25.0 }
+ };
+
+ private double[][] testNonSquare = {
+ { -540.0 / 625.0, 963.0 / 625.0, -216.0 / 625.0 },
+ { -1730.0 / 625.0, -744.0 / 625.0, 1008.0 / 625.0 },
+ { -720.0 / 625.0, 1284.0 / 625.0, -288.0 / 625.0 },
+ { -360.0 / 625.0, 192.0 / 625.0, 1756.0 / 625.0 },
+ };
+
+ private static final double normTolerance = 10e-14;
+
+ public SingularValueDecompositionImplTest(String name) {
+ super(name);
+ }
+
+ public static Test suite() {
+ TestSuite suite = new
TestSuite(SingularValueDecompositionImplTest.class);
+ suite.setName("SingularValueDecompositionImpl Tests");
+ return suite;
+ }
+
+ public void testMoreRows() {
+ final double[] singularValues = { 123.456, 2.3, 1.001, 0.999 };
+ final int rows = singularValues.length + 2;
+ final int columns = singularValues.length;
+ Random r = new Random(15338437322523l);
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(createTestMatrix(r, rows,
columns, singularValues));
+ double[] computedSV = svd.getSingularValues();
+ assertEquals(singularValues.length, computedSV.length);
+ for (int i = 0; i < singularValues.length; ++i) {
+ assertEquals(singularValues[i], computedSV[i], 1.0e-10);
+ }
+ }
+
+ public void testMoreColumns() {
+ final double[] singularValues = { 123.456, 2.3, 1.001, 0.999 };
+ final int rows = singularValues.length;
+ final int columns = singularValues.length + 2;
+ Random r = new Random(732763225836210l);
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(createTestMatrix(r, rows,
columns, singularValues));
+ double[] computedSV = svd.getSingularValues();
+ assertEquals(singularValues.length, computedSV.length);
+ for (int i = 0; i < singularValues.length; ++i) {
+ assertEquals(singularValues[i], computedSV[i], 1.0e-10);
+ }
+ }
+
+ /** test dimensions */
+ public void testDimensions() {
+ RealMatrixImpl matrix = new RealMatrixImpl(testSquare, false);
+ final int m = matrix.getRowDimension();
+ final int n = matrix.getColumnDimension();
+ SingularValueDecomposition svd = new
SingularValueDecompositionImpl(matrix);
+ assertEquals(m, svd.getU().getRowDimension());
+ assertEquals(m, svd.getU().getColumnDimension());
+ assertEquals(m, svd.getS().getColumnDimension());
+ assertEquals(n, svd.getS().getColumnDimension());
+ assertEquals(n, svd.getV().getRowDimension());
+ assertEquals(n, svd.getV().getColumnDimension());
+
+ }
+
+ /** test A = USVt */
+ public void testAEqualUSVt() {
+ checkAEqualUSVt(new RealMatrixImpl(testSquare, false));
+ checkAEqualUSVt(new RealMatrixImpl(testNonSquare, false));
+ checkAEqualUSVt(new RealMatrixImpl(testNonSquare, false).transpose());
+ }
+
+ public void checkAEqualUSVt(final RealMatrix matrix) {
+ SingularValueDecomposition svd = new
SingularValueDecompositionImpl(matrix);
+ RealMatrix u = svd.getU();
+ RealMatrix s = svd.getS();
+ RealMatrix v = svd.getV();
+ double norm =
u.multiply(s).multiply(v.transpose()).subtract(matrix).getNorm();
+ assertEquals(0, norm, normTolerance);
+
+ }
+
+ /** test that U is orthogonal */
+ public void testUOrthogonal() {
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testSquare, false)).getU());
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testNonSquare, false)).getU());
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testNonSquare, false).transpose()).getU());
+ }
+
+ /** test that V is orthogonal */
+ public void testVOrthogonal() {
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testSquare, false)).getV());
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testNonSquare, false)).getV());
+ checkOrthogonal(new SingularValueDecompositionImpl(new
RealMatrixImpl(testNonSquare, false).transpose()).getV());
+ }
+
+ public void checkOrthogonal(final RealMatrix m) {
+ RealMatrix mTm = m.transpose().multiply(m);
+ RealMatrix id =
MatrixUtils.createRealIdentityMatrix(mTm.getRowDimension());
+ assertEquals(0, mTm.subtract(id).getNorm(), normTolerance);
+ }
+
+ /** test solve dimension errors */
+ public void testSolveDimensionErrors() {
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(new RealMatrixImpl(testSquare,
false));
+ RealMatrix b = new RealMatrixImpl(new double[3][2]);
+ try {
+ svd.solve(b);
+ fail("an exception should have been thrown");
+ } catch (IllegalArgumentException iae) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ try {
+ svd.solve(b.getColumn(0));
+ fail("an exception should have been thrown");
+ } catch (IllegalArgumentException iae) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ try {
+ svd.solve(new
RealVectorImplTest.RealVectorTestImpl(b.getColumn(0)));
+ fail("an exception should have been thrown");
+ } catch (IllegalArgumentException iae) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ }
+
+ /** test solve singularity errors */
+ public void testSolveSingularityErrors() {
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(new RealMatrixImpl(new
double[][] {
+ { 1.0,
0.0 },
+ { 0.0,
0.0 }
+ }, false));
+ RealMatrix b = new RealMatrixImpl(new double[2][2]);
+ try {
+ svd.solve(b);
+ fail("an exception should have been thrown");
+ } catch (InvalidMatrixException ime) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ try {
+ svd.solve(b.getColumn(0));
+ fail("an exception should have been thrown");
+ } catch (InvalidMatrixException ime) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ try {
+ svd.solve(b.getColumnVector(0));
+ fail("an exception should have been thrown");
+ } catch (InvalidMatrixException ime) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ try {
+ svd.solve(new
RealVectorImplTest.RealVectorTestImpl(b.getColumn(0)));
+ fail("an exception should have been thrown");
+ } catch (InvalidMatrixException ime) {
+ // expected behavior
+ } catch (Exception e) {
+ fail("wrong exception caught");
+ }
+ }
+
+ /** test solve */
+ public void testSolve() {
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(new RealMatrixImpl(testSquare,
false));
+ RealMatrix b = new RealMatrixImpl(new double[][] {
+ { 1, 2, 3 }, { 0, -5, 1 }
+ });
+ RealMatrix xRef = new RealMatrixImpl(new double[][] {
+ { -8.0 / 25.0, -263.0 / 75.0, -29.0 / 75.0 },
+ { 19.0 / 25.0, 78.0 / 25.0, 49.0 / 25.0 }
+ });
+
+ // using RealMatrix
+ assertEquals(0, svd.solve(b).subtract(xRef).getNorm(), normTolerance);
+
+ // using double[]
+ for (int i = 0; i < b.getColumnDimension(); ++i) {
+ assertEquals(0,
+ new
RealVectorImpl(svd.solve(b.getColumn(i))).subtract(xRef.getColumnVector(i)).getNorm(),
+ 1.0e-13);
+ }
+
+ // using RealMatrixImpl
+ for (int i = 0; i < b.getColumnDimension(); ++i) {
+ assertEquals(0,
+
svd.solve(b.getColumnVector(i)).subtract(xRef.getColumnVector(i)).getNorm(),
+ 1.0e-13);
+ }
+
+ // using RealMatrix with an alternate implementation
+ for (int i = 0; i < b.getColumnDimension(); ++i) {
+ RealVectorImplTest.RealVectorTestImpl v =
+ new RealVectorImplTest.RealVectorTestImpl(b.getColumn(i));
+ assertEquals(0,
+
svd.solve(v).subtract(xRef.getColumnVector(i)).getNorm(),
+ 1.0e-13);
+ }
+
+ }
+
+ /** test matrices values */
+ public void testMatricesValues1() {
+ SingularValueDecomposition svd =
+ new SingularValueDecompositionImpl(new RealMatrixImpl(testSquare,
false));
+ RealMatrix uRef = new RealMatrixImpl(new double[][] {
+ { 3.0 / 5.0, -4.0 / 5.0 },
+ { 4.0 / 5.0, 3.0 / 5.0 }
+ });
+ RealMatrix sRef = new RealMatrixImpl(new double[][] {
+ { 3.0, 0.0 },
+ { 0.0, 1.0 }
+ });
+ RealMatrix vRef = new RealMatrixImpl(new double[][] {
+ { 4.0 / 5.0, 3.0 / 5.0 },
+ { 3.0 / 5.0, -4.0 / 5.0 }
+ });
+
+ // check values against known references
+ RealMatrix u = svd.getU();
+ assertEquals(0, u.subtract(uRef).getNorm(), normTolerance);
+ RealMatrix s = svd.getS();
+ assertEquals(0, s.subtract(sRef).getNorm(), normTolerance);
+ RealMatrix v = svd.getV();
+ assertEquals(0, v.subtract(vRef).getNorm(), normTolerance);
+
+ // check the same cached instance is returned the second time
+ assertTrue(u == svd.getU());
+ assertTrue(s == svd.getS());
+ assertTrue(v == svd.getV());
+
+ }
+
+ /** test matrices values */
+ public void testMatricesValues2() {
+
+ RealMatrix uRef = new RealMatrixImpl(new double[][] {
+ { 0.0 / 5.0, 3.0 / 5.0, 0.0 / 5.0 },
+ { -4.0 / 5.0, 0.0 / 5.0, -3.0 / 5.0 },
+ { 0.0 / 5.0, 4.0 / 5.0, 0.0 / 5.0 },
+ { -3.0 / 5.0, 0.0 / 5.0, 4.0 / 5.0 }
+ });
+ RealMatrix sRef = new RealMatrixImpl(new double[][] {
+ { 4.0, 0.0, 0.0 },
+ { 0.0, 3.0, 0.0 },
+ { 0.0, 0.0, 2.0 }
+ });
+ RealMatrix vRef = new RealMatrixImpl(new double[][] {
+ { 80.0 / 125.0, -60.0 / 125.0, 75.0 / 125.0 },
+ { 24.0 / 125.0, 107.0 / 125.0, 60.0 / 125.0 },
+ { -93.0 / 125.0, -24.0 / 125.0, 80.0 / 125.0 }
+ });
+
+ // check values against known references
+ SingularValueDecomposition svd = new SingularValueDecompositionImpl();
+ svd.decompose(new RealMatrixImpl(testNonSquare, false));
+ RealMatrix u = svd.getU();
+ assertEquals(0, u.subtract(uRef).getNorm(), normTolerance);
+ RealMatrix s = svd.getS();
+ assertEquals(0, s.subtract(sRef).getNorm(), normTolerance);
+ RealMatrix v = svd.getV();
+ assertEquals(0, v.subtract(vRef).getNorm(), normTolerance);
+
+ // check the same cached instance is returned the second time
+ assertTrue(u == svd.getU());
+ assertTrue(s == svd.getS());
+ assertTrue(v == svd.getV());
+
+ }
+
+ /** test condition number */
+ public void testConditionNumber() {
+ SingularValueDecompositionImpl svd =
+ new SingularValueDecompositionImpl(new RealMatrixImpl(testSquare,
false));
+ assertEquals(3.0, svd.getConditionNumber(), 1.0e-15);
+ }
+
+ private RealMatrix createTestMatrix(final Random r, final int rows, final
int columns,
+ final double[] singularValues) {
+ final RealMatrix u =
+ EigenDecompositionImplTest.createOrthogonalMatrix(r, rows);
+ final RealMatrix d =
+ EigenDecompositionImplTest.createDiagonalMatrix(singularValues,
rows, columns);
+ final RealMatrix v =
+ EigenDecompositionImplTest.createOrthogonalMatrix(r, columns);
+ return u.multiply(d).multiply(v);
+ }
+
+}
Propchange:
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
------------------------------------------------------------------------------
svn:executable = *
Propchange:
commons/proper/math/trunk/src/test/org/apache/commons/math/linear/SingularValueDecompositionImplTest.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision