Class RealBalancer

java.lang.Object
org.flag4j.linalg.decompositions.Decomposition<Matrix>
org.flag4j.linalg.decompositions.balance.Balancer<Matrix>
org.flag4j.linalg.decompositions.balance.RealBalancer
public class RealBalancer extends Balancer<Matrix>

Instances of this class may be used to balance real dense matrices. 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: \[ \begin{align*} B &= T^{-1} A T \\ &= D^{-1} P^{-1} A P D. \end{align*} \] Solving for \( A \), balancing may be viewed as the following decomposition: \[ \begin{align*} A &= T B T^{-1} \\ &= P D B D^{-1} P^{-1}. \end{align*} \] 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, \[ \begin{align*} P^{-1}AP = \begin{bmatrix} T_1 & X & Y \\ \mathbf{0} & B_1 & Z \\ \mathbf{0} & \mathbf{0} & T_2 \end{bmatrix} \end{align*} \] Where \( T_{1} \) and \( T_{2} \) are upper triangular matrices whose eigenvalues lie along the diagonal. These are also eigenvalues of \( A \). Then, if scaling is applied we obtain: \[ D^{-1}P^{-1}APD = \begin{bmatrix} T_1 & XD_1 & Y \\ \mathbf{0} & D_1^{-1}B_1D_1 & D_1^{-1}Z \\ \mathbf{0} & \mathbf{0} & T_2 \end{bmatrix} \] where \( D_{1} \) is a diagonal matrix such that, \[ D = \begin{bmatrix} I_1 & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & D_1 & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & I_2 \end{bmatrix} \] Where \( I_{1} \) and \( I_{2} \) are identity matrices with equivalent shapes to \( T_{1} \) and \( T_{2} \).

Once balancing has been applied, one need only compute the eigenvalues of \( B_{1} \) and combine them with the diagonal entries of \( T_{1} \) and \( T_{2} \) 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:

  • Constructor Details

    • RealBalancer

      public RealBalancer()

      Constructs a real balancer which will perform both the permutations and scaling steps out-of-place.

      To specify if permutations or scaling should be or should not be performed, use RealBalancer(boolean, boolean). To specify if the balancing should be done in-place, use RealBalancer(boolean, boolean, boolean).

    • RealBalancer

      public RealBalancer(boolean doPermutations, boolean doScaling)

      Constructs a real balancer optionally performing the permutation and scaling steps out-of-place.

      To specify if the balancing should be done in-place, use RealBalancer(boolean, boolean, boolean).

      Parameters:
      doPermutations - Flag indicating if the permutation step should be performed during balancing.
      • If true: the permutation step will be performed.
      • If false: the permutation step will not be performed.
      doScaling - Flag indicating if the scaling step should be performed during balancing.
      • If true: the scaling step will be performed.
      • If false: the scaling step will not be performed.

    • RealBalancer

      public RealBalancer(boolean doPermutations, boolean doScaling, boolean inPlace)

      Constructs a real balancer optionally performing the permutation and scaling steps in/out-of-place.

      Parameters:
      doPermutations - Flag indicating if the permutation step should be performed during balancing.
      • If true: the permutation step will be performed.
      • If false: the permutation step will not be performed.
      doScaling - Flag indicating if the scaling step should be performed during balancing.
      • If true: the scaling step will be performed.
      • If false: the scaling step will not be performed.
      inPlace - Flag indicating if the balancing should be done in or out-of-place.
      • If true: balancing will be done in-place and the source matrix will be overwritten.
      • If false: balancing will be done out-of-place.

  • Method Details

    • swapRows

      protected void swapRows(int rowIdx1, int rowIdx2, int start, int stop)
      Swaps two rows, over a specified range, within the Balancer.balancedMatrix matrix.
      Specified by:
      swapRows in class Balancer<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 void swapCols(int colIdx1, int colIdx2, int start, int stop)
      Swaps two columns, over a specified range, within the Balancer.balancedMatrix matrix.
      Specified by:
      swapCols in class Balancer<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 boolean isZero(int idx)
      Checks if a value within Balancer.balancedMatrix is zero.
      Specified by:
      isZero in class Balancer<Matrix>
      Parameters:
      idx - Index of value within flat data Balancer.balancedMatrix to check if it is zero.

    • vectorNorm

      protected double vectorNorm(int start, int n, int stride)
      Computes the \( \ell ^{2} \) norm of a vector with n elements from Balancer.balancedMatrix's 1D data array starting at index start and spaced by stride.
      Specified by:
      vectorNorm in class Balancer<Matrix>
      Parameters:
      start - Starting index within Balancer.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 Balancer.balancedMatrix's 1D data array to norm of.
      Returns:
      The norm of the vector containing the specified elements from Balancer.balancedMatrix's 1D data array.

    • vectorMaxAbs

      protected double vectorMaxAbs(int start, int n, int stride)
      Computes the maximum absolute value of a vector with n elements from Balancer.balancedMatrix's 1D data array starting at index start and spaced by stride.
      Specified by:
      vectorMaxAbs in class Balancer<Matrix>
      Parameters:
      start - Starting index within Balancer.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 Balancer.balancedMatrix's 1D data array to compute maximum absolute value of.
      Returns:
      The maximum absolute value of the vector containing the specified elements from Balancer.balancedMatrix's 1D data array.

    • vectorScale

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

    • applyLeftTransform

      public Matrix applyLeftTransform(Matrix src)
      Efficiently left multiplies \( PD \) to the provided src matrix.
      Specified by:
      applyLeftTransform in class Balancer<Matrix>
      Parameters:
      src - Matrix to apply transform to.
      Returns:
      The result of left multiplying \( PD \) to the src matrix.

    • applyRightTransform

      public Matrix applyRightTransform(Matrix src)
      Efficiently right multiplies \( D^{-1}P^{-1} \) to the provided src matrix.
      Specified by:
      applyRightTransform in class Balancer<Matrix>
      Parameters:
      src - Matrix to apply transform to.
      Returns:
      The result of right multiplying \( D^{-1}P^{-1} \) to the src matrix.