template<typename _MatrixType>
Eigen::Tridiagonalization class

Tridiagonal decomposition of a selfadjoint matrix.

Template parameters
_MatrixType the type of the matrix of which we are computing the tridiagonal decomposition; this is expected to be an instantiation of the Matrix class template.

Contents

This is defined in the Eigenvalues module. #include <Eigen/Eigenvalues>

This class performs a tridiagonal decomposition of a selfadjoint matrix $ A $ such that: $ A = Q T Q^* $ where $ Q $ is unitary and $ T $ a real symmetric tridiagonal matrix.

A tridiagonal matrix is a matrix which has nonzero elements only on the main diagonal and the first diagonal below and above it. The Hessenberg decomposition of a selfadjoint matrix is in fact a tridiagonal decomposition. This class is used in SelfAdjointEigenSolver to compute the eigenvalues and eigenvectors of a selfadjoint matrix.

Call the function compute() to compute the tridiagonal decomposition of a given matrix. Alternatively, you can use the Tridiagonalization(const MatrixType&) constructor which computes the tridiagonal Schur decomposition at construction time. Once the decomposition is computed, you can use the matrixQ() and matrixT() functions to retrieve the matrices Q and T in the decomposition.

The documentation of Tridiagonalization(const MatrixType&) contains an example of the typical use of this class.

Public types

using HouseholderSequenceType = HouseholderSequence<MatrixType, typename internal::remove_all<typename CoeffVectorType::ConjugateReturnType>::type>
Return type of matrixQ()
using Index = Eigen::Index deprecated
using MatrixType = _MatrixType
Synonym for the template parameter _MatrixType.

Constructors, destructors, conversion operators

Tridiagonalization(Index size = Size==Dynamic ? 2 :Size) explicit
Default constructor.
template<typename InputType>
Tridiagonalization(const EigenBase<InputType>& matrix) explicit
Constructor; computes tridiagonal decomposition of given matrix.

Public functions

template<typename InputType>
auto compute(const EigenBase<InputType>& matrix) -> Tridiagonalization&
Computes tridiagonal decomposition of given matrix.
auto diagonal() const -> DiagonalReturnType
Returns the diagonal of the tridiagonal matrix T in the decomposition.
auto householderCoefficients() const -> CoeffVectorType
Returns the Householder coefficients.
auto matrixQ() const -> HouseholderSequenceType
Returns the unitary matrix Q in the decomposition.
auto matrixT() const -> MatrixTReturnType
Returns an expression of the tridiagonal matrix T in the decomposition.
auto packedMatrix() const -> const MatrixType&
Returns the internal representation of the decomposition.
auto subDiagonal() const -> SubDiagonalReturnType
Returns the subdiagonal of the tridiagonal matrix T in the decomposition.

Typedef documentation

template<typename _MatrixType>
typedef Eigen::Index Eigen::Tridiagonalization<_MatrixType>::Index

Function documentation

template<typename _MatrixType>
Eigen::Tridiagonalization<_MatrixType>::Tridiagonalization(Index size = Size==Dynamic ? 2 :Size) explicit

Default constructor.

Parameters
size in Positive integer, size of the matrix whose tridiagonal decomposition will be computed.

The default constructor is useful in cases in which the user intends to perform decompositions via compute(). The size parameter is only used as a hint. It is not an error to give a wrong size, but it may impair performance.

template<typename _MatrixType> template<typename InputType>
Eigen::Tridiagonalization<_MatrixType>::Tridiagonalization(const EigenBase<InputType>& matrix) explicit

Constructor; computes tridiagonal decomposition of given matrix.

Parameters
matrix in Selfadjoint matrix whose tridiagonal decomposition is to be computed.

This constructor calls compute() to compute the tridiagonal decomposition.

Example:

MatrixXd X = MatrixXd::Random(5,5);
MatrixXd A = X + X.transpose();
cout << "Here is a random symmetric 5x5 matrix:" << endl << A << endl << endl;
Tridiagonalization<MatrixXd> triOfA(A);
MatrixXd Q = triOfA.matrixQ();
cout << "The orthogonal matrix Q is:" << endl << Q << endl;
MatrixXd T = triOfA.matrixT();
cout << "The tridiagonal matrix T is:" << endl << T << endl << endl;
cout << "Q * T * Q^T = " << endl << Q * T * Q.transpose() << endl;

Output:

Here is a random symmetric 5x5 matrix:
  1.36 -0.816  0.521   1.43 -0.144
-0.816 -0.659  0.794 -0.173 -0.406
 0.521  0.794 -0.541  0.461  0.179
  1.43 -0.173  0.461  -1.43  0.822
-0.144 -0.406  0.179  0.822  -1.37

The orthogonal matrix Q is:
       1        0        0        0        0
       0   -0.471    0.127   -0.671   -0.558
       0    0.301   -0.195    0.437   -0.825
       0    0.825   0.0459   -0.563 -0.00872
       0  -0.0832   -0.971   -0.202   0.0922
The tridiagonal matrix T is:
  1.36   1.73      0      0      0
  1.73   -1.2 -0.966      0      0
     0 -0.966  -1.28  0.214      0
     0      0  0.214  -1.69  0.345
     0      0      0  0.345  0.164

Q * T * Q^T = 
  1.36 -0.816  0.521   1.43 -0.144
-0.816 -0.659  0.794 -0.173 -0.406
 0.521  0.794 -0.541  0.461  0.179
  1.43 -0.173  0.461  -1.43  0.822
-0.144 -0.406  0.179  0.822  -1.37

template<typename _MatrixType> template<typename InputType>
Tridiagonalization& Eigen::Tridiagonalization<_MatrixType>::compute(const EigenBase<InputType>& matrix)

Computes tridiagonal decomposition of given matrix.

Parameters
matrix in Selfadjoint matrix whose tridiagonal decomposition is to be computed.
Returns Reference to *this

The tridiagonal decomposition is computed by bringing the columns of the matrix successively in the required form using Householder reflections. The cost is $ 4n^3/3 $ flops, where $ n $ denotes the size of the given matrix.

This method reuses of the allocated data in the Tridiagonalization object, if the size of the matrix does not change.

Example:

Tridiagonalization<MatrixXf> tri;
MatrixXf X = MatrixXf::Random(4,4);
MatrixXf A = X + X.transpose();
tri.compute(A);
cout << "The matrix T in the tridiagonal decomposition of A is: " << endl;
cout << tri.matrixT() << endl;
tri.compute(2*A); // re-use tri to compute eigenvalues of 2A
cout << "The matrix T in the tridiagonal decomposition of 2A is: " << endl;
cout << tri.matrixT() << endl;

Output:

The matrix T in the tridiagonal decomposition of A is: 
  1.36 -0.704      0      0
-0.704 0.0147   1.71      0
     0   1.71  0.856  0.641
     0      0  0.641 -0.506
The matrix T in the tridiagonal decomposition of 2A is: 
  2.72  -1.41      0      0
 -1.41 0.0294   3.43      0
     0   3.43   1.71   1.28
     0      0   1.28  -1.01

template<typename _MatrixType>
DiagonalReturnType Eigen::Tridiagonalization<_MatrixType>::diagonal() const

Returns the diagonal of the tridiagonal matrix T in the decomposition.

Returns expression representing the diagonal of T

Example:

MatrixXcd X = MatrixXcd::Random(4,4);
MatrixXcd A = X + X.adjoint();
cout << "Here is a random self-adjoint 4x4 matrix:" << endl << A << endl << endl;

Tridiagonalization<MatrixXcd> triOfA(A);
MatrixXd T = triOfA.matrixT();
cout << "The tridiagonal matrix T is:" << endl << T << endl << endl;

cout << "We can also extract the diagonals of T directly ..." << endl;
VectorXd diag = triOfA.diagonal();
cout << "The diagonal is:" << endl << diag << endl; 
VectorXd subdiag = triOfA.subDiagonal();
cout << "The subdiagonal is:" << endl << subdiag << endl;

Output:

Here is a random self-adjoint 4x4 matrix:
    (-0.422,0)  (0.705,-1.01) (-0.17,-0.552) (0.338,-0.357)
  (0.705,1.01)      (0.515,0) (0.241,-0.446)   (0.05,-1.64)
 (-0.17,0.552)  (0.241,0.446)      (-1.03,0)  (0.0449,1.72)
 (0.338,0.357)    (0.05,1.64) (0.0449,-1.72)       (1.36,0)

The tridiagonal matrix T is:
-0.422  -1.45      0      0
 -1.45   1.01  -1.42      0
     0  -1.42    1.8   -1.2
     0      0   -1.2  -1.96

We can also extract the diagonals of T directly ...
The diagonal is:
-0.422
  1.01
   1.8
 -1.96
The subdiagonal is:
-1.45
-1.42
 -1.2

template<typename _MatrixType>
CoeffVectorType Eigen::Tridiagonalization<_MatrixType>::householderCoefficients() const

Returns the Householder coefficients.

Returns a const reference to the vector of Householder coefficients

The Householder coefficients allow the reconstruction of the matrix $ Q $ in the tridiagonal decomposition from the packed data.

Example:

Matrix4d X = Matrix4d::Random(4,4);
Matrix4d A = X + X.transpose();
cout << "Here is a random symmetric 4x4 matrix:" << endl << A << endl;
Tridiagonalization<Matrix4d> triOfA(A);
Vector3d hc = triOfA.householderCoefficients();
cout << "The vector of Householder coefficients is:" << endl << hc << endl;

Output:

Here is a random symmetric 4x4 matrix:
   1.36   0.612   0.122   0.326
  0.612   -1.21  -0.222   0.563
  0.122  -0.222 -0.0904    1.16
  0.326   0.563    1.16    1.66
The vector of Householder coefficients is:
1.87
1.24
   0

template<typename _MatrixType>
HouseholderSequenceType Eigen::Tridiagonalization<_MatrixType>::matrixQ() const

Returns the unitary matrix Q in the decomposition.

Returns object representing the matrix Q

This function returns a light-weight object of template class HouseholderSequence. You can either apply it directly to a matrix or you can convert it to a matrix of type MatrixType.

template<typename _MatrixType>
MatrixTReturnType Eigen::Tridiagonalization<_MatrixType>::matrixT() const

Returns an expression of the tridiagonal matrix T in the decomposition.

Returns expression object representing the matrix T

Currently, this function can be used to extract the matrix T from internal data and copy it to a dense matrix object. In most cases, it may be sufficient to directly use the packed matrix or the vector expressions returned by diagonal() and subDiagonal() instead of creating a new dense copy matrix with this function.

template<typename _MatrixType>
const MatrixType& Eigen::Tridiagonalization<_MatrixType>::packedMatrix() const

Returns the internal representation of the decomposition.

Returns a const reference to a matrix with the internal representation of the decomposition.

The returned matrix contains the following information:

  • the strict upper triangular part is equal to the input matrix A.
  • the diagonal and lower sub-diagonal represent the real tridiagonal symmetric matrix T.
  • the rest of the lower part contains the Householder vectors that, combined with Householder coefficients returned by householderCoefficients(), allows to reconstruct the matrix Q as $ Q = H_{N-1} \ldots H_1 H_0 $ . Here, the matrices $ H_i $ are the Householder transformations $ H_i = (I - h_i v_i v_i^T) $ where $ h_i $ is the $ i $ th Householder coefficient and $ v_i $ is the Householder vector defined by $ v_i = [ 0, \ldots, 0, 1, M(i+2,i), \ldots, M(N-1,i) ]^T $ with M the matrix returned by this function.

See LAPACK for further details on this packed storage.

Example:

Matrix4d X = Matrix4d::Random(4,4);
Matrix4d A = X + X.transpose();
cout << "Here is a random symmetric 4x4 matrix:" << endl << A << endl;
Tridiagonalization<Matrix4d> triOfA(A);
Matrix4d pm = triOfA.packedMatrix();
cout << "The packed matrix M is:" << endl << pm << endl;
cout << "The diagonal and subdiagonal corresponds to the matrix T, which is:" 
     << endl << triOfA.matrixT() << endl;

Output:

Here is a random symmetric 4x4 matrix:
   1.36   0.612   0.122   0.326
  0.612   -1.21  -0.222   0.563
  0.122  -0.222 -0.0904    1.16
  0.326   0.563    1.16    1.66
The packed matrix M is:
  1.36  0.612  0.122  0.326
-0.704 0.0147 -0.222  0.563
0.0925   1.71  0.856   1.16
 0.248  0.785  0.641 -0.506
The diagonal and subdiagonal corresponds to the matrix T, which is:
  1.36 -0.704      0      0
-0.704 0.0147   1.71      0
     0   1.71  0.856  0.641
     0      0  0.641 -0.506

template<typename _MatrixType>
SubDiagonalReturnType Eigen::Tridiagonalization<_MatrixType>::subDiagonal() const

Returns the subdiagonal of the tridiagonal matrix T in the decomposition.

Returns expression representing the subdiagonal of T