Package com.irurueta.algebra

Class LUDecomposer

java.lang.Object
com.irurueta.algebra.Decomposer
com.irurueta.algebra.LUDecomposer
public class LUDecomposer extends Decomposer
This class allows decomposition of matrices using LU decomposition, which consists on retrieving two triangular matrices (lower triangular and upper triangular) as a decomposition of provided input matrix. In other words, if input matrix is A, then: A = L * U, where L is lower triangular matrix and U is upper triangular matrix. LU decomposition is a useful and fast way of solving systems of linear equations, computing determinants or finding whether a matrix is singular.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final double
    DEFAULT_ROUND_ERROR
    Constant defining default round error when determining singularity of matrices.
    private Matrix
    lu
    Internal matrix containing results of decomposition.
    static final double
    MIN_ROUND_ERROR
    Constant defining minimum allowed round error value when determining singularity of matrices.
    (package private) int[]
    piv
    Internal array containing pivotings after decomposition.
    (package private) int
    pivSign
    Member containing pivot sign after decomposition.

    Fields inherited from class com.irurueta.algebra.Decomposer

    inputMatrix, locked

  • Constructor Summary

    Constructors
    Constructor
    Description
    LUDecomposer()
    Constructor of this class.
    LUDecomposer(Matrix inputMatrix)
    Constructor of this class.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    decompose()
    This method computes LU matrix decomposition, which consists on retrieving two triangular matrices (Lower triangular and Upper triangular) as a decomposition of provided input matrix.
    double
    determinant()
    Returns determinant of provided input matrix using LU decomposition as means to obtain it.
    DecomposerType
    getDecomposerType()
    Returns decomposer type corresponding to LU decomposition
    Matrix
    getL()
    Returns a new matrix instance containing the pivot corrected Lower triangular matrix resulting from LU decomposition for provided input matrix.
    void
    getL(Matrix l)
    Fills provided matrix instance with the pivot corrected Lower triangular matrix resulting from LU decomposition for provided input matrix.
    int[]
    getPivot()
    Returns pivot permutation vector.
    Matrix
    getPivottedL()
    Returns a new matrix instance containing the Lower triangular matrix resulting from LU decomposition before correcting any possible pivots.
    void
    getPivottedL(Matrix pivottedL)
    Fills provided matrix instance with the Lower triangular matrix resulting from LU decomposition before correcting any possible pivots.
    Matrix
    getU()
    Returns a new matrix instance containing the Upper triangular matrix resulting from LU decomposition for provided input matrix.
    void
    getU(Matrix u)
    Fills provided matrix instance with the Upper triangular matrix resulting from LU decomposition for provided input matrix.
    boolean
    isDecompositionAvailable()
    Returns boolean indicating whether decomposition has been computed and results can be retrieved.
    boolean
    isSingular()
    Return boolean indicating whether provided input matrix is singular or not after computing LU decomposition.
    boolean
    isSingular(double roundingError)
    Return boolean indicating whether provided input matrix is singular or not after computing LU decomposition.
    void
    setInputMatrix(Matrix inputMatrix)
    Sets reference to input matrix to be decomposed.
    Matrix
    solve(Matrix b)
    Solves a linear system of equations of the following form: A * X = B.
    Matrix
    solve(Matrix b, double roundingError)
    Solves a linear system of equations of the following form: A * X = B.
    void
    solve(Matrix b, double roundingError, Matrix result)
    Solves a linear system of equations of the following form: A * X = B.
    void
    solve(Matrix b, Matrix result)
    Solves a linear system of equations of the following form: A * X = B.

    Methods inherited from class com.irurueta.algebra.Decomposer

    getInputMatrix, isLocked, isReady

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • DEFAULT_ROUND_ERROR

      public static final double DEFAULT_ROUND_ERROR
      Constant defining default round error when determining singularity of matrices. This value is zero by default.
      See Also:

    • MIN_ROUND_ERROR

      public static final double MIN_ROUND_ERROR
      Constant defining minimum allowed round error value when determining singularity of matrices.
      See Also:

    • lu

      private Matrix lu
      Internal matrix containing results of decomposition.

    • piv

      int[] piv
      Internal array containing pivotings after decomposition.

    • pivSign

      int pivSign
      Member containing pivot sign after decomposition.

  • Constructor Details

    • LUDecomposer

      public LUDecomposer()
      Constructor of this class.

    • LUDecomposer

      public LUDecomposer(Matrix inputMatrix)
      Constructor of this class.
      Parameters:
      inputMatrix - Reference to input matrix to be decomposed

  • Method Details

    • getDecomposerType

      public DecomposerType getDecomposerType()
      Returns decomposer type corresponding to LU decomposition
      Specified by:
      getDecomposerType in class Decomposer
      Returns:
      Decomposer type

    • setInputMatrix

      public void setInputMatrix(Matrix inputMatrix) throws LockedException
      Sets reference to input matrix to be decomposed.
      Overrides:
      setInputMatrix in class Decomposer
      Parameters:
      inputMatrix - Reference to input matrix to be decomposed.
      Throws:
      LockedException - Exception thrown if attempting to call this method while this instance remains locked.

    • isDecompositionAvailable

      public boolean isDecompositionAvailable()
      Returns boolean indicating whether decomposition has been computed and results can be retrieved. Attempting to retrieve decomposition results when not available, will probably raise a NotAvailableException
      Specified by:
      isDecompositionAvailable in class Decomposer
      Returns:
      Boolean indicating whether decomposition has been computed and results can be retrieved.

    • decompose

      public void decompose() throws NotReadyException, LockedException, DecomposerException
      This method computes LU matrix decomposition, which consists on retrieving two triangular matrices (Lower triangular and Upper triangular) as a decomposition of provided input matrix. In other words, if input matrix is A, then: A = L * U Note: During execution of this method, this instance will be locked, and hence attempting to set some parameters might raise a LockedException. Note: After execution of this method, LU decomposition will be available and operations such as retrieving L and U matrices or computing determinants among others will be able to be done. Attempting to call any of such operations before calling this method will raise a NotAvailableException because they require computation of LU decomposition first.
      Specified by:
      decompose in class Decomposer
      Throws:
      NotReadyException - Exception thrown if attempting to call this method when this instance is not ready (i.e. no input matrix has been provided).
      LockedException - Exception thrown if attempting to call this method when this instance is not ready (i.e. no input matrix has been provided).
      DecomposerException - Exception thrown if for any reason decomposition fails while executing, like when convergence of results can not be obtained, etc.

    • isSingular

      public boolean isSingular() throws NotAvailableException, WrongSizeException
      Return boolean indicating whether provided input matrix is singular or not after computing LU decomposition. Returns true if singular and false otherwise. A matrix is defined as singular if its determinant is zero, hence provided input matrix must be square (even though LU decomposition can be computed for non-square matrices), otherwise a WrongSizeException will be raised when calling this method. LU decomposition can be used to avoid determinant computation by means of pivoting, because LU decomposition obtains two triangular matrices, and the determinant of a triangular matrix is just the product of the diagonal elements. Hence, if any element on the diagonal of LU decomposition is zero, determinant will be zero and input matrix will be singular.
      Returns:
      Boolean indicating whether provided input matrix is singular or not.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR)
      See Also:

    • isSingular

      public boolean isSingular(double roundingError) throws NotAvailableException, WrongSizeException
      Return boolean indicating whether provided input matrix is singular or not after computing LU decomposition. Returns true if singular and false otherwise. A matrix is defined as singular if its determinant is zero, hence provided input matrix must be square (even though LU decomposition can be computed for non-square matrices), otherwise a WrongSizeException will be raised when calling this method. LU decomposition can be used to avoid determinant computation by means of pivoting, because LU decomposition obtains two triangular matrices, and the determinant of a triangular matrix is just the product of the diagonal elements. Hence, if any element on the diagonal of LU decomposition is zero, determinant will be zero and input matrix will be singular.
      Parameters:
      roundingError - Determines the amount of margin given to determine whether a matrix is singular or not due to rounding errors. If not provided, by default rounding error is set to zero, but this value can be relaxed if needed.
      Returns:
      Boolean indicating whether provided input matrix is singular or not.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR)
      See Also:

    • getPivottedL

      public void getPivottedL(Matrix pivottedL) throws NotAvailableException
      Fills provided matrix instance with the Lower triangular matrix resulting from LU decomposition before correcting any possible pivots. Hence, this matrix is only ensured to be Lower triangular. In other words, this matrix does not ensure the product A = L * U, to achieve this, we need to apply pivot correction. A pivot corrected version of this matrix can be obtained by calling method getL().
      Parameters:
      pivottedL - Lower triangular matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getPivottedL

      public Matrix getPivottedL() throws NotAvailableException
      Returns a new matrix instance containing the Lower triangular matrix resulting from LU decomposition before correcting any possible pivots. Hence, this matrix is only ensured to be Lower triangular. In other words, this matrix does not ensure the product A = L * U, to achieve this, we need to apply pivot correction. A pivot corrected version of this matrix can be obtained by calling method getL().
      Returns:
      Lower triangular matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getL

      public void getL(Matrix l) throws NotAvailableException
      Fills provided matrix instance with the pivot corrected Lower triangular matrix resulting from LU decomposition for provided input matrix. Since this matrix is pivot corrected, it might not be completely triangular, except for some row pivotting. Notice that LU decomposition obtains matrices in the form of A = L * U, where A is provided input matrix, L is lower triangular matrix and U is upper triangular matrix.
      Parameters:
      l - the Lower triangular matrix resulting from LU decomposition for provided input matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getL

      public Matrix getL() throws NotAvailableException
      Returns a new matrix instance containing the pivot corrected Lower triangular matrix resulting from LU decomposition for provided input matrix. Since this matrix is pivot corrected, it might not be completely triangular, except for some row pivotting. Notice that LU decomposition obtains matrices in the form of A = L * U, where A is provided input matrix, L is lower triangular matrix and U is upper triangular matrix.
      Returns:
      Returns the Lower triangular matrix resulting from LU decomposition for provided input matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getU

      public void getU(Matrix u) throws NotAvailableException
      Fills provided matrix instance with the Upper triangular matrix resulting from LU decomposition for provided input matrix. Notice that LU decomposition obtains matrices in the form A = L * U, where A is provided input matrix, L is lower triangular matrix and U is upper triangular matrix.
      Parameters:
      u - Returns the Upper triangular matrix resulting from LU decomposition for provided input matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getU

      public Matrix getU() throws NotAvailableException
      Returns a new matrix instance containing the Upper triangular matrix resulting from LU decomposition for provided input matrix. Notice that LU decomposition obtains matrices in the form A = L * U, where A is provided input matrix, L is lower triangular matrix and U is upper triangular matrix.
      Returns:
      Returns the Upper triangular matrix resulting from LU decomposition for provided input matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      See Also:

    • getPivot

      public int[] getPivot() throws NotAvailableException
      Returns pivot permutation vector.
      Returns:
      Pivot permutation vector.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.

    • determinant

      public double determinant() throws NotAvailableException, WrongSizeException
      Returns determinant of provided input matrix using LU decomposition as means to obtain it. Provided input matrix must be square (even though LU decomposition can be computed for non-square matrices), otherwise a WrongSizeException will be raised when calling this method. LU decomposition can be used to avoid determinant computation using other slow methods, because LU decomposition obtains two triangular matrices, and the determinant of a triangular matrix is just the product of the diagonal elements. Since the determinant of a matrix product is the product of determinants, then determinant of input matrix can be computed as the product of determinants of L and U. Finally, since L has ones on its diagonal, its determinant will be +-1, depending on the amount of pivots done on L, and determinant of U will be just the product of its diagonal elements.
      Returns:
      Determinant of provided input matrix.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix.
      See Also:

    • solve

      public void solve(Matrix b, Matrix result) throws NotAvailableException, WrongSizeException, SingularMatrixException
      Solves a linear system of equations of the following form: A * X = B. Where A is the input matrix provided for LU decomposition, X is the solution to the system of equations, and B is the parameters vector/matrix. Note: This method can be reused for different b vectors/matrices without having to recompute LU decomposition on the same input matrix. Note: Provided b matrix must have the same number of rows as provided input matrix A, otherwise a WrongSizeException will be raised. Note: Provided input matrix A must be square, otherwise a WrongSizeException will be raised as well. Note: If provided input matrix A is singular, a SingularMatrixException will be thrown. Note: In order to execute this method, an LU decomposition must be available, otherwise a NotAvailableException will be raised. In order to avoid this exception call decompose() method first. Note: DEFAULT_ROUND_ERROR is used as rounding error Note: Solution of linear system of equations is stored in provided result matrix
      Parameters:
      b - Parameters matrix that determine a linear system of equations. Provided matrix must have the same number of rows as provided input matrix for LU decomposition. Besides, each column on parameters matrix will represent a new system of equations, whose solution will be returned on appropriate column as an output of this method.
      result - Matrix containing solution of linear system of equations on each column for each column of provided parameters matrix b.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix; or if provided parameters matrix (b) does not have the same number of rows as input matrix being LU decomposed.
      SingularMatrixException - Exception thrown if provided input matrix to be LU decomposed is singular. In this case linear system of equations cannot be solved.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR).
      See Also:

    • solve

      public void solve(Matrix b, double roundingError, Matrix result) throws NotAvailableException, WrongSizeException, SingularMatrixException
      Solves a linear system of equations of the following form: A * X = B. Where A is the input matrix provided for LU decomposition, X is the solution to the system of equations, and B is the parameters vector/matrix. Note: This method can be reused for different b vectors/matrices without having to recompute LU decomposition on the same input matrix. Note: Provided b matrix must have the same number of rows as provided input matrix A, otherwise a WrongSizeException will be raised. Note: Provided input matrix A must be square, otherwise a WrongSizeException will be raised as well. Note: If provided input matrix A is singular, a SingularMatrixException will be thrown. Note: In order to execute this method, an LU decomposition must be available, otherwise a NotAvailableException will be raised. In order to avoid this exception call decompose() method first. Note: Solution of linear system of equations is stored in provided result matrix
      Parameters:
      b - Parameters matrix that determine a linear system of equations. Provided matrix must have the same number of rows as provided input matrix for LU decomposition. Besides, each column on parameters matrix will represent a new system of equations, whose solution will be returned on appropriate column as an output of this method.
      roundingError - Determines the amount of margin given to determine whether a matrix is singular or not due to rounding errors. If not provided, by default rounding error is set to zero, but this value can be relaxed if needed.
      result - Matrix containing solution of linear system of equations on each column for each column of provided parameters matrix b.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix; or if provided parameters matrix (b) does not have the same number of rows as input matrix being LU decomposed.
      SingularMatrixException - Exception thrown if provided input matrix to be LU decomposed is singular. In this case linear system of equations cannot be solved.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR).
      See Also:

    • solve

      public Matrix solve(Matrix b) throws NotAvailableException, WrongSizeException, SingularMatrixException
      Solves a linear system of equations of the following form: A * X = B. Where A is the input matrix provided for LU decomposition, X is the solution to the system of equations, and B is the parameters vector/matrix. Note: This method can be reused for different b vectors/matrices without having to recompute LU decomposition on the same input matrix. Note: Provided b matrix must have the same number of rows as provided input matrix A, otherwise a WrongSizeException will be raised. Note: Provided input matrix A must be square, otherwise a WrongSizeException will be raised as well. Note: If provided input matrix A is singular, a SingularMatrixException will be thrown. Note: In order to execute this method, an LU decomposition must be available, otherwise a NotAvailableException will be raised. In order to avoid this exception call decompose() method first. Note: DEFAULT_ROUND_ERROR is used as rounding error
      Parameters:
      b - Parameters matrix that determine a linear system of equations. Provided matrix must have the same number of rows as provided input matrix for LU decomposition. Besides, each column on parameters matrix will represent a new system of equations, whose solution will be returned on appropriate column as an output of this method.
      Returns:
      Matrix containing solution of linear system of equations on each column for each column of provided parameters matrix b.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix; or if provided parameters matrix (b) does not have the same number of rows as input matrix being LU decomposed.
      SingularMatrixException - Exception thrown if provided input matrix to be LU decomposed is singular. In this case linear system of equations cannot be solved.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR).
      See Also:

    • solve

      public Matrix solve(Matrix b, double roundingError) throws NotAvailableException, WrongSizeException, SingularMatrixException
      Solves a linear system of equations of the following form: A * X = B. Where A is the input matrix provided for LU decomposition, X is the solution to the system of equations, and B is the parameters vector/matrix. Note: This method can be reused for different b vectors/matrices without having to recompute LU decomposition on the same input matrix. Note: Provided b matrix must have the same number of rows as provided input matrix A, otherwise a WrongSizeException will be raised. Note: Provided input matrix A must be square, otherwise a WrongSizeException will be raised as well. Note: If provided input matrix A is singular, a SingularMatrixException will be thrown. Note: In order to execute this method, an LU decomposition must be available, otherwise a NotAvailableException will be raised. In order to avoid this exception call decompose() method first.
      Parameters:
      b - Parameters matrix that determine a linear system of equations. Provided matrix must have the same number of rows as provided input matrix for LU decomposition. Besides, each column on parameters matrix will represent a new system of equations, whose solution will be returned on appropriate column as an output of this method.
      roundingError - Determines the amount of margin given to determine whether a matrix is singular or not due to rounding errors. If not provided, by default rounding error is set to zero, but this value can be relaxed if needed.
      Returns:
      Matrix containing solution of linear system of equations on each column for each column of provided parameters matrix b.
      Throws:
      NotAvailableException - Exception thrown if attempting to call this method before computing LU decomposition. To avoid this exception call decompose() method first.
      WrongSizeException - Exception thrown if attempting to call this method using a non-square input matrix; or if provided parameters matrix (b) does not have the same number of rows as input matrix being LU decomposed.
      SingularMatrixException - Exception thrown if provided input matrix to be LU decomposed is singular. In this case linear system of equations cannot be solved.
      IllegalArgumentException - Exception thrown if provided rounding error is lower than minimum allowed value (MIN_ROUND_ERROR).
      See Also: