Class ExactSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>

java.lang.Object
org.flag4j.linalg.solvers.exact.ExactSolver<T,U>
Type Parameters:
T - The type of the coefficient matrix in the linear system.
U - The type of vector in the linear system.
All Implemented Interfaces:
LinearMatrixSolver<T,U>, LinearSolver<T>
Direct Known Subclasses:
ComplexExactSolver, RealExactSolver

public abstract class ExactSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>> extends Object implements LinearMatrixSolver<T,U>

Solves a well determined system of equations \( Ax = b \) or \( AX = B \) in an exact sense.

If the system is not well determined, i.e. \( A \) is not square or not full rank, then use a least-squares solver.

Usage:

A single system may be solved by calling either solve(MatrixMixin, VectorMixin) or solve(MatrixMixin, VectorMixin).

Instances of this solver may also be used to efficiently solve many systems of the form \( Ax = b \) or \( AX = B \) for the same coefficient matrix \( A \) but numerous constant vectors/matrices \( b \) or \( B \). To do this, the workflow would be as follows:

  1. Create a concrete instance of LinearMatrixSolver.
  2. Call decompse(A) once on the coefficient matrix \( A \).
  3. Call solve(b) or solve(B) as many times as needed to solve each system for with the various \( b \) vectors and/or \( B \) matrices.
Note: Any call made to one of the following methods after a call to decompse(A) will override the coefficient matrix set that call:

Specialized solvers are provided for inversion using solveIdentity(MatrixMixin). This should be preferred over calling on of the other solve methods and providing an identity matrix explicitly.

Implementation Notes:

The
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final BackSolver<T,U,?>
    Backwards solver for solving system with upper triangular coefficient matrix.
    protected final ForwardSolver<T,U,?>
    Forward Solver for solving system with lower triangular coefficient matrix.
    protected final LU<T>
    Decomposer to compute LU decomposition.
    protected T
    The unit-lower and upper triangular matrices from the LU decomposition stored in a single matrix.
    Row permutation matrix for LU decomposition.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    ExactSolver(LU<T> lu, ForwardSolver<T,U,?> forwardSolver, BackSolver<T,U,?> backSolver)
    Constructs an exact LU solver with a specified LU decomposer.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Decomposes a matrix \( A \) using an LU decomposition.
    protected abstract T
    Permute the rows of a matrix using the row permutation matrix from the LU decomposition.
    protected abstract U
    Permute the rows of a vector using the row permutation matrix from the LU decomposition.
    solve(T B)
    Solves the set of linear system of equations given by \( AX = B \) for the matrix \( X \).
    solve(T A, T B)
    Solves the set of linear system of equations given by \( AX = B \) for the matrix \( X \).
    solve(T A, U b)
    Solves the linear system of equations given by \( Ax = b \) for the vector \( x \).
    solve(U b)
    Solves the linear system of equations given by \( Ax = b \) for the vector \( x \).
    Solves the set of linear system of equations given by \( AX = I \) for the matrix \( x \) where I is the identity matrix of the appropriate size.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • forwardSolver

      protected final ForwardSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>,?> forwardSolver
      Forward Solver for solving system with lower triangular coefficient matrix.
    • backSolver

      protected final BackSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>,?> backSolver
      Backwards solver for solving system with upper triangular coefficient matrix.
    • lu

      protected final LU<T extends MatrixMixin<T,?,U,?>> lu
      Decomposer to compute LU decomposition.
    • LU

      protected T extends MatrixMixin<T,?,U,?> LU
      The unit-lower and upper triangular matrices from the LU decomposition stored in a single matrix.
    • rowPermute

      protected PermutationMatrix rowPermute
      Row permutation matrix for LU decomposition.
  • Constructor Details

    • ExactSolver

      protected ExactSolver(LU<T> lu, ForwardSolver<T,U,?> forwardSolver, BackSolver<T,U,?> backSolver)
      Constructs an exact LU solver with a specified LU decomposer.
      Parameters:
      lu - LU decomposer to employ in solving the linear system.
      forwardSolver - Solver to use when solving \( Ly = b \) or \( LY = B \).
      backSolver - Solver to use when solving \( Ly = b \) or \( LY = B \).
      Throws:
      IllegalArgumentException - If the LU decomposer does not use partial pivoting.
  • Method Details

    • decompose

      public void decompose(T A)
      Decomposes a matrix \( A \) using an LU decomposition. This decomposition is then used by solve(VectorMixin) and solve(MatrixMixin) to efficiently solve the systems \( Ax = b \) and \( AX = B \) respectively.

      Note: Any subsequent call to solve(MatrixMixin, VectorMixin) or solve(MatrixMixin, MatrixMixin) after a call to this method will override the coefficient matrix.

      This is useful, and more efficient than solve(MatrixMixin, VectorMixin) and solve(MatrixMixin, MatrixMixin), if you need to solve multiple systems of this form for the same \( A \) but numerous \( b \)'s or \( B \)'s that may not all be available at the same time.

      Parameters:
      A - Matrix to decompose.
    • solve

      public U solve(U b)

      Solves the linear system of equations given by \( Ax = b \) for the vector \( x \). The system must be well determined.

      Parameters:
      b - Vector of constants, \( b \), in the linear system.
      Returns:
      The solution to \( x \) in the linear system \( Ax = b \) for the last \( A \) passed to decompose(MatrixMixin).
      Throws:
      IllegalStateException - If no coefficient matrix has been specified for this solver by first calling one of the following:
    • solve

      public T solve(T B)

      Solves the set of linear system of equations given by \( AX = B \) for the matrix \( X \).

      Parameters:
      B - Matrix of constants, \( B \), in the linear system.
      Throws:
      IllegalStateException - If no coefficient matrix has been specified for this solver by first calling one of the following:
    • solve

      public U solve(T A, U b)

      Solves the linear system of equations given by \( Ax = b \) for the vector \( x \). The system must be well determined.

      Note: Any call of this method will override the coefficient matrix specified in any previous calls to decompose(MatrixMixin) on the same solver instance.

      Specified by:
      solve in interface LinearMatrixSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>
      Parameters:
      A - Coefficient matrix, \( A \), in the linear system. Must be square and have full rank (i.e. all rows, or equivalently columns, must be linearly independent).
      b - Vector of constants, \( b \), in the linear system.
      Returns:
      The solution to \( x \) in the linear system \( Ax = b \).
      Throws:
      IllegalArgumentException - If the number of columns in A is not equal to the number of data in b.
      IllegalArgumentException - If A is not square.
      SingularMatrixException - If A is singular.
    • solve

      public T solve(T A, T B)

      Solves the set of linear system of equations given by \( AX = B \) for the matrix \( X \).

      Note: Any call of this method will override the coefficient matrix specified in any previous calls to decompose(MatrixMixin) on the same solver instance.

      Specified by:
      solve in interface LinearMatrixSolver<T extends MatrixMixin<T,?,U,?>,U extends VectorMixin<U,T,?,?>>
      Specified by:
      solve in interface LinearSolver<T extends MatrixMixin<T,?,U,?>>
      Parameters:
      A - Coefficient matrix, \( A \), in the linear system. Must be square and have full rank (i.e. all rows, or equivalently columns, must be linearly independent).
      B - Matrix of constants, \( B \), in the linear system.
      Returns:
      The solution to \( x \) in the linear system \( AX = B \).
      Throws:
      IllegalArgumentException - If the number of columns in A is not equal to the number of rows in B.
      IllegalArgumentException - If A is not square.
      SingularMatrixException - If A is singular.
    • solveIdentity

      public T solveIdentity(T A)
      Solves the set of linear system of equations given by \( AX = I \) for the matrix \( x \) where I is the identity matrix of the appropriate size. Thus, \( X = A^{-1} \) meaning this method computes the inverse of \( A \).

      This method should be preferred over solve(A, Matrix.I(A.shape)) or solve(A, CMatrix.I(A.shape)) as it uses specialized solvers that take advantage of the structure of the identity matrix.

      Parameters:
      A - Coefficient matrix in the linear system.
      Returns:
      The solution to \( x \) in the linear system \( AX = I \).
      Throws:
      IllegalArgumentException - If A is not square.
      SingularMatrixException - If A is singular.
    • permuteRows

      protected abstract U permuteRows(U b)
      Permute the rows of a vector using the row permutation matrix from the LU decomposition.
      Parameters:
      b - Vector to permute the rows of.
      Returns:
      A vector which is the result of applying the row permutation from the LU decomposition to the vector b.
    • permuteRows

      protected abstract T permuteRows(T B)
      Permute the rows of a matrix using the row permutation matrix from the LU decomposition.
      Parameters:
      B - matrix to permute the rows of.
      Returns:
      A matrix which is the result of applying the row permutation from the LU decomposition to the matrix B.