Package com.imsl.math

Class LU

java.lang.Object
com.imsl.math.LU
All Implemented Interfaces:
Serializable, Cloneable
public class LU extends Object implements Serializable, Cloneable
LU factorization of a matrix of type double.

LU performs an LU factorization of a real general coefficient matrix. The condition method estimates the reciprocal of the \(L_1\) condition number of the matrix. The LU factorization is done using scaled partial pivoting. Scaled partial pivoting differs from partial pivoting in that the pivoting strategy is the same as if each row were scaled to have the same infinity norm.

The \(L_1\) condition number of the matrix A is defined to be \(\kappa(A)=||A||_1 ||A^{-1}||_1\). Since it is expensive to compute \(||A^{-1}||_1\), the condition number is only estimated. The estimation algorithm is the same as used by LINPACK and is described in a paper by Cline et al. (1979).

Note that A is not retained for use by other methods of this class, only the factorization of A is retained. Thus, A is a required parameter to the condition method.

An estimated condition number greater than \(1/\epsilon\) (where \(\epsilon\) is machine precision) indicates that very small changes in A can cause very large changes in the solution x. Iterative refinement can sometimes find the solution to such a system. If there is conern about the input matrix being ill-conditioned, the user of this class should check the condition number of the input matrix using the condition method before using one of the other class methods.

LU fails if U, the upper triangular part of the factorization, has a zero diagonal element. This can occur only if A either is singular or is very close to a singular matrix.

Use the solve method to solve systems of equations. The determinant method can be called to compute the determinant of the coefficient matrix.

LU is based on the LINPACK routine SGECO; see Dongarra et al. (1979). SGECO uses unscaled partial pivoting.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected double[][]
    factor
    This is an n by n matrix containing the LU factorization of the matrix A.
    protected int[]
    ipvt
    Vector of length n containing the pivot sequence for the factorization.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LU(double[][] a)
    Creates the LU factorization of a square matrix of type double.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    condition(double[][] a)
    Return an estimate of the reciprocal of the \(L_1\) condition number of a matrix.
    double
    determinant()
    Return the determinant of the matrix used to construct this instance.
    double[][]
    getL()
    Returns the lower triangular portion of the LU factorization of A.
    double[][]
    getPermutationMatrix()
    Returns the permutation matrix which results from the LU factorization of A.
    double[][]
    getU()
    Returns the unit upper triangular portion of the LU factorization of A.
    double[][]
    inverse()
    Returns the inverse of the matrix used to construct this instance.
    double[]
    solve(double[] b)
    Return the solution x of the linear system Ax = b using the LU factorization of A.
    static double[]
    solve(double[][] a, double[] b)
    Solve Ax = b for x using the LU factorization of A.
    double[]
    solveTranspose(double[] b)
    Return the solution x of the linear system \(A^T = b\).

    Methods inherited from class java.lang.Object

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

  • Field Details

    • factor

      protected double[][] factor
      This is an n by n matrix containing the LU factorization of the matrix A.

    • ipvt

      protected int[] ipvt
      Vector of length n containing the pivot sequence for the factorization.

  • Constructor Details

    • LU

      public LU(double[][] a) throws SingularMatrixException
      Creates the LU factorization of a square matrix of type double.
      Parameters:
      a - the double square matrix to be factored
      Throws:
      IllegalArgumentException - is thrown when the row lengths of input matrix are not equal (for example, the matrix edges are "jagged".)
      SingularMatrixException - is thrown when the input matrix is singular.

  • Method Details

    • getL

      public double[][] getL()
      Returns the lower triangular portion of the LU factorization of A.

      Scaled partial pivoting is used to achieve the LU factorization. The resulting factorization is such that \(AP = LU\), where A is the input matrix a, P is the permutation matrix returned by getPermutationMatrix, L is the lower triangular matrix returned by getL, and U is the unit upper triangular matrix returned by getU.

      Returns:
      a double matrix containing L, the lower triangular portion of the LU factorization of A.

    • getU

      public double[][] getU()
      Returns the unit upper triangular portion of the LU factorization of A.

      Scaled partial pivoting is used to achieve the LU factorization. The resulting factorization is such that \(AP = LU\), where A is the input matrix a, P is the permutation matrix returned by getPermutationMatrix, L is the lower triangular matrix returned by getL, and U is the unit upper triangular matrix returned by getU.

      Returns:
      a double matrix containing U, the unit upper triangular portion of the LU factorization of A.

    • getPermutationMatrix

      public double[][] getPermutationMatrix()
      Returns the permutation matrix which results from the LU factorization of A.

      Scaled partial pivoting is used to achieve the LU factorization. The resulting factorization is such that \(AP = LU\), where A is the input matrix a, P is the permutation matrix returned by getPermutationMatrix, L is the lower triangular matrix returned by getL, and U is the unit upper triangular matrix returned by getU.

      Returns:
      a double matrix containing the permuted identity matrix as a result of the LU factorization of A.

    • solve

      public double[] solve(double[] b)
      Return the solution x of the linear system Ax = b using the LU factorization of A.
      Parameters:
      b - a double array containing the right-hand side of the linear system
      Returns:
      a double array containing the solution to the linear system of equations

    • solveTranspose

      public double[] solveTranspose(double[] b)
      Return the solution x of the linear system \(A^T = b\).
      Parameters:
      b - double array containing the right-hand side of the linear system
      Returns:
      double array containing the solution to the linear system of equations

    • determinant

      public double determinant()
      Return the determinant of the matrix used to construct this instance.
      Returns:
      a double scalar containing the determinant of the matrix used to construct this instance

    • solve

      public static double[] solve(double[][] a, double[] b) throws SingularMatrixException
      Solve Ax = b for x using the LU factorization of A.
      Parameters:
      a - a double square matrix
      b - a double column vector
      Returns:
      a double column vector containing the solution to the linear system of equations
      Throws:
      IllegalArgumentException - This exception is thrown when (1) the lengths of the rows of the input matrix are not uniform, and (2) the number of rows in the input matrix is not equal to the number of elements in x.
      SingularMatrixException - is thrown when the matrix is singular.

    • inverse

      public double[][] inverse()
      Returns the inverse of the matrix used to construct this instance.
      Returns:
      a double matrix representing the inverse of the matrix used to construct this instance

    • condition

      public double condition(double[][] a)
      Return an estimate of the reciprocal of the \(L_1\) condition number of a matrix.
      Parameters:
      a - the double square matrix for which the reciprocal of the \(L_1\) condition number is desired
      Returns:
      a double value representing an estimate of the reciprocal of the \(L_1\) condition number of the matrix