Class Balancer<T extends MatrixMixin<T,?,?,?>>

java.lang.Object
org.flag4j.linalg.decompositions.balance.Balancer<T>
Type Parameters:
T - The type of matrix being balanced.
All Implemented Interfaces:
Decomposition<T>
Direct Known Subclasses:
ComplexBalancer, RealBalancer
public abstract class Balancer<T extends MatrixMixin<T,?,?,?>> extends Object implements Decomposition<T>

Base class for all decompositions which implement matrix balancing. Balancing a matrix involves computing a diagonal similarity transformation to "balance" the rows and columns of the matrix. This balancing is achieved by attempting to scale the entries of the matrix by similarity transformations such that the 1-norms of corresponding rows and columns have the similar 1-norms. Rows and columns may also be permuted during balancing if requested.

Balancing is often used as a preprocessing step to improve the conditioning of eigenvalue problems. Because the balancing transformation is a similarity transformation, the eigenvalues are preserved. Further, when permutations are done during balancing it is possible to isolate decoupled eigenvalues.

The similarity transformation of a square matrix A into the balanced matrix B can be described as: 

     B = T-1 A T
       = D-1 P-1 A P D.
Solving for A, balancing may be viewed as the following decomposition: 
     A = T B T-1
       = P D B D-1 P-1.
Where P is a permutation matrix, and D is a diagonal scaling matrix.

When permutations are used during balancing we obtain a specific form. First, 

             [ T1  X   Y  ]
   P-1 A P = [  0  B1  Z  ]
             [  0  0   T2 ]
Where T1 and T2 are upper triangular matrices whose eigenvalues lie along the diagonal. These are also eigenvalues of A. Then, if scaling is applied we obtain: 
                  [ T1     X*D1       Y    ]
   D-1 P-1 A P D = [  0  D1-1*B*1D1  D1-1*Z  ]
                  [  0      0         T2   ]
Where D1 is a diagonal matrix such that, 
         [ I1 0  0  ]
     D = [ 0  D1 0  ]
         [ 0  0  I2 ]
Where I1 and I2 are identity matrices with equivalent shapes to T1 and T2.

Once balancing has been applied, one need only compute the eigenvalues of B1 and combine them with the diagonal entries of T1 and T2 to obtain all eigenvalues of A.

The code in this class if heavily based on LAPACK's reference implementations of xGEBAL (v 3.12.1).

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected T
    balancedMatrix
    Stores the balanced matrix.
    protected boolean
    doPermutations
    Flag indicating if permutations should be done during balancing.
    protected boolean
    doScaling
    Flag indicating if scaling should be done during balancing.
    protected int
    iHigh
    Tracks the ending row/column index of the un-permuted submatrix to be balanced (exclusive).
    protected int
    iLow
    Tracks the starting row/column index of the un-permuted submatrix to be balanced (inclusive).
    final boolean
    inPlace
    Flag indicating if the balancing should be done in-place or if a copy should be made.
    protected double[]
    scalePerm
    Stores both the scaling and permutation information for the balanced matrix.
    protected int
    size
    This size of the matrix to be balanced.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Balancer(boolean doPermutations, boolean doScaling, boolean inPlace)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    Balancer<T>
    decompose(T src)
    Balances a matrix so that the rows and columns have roughly similar sized norms.
    protected void
    doIterativePermutations()
    Performs the permutation step of matrix balancing.
    protected void
    doIterativeScaling()
    Performs the scaling step of matrix balancing.
    T
    getB()
    Gets the full balanced matrix, B, for the last matrix balanced by this balancer.
    T
    getBSubMatrix()
    Gets the sub-matrix B1 of the full balanced matrix which did not isolate eigenvalues.
    Matrix
    getD()
    Gets the diagonal scaling factors for the last matrix balanced by this balancer.
    Matrix
    getD(boolean full)
    Gets the diagonal scaling matrix for the last matrix balanced by this balancer.
    int
    getIHigh()
    Gets the starting index (exclusive) for the sub-matrix B1 of the balanced matrix which did not isolate eigenvalues.
    int
    getILow()
    Gets the starting index (inclusive) for the sub-matrix B1 of the balanced matrix which did not isolate eigenvalues.
    PermutationMatrix
    getP()
    Gets the permutation matrix for the last matrix balanced by this balancer.
    double[]
    getScalePerm()
    Gets the raw scaling factors and permutation data stored in a single array.
    Matrix
    getT()
    Get the combined permutation and diagonal scaling matrix, T, from the last matrix balanced.
    protected abstract boolean
    isZero(int idx)
    Checks if a value within balancedMatrix is zero.
    protected abstract void
    swapCols(int colIdx1, int colIdx2, int start, int stop)
    Swaps two columns, over a specified range, within the balancedMatrix matrix.
    protected abstract void
    swapRows(int rowIdx1, int rowIdx2, int start, int stop)
    Swaps two rows, over a specified range, within the balancedMatrix matrix.
    protected abstract double
    vectorMaxAbs(int start, int n, int stride)
    Computes the maximum absolute value of a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride.
    protected abstract double
    vectorNorm(int start, int n, int stride)
    Computes the ℓ2 norm of a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride.
    protected abstract void
    vectorScale(double factor, int start, int n, int stride)
    Scales a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • scalePerm

      protected double[] scalePerm

      Stores both the scaling and permutation information for the balanced matrix.

      Let perm[j] be the index of the row and column swapped with row and column j and scale[j] be the scaling factor applied to row and column j. Then,

      • scalePerm[j] = perm[j] for j = 0, ..., iLow-1.
      • scalePerm[j] = scale[j] for j = iLow, ..., iHigh-1.
      • scalePerm[j] = perm[j] for j = iHigh, ..., size-1.
      The order which row and column swaps are made is size-1 to iHigh, then from 0 to iLow.

    • balancedMatrix

      protected T extends MatrixMixin<T,?,?,?> balancedMatrix
      Stores the balanced matrix.

    • size

      protected int size
      This size of the matrix to be balanced.

    • iHigh

      protected int iHigh
      Tracks the ending row/column index of the un-permuted submatrix to be balanced (exclusive).

    • iLow

      protected int iLow
      Tracks the starting row/column index of the un-permuted submatrix to be balanced (inclusive).

    • doScaling

      protected boolean doScaling
      Flag indicating if scaling should be done during balancing.
      • If true, then scaling will be performed during balancing.
      • If false, the no scaling will be done during balancing.

    • doPermutations

      protected boolean doPermutations
      Flag indicating if permutations should be done during balancing.
      • If true: Then row/column permutations will be performed during balancing.
      • If false: Then row/column permutations will be performed during balancing.

    • inPlace

      public final boolean inPlace
      Flag indicating if the balancing should be done in-place or if a copy should be made.
      • If true, the balancing will be done in-place and the matrix to be balanced will be overwritten.
      • If false, a copy will be made of the matrix before balancing is applied and the original matrix will remain unmodified.

  • Constructor Details

    • Balancer

      protected Balancer(boolean doPermutations, boolean doScaling, boolean inPlace)
      Parameters:
      doPermutations - Flag indicating if row/column permutations should be used when balancing the matrix.
      • If true, permutations will be used and P will be computed.
      • If false, permutations will not be used and the row and column positions will not be affected.
      doScaling - Flag indicating if row/column scaling should be done when balancing the matrix.
      • If true, scaling will be used and D will be computed.
      • If false, scaling will not be used.
      inPlace - Flag indicating if the balancing should be done in-place or if a copy should be made.
      • If true, the balancing will be done in-place and the matrix to be balanced will be overwritten.
      • If false, a copy will be made of the matrix before balancing is applied and the original matrix will remain unmodified.

  • Method Details

    • swapRows

      protected abstract void swapRows(int rowIdx1, int rowIdx2, int start, int stop)
      Swaps two rows, over a specified range, within the balancedMatrix matrix.
      Parameters:
      rowIdx1 - Index of the first row to swap.
      rowIdx2 - Index of the second row to swap.
      start - Index of the column specifying the start of the range for the row swap (inclusive).
      stop - Index of the column specifying the end of the range for the row swap (exclusive).

    • swapCols

      protected abstract void swapCols(int colIdx1, int colIdx2, int start, int stop)
      Swaps two columns, over a specified range, within the balancedMatrix matrix.
      Parameters:
      colIdx1 - Index of the first column to swap.
      colIdx2 - Index of the second column to swap.
      start - Index of the row specifying the start of the range for the column swap (inclusive).
      stop - Index of the row specifying the end of the range for the column swap (exclusive).

    • isZero

      protected abstract boolean isZero(int idx)
      Checks if a value within balancedMatrix is zero.
      Parameters:
      idx - Index of value within balancedMatrix's 1D data array to check if it is zero.

    • vectorNorm

      protected abstract double vectorNorm(int start, int n, int stride)
      Computes the ℓ2 norm of a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride.
      Parameters:
      start - Starting index within balancedMatrix's 1D data array to compute norm of.
      n - The number of elements in the vector to compute norm of.
      stride - The spacing between each element within balancedMatrix's 1D data array to norm of.
      Returns:
      The norm of the vector containing the specified elements from balancedMatrix's 1D data array.

    • vectorMaxAbs

      protected abstract double vectorMaxAbs(int start, int n, int stride)
      Computes the maximum absolute value of a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride.
      Parameters:
      start - Starting index within balancedMatrix's 1D data array to compute maximum absolute value of.
      n - The number of elements in the vector to compute maximum absolute value of.
      stride - The spacing between each element within balancedMatrix's 1D data array to compute maximum absolute value of.
      Returns:
      The maximum absolute value of the vector containing the specified elements from balancedMatrix's 1D data array.

    • vectorScale

      protected abstract void vectorScale(double factor, int start, int n, int stride)
      Scales a vector with n elements from balancedMatrix's 1D data array starting at index start and spaced by stride. This operation must be done in-place.
      Parameters:
      factor - Factor to scale elements by.
      start - Starting index within balancedMatrix's 1D data array begin scaling.
      n - The number of elements to scale.
      stride - The spacing between each element within balancedMatrix's 1D data array to scale.

    • decompose

      public Balancer<T> decompose(T src)
      Balances a matrix so that the rows and columns have roughly similar sized norms.
      Specified by:
      decompose in interface Decomposition<T extends MatrixMixin<T,?,?,?>>
      Parameters:
      src - Matrix to balance. Must be square. If == true then src will be modified. Otherwise, src will not be modified.
      Returns:
      A reference to this balancer object.
      Throws:
      TensorShapeException - If src is not a square matrix.

    • doIterativePermutations

      protected void doIterativePermutations()

      Performs the permutation step of matrix balancing.

      This is, identifies rows and columns which are decoupled from the rest of the matrix and hence isolate an eigenvalue. Rows which isolate an eigenvalue are pushed to the bottom of the matrix. Similarly, columns which isolate an eigenvalue are pushed to the left of the matrix. To ensure that the row/column swaps are similarity transforms, if any two rows are swapped the same columns are swapped.

      Such row and column permutations transform the original matrix A into the following form: 

                   [ T1  X  Y  ]
   P-1 A P = [  0  B  Z  ]
             [  0  0  T2 ]

      Where T1 and T2 are upper-triangular matrices whose eigenvalues are the diagonal elements of the matrix. P is the permutation matrix representing the row and column swaps performed within this method.

      iLow and iHigh Specify the starting (inclusive) and ending (exclusive) row/column index of the submatrix B.

    • doIterativeScaling

      protected void doIterativeScaling()

      Performs the scaling step of matrix balancing.

      That is, computes scaling factors such that when a column is scaled by such value and the row is scaled by the reciprocal of that value, there ℓ1 norms are "close". Scaling need only be done for rows/column of the matrix which do not isolate eigenvalues; rows between iLow (inclusive) to iHigh (exclusive).

      D1 is the diagonal matrix describing such scaling and is the diagonal matrix computed by this method. \ The diagonal values of D1 are stored in scalePerm between indices iLow (inclusive) to iHigh (exclusive).

    • getILow

      public int getILow()
      Gets the starting index (inclusive) for the sub-matrix B1 of the balanced matrix which did not isolate eigenvalues.
      Returns:
      The starting index (inclusive) for the sub-matrix of the balanced matrix which did not isolate eigenvalues.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getIHigh

      public int getIHigh()
      Gets the starting index (exclusive) for the sub-matrix B1 of the balanced matrix which did not isolate eigenvalues.
      Returns:
      The starting index (exclusive) for the sub-matrix of the balanced matrix which did not isolate eigenvalues.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getB

      public T getB()
      Gets the full balanced matrix, B, for the last matrix balanced by this balancer.
      Returns:
      The full balanced matrix for the last matrix balanced by this balancer.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getBSubMatrix

      public T getBSubMatrix()
      Gets the sub-matrix B1 of the full balanced matrix which did not isolate eigenvalues.
      Returns:
      The sub-matrix of the full balanced matrix which did not isolate eigenvalues.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getScalePerm

      public double[] getScalePerm()

      Gets the raw scaling factors and permutation data stored in a single array.

      Let perm[j] be the index of the row and column swapped with row and column j and scale[j] be the scaling factor applied to row and column j. Then,

      • scalePerm[j] = perm[j] for j = 0, ..., iLow-1.
      • scalePerm[j] = scale[j] for j = iLow, ..., iHigh-1.
      • scalePerm[j] = perm[j] for j = iHigh, ..., size-1.
      The order which row and column swaps are made is size-1 to iHigh, then from 0 to iLow.
      Returns:
      The raw scaling factors and permutation data stored in a single array.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getD

      public Matrix getD(boolean full)
      Gets the diagonal scaling matrix for the last matrix balanced by this balancer.
      Parameters:
      full - Flag indicating if the full diagonal scaling matrix should be constructed or if only the scaling factors should be returned. If the last matrix balanced had shape n-by-n then,
      • If true: The full n-by-n diagonal scaling matrix will be created.
      • If false: A matrix of shape 1-by-n containing only the scaling factors (i.e. the diagonal entries of the full scaling matrix).
      Returns:
      If full == true then the full n-by-n scaling matrix is returned. Otherwise if full == false a matrix of shape 1-by-n containing only the diagonal scaling factors is returned.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.
      See Also:

    • getD

      public Matrix getD()

      Gets the diagonal scaling factors for the last matrix balanced by this balancer.

      Note, this method will not construct the full diagonal scaling matrix. If the full matrix is desired, use getD(boolean).

      Returns:
      A 1-by-n matrix containing the diagonal elements of the full n-by-n diagonal scaling matrix.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.
      See Also:

    • getP

      public PermutationMatrix getP()

      Gets the permutation matrix for the last matrix balanced by this balancer.

      Returns:
      The permutation matrix for the last matrix balanced by this balancer.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.

    • getT

      public Matrix getT()
      Get the combined permutation and diagonal scaling matrix, T, from the last matrix balanced. This is equivalent to getP().leftMult(getD(true)).
      Returns:
      The combined permutation and diagonal scaling matrix from the last matrix balanced.
      Throws:
      IllegalStateException - If decompose(MatrixMixin) has not yet been called on this instance.