cern.colt.matrix.linalg
Class LUDecompositionQuick

java.lang.Object
  extended by cern.colt.matrix.linalg.LUDecompositionQuick
All Implemented Interfaces:
java.io.Serializable

public class LUDecompositionQuick
extends java.lang.Object
implements java.io.Serializable

A low level version of LUDecomposition, avoiding unnecessary memory allocation and copying. The input to decompose methods is overriden with the result (LU). The input to solve methods is overriden with the result (X). In addition to LUDecomposition, this class also includes a faster variant of the decomposition, specialized for tridiagonal (and hence also diagonal) matrices, as well as a solver tuned for vectors. Its disadvantage is that it is a bit more difficult to use than LUDecomposition. Thus, you may want to disregard this class and come back later, if a need for speed arises.

An instance of this class remembers the result of its last decomposition. Usage pattern is as follows: Create an instance of this class, call a decompose method, then retrieve the decompositions, determinant, and/or solve as many equation problems as needed. Once another matrix needs to be LU-decomposed, you need not create a new instance of this class. Start again by calling a decompose method, then retrieve the decomposition and/or solve your equations, and so on. In case a LU matrix is already available, call method setLU instead of decompose and proceed with solving et al.

If a matrix shall not be overriden, use matrix.copy() and hand the the copy to methods.

For an m x n matrix A with m >= n, the LU decomposition is an m x n unit lower triangular matrix L, an n x n upper triangular matrix U, and a permutation vector piv of length m so that A(piv,:) = L*U; If m < n, then L is m x m and U is m x n.

The LU decomposition with pivoting always exists, even if the matrix is singular, so the decompose methods will never fail. The primary use of the LU decomposition is in the solution of square systems of simultaneous linear equations. Attempting to solve such a system will throw an exception if isNonsingular() returns false.

See Also:
Serialized Form

Field Summary
protected  Algebra algebra
           
protected  boolean isNonSingular
           
protected  DoubleMatrix2D LU
          Array for internal storage of decomposition.
protected  int[] piv
          Internal storage of pivot vector.
protected  int pivsign
          pivot sign.
protected  int[] work1
           
protected  int[] work2
           
protected  double[] workDouble
           
 
Constructor Summary
LUDecompositionQuick()
          Constructs and returns a new LU Decomposition object with default tolerance 1.0E-9 for singularity detection.
LUDecompositionQuick(double tolerance)
          Constructs and returns a new LU Decomposition object which uses the given tolerance for singularity detection;
 
Method Summary
 void decompose(DoubleMatrix2D A)
          Decomposes matrix A into L and U (in-place).
 void decompose(DoubleMatrix2D A, int semiBandwidth)
          Decomposes the banded and square matrix A into L and U (in-place).
 double det()
          Returns the determinant, det(A).
protected  double[] getDoublePivot()
          Returns pivot permutation vector as a one-dimensional double array
 DoubleMatrix2D getL()
          Returns the lower triangular factor, L.
 DoubleMatrix2D getLU()
          Returns a copy of the combined lower and upper triangular factor, LU.
 int[] getPivot()
          Returns the pivot permutation vector (not a copy of it).
 DoubleMatrix2D getU()
          Returns the upper triangular factor, U.
 boolean isNonsingular()
          Returns whether the matrix is nonsingular (has an inverse).
protected  boolean isNonsingular(DoubleMatrix2D matrix)
          Returns whether the matrix is nonsingular.
protected  DoubleMatrix2D lowerTriangular(DoubleMatrix2D A)
          Modifies the matrix to be a lower triangular matrix.
protected  int m()
           
protected  int n()
           
 void setLU(DoubleMatrix2D LU)
          Sets the combined lower and upper triangular factor, LU.
 void solve(DoubleMatrix1D B)
          Solves the system of equations A*X = B (in-place).
 void solve(DoubleMatrix2D B)
          Solves the system of equations A*X = B (in-place).
 java.lang.String toString()
          Returns a String with (propertyName, propertyValue) pairs.
protected  DoubleMatrix2D upperTriangular(DoubleMatrix2D A)
          Modifies the matrix to be an upper triangular matrix.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

LU

protected DoubleMatrix2D LU
Array for internal storage of decomposition.


pivsign

protected int pivsign
pivot sign.


piv

protected int[] piv
Internal storage of pivot vector.


isNonSingular

protected boolean isNonSingular

algebra

protected Algebra algebra

workDouble

protected transient double[] workDouble

work1

protected transient int[] work1

work2

protected transient int[] work2
Constructor Detail

LUDecompositionQuick

public LUDecompositionQuick()
Constructs and returns a new LU Decomposition object with default tolerance 1.0E-9 for singularity detection.


LUDecompositionQuick

public LUDecompositionQuick(double tolerance)
Constructs and returns a new LU Decomposition object which uses the given tolerance for singularity detection;

Method Detail

decompose

public void decompose(DoubleMatrix2D A)
Decomposes matrix A into L and U (in-place). Upon return A is overridden with the result LU, such that L*U = A. Uses a "left-looking", dot-product, Crout/Doolittle algorithm.

Parameters:
A - any matrix.

decompose

public void decompose(DoubleMatrix2D A,
                      int semiBandwidth)
Decomposes the banded and square matrix A into L and U (in-place). Upon return A is overridden with the result LU, such that L*U = A. Currently supports diagonal and tridiagonal matrices, all other cases fall through to decompose(DoubleMatrix2D).

Parameters:
semiBandwidth - == 1 --> A is diagonal, == 2 --> A is tridiagonal.
A - any matrix.

det

public double det()
Returns the determinant, det(A).

Throws:
java.lang.IllegalArgumentException - if A.rows() != A.columns() (Matrix must be square).

getDoublePivot

protected double[] getDoublePivot()
Returns pivot permutation vector as a one-dimensional double array

Returns:
(double) piv

getL

public DoubleMatrix2D getL()
Returns the lower triangular factor, L.

Returns:
L

getLU

public DoubleMatrix2D getLU()
Returns a copy of the combined lower and upper triangular factor, LU.

Returns:
LU

getPivot

public int[] getPivot()
Returns the pivot permutation vector (not a copy of it).

Returns:
piv

getU

public DoubleMatrix2D getU()
Returns the upper triangular factor, U.

Returns:
U

isNonsingular

public boolean isNonsingular()
Returns whether the matrix is nonsingular (has an inverse).

Returns:
true if U, and hence A, is nonsingular; false otherwise.

isNonsingular

protected boolean isNonsingular(DoubleMatrix2D matrix)
Returns whether the matrix is nonsingular.

Returns:
true if matrix is nonsingular; false otherwise.

lowerTriangular

protected DoubleMatrix2D lowerTriangular(DoubleMatrix2D A)
Modifies the matrix to be a lower triangular matrix.

Examples:

3 x 5 matrix:
9, 9, 9, 9, 9
9, 9, 9, 9, 9
9, 9, 9, 9, 9
triang.Upper
==>
3 x 5 matrix:
9, 9, 9, 9, 9
0, 9, 9, 9, 9
0, 0, 9, 9, 9
5 x 3 matrix:
9, 9, 9
9, 9, 9
9, 9, 9
9, 9, 9
9, 9, 9
triang.Upper
==>
5 x 3 matrix:
9, 9, 9
0, 9, 9
0, 0, 9
0, 0, 0
0, 0, 0
3 x 5 matrix:
9, 9, 9, 9, 9
9, 9, 9, 9, 9
9, 9, 9, 9, 9
triang.Lower
==>
3 x 5 matrix:
1, 0, 0, 0, 0
9, 1, 0, 0, 0
9, 9, 1, 0, 0
5 x 3 matrix:
9, 9, 9
9, 9, 9
9, 9, 9
9, 9, 9
9, 9, 9
triang.Lower
==>
5 x 3 matrix:
1, 0, 0
9, 1, 0
9, 9, 1
9, 9, 9
9, 9, 9

Returns:
A (for convenience only).
See Also:
#triangulateUpper(DoubleMatrix2D)

m

protected int m()

n

protected int n()

setLU

public void setLU(DoubleMatrix2D LU)
Sets the combined lower and upper triangular factor, LU. The parameter is not checked; make sure it is indeed a proper LU decomposition.


solve

public void solve(DoubleMatrix1D B)
Solves the system of equations A*X = B (in-place). Upon return B is overridden with the result X, such that L*U*X = B(piv).

Parameters:
B - A vector with B.size() == A.rows().
Throws:
java.lang.IllegalArgumentException - if B.size() != A.rows().
java.lang.IllegalArgumentException - if A is singular, that is, if !isNonsingular().
java.lang.IllegalArgumentException - if A.rows() < A.columns().

solve

public void solve(DoubleMatrix2D B)
Solves the system of equations A*X = B (in-place). Upon return B is overridden with the result X, such that L*U*X = B(piv,:).

Parameters:
B - A matrix with as many rows as A and any number of columns.
Throws:
java.lang.IllegalArgumentException - if B.rows() != A.rows().
java.lang.IllegalArgumentException - if A is singular, that is, if !isNonsingular().
java.lang.IllegalArgumentException - if A.rows() < A.columns().

toString

public java.lang.String toString()
Returns a String with (propertyName, propertyValue) pairs. Useful for debugging or to quickly get the rough picture. For example,
rank          : 3
trace         : 0

Overrides:
toString in class java.lang.Object

upperTriangular

protected DoubleMatrix2D upperTriangular(DoubleMatrix2D A)
Modifies the matrix to be an upper triangular matrix.

Returns:
A (for convenience only).
See Also:
#triangulateLower(DoubleMatrix2D)