Class SymmetricTridiagonalDecomposition
- java.lang.Object
-
- dev.nm.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.
-
-
Constructor Summary
Constructors Constructor Description SymmetricTridiagonalDecomposition(Matrix A)
Runs the tridiagonal decomposition for a square, symmetric matrix.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Matrix
Q()
Returns the rotation matrix.TridiagonalMatrix
T()
Gets the symmetric tridiagonal T matrix.
-
-
-
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
-
-