Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Tridiagonalization.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_TRIDIAGONALIZATION_H
13#define EIGEN_TRIDIAGONALIZATION_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
22template <typename MatrixType>
23struct TridiagonalizationMatrixTReturnType;
24template <typename MatrixType>
25struct traits<TridiagonalizationMatrixTReturnType<MatrixType>> : public traits<typename MatrixType::PlainObject> {
26 // matrixT() returns a dense n x n matrix. A band-stored alternative (e.g. a
27 // future matrixTBand() returning BandMatrix<Scalar, Dynamic, Dynamic, 1, 1>)
28 // would be ~3n storage instead of n^2, but changing this ReturnType in place
29 // would be API-breaking for callers that assume a dense matrix.
30 using ReturnType = typename MatrixType::PlainObject;
31 enum { Flags = 0 };
32};
33
34template <typename MatrixType, typename CoeffVectorType>
35EIGEN_DEVICE_FUNC void tridiagonalization_inplace(MatrixType& matA, CoeffVectorType& hCoeffs);
36} // namespace internal
37
70template <typename MatrixType_>
72 public:
74 using MatrixType = MatrixType_;
75
76 using Scalar = typename MatrixType::Scalar;
77 using RealScalar = typename NumTraits<Scalar>::Real;
78 using Index = Eigen::Index;
79
80 enum {
81 Size = MatrixType::RowsAtCompileTime,
82 SizeMinusOne = Size == Dynamic ? Dynamic : (Size > 1 ? Size - 1 : 1),
83 Options = internal::plain_object_options<MatrixType>::value,
84 MaxSize = MatrixType::MaxRowsAtCompileTime,
85 MaxSizeMinusOne = MaxSize == Dynamic ? Dynamic : (MaxSize > 1 ? MaxSize - 1 : 1)
86 };
87
89 using DiagonalType = typename internal::plain_col_type<MatrixType, RealScalar>::type;
91 using MatrixTypeRealView = internal::remove_all_t<typename MatrixType::RealReturnType>;
92 using MatrixTReturnType = internal::TridiagonalizationMatrixTReturnType<MatrixTypeRealView>;
93
94 using DiagonalReturnType =
95 std::conditional_t<NumTraits<Scalar>::IsComplex,
96 internal::add_const_on_value_type_t<typename Diagonal<const MatrixType>::RealReturnType>,
98
99 using SubDiagonalReturnType =
100 std::conditional_t<NumTraits<Scalar>::IsComplex,
101 internal::add_const_on_value_type_t<typename Diagonal<const MatrixType, -1>::RealReturnType>,
102 const Diagonal<const MatrixType, -1>>;
103
107
120 explicit Tridiagonalization(Index size = Size == Dynamic ? 2 : Size)
121 : m_matrix(size, size), m_hCoeffs(size > 1 ? size - 1 : 1), m_isInitialized(false) {}
122
133 template <typename InputType>
135 : m_matrix(matrix.derived()), m_hCoeffs(matrix.cols() > 1 ? matrix.cols() - 1 : 1), m_isInitialized(false) {
136 internal::tridiagonalization_inplace(m_matrix, m_hCoeffs);
137 m_isInitialized = true;
138 }
139
148 template <typename InputType>
150 : m_matrix(matrix.derived()), m_hCoeffs(matrix.cols() > 1 ? matrix.cols() - 1 : 1), m_isInitialized(false) {
151 internal::tridiagonalization_inplace(m_matrix, m_hCoeffs);
152 m_isInitialized = true;
153 }
154
172 template <typename InputType>
174 m_matrix = matrix.derived();
175 m_hCoeffs.resize(matrix.rows() - 1, 1);
176 internal::tridiagonalization_inplace(m_matrix, m_hCoeffs);
177 m_isInitialized = true;
178 return *this;
179 }
180
197 inline CoeffVectorType householderCoefficients() const {
198 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
199 return m_hCoeffs;
200 }
201
233 inline const MatrixType& packedMatrix() const {
234 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
235 return m_matrix;
236 }
237
254 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
255 return HouseholderSequenceType(m_matrix, m_hCoeffs.conjugate()).setLength(m_matrix.rows() - 1).setShift(1);
256 }
257
275 MatrixTReturnType matrixT() const {
276 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
277 return MatrixTReturnType(m_matrix.real());
278 }
279
293 DiagonalReturnType diagonal() const;
294
305 SubDiagonalReturnType subDiagonal() const;
306
307 protected:
308 MatrixType m_matrix;
309 CoeffVectorType m_hCoeffs;
310 bool m_isInitialized;
311};
312
313template <typename MatrixType>
314typename Tridiagonalization<MatrixType>::DiagonalReturnType Tridiagonalization<MatrixType>::diagonal() const {
315 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
316 return m_matrix.diagonal().real();
317}
318
319template <typename MatrixType>
320typename Tridiagonalization<MatrixType>::SubDiagonalReturnType Tridiagonalization<MatrixType>::subDiagonal() const {
321 eigen_assert(m_isInitialized && "Tridiagonalization is not initialized.");
322 return m_matrix.template diagonal<-1>().real();
323}
324
325namespace internal {
326
351template <typename MatrixType, typename CoeffVectorType>
352EIGEN_DEVICE_FUNC void tridiagonalization_inplace_unblocked(MatrixType& matA, CoeffVectorType& hCoeffs) {
353 using Scalar = typename MatrixType::Scalar;
354 using RealScalar = typename MatrixType::RealScalar;
355 Index n = matA.rows();
356 EIGEN_INTERNAL_ASSERT_SQUARE(matA);
357 eigen_assert(n == hCoeffs.size() + 1 || n == 1);
358
359 for (Index i = 0; i < n - 1; ++i) {
360 Index remainingSize = n - i - 1;
361 RealScalar beta;
362 Scalar h;
363 matA.col(i).tail(remainingSize).makeHouseholderInPlace(h, beta);
364
365 // Apply similarity transformation to remaining columns,
366 // i.e., A = H A H' where H = I - h v v' and v = matA.col(i).tail(n-i-1)
367 matA.col(i).coeffRef(i + 1) = Scalar(1);
368
369 hCoeffs.tail(n - i - 1).noalias() =
370 (matA.bottomRightCorner(remainingSize, remainingSize).template selfadjointView<Lower>() *
371 (numext::conj(h) * matA.col(i).tail(remainingSize)));
372
373 hCoeffs.tail(n - i - 1) +=
374 (numext::conj(h) * RealScalar(-0.5) * (hCoeffs.tail(remainingSize).dot(matA.col(i).tail(remainingSize)))) *
375 matA.col(i).tail(n - i - 1);
376
377 matA.bottomRightCorner(remainingSize, remainingSize)
378 .template selfadjointView<Lower>()
379 .rankUpdate(matA.col(i).tail(remainingSize), hCoeffs.tail(remainingSize), Scalar(-1));
380
381 matA.col(i).coeffRef(i + 1) = beta;
382 hCoeffs.coeffRef(i) = h;
383 }
384}
385
386#if !defined(EIGEN_GPU_COMPILE_PHASE)
393template <typename MatrixType, typename CoeffVectorType>
394void tridiagonalization_inplace_blocked(MatrixType& matA, CoeffVectorType& hCoeffs, Index nb = 16) {
395 using Scalar = typename MatrixType::Scalar;
396 using RealScalar = typename MatrixType::RealScalar;
397 const Index n = matA.rows();
398 EIGEN_INTERNAL_ASSERT_SQUARE(matA);
399 eigen_assert(n == hCoeffs.size() + 1);
400 eigen_assert(nb >= 2 && nb < n);
401
402 enum {
403 StorageOrder = (traits<MatrixType>::Flags & RowMajorBit) ? RowMajor : ColMajor,
404 RhsStorageOrder = (StorageOrder == ColMajor) ? RowMajor : ColMajor
405 };
406
407 // Workspace: W matrix (n x nb) for deferred update vectors, temp vector (nb) for GEMV, betas (nb).
408 using WorkMatrixType = Matrix<Scalar, Dynamic, Dynamic, StorageOrder>;
409 WorkMatrixType W(n, nb);
410 Matrix<Scalar, Dynamic, 1> temp(nb);
411 Matrix<RealScalar, Dynamic, 1> betas(nb);
412
413 // Pre-allocate GEMM blocking workspace for the largest trailing matrix (first panel).
414 // Reused across all panels to avoid repeated heap allocations.
415 using BlockingType = gemm_blocking_space<StorageOrder, Scalar, Scalar, Dynamic, Dynamic, Dynamic>;
416 const Index maxTrailingSize = n - nb;
417 BlockingType blocking(maxTrailingSize, maxTrailingSize, nb, 1, false);
418 blocking.allocateAll();
419
420 Index j0 = 0;
421 for (; j0 + nb < n - 1; j0 += nb) {
422 const Index j_end = j0 + nb;
423
424 // ---- Panel factorization (dlatrd) ----
425 // Process columns j0..j_end-1, computing Householder vectors (stored in matA)
426 // and update vectors (stored in W). The rank-2k update to the trailing
427 // submatrix is deferred until after the panel.
428 for (Index j = j0; j < j_end; ++j) {
429 const Index local_j = j - j0;
430 const Index remainingSize = n - j - 1;
431
432 // Step 1: Update column j for deferred rank-2 updates from columns j0..j-1.
433 // A(j:n-1, j) -= V * W(j,:)^H + W * V(j,:)^H
434 // where V = matA(j:n-1, j0:j-1) holds Householder vectors,
435 // and W(j:n-1, 0:lj-1) holds the corresponding update vectors.
436 if (local_j > 0) {
437 auto col_j = matA.col(j).segment(j, n - j);
438 col_j.noalias() -= matA.block(j, j0, n - j, local_j) * W.row(j).head(local_j).adjoint();
439 col_j.noalias() -= W.block(j, 0, n - j, local_j) * matA.row(j).segment(j0, local_j).adjoint();
440 // Keep diagonal real (for complex scalars; no-op for real).
441 matA.coeffRef(j, j) = numext::real(matA.coeff(j, j));
442 }
443
444 // Step 2: Compute Householder reflector for column j.
445 RealScalar beta;
446 Scalar h;
447 matA.col(j).tail(remainingSize).makeHouseholderInPlace(h, beta);
448 betas(local_j) = beta;
449 matA.col(j).coeffRef(j + 1) = Scalar(1);
450
451 auto v = matA.col(j).tail(remainingSize);
452 auto w = W.col(local_j).tail(remainingSize);
453
454 // Step 3: Compute w = conj(h) * A_eff * v where A_eff accounts for deferred updates.
455 // Start with SYMV on the stored (not yet updated) trailing submatrix.
456 w.noalias() = matA.bottomRightCorner(remainingSize, remainingSize).template selfadjointView<Lower>() *
457 (numext::conj(h) * v);
458
459 // GEMV corrections for deferred rank-2 updates within this panel.
460 if (local_j > 0) {
461 auto V_prev = matA.block(j + 1, j0, remainingSize, local_j);
462 auto W_prev = W.block(j + 1, 0, remainingSize, local_j);
463
464 // w -= conj(h) * V_prev * (W_prev^H * v)
465 temp.head(local_j).noalias() = W_prev.adjoint() * v;
466 w.noalias() -= numext::conj(h) * (V_prev * temp.head(local_j));
467
468 // w -= conj(h) * W_prev * (V_prev^H * v)
469 temp.head(local_j).noalias() = V_prev.adjoint() * v;
470 w.noalias() -= numext::conj(h) * (W_prev * temp.head(local_j));
471 }
472
473 // Step 4: Half-dot correction: w -= 0.5 * conj(h) * (w^H * v) * v
474 w += (numext::conj(h) * RealScalar(-0.5) * w.dot(v)) * v;
475
476 hCoeffs.coeffRef(j) = h;
477 }
478
479 // ---- Apply rank-2k update to trailing submatrix ----
480 // A(j_end:n-1, j_end:n-1) -= V_trail * W_trail^H + W_trail * V_trail^H
481 // using Level 3 BLAS (triangular GEMM).
482 const Index trailingSize = n - j_end;
483 if (trailingSize > 0) {
484 const Scalar* V_data = &matA.coeffRef(j_end, j0);
485 const Scalar* W_data = &W.coeffRef(j_end, 0);
486 Scalar* C_data = &matA.coeffRef(j_end, j_end);
487 const Index V_stride = matA.outerStride();
488 const Index W_stride = W.outerStride();
489 const Index C_stride = matA.outerStride();
490
491 // C -= V * W^H
492 general_matrix_matrix_triangular_product<Index, Scalar, StorageOrder, false, Scalar, RhsStorageOrder,
493 NumTraits<Scalar>::IsComplex, StorageOrder, 1,
494 Lower>::run(trailingSize, nb, V_data, V_stride, W_data, W_stride, C_data,
495 1, C_stride, Scalar(-1), blocking);
496
497 // C -= W * V^H
498 general_matrix_matrix_triangular_product<Index, Scalar, StorageOrder, false, Scalar, RhsStorageOrder,
499 NumTraits<Scalar>::IsComplex, StorageOrder, 1,
500 Lower>::run(trailingSize, nb, W_data, W_stride, V_data, V_stride, C_data,
501 1, C_stride, Scalar(-1), blocking);
502 }
503
504 // Restore subdiagonal entries (overwritten with 1 for Householder vectors).
505 for (Index j = j0; j < j_end; ++j) {
506 matA.coeffRef(j + 1, j) = betas(j - j0);
507 }
508 }
509
510 // ---- Process remaining columns with unblocked algorithm ----
511 if (j0 < n - 1) {
512 const Index remaining = n - j0;
513 auto trailing = matA.bottomRightCorner(remaining, remaining);
514 auto hCoeffs_tail = hCoeffs.segment(j0, remaining - 1);
515 tridiagonalization_inplace_unblocked(trailing, hCoeffs_tail);
516 }
517}
518#endif // !EIGEN_GPU_COMPILE_PHASE
519
524template <typename MatrixType, typename CoeffVectorType>
525EIGEN_DEVICE_FUNC void tridiagonalization_inplace(MatrixType& matA, CoeffVectorType& hCoeffs) {
526 EIGEN_INTERNAL_ASSERT_SQUARE(matA);
527 eigen_assert(matA.rows() == hCoeffs.size() + 1 || matA.rows() == 1);
528
529#if !defined(EIGEN_GPU_COMPILE_PHASE)
530 EIGEN_IF_CONSTEXPR (MatrixType::RowsAtCompileTime == Dynamic || MatrixType::ColsAtCompileTime == Dynamic) {
531 if (matA.rows() >= 96) {
532 tridiagonalization_inplace_blocked(matA, hCoeffs);
533 return;
534 }
535 }
536#endif
537 tridiagonalization_inplace_unblocked(matA, hCoeffs);
538}
539
540// forward declaration, implementation at the end of this file
541template <typename MatrixType, int Size = MatrixType::ColsAtCompileTime,
542 bool IsComplex = NumTraits<typename MatrixType::Scalar>::IsComplex>
543struct tridiagonalization_inplace_selector;
544
587template <typename MatrixType, typename DiagonalType, typename SubDiagonalType, typename CoeffVectorType,
588 typename WorkSpaceType>
589EIGEN_DEVICE_FUNC void tridiagonalization_inplace(MatrixType& mat, DiagonalType& diag, SubDiagonalType& subdiag,
590 CoeffVectorType& hcoeffs, WorkSpaceType& workspace, bool extractQ) {
591 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
592 EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_ROWS(diag, mat);
593 eigen_assert(subdiag.size() == mat.rows() - 1);
594 tridiagonalization_inplace_selector<MatrixType>::run(mat, diag, subdiag, hcoeffs, workspace, extractQ);
595}
596
600template <typename MatrixType, int Size, bool IsComplex>
601struct tridiagonalization_inplace_selector {
602 using HouseholderSequenceType = typename Tridiagonalization<MatrixType>::HouseholderSequenceType;
603 template <typename DiagonalType, typename SubDiagonalType, typename CoeffVectorType, typename WorkSpaceType>
604 static EIGEN_DEVICE_FUNC void run(MatrixType& mat, DiagonalType& diag, SubDiagonalType& subdiag,
605 CoeffVectorType& hCoeffs, WorkSpaceType& workspace, bool extractQ) {
606 tridiagonalization_inplace(mat, hCoeffs);
607 diag = mat.diagonal().real();
608 subdiag = mat.template diagonal<-1>().real();
609 if (extractQ) {
610 HouseholderSequenceType(mat, hCoeffs.conjugate()).setLength(mat.rows() - 1).setShift(1).evalTo(mat, workspace);
611 }
612 }
613};
614
619template <typename MatrixType>
620struct tridiagonalization_inplace_selector<MatrixType, 3, false> {
621 using Scalar = typename MatrixType::Scalar;
622 using RealScalar = typename MatrixType::RealScalar;
623
624 template <typename DiagonalType, typename SubDiagonalType, typename CoeffVectorType, typename WorkSpaceType>
625 static EIGEN_DEVICE_FUNC void run(MatrixType& mat, DiagonalType& diag, SubDiagonalType& subdiag, CoeffVectorType&,
626 WorkSpaceType&, bool extractQ) {
627 const RealScalar tol = (std::numeric_limits<RealScalar>::min)();
628 diag[0] = mat(0, 0);
629 RealScalar v1norm2 = numext::abs2(mat(2, 0));
630 if (v1norm2 <= tol) {
631 diag[1] = mat(1, 1);
632 diag[2] = mat(2, 2);
633 subdiag[0] = mat(1, 0);
634 subdiag[1] = mat(2, 1);
635 if (extractQ) mat.setIdentity();
636 } else {
637 RealScalar beta = numext::sqrt<RealScalar>(numext::abs2(mat(1, 0)) + v1norm2);
638 RealScalar invBeta = RealScalar(1) / beta;
639 Scalar m01 = mat(1, 0) * invBeta;
640 Scalar m02 = mat(2, 0) * invBeta;
641 Scalar q = RealScalar(2) * m01 * mat(2, 1) + m02 * (mat(2, 2) - mat(1, 1));
642 diag[1] = mat(1, 1) + m02 * q;
643 diag[2] = mat(2, 2) - m02 * q;
644 subdiag[0] = beta;
645 subdiag[1] = mat(2, 1) - m01 * q;
646 if (extractQ) {
647 mat << Scalar(1), Scalar(0), Scalar(0), Scalar(0), m01, m02, Scalar(0), m02, -m01;
648 }
649 }
650 }
651};
652
656template <typename MatrixType, bool IsComplex>
657struct tridiagonalization_inplace_selector<MatrixType, 1, IsComplex> {
658 using Scalar = typename MatrixType::Scalar;
659
660 template <typename DiagonalType, typename SubDiagonalType, typename CoeffVectorType, typename WorkSpaceType>
661 static EIGEN_DEVICE_FUNC void run(MatrixType& mat, DiagonalType& diag, SubDiagonalType&, CoeffVectorType&,
662 WorkSpaceType&, bool extractQ) {
663 diag(0, 0) = numext::real(mat(0, 0));
664 if (extractQ) mat(0, 0) = Scalar(1);
665 }
666};
667
675template <typename MatrixType>
676struct TridiagonalizationMatrixTReturnType : public ReturnByValue<TridiagonalizationMatrixTReturnType<MatrixType>> {
677 public:
682 TridiagonalizationMatrixTReturnType(const MatrixType& mat) : m_matrix(mat) {}
683
684 template <typename ResultType>
685 inline void evalTo(ResultType& result) const {
686 result.setZero();
687 result.template diagonal<1>() = m_matrix.template diagonal<-1>().conjugate();
688 result.diagonal() = m_matrix.diagonal();
689 result.template diagonal<-1>() = m_matrix.template diagonal<-1>();
690 }
691
692 constexpr Index rows() const noexcept { return m_matrix.rows(); }
693 constexpr Index cols() const noexcept { return m_matrix.cols(); }
694
695 protected:
696 typename MatrixType::Nested m_matrix;
697};
698
699} // end namespace internal
700
701} // end namespace Eigen
702
703#endif // EIGEN_TRIDIAGONALIZATION_H
Expression of a diagonal/subdiagonal/superdiagonal in a matrix.
Definition Diagonal.h:78
Sequence of Householder reflections acting on subspaces with decreasing size.
Definition HouseholderSequence.h:155
HouseholderSequence & setLength(Index length)
Sets the length of the Householder sequence.
Definition HouseholderSequence.h:590
HouseholderSequence & setShift(Index shift)
Sets the shift of the Householder sequence.
Definition HouseholderSequence.h:606
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Tridiagonalization(Index size=Size==Dynamic ? 2 :Size)
Default constructor.
Definition Tridiagonalization.h:120
DiagonalReturnType diagonal() const
Returns the diagonal of the tridiagonal matrix T in the decomposition.
Definition Tridiagonalization.h:314
Tridiagonalization(EigenBase< InputType > &matrix)
Constructor for inplace decomposition .
Definition Tridiagonalization.h:149
Eigen::Index Index
Definition Tridiagonalization.h:78
const MatrixType & packedMatrix() const
Returns the internal representation of the decomposition.
Definition Tridiagonalization.h:233
CoeffVectorType householderCoefficients() const
Returns the Householder coefficients.
Definition Tridiagonalization.h:197
HouseholderSequence< MatrixType, internal::remove_all_t< typename CoeffVectorType::ConjugateReturnType > > HouseholderSequenceType
Definition Tridiagonalization.h:105
SubDiagonalReturnType subDiagonal() const
Returns the subdiagonal of the tridiagonal matrix T in the decomposition.
Definition Tridiagonalization.h:320
HouseholderSequenceType matrixQ() const
Returns the unitary matrix Q in the decomposition.
Definition Tridiagonalization.h:253
MatrixType MatrixType
Definition Tridiagonalization.h:74
MatrixTReturnType matrixT() const
Returns an expression of the tridiagonal matrix T in the decomposition.
Definition Tridiagonalization.h:275
Tridiagonalization(const EigenBase< InputType > &matrix)
Constructor; computes tridiagonal decomposition of given matrix.
Definition Tridiagonalization.h:134
Tridiagonalization & compute(const EigenBase< InputType > &matrix)
Computes tridiagonal decomposition of given matrix.
Definition Tridiagonalization.h:173
@ Lower
Definition Constants.h:212
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int RowMajorBit
Definition Constants.h:71
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index rows() const noexcept
Definition EigenBase.h:60