# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.diagonalization

## Class SymmetricTridiagonalDecomposition

• java.lang.Object
• com.numericalmethod.suanshu.algebra.linear.matrix.doubles.factorization.diagonalization.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.
"Golub, G. H., van Loan, C. F., "Algorithm 8.3.1 (Householder Tridiagonalization)," Matrix Computations, 3rd edition."
• ### Constructor Summary

Constructors
Constructor and Description
SymmetricTridiagonalDecomposition(Matrix A)
Runs the tridiagonal decomposition for a square, symmetric matrix.
• ### Method Summary

All Methods
Modifier and Type Method and Description
Matrix Q()
Returns the rotation matrix.
TridiagonalMatrix T()
Gets the symmetric tridiagonal T matrix.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### 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
"Golub, G. H., van Loan, C. F., "Algorithm 8.3.1," Matrix Computations, 3rd edition."
• ### 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