package jsat.linear;

import java.io.Serializable;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.utils.SystemInfo;

/**
 * This class uses the LUP decomposition of a matrix to provide efficient methods for solving A x = b, as well as computing the determinant of A. 
 * @author Edward Raff
 */
public class LUPDecomposition implements Cloneable, Serializable
{

	private static final long serialVersionUID = -149659693838168048L;
	private static final int threads = SystemInfo.LogicalCores;
    private final Matrix L, U, P;

    public LUPDecomposition(Matrix L, Matrix U, Matrix P)
    {
        this.L = L;
        this.U = U;
        this.P = P;
    }

    public LUPDecomposition(Matrix A)
    {
        Matrix[] lup = A.clone().lup();
        L = lup[0];
        U = lup[1];
        P = lup[2];
    }
    
    public LUPDecomposition(Matrix A, ExecutorService threadpool)
    {
        Matrix[] lup = A.clone().lup(threadpool);
        L = lup[0];
        U = lup[1];
        P = lup[2];
    }
    
    /**
     * 
     * @return true if the original matrix A, from which this factorization is from, is a square matrix
     */
    public boolean isSquare()
    {
        return L.isSquare() && U.isSquare();
    }
    
    /**
     * 
     * @return the determinant of the original Matrix A, |A|
     */
    public double det()
    {
        if(!isSquare())
            throw new ArithmeticException("Rectangual matricies do not have a determinat");
        double det = 1;
        
        for(int i = 0; i < Math.min(U.rows(), U.cols()); i++)
            det *= U.get(i, i);
        
        //We need to swap back P to get the sign, so we make a clone. This could be cached if we need to 
        int rowSwaps = 0;
        
        Matrix pCopy = P.clone();
        //The number of row swaps in P is the sign change
        for(int i = 0; i < pCopy.cols(); i++)
            if(pCopy.get(i, i) != 1)
            {
                rowSwaps++;
                //find the row that has our '1'! 
                int j = i+1;
                while(pCopy.get(j, i) == 0)
                    j++;
                
                pCopy.swapRows(i, j);//Dont really care who we swap with, it will work out in the end
            }
        
        
        return rowSwaps % 2 !=0 ? -det : det;
    }
    
    public Vec solve(Vec b)
    {
        //Solve P A x = L U x = P b, for x 
        
        //First solve L y = P b
        Vec y = forwardSub(L, P.multiply(b));
        //Sole U x = y
        Vec x = backSub(U, y);
        
        return x;
    }
    
    public Matrix solve(Matrix B)
    {
        //Solve P A x = L U x = P b, for x 
        
        //First solve L y = P b
        Matrix y = forwardSub(L, P.multiply(B));
        //Sole U x = y
        Matrix x = backSub(U, y);
        
        return x;
    }
    
    public Matrix solve(Matrix B, ExecutorService threadpool)
    {
        //Solve P A x = L U x = P b, for x 
        
        //First solve L y = P b
        Matrix y = forwardSub(L, P.multiply(B), threadpool);
        //Sole U x = y
        Matrix x = backSub(U, y, threadpool);
        
        return x;
    }

    @Override
    public LUPDecomposition clone() 
    {
        return new LUPDecomposition(L.clone(), U.clone(), P.clone());
    }
    
    /**
     * Solves for the vector x such that L x = b
     * 
     * @param L a lower triangular matrix
     * @param b a vector whos length is equal to the rows in L
     * @return x such that L x = b
     */
    public static Vec forwardSub(Matrix L, Vec b)
    {
        if(b.length() != L.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");
        
        Vec y = b instanceof SparseVector ? new SparseVector(b.length()) : new DenseVector(b.length());
        
        for(int i = 0; i < b.length(); i++)
        {
            double y_i = b.get(i);
            for(int j = 0; j < i; j++)
                y_i -= L.get(i, j)*y.get(j);
            y_i /= L.get(i, i);
            
            y.set(i, y_i);
        }
        
        return y;
    }
    
    /**
     * Solves for the matrix x such that L x = b
     * 
     * @param L a lower triangular matrix
     * @param b a matrix with the same number of rows as L
     * @return x such that L x = b
     */
    public static Matrix forwardSub(Matrix L, Matrix b)
    {
        if (b.rows() != L.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");

        Matrix y = new DenseMatrix(b.rows(), b.cols());
        //Store the colum seperatly so that we can access this array in row major order, instead of the matrix in column major (yay cache!)
        double[] y_col_k = new double[b.rows()];
        for (int k = 0; k < b.cols(); k++)
        {
            for (int i = 0; i < b.rows(); i++)//We operate the same as forwardSub(Matrix, Vec), but we aplly each column of B as its own Vec.
            {
                y_col_k[i] = b.get(i, k);
                for (int j = 0; j < i; j++)
                    y_col_k[i] -= L.get(i, j) * y_col_k[j];
                y_col_k[i] /= L.get(i, i);
            }
            
            for(int z = 0; z < y_col_k.length; z++)
                y.set(z, k, y_col_k[z]);
        }

        return y;
    }
    

    /**
     * Solves for the matrix x such that L x = b
     * 
     * @param L a lower triangular matrix
     * @param b a matrix with the same number of rows as L
     * @param threadpool source of threads for the parallel computation 
     * @return x such that L x = b
     */
    public static Matrix forwardSub(final Matrix L, final Matrix b, ExecutorService threadpool)
    {
        if (b.rows() != L.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");

        final CountDownLatch latch = new CountDownLatch(threads);
        
        final Matrix y = new DenseMatrix(b.rows(), b.cols());
        for(int threadNum = 0; threadNum < threads; threadNum++)
        {
            final int threadID = threadNum;
            threadpool.submit(new Runnable() {

                public void run()
                {
                    //Store the colum seperatly so that we can access this array in row major order, instead of the matrix in column major (yay cache!)
                    double[] y_col_k = new double[b.rows()];
                    for (int k = threadID; k < b.cols(); k+=threads)
                    {
                        for (int i = 0; i < b.rows(); i++)//We operate the same as forwardSub(Matrix, Vec), but we aplly each column of B as its own Vec. We sawp the order for better cache use
                        {
                            y_col_k[i] = b.get(i, k);
                            for (int j = 0; j < i; j++)
                                y_col_k[i] -= L.get(i, j) * y_col_k[j];
                            y_col_k[i] /= L.get(i, i);

                            //y.set(i, k, y_i);
                        }

                        for(int z = 0; z < y_col_k.length; z++)
                            y.set(z, k, y_col_k[z]);
                    }
                    latch.countDown();
                }
            });
        }
        try
        {
            latch.await();
        }
        catch (InterruptedException ex)
        {
            Logger.getLogger(LUPDecomposition.class.getName()).log(Level.SEVERE, null, ex);
            return forwardSub(L, b);
        }

        return y;
    }

    /**
     * Solves for the vector x such that U x = y
     * 
     * @param U an upper triangular matrix
     * @param y a vector whos length is equal to the rows in U
     * @return x such that U x = y
     */
    public static Vec backSub(Matrix U, Vec y)
    {
        if (y.length() != U.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");

        Vec x = y instanceof SparseVector ? new SparseVector(U.cols()) : new DenseVector(U.cols());
        
        final int start = Math.min(U.rows(), U.cols())-1;

        for (int i = start; i >= 0; i--)
        {
            double x_i = y.get(i);
            for (int j = i + 1; j <= start; j++)
                x_i -= U.get(i, j) * x.get(j);
            x_i /= U.get(i, i);
            if(Double.isInfinite(x_i))//Occurs when U_(i,i) = 0
                x_i = 0;
            x.set(i, x_i);
        }

        return x;
    }

    /**
     * Solves for the matrix x such that U x = y
     * 
     * @param U an upper triangular matrix
     * @param y a matrix with the same number of rows as U
     * @return x such that U x = y
     */
    public static Matrix backSub(Matrix U, Matrix y)
    {
        if (y.rows() != U.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");

        Matrix x = new DenseMatrix(U.cols(), y.cols());

        double[] x_col_k = new double[y.rows()];
        
        final int start = Math.min(U.rows(), U.cols())-1;
        
        for (int k = 0; k < y.cols(); k++)
        {
            for (int i = start; i >= 0; i--)//We operate the same as forwardSub(Matrix, Vec), but we aplly each column of B as its own Vec.
            {
                x_col_k[i] = y.get(i, k);
                for (int j = i + 1; j <= start; j++)
                    x_col_k[i] -= U.get(i, j) * x_col_k[j];
                x_col_k[i] /= U.get(i, i);
            }
            
            for(int i = 0; i < x_col_k.length; i++)
                if(Double.isInfinite(x_col_k[i]))//Occurs when U_(i,i) = 0
                    x.set(i, k, 0);
                else
                    x.set(i, k, x_col_k[i]);
                
        }

        return x;
    }
    
    /**
     * Solves for the matrix x such that U x = y
     * 
     * @param U an upper triangular matrix
     * @param y a matrix with the same number of rows as U
     * @param threadpool source of threads for the parallel computation 
     * @return x such that U x = y
     */
    public static Matrix backSub(final Matrix U, final Matrix y, ExecutorService threadpool)
    {
        if (y.rows() != U.rows())
            throw new ArithmeticException("Vector and matrix sizes do not agree");

        final Matrix x = new DenseMatrix(U.cols(), y.cols());
        final CountDownLatch latch = new CountDownLatch(threads);
        
        final int start = Math.min(U.rows(), U.cols())-1;

        for (int threadNum = 0; threadNum < threads; threadNum++)
        {
            final int threadID = threadNum;
            threadpool.submit(new Runnable()
            {

                public void run()
                {
                    double[] x_col_k = new double[y.rows()];
                    for (int k = threadID; k < y.cols(); k += threads)
                    {
                        for (int i = start; i >= 0; i--)//We operate the same as forwardSub(Matrix, Vec), but we aplly each column of B as its own Vec.
                        {
                            x_col_k[i] = y.get(i, k);
                            for (int j = i + 1; j <= start; j++)
                                x_col_k[i] -= U.get(i, j) * x_col_k[j];
                            x_col_k[i] /= U.get(i, i);
                        }

                        for (int i = 0; i < x_col_k.length; i++)
                            if(Double.isInfinite(x_col_k[i]))//Occurs when U_(i,i) = 0
                                x.set(i, k, 0);
                            else
                                x.set(i, k, x_col_k[i]);
                    }
                    latch.countDown();
                }
            });
        }
        try
        {
            latch.await();
        }
        catch (InterruptedException ex)
        {
            Logger.getLogger(LUPDecomposition.class.getName()).log(Level.SEVERE, null, ex);
            return backSub(U, y);
        }

        return x;
    }
}

 

Ads help maintain this website.