package jsat.linear;
import java.io.Serializable;
import java.util.concurrent.ExecutorService;
import static java.lang.Math.*;
import java.util.concurrent.CountDownLatch;
import java.util.logging.Level;
import java.util.logging.Logger;
import static jsat.linear.LUPDecomposition.*;
import jsat.utils.SystemInfo;
/**
* The Cholesky Decomposition factors a symmetric positive definite matrix A
* into the form A = L LT. The Cholesky Decomposition of a matrix is
* unique.
*
* @author Edward Raff
*/
public class CholeskyDecomposition implements Serializable
{
//TODO add block decomposition for efficency
private static final long serialVersionUID = 8925094456733750112L;
/**
* Contains the matrix 'L', but instead of just keeping the lower triangular, we keep it
* in a symmetric copy so {@link LUPDecomposition#forwardSub(jsat.linear.Matrix, jsat.linear.Vec) }
* and backSub can be done without copying.
*/
private Matrix L;
/**
* Computes the Cholesky Decomposition of the matrix A. The matrix
* A will be altered to form the decomposition L. If A is
* still needed after this computation a {@link Matrix#clone() clone} of the
* matrix should be given instead.
* NOTE: No check for the symmetric positive definite property will occur.
* The results of passing a matrix that does not meet this properties is
* undefined.
*
* @param A the matrix to create the Cholesky Decomposition of
*/
public CholeskyDecomposition(final Matrix A)
{
if(!A.isSquare())
throw new ArithmeticException("Input matrix must be symmetric positive definite");
L = A;
final int ROWS = A.rows();
for (int j = 0; j < ROWS; j++)
{
double L_jj = computeLJJ(A, j);
L.set(j, j, L_jj);
updateRows(j, j + 1, ROWS, 1, A, L_jj);
}
copyUpperToLower(ROWS);
}
/**
* Computes the Cholesky Decomposition of the matrix A. The matrix
* A will be altered to form the decomposition L. If A is
* still needed after this computation a {@link Matrix#clone() clone} of the
* matrix should be given instead.
* NOTE: No check for the symmetric positive definite property will occur.
* The results of passing a matrix that does not meet this properties is
* undefined.
*
* @param A the matrix to create the Cholesky Decomposition of
* @param threadpool the source of threads for computation
*/
public CholeskyDecomposition(final Matrix A, ExecutorService threadpool)
{
if(!A.isSquare())
throw new ArithmeticException("Input matrix must be symmetric positive definite");
L = A;
final int ROWS = A.rows();
double nextLJJ = computeLJJ(A, 0);
for (int j = 0; j < ROWS; j++)
{
final int J = j;
final double L_jj = nextLJJ;//computeLJJ(A, j);
L.set(j, j, L_jj);
final CountDownLatch latch = new CountDownLatch(SystemInfo.LogicalCores-1);
for (int i = 1; i < SystemInfo.LogicalCores; i++)
{
final int ID = i;
threadpool.submit(new Runnable()
{
@Override
public void run()
{
updateRows(J, J + 1+ID, ROWS, SystemInfo.LogicalCores, A, L_jj);
latch.countDown();
}
});
}
try
{
updateRows(J, J+1, ROWS, SystemInfo.LogicalCores, A, L_jj);
if(j+1 < ROWS)
nextLJJ = computeLJJ(A, j+1);
latch.await();
}
catch (InterruptedException ex)
{
Logger.getLogger(CholeskyDecomposition.class.getName()).log(Level.SEVERE, null, ex);
}
}
copyUpperToLower(ROWS);
}
/**
* The Cholesky Decomposition computes the factorization A = L LT. This method returns LT
* @return The upper triangular matrix LT
*/
public Matrix getLT()
{
Matrix LT = new DenseMatrix(L.rows(), L.cols());
for(int i = 0; i < L.rows(); i++)
for(int j = i; j < L.rows(); j++)
LT.set(i, j, L.get(i, j));
return LT;
}
/**
* Solves the linear system of equations A x = b
* @param b the vectors of values
* @return the vector x such that A x = b
*/
public Vec solve(Vec b)
{
//Solve A x = L L^T x = b, for x
//First solve L y = b
Vec y = forwardSub(L, b);
//Sole L^T x = y
Vec x = backSub(L, y);
return x;
}
/**
* Solves the linear system of equations A x = B
* @param B the matrix of values
* @return the matrix c such that A x = B
*/
public Matrix solve(Matrix B)
{
//Solve A x = L L^T x = b, for x
//First solve L y = b
Matrix y = forwardSub(L, B);
//Sole L^T x = y
Matrix x = backSub(L, y);
return x;
}
/**
* Solves the linear system of equations A x = B
* @param B the matrix of values
* @param threadpool the source of threads for parallel evaluation
* @return the matrix c such that A x = B
*/
public Matrix solve(Matrix B, ExecutorService threadpool)
{
//Solve A x = L L^T x = b, for x
//First solve L y = b
Matrix y = forwardSub(L, B, threadpool);
//Sole L^T x = y
Matrix x = backSub(L, y, threadpool);
return x;
}
/**
* Computes the determinant of A
* @return the determinant of A
*/
public double getDet()
{
double det = 1;
for(int i = 0; i < L.rows(); i++)
det *= L.get(i, i);
return det;
}
private double computeLJJ(final Matrix A, final int j)
{
/**
* _________________
* / j - 1
* / =====
* / \ 2
* L = / A - > L
* j j / j j / j k
* / =====
* \/ k = 1
*/
double L_jj = A.get(j, j);
for(int k = 0; k < j; k++)
L_jj -= pow(L.get(j, k), 2);
final double result = sqrt(L_jj);
if(Double.isNaN(result))
throw new ArithmeticException("input matrix is not positive definite");
return result;
}
private void updateRows(final int j, final int start, final int end, final int skip, final Matrix A, final double L_jj)
{
/*
*
* / j - 1 \
* | ===== |
* 1 | \ |
* L = ---- |A - > L L |
* i j L | i j / i k j k|
* j j | ===== |
* \ k = 1 /
*/
for(int i = start; i < end; i+=skip)
{
double L_ij = A.get(i, j);
for(int k = 0; k < j; k++)
L_ij -= L.get(i, k)*L.get(j, k);
L.set(i, j, L_ij/L_jj);
}
}
private void copyUpperToLower(final int ROWS)
{
//Now copy so that All of L is filled
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < i; j++)
L.set(j, i, L.get(i, j));
}
}
Ads help maintain this website.