Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TridiagonalEigenSolver.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2026 Rasmus Munk Larsen <rmlarsen@gmail.com>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_TRIDIAGONAL_EIGENSOLVER_H
12#define EIGEN_TRIDIAGONAL_EIGENSOLVER_H
13
14#include "./TridiagonalBisection.h"
15#include "./TridiagonalInverseIteration.h"
16
17// IWYU pragma: private
18#include "./InternalHeaderCheck.h"
19
20namespace Eigen {
21
75template <typename Scalar_>
77 public:
79 using Scalar = Scalar_;
80 using RealScalar = Scalar;
81 static_assert(NumTraits<Scalar>::IsComplex == 0 && NumTraits<Scalar>::IsInteger == 0,
82 "TridiagonalEigenSolver requires a real floating-point scalar type; for the eigenvalues of a complex "
83 "Hermitian tridiagonal matrix, pass subdiag.cwiseAbs() as the real sub-diagonal (see the class "
84 "documentation).");
85
90
93
95 explicit TridiagonalEigenSolver(Index size)
96 : m_eivalues(size), m_eivec(size, size), m_diag(size), m_subdiag(size > 1 ? size - 1 : 0) {}
97
102 template <typename DiagType, typename SubdiagType>
104 int options = ComputeEigenvectors, const EigenvalueRange& range = EigenvalueRange::all())
106 compute(diag, subdiag, options, range);
107 }
108
123 template <typename DiagType, typename SubdiagType>
125 int options = ComputeEigenvectors,
126 const EigenvalueRange& range = EigenvalueRange::all()) {
127 eigen_assert((options & ~EigVecMask) == 0 && (options & EigVecMask) != EigVecMask && "invalid option parameter");
128 computeEigenvalues(diag, subdiag, range);
129 if (m_info == Success && (options & ComputeEigenvectors) == ComputeEigenvectors) computeEigenvectors();
130 return *this;
131 }
132
147 template <typename DiagType, typename SubdiagType>
149 const EigenvalueRange& range = EigenvalueRange::all());
150
168 eigen_assert(m_isInitialized && "TridiagonalEigenSolver is not initialized.");
169 eigen_assert(m_info == Success && "computeEigenvectors() requires a preceding successful eigenvalue computation");
170 computeEigenvectorsImpl();
171 return *this;
172 }
173
216 template <typename DiagType, typename SubdiagType, typename EivalsType>
219
228 const VectorType& eigenvalues() const {
229 eigen_assert(m_isInitialized && "TridiagonalEigenSolver is not initialized.");
230 return m_eivalues;
231 }
232
241 const MatrixType& eigenvectors() const {
242 eigen_assert(m_isInitialized && "TridiagonalEigenSolver is not initialized.");
243 eigen_assert(m_eigenvectorsOk && "The eigenvectors have not been computed.");
244 return m_eivec;
245 }
246
252 eigen_assert(m_isInitialized && "TridiagonalEigenSolver is not initialized.");
253 return m_info;
254 }
255
256 protected:
257 // Sturm counts, bisection targets, and inverse-iteration thresholds are carried in the scalar type
258 // itself, so scalars narrower than float (half, bfloat16) compute in float internally: their
259 // epsilon cannot represent consecutive integer counts beyond ~1/eps (a 257-element bfloat16
260 // identity would report an eigenvalue of "5.19"), and intermediates such as the coincident-shift
261 // perturbation quantize away. Results are rounded back to Scalar on output.
262 using ComputeScalar = std::conditional_t<(NumTraits<Scalar>::digits() < NumTraits<float>::digits()), float, Scalar>;
263
264 void computeEigenvectorsImpl();
265
266 VectorType m_eivalues;
267 MatrixType m_eivec;
268 // The tridiagonal retained by the last compute step, so the staged computeEigenvectors() can
269 // re-form T - lambda*I without the caller having to keep diag/subdiag alive.
270 VectorType m_diag;
271 VectorType m_subdiag;
272 // Narrow scalars only: the unrounded float eigenvalues of the last computeEigenvalues(), kept so
273 // the staged eigenvector pass shifts by them rather than by the Scalar-rounded m_eivalues --
274 // shifts quantized to Scalar collapse neighbouring eigenvalues and yield near-parallel vectors.
275 // Empty whenever m_eivalues did not come from this solver's own bisection.
277 // Absolute error bound of the eigenvalues of the last computeEigenvalues(), as the staged eigenvector
278 // pass receives them: the bisection tolerance, about eps * ||T||. Zero for caller-supplied eigenvalues,
279 // which inverse iteration takes as exact. A disconnected block far below ||T|| may need its shifts
280 // re-bisected at its own scale (see internal::tridiagonal_inverse_iteration()).
281 ComputeScalar m_shiftTol = ComputeScalar(0);
283 bool m_isInitialized = false;
284 bool m_eigenvectorsOk = false;
285};
286
287template <typename Scalar_>
288template <typename DiagType, typename SubdiagType>
289TridiagonalEigenSolver<Scalar_>& TridiagonalEigenSolver<Scalar_>::computeEigenvalues(
290 const MatrixBase<DiagType>& diag, const MatrixBase<SubdiagType>& subdiag, const EigenvalueRange& range) {
291 static_assert(internal::is_same<typename DiagType::Scalar, Scalar>::value &&
292 internal::is_same<typename SubdiagType::Scalar, Scalar>::value,
293 "diag and subdiag must have the solver's scalar type");
294 const Index n = diag.size();
295 EIGEN_UNUSED_VARIABLE(n);
296 eigen_assert(subdiag.size() == (n > 0 ? n - 1 : 0) && "sub-diagonal must have one fewer entry than the diagonal");
297
298 m_diag = diag;
299 m_subdiag = subdiag;
300 m_eigenvectorsOk = false;
301
302 // Reject non-finite input up front (cf. SelfAdjointEigenSolver::computeFromTridiagonal()): the
303 // Gershgorin bracketing below would otherwise iterate on NaN brackets and return garbage with
304 // info() == Success. allFinite() rather than a max-reduction, whose default PropagateFast
305 // semantics may not surface a NaN.
306 if (!(m_diag.allFinite() && m_subdiag.allFinite())) {
307 m_eivalues.resize(0);
308 m_eivaluesc.resize(0);
309 m_shiftTol = ComputeScalar(0);
310 m_info = NoConvergence;
311 m_isInitialized = true;
312 return *this;
313 }
314
315 if (internal::is_same<Scalar, ComputeScalar>::value) {
316 RealScalar shift_tol(0);
317 internal::tridiagonal_bisection(m_diag, m_subdiag, range, RealScalar(0), m_eivalues, &shift_tol);
318 m_shiftTol = ComputeScalar(shift_tol);
319 m_eivaluesc.resize(0);
320 } else {
321 // Narrow scalar: bisect in float and round the eigenvalues back (see ComputeScalar). The
322 // unrounded values are retained for the staged eigenvector pass (see m_eivaluesc).
323 const Matrix<ComputeScalar, Dynamic, 1> cdiag = m_diag.template cast<ComputeScalar>();
324 const Matrix<ComputeScalar, Dynamic, 1> csubdiag = m_subdiag.template cast<ComputeScalar>();
325 internal::tridiagonal_bisection(cdiag, csubdiag, range, ComputeScalar(0), m_eivaluesc, &m_shiftTol);
326 m_eivalues = m_eivaluesc.template cast<Scalar>();
327 }
328 m_info = Success;
329 m_isInitialized = true;
330 return *this;
331}
332
333template <typename Scalar_>
334template <typename DiagType, typename SubdiagType, typename EivalsType>
336 const MatrixBase<DiagType>& diag, const MatrixBase<SubdiagType>& subdiag,
337 const MatrixBase<EivalsType>& eigenvalues) {
338 static_assert(internal::is_same<typename DiagType::Scalar, Scalar>::value &&
339 internal::is_same<typename SubdiagType::Scalar, Scalar>::value &&
340 internal::is_same<typename EivalsType::Scalar, Scalar>::value,
341 "diag, subdiag and eigenvalues must have the solver's scalar type");
342 const Index n = diag.size();
343 EIGEN_UNUSED_VARIABLE(n);
344 eigen_assert(subdiag.size() == (n > 0 ? n - 1 : 0) && "sub-diagonal must have one fewer entry than the diagonal");
345 eigen_assert(eigenvalues.size() <= n && "cannot request more eigenvectors than the size of the matrix");
346
347 m_diag = diag;
348 m_subdiag = subdiag;
349 m_eivalues = eigenvalues;
350 m_eivaluesc.resize(0); // the caller's Scalar eigenvalues are authoritative here
351 m_shiftTol = ComputeScalar(0);
352
353 // Reject non-finite input up front, mirroring computeEigenvalues(): inverse iteration on NaN/Inf
354 // data (or NaN shifts) would return NaN vectors with info() == Success.
355 if (!(m_diag.allFinite() && m_subdiag.allFinite() && m_eivalues.allFinite())) {
356 m_eivalues.resize(0);
357 m_eivec.resize(m_diag.size(), 0);
358 m_info = NoConvergence;
359 m_isInitialized = true;
360 m_eigenvectorsOk = false;
361 return *this;
362 }
363
364 computeEigenvectorsImpl();
365 return *this;
366}
367
368template <typename Scalar_>
369void TridiagonalEigenSolver<Scalar_>::computeEigenvectorsImpl() {
370 const Index n = m_diag.size();
371 const Index m = m_eivalues.size();
372 m_eivec.resize(n, m);
373 Index nonconv;
374 if (internal::is_same<Scalar, ComputeScalar>::value) {
375 nonconv = internal::tridiagonal_inverse_iteration(m_diag, m_subdiag, m_eivalues, m_eivec, RealScalar(m_shiftTol));
376 // Refine the eigenvectors of any genuinely degenerate cluster (Rayleigh-Ritz). The eigenvalues
377 // are left unchanged, and a non-degenerate spectrum is untouched.
378 internal::tridiagonal_rayleigh_ritz_refine(m_diag, m_subdiag, m_eivalues, m_eivec);
379 } else {
380 // Narrow scalar: iterate and refine in float, then round the vectors back (see ComputeScalar).
381 // Shift by the retained unrounded eigenvalues when they exist (the staged path): shifts rounded
382 // to Scalar collapse neighbouring eigenvalues and produce near-parallel vectors.
383 const Matrix<ComputeScalar, Dynamic, 1> cdiag = m_diag.template cast<ComputeScalar>();
384 const Matrix<ComputeScalar, Dynamic, 1> csubdiag = m_subdiag.template cast<ComputeScalar>();
386 (m_eivaluesc.size() == m) ? m_eivaluesc : m_eivalues.template cast<ComputeScalar>();
388 nonconv = internal::tridiagonal_inverse_iteration(cdiag, csubdiag, cw, cvec, m_shiftTol);
389 internal::tridiagonal_rayleigh_ritz_refine(cdiag, csubdiag, cw, cvec);
390 m_eivec = cvec.template cast<Scalar>();
391 }
392
393 // Like LAPACK xSTEIN, report NoConvergence if any eigenvector failed the inverse-iteration growth
394 // test (the columns are still returned, best effort, so eigenvectors() remains usable).
395 m_info = (nonconv == 0) ? Success : NoConvergence;
396 m_isInitialized = true;
397 m_eigenvectorsOk = true;
398}
399
400} // namespace Eigen
401
402#endif // EIGEN_TRIDIAGONAL_EIGENSOLVER_H
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Computes eigenvalues and eigenvectors of a real symmetric tridiagonal matrix.
Definition TridiagonalEigenSolver.h:76
Matrix< Scalar, Dynamic, 1 > VectorType
Type for the eigenvalues and the input diagonals: a dynamic-size column vector.
Definition TridiagonalEigenSolver.h:87
TridiagonalEigenSolver & computeEigenvectors(const MatrixBase< DiagType > &diag, const MatrixBase< SubdiagType > &subdiag, const MatrixBase< EivalsType > &eigenvalues)
Computes eigenvectors of a tridiagonal matrix by inverse iteration from known eigenvalues.
TridiagonalEigenSolver & computeEigenvectors()
Computes eigenvectors for the eigenvalues of the preceding compute step, by inverse iteration.
Definition TridiagonalEigenSolver.h:167
ComputationInfo info() const
Reports whether the computation was successful.
Definition TridiagonalEigenSolver.h:251
TridiagonalEigenSolver & compute(const MatrixBase< DiagType > &diag, const MatrixBase< SubdiagType > &subdiag, int options=ComputeEigenvectors, const EigenvalueRange &range=EigenvalueRange::all())
Computes the selected eigenvalues, and optionally eigenvectors, of a real symmetric tridiagonal matri...
Definition TridiagonalEigenSolver.h:124
const MatrixType & eigenvectors() const
Returns the computed eigenvectors, one column per eigenvalue.
Definition TridiagonalEigenSolver.h:241
TridiagonalEigenSolver(Index size)
Constructor pre-allocating room for the full spectrum of a matrix of dimension size.
Definition TridiagonalEigenSolver.h:95
TridiagonalEigenSolver()=default
Default constructor. Call compute() before querying any result.
Matrix< Scalar, Dynamic, Dynamic > MatrixType
Type for the eigenvector matrix: dynamic-size, one column per selected eigenvalue.
Definition TridiagonalEigenSolver.h:89
TridiagonalEigenSolver & computeEigenvalues(const MatrixBase< DiagType > &diag, const MatrixBase< SubdiagType > &subdiag, const EigenvalueRange &range=EigenvalueRange::all())
Computes the selected eigenvalues (only) of a real symmetric tridiagonal matrix.
TridiagonalEigenSolver(const MatrixBase< DiagType > &diag, const MatrixBase< SubdiagType > &subdiag, int options=ComputeEigenvectors, const EigenvalueRange &range=EigenvalueRange::all())
Constructor; computes the eigendecomposition of the given tridiagonal matrix.
Definition TridiagonalEigenSolver.h:103
Scalar_ Scalar
Scalar type of the matrix; must be real.
Definition TridiagonalEigenSolver.h:79
const VectorType & eigenvalues() const
Returns the computed eigenvalues, in non-decreasing order.
Definition TridiagonalEigenSolver.h:228
ComputationInfo
Definition Constants.h:455
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
@ ComputeEigenvectors
Definition Constants.h:406
Selects which eigenvalues to compute in a spectral-bisection solve.
Definition TridiagonalBisection.h:38
static EigenvalueRange all()
Definition TridiagonalBisection.h:50