Class SymmetricTridiagonalDecomposition


  • public class SymmetricTridiagonalDecomposition
    extends Object
    Given a square, symmetric matrix A, we find Q such that Q' * A * Q = T , where T is a tridiagonal matrix. This implementation uses Householder reflection to repeatedly zero out the elements below and above the sub-diagonal. For example, the first step is to left multiply A by a Householder matrix Q1 so that matrix Q1 * A has zeros in the left column (except for the first two rows). That is (Q's are symmetric.), \[ Q_1 \times A = Q_1' \times A = \begin{bmatrix} a_{11} & * & ... & * \\ a_{21} & & & \\ 0 & & & \\ \vdots & & A ' & \\ 0 & & & \end{bmatrix} \] Then, we right multiply A by Q1 so that matrix Q1 A*Q1 has zeros in the first row except first two columns. We have \[ Q_1' \times A \times Q_1 = \begin{bmatrix} a_{11} & a_{12} &0 & \cdots & 0 \\ a_{21} & & & &\\ 0 & & & &\\ \vdots & & A'' && \\ 0 & & & & \end{bmatrix} \] At the end, we have a tridiagonal matrix T such that \[ (Q_n' \times ... \times Q_1') \times A \times (Q_1 \times ... \times Q_n) = T \] Denote \[ Q = (Q_1 \times ... \times Q_n) \] we have \[ Q'\times A \times Q = T \] This transformation always succeeds.
    • Constructor Detail

      • SymmetricTridiagonalDecomposition

        public SymmetricTridiagonalDecomposition​(Matrix A)
        Runs the tridiagonal decomposition for a square, symmetric matrix. This decomposition does not require a precision parameter, though checking the result will need an epsilon.

        The algorithm implemented here has two differences than Algorithm 8.3.1 in the reference. First the generation of a Householder matrix does not follow Algorithm 5.1.1 in the reference. The Householder matrix defining vector v of generator vector xis calculated as \[ v = (x-\rho||x||e_1 )/||x-\rho||x||e_1 || \], where\(\rho = sign(x_1)\) and \(e_1=(1,0,\cdots,0)^T\).

        Secondly the sub-matrices A(k+2:dim,k) and A(k,k+2:dim) are updated to zero after the calculation in the k-th iteration. This update is not documented in Algorithm 8.3.1 in the reference.

        Parameters:
        A - a square and symmetric matrix
        Throws:
        IllegalArgumentException - if A is not square nor symmetric
    • Method Detail

      • Q

        public Matrix Q()
        Returns the rotation matrix. \[ Q = P_1\times P_2\times\cdots\times P_{n-2} \]. Q'AQ is a tridiagonal matrix.
        Returns:
        the rotation matrix
      • T

        public TridiagonalMatrix T()
        Gets the symmetric tridiagonal T matrix.
        Returns:
        T