Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ComplexQZ.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 Alexey Korepanov
5// Copyright (C) 2025 Ludwig Striet <ludwig.striet@mathematik.uni-freiburg.de>
6//
7// This Source Code Form is subject to the terms of the
8// Mozilla Public License v. 2.0. If a copy of the MPL
9// was not distributed with this file, You can obtain one at
10// https://mozilla.org/MPL/2.0/.
11//
12// Derived from: Eigen/src/Eigenvalues/RealQZ.h
13// SPDX-License-Identifier: MPL-2.0
14
15#ifndef EIGEN_COMPLEX_QZ_H_
16#define EIGEN_COMPLEX_QZ_H_
17
18// IWYU pragma: private
19#include "./InternalHeaderCheck.h"
20
48
49namespace Eigen {
50
51template <typename MatrixType_>
52class ComplexQZ {
53 public:
54 using MatrixType = MatrixType_;
55 using Scalar = typename MatrixType_::Scalar;
56 using RealScalar = typename MatrixType_::RealScalar;
57
58 enum {
59 RowsAtCompileTime = MatrixType::RowsAtCompileTime,
60 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
61 Options = internal::plain_object_options<MatrixType>::value,
62 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
63 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
64 };
65
68 using PlainMatrixType =
69 Matrix<Scalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime>;
70
71 using Vec = Matrix<Scalar, Dynamic, 1>;
72 using Vec2 = Matrix<Scalar, 2, 1>;
73 using Vec3 = Matrix<Scalar, 3, 1>;
74 using Row2 = Matrix<Scalar, 1, 2>;
75 using Mat2 = Matrix<Scalar, 2, 2>;
76
81 const PlainMatrixType& matrixQ() const {
82 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
83 eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition.");
84 return m_Q;
85 }
86
91 const PlainMatrixType& matrixZ() const {
92 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
93 eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition.");
94 return m_Z;
95 }
96
101 const MatrixType& matrixS() const {
102 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
103 return m_S;
104 }
105
110 const MatrixType& matrixT() const {
111 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
112 return m_T;
113 }
114
123 ComplexQZ(Index n, bool computeQZ = true, unsigned int maxIters = 400)
124 : m_n(n),
125 m_maxIters(maxIters),
126 m_computeQZ(computeQZ),
127 m_S(n, n),
128 m_T(n, n),
129 m_Q(computeQZ ? n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
130 computeQZ ? n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
131 m_Z(computeQZ ? n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
132 computeQZ ? n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
133 m_ws(2 * n),
134 m_hCoeffs(n) {}
135
147 template <typename InputTypeA, typename InputTypeB>
148 ComplexQZ(const EigenBase<InputTypeA>& A, const EigenBase<InputTypeB>& B, bool computeQZ = true,
149 unsigned int maxIters = 400)
150 : m_n(A.rows()),
151 m_maxIters(maxIters),
152 m_computeQZ(computeQZ),
153 m_S(A.derived()),
154 m_T(B.derived()),
155 m_Q(computeQZ ? m_n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
156 computeQZ ? m_n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
157 m_Z(computeQZ ? m_n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
158 computeQZ ? m_n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
159 m_ws(2 * m_n),
160 m_hCoeffs(m_n) {
161 computeInPlace(computeQZ);
162 }
163
175 template <typename InputTypeA, typename InputTypeB>
176 ComplexQZ(EigenBase<InputTypeA>& A, EigenBase<InputTypeB>& B, bool computeQZ = true, unsigned int maxIters = 400)
177 : m_n(A.rows()),
178 m_maxIters(maxIters),
179 m_computeQZ(computeQZ),
180 m_S(A.derived()),
181 m_T(B.derived()),
182 m_Q(computeQZ ? m_n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
183 computeQZ ? m_n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
184 m_Z(computeQZ ? m_n : (MatrixType::RowsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::RowsAtCompileTime),
185 computeQZ ? m_n : (MatrixType::ColsAtCompileTime == Eigen::Dynamic ? 0 : MatrixType::ColsAtCompileTime)),
186 m_ws(2 * m_n),
187 m_hCoeffs(m_n) {
188 computeInPlace(computeQZ);
189 }
190
197 template <typename InputTypeA, typename InputTypeB>
198 void compute(const EigenBase<InputTypeA>& A, const EigenBase<InputTypeB>& B, bool computeQZ = true);
199
206 template <typename SparseMatrixType_>
207 void computeSparse(const SparseMatrixType_& A, const SparseMatrixType_& B, bool computeQZ = true);
208
217 ComputationInfo info() const {
218 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
219 return m_info;
220 }
221
224 unsigned int iterations() const {
225 eigen_assert(m_isInitialized && "ComplexQZ is not initialized.");
226 return m_global_iter;
227 }
228
229 private:
230 Index m_n;
231 const unsigned int m_maxIters;
232 unsigned int m_global_iter = 0;
233 bool m_isInitialized = false;
234 bool m_computeQZ;
235 ComputationInfo m_info = InvalidInput;
236 MatrixType m_S, m_T;
237 PlainMatrixType m_Q, m_Z;
238 RealScalar m_normOfT, m_normOfS;
239 Vec m_ws;
240 Vec m_hCoeffs;
241
242 // Test if a Scalar is 0 up to a certain tolerance
243 static bool is_negligible(const Scalar x, const RealScalar tol = NumTraits<RealScalar>::epsilon()) {
244 return numext::abs(x) <= tol;
245 }
246
247 void do_QZ_step(Index f, Index l, unsigned int iter);
248
249 Vec3 shiftColumn(Index p, Index l, unsigned int iter) const;
250
251 JacobiRotation<Scalar> computeZk2(const Row2& b);
252
253 void computeInPlace(bool computeQZ);
254
255 // This is basically taken from Eigen3::RealQZ
256 void hessenbergTriangular();
257
258 // This function can be called when m_Q and m_Z are initialized and m_S, m_T
259 // are in hessenberg-triangular form
260 void reduceHessenbergTriangular();
261
262 void computeNorms();
263
264 Index findSmallSubdiagEntry(Index l);
265 Index findSmallDiagEntry(Index f, Index l);
266
267 void push_down_zero_ST(Index k, Index l);
268
269 void reduceDiagonal2x2block(Index i);
270};
271
272template <typename MatrixType_>
273template <typename InputTypeA, typename InputTypeB>
274void ComplexQZ<MatrixType_>::compute(const EigenBase<InputTypeA>& A, const EigenBase<InputTypeB>& B, bool computeQZ) {
275 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(A, "A is not a square matrix");
276 EIGEN_INTERNAL_ASSERT_SAME_SHAPE_MSG(A, B, "B is not a square matrix or B is not of the same size as A");
277 // Copy A and B, these will be the matrices on which we operate later
278 m_S = A.derived();
279 m_T = B.derived();
280 computeInPlace(computeQZ);
281}
282
284template <typename MatrixType_>
285void ComplexQZ<MatrixType_>::computeInPlace(bool computeQZ) {
286 m_computeQZ = computeQZ;
287 m_n = m_S.rows();
288
289 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_S, "A is not a square matrix");
290 EIGEN_INTERNAL_ASSERT_SAME_SHAPE_MSG(m_S, m_T, "B is not a square matrix or B is not of the same size as A");
291
292 m_isInitialized = true;
293 m_global_iter = 0;
294 m_info = Success;
295
296 // Scale S and T separately by powers of two near their largest coefficients, so that the iteration neither overflows
297 // nor underflows. The scaling is exact: it leaves Q and Z unchanged and is undone on S and T. The coefficients are
298 // measured by their largest real or imaginary part, propagating NaN: the modulus of a finite coefficient can
299 // overflow, which would leave the pencil unscaled.
300 using Scaling = internal::safe_scaling<RealScalar>;
301 const RealScalar maxS = Scaling::max_abs_component(m_S);
302 const RealScalar maxT = Scaling::max_abs_component(m_T);
303 const internal::safe_scaling_factors<RealScalar> factorsS = Scaling::scale_in_place(m_S, maxS);
304 const internal::safe_scaling_factors<RealScalar> factorsT = Scaling::scale_in_place(m_T, maxT);
305
306 // This will initialize m_Q and m_Z and bring m_S, m_T to hessenberg-triangular form
307 hessenbergTriangular();
308
309 // We assume that we already have that S is upper-Hessenberg and T is
310 // upper-triangular. This is what the hessenbergTriangular(...) method does
311 reduceHessenbergTriangular();
312
313 Scaling::unscale_in_place(m_S, maxS, factorsS);
314 Scaling::unscale_in_place(m_T, maxT, factorsT);
315 // A non-finite A or B is left unscaled and can still leave S and T finite: an infinite S(k, k-1) passes
316 // |S(k, k-1)| <= eps (|S(k-1, k-1)| + |S(k, k)|) where that sum is infinite, or eps m_normOfS = inf where it is 0,
317 // and is set to 0.
318 const bool finiteInput = (numext::isfinite)(maxS) && (numext::isfinite)(maxT);
319 // Where Q^* A Z or Q^* B Z is not representable, unscaling overflows; Success has to mean that S and T are usable.
320 if (m_info == Success && !(finiteInput && m_S.allFinite() && m_T.allFinite())) m_info = NumericalIssue;
321}
322
323// This is basically taken from Eigen3::RealQZ
324template <typename MatrixType_>
326 // Perform the QR decomposition of T in place: T holds R above the Householder vectors Q is formed from
327 m_ws.resize(2 * m_n);
328 m_hCoeffs.resize(m_n);
329 internal::householder_qr_inplace_blocked<MatrixType, Vec>::run(m_T, m_hCoeffs, 48, m_ws.data());
330 Map<Vec> workspace(m_ws.data(), m_n);
331 const auto householderQ = householderSequence(m_T, m_hCoeffs.conjugate());
332 if (m_computeQZ) householderQ.evalTo(m_Q, workspace);
333
334 // overwrite S with Q* x S
335 householderQ.adjoint().applyThisOnTheLeft(m_S, workspace);
336
337 m_T.template triangularView<StrictlyLower>().setZero();
338
339 if (m_computeQZ) m_Z = PlainMatrixType::Identity(m_n, m_n);
340
341 // reduce S to upper Hessenberg with Givens rotations
342 for (Index j = 0; j <= m_n - 3; j++) {
343 for (Index i = m_n - 1; i >= j + 2; i--) {
344 JacobiRotation<Scalar> G;
345 // delete S(i,j)
346 if (!numext::is_exactly_zero(m_S.coeff(i, j))) {
347 G.makeGivens(m_S.coeff(i - 1, j), m_S.coeff(i, j), &m_S.coeffRef(i - 1, j));
348 m_S.coeffRef(i, j) = Scalar(0);
349 m_T.rightCols(m_n - i + 1).applyOnTheLeft(i - 1, i, G.adjoint());
350 m_S.rightCols(m_n - j - 1).applyOnTheLeft(i - 1, i, G.adjoint());
351 // This is what we want to achieve
352 if (!is_negligible(m_S(i, j)))
354 else
355 m_S(i, j) = Scalar(0);
356 // update Q
357 if (m_computeQZ) m_Q.applyOnTheRight(i - 1, i, G);
358 }
359
360 if (!numext::is_exactly_zero(m_T.coeff(i, i - 1))) {
361 // Compute rotation and update matrix T
362 G.makeGivens(m_T.coeff(i, i), m_T.coeff(i, i - 1), &m_T.coeffRef(i, i));
363 m_T.topRows(i).applyOnTheRight(i - 1, i, G.adjoint());
364 m_T.coeffRef(i, i - 1) = Scalar(0);
365 // Update matrix S
366 m_S.applyOnTheRight(i - 1, i, G.adjoint());
367 // update Z
368 if (m_computeQZ) m_Z.applyOnTheLeft(i - 1, i, G);
369 }
370 }
371 }
372}
373
374template <typename MatrixType>
375template <typename SparseMatrixType_>
376void ComplexQZ<MatrixType>::computeSparse(const SparseMatrixType_& A, const SparseMatrixType_& B, bool computeQZ) {
377 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(A, "A is not a square matrix");
378 EIGEN_INTERNAL_ASSERT_SAME_SHAPE_MSG(A, B, "B is not a square matrix or B is not of the same size as A");
379 // S, T, Q and Z are dense and the iteration costs O(n^3), so a sparse QR of B would save no order of work. The dense
380 // reduction is also backward stable where SparseQR's reflectors are not (they form sums of squares unscaled), and it
381 // does not drop a column of B that holds a NaN.
382 m_S = A.toDense();
383 m_T = B.toDense();
384 computeInPlace(computeQZ);
385}
386
387template <typename MatrixType_>
389 m_ws.resize(2 * m_n);
390 Index l = m_n - 1, f;
391 unsigned int local_iter = 0;
392 computeNorms();
393
394 while (l > 0) {
395 f = findSmallSubdiagEntry(l);
396
397 // Subdiag entry is small -> can be safely set to 0
398 if (f > 0) {
399 m_S.coeffRef(f, f - 1) = Scalar(0);
400 }
401 if (f == l) { // One root found
402 l--;
403 local_iter = 0;
404 } else if (f == l - 1) { // Two roots found
405 // We found an undesired non-zero at (f+1,f) in S and eliminate it immediately
406 reduceDiagonal2x2block(f);
407 l -= 2;
408 local_iter = 0;
409 } else {
410 // The limit is checked before a step rather than before the deflation test, so a deflation the last allowed
411 // step produces is still found. Every pass deflates or takes a step, so the loop ends after at most
412 // n (maxIters + 1) passes even if a chase makes no progress.
413 if (local_iter >= m_maxIters) break;
414 Index z = findSmallDiagEntry(f, l);
415 if (z >= f) {
416 push_down_zero_ST(z, l);
417 } else {
418 do_QZ_step(f, l, local_iter);
419 m_global_iter++;
420 }
421 local_iter++;
422 }
423 }
424
425 // Part of the pencil is not reduced: that takes precedence over a NumericalIssue reported before.
426 if (l > 0) m_info = NoConvergence;
427}
428
429template <typename MatrixType_>
430JacobiRotation<typename ComplexQZ<MatrixType_>::Scalar> ComplexQZ<MatrixType_>::computeZk2(const Row2& b) {
431 JacobiRotation<Scalar> J;
432 J.makeGivens(numext::conj(b(1)), numext::conj(b(0)));
433 // S J S = J.transpose() for the exchange matrix S and a real Givens cosine.
434 return J.transpose();
435}
436
438template <typename MatrixType_>
439typename ComplexQZ<MatrixType_>::Vec3 ComplexQZ<MatrixType_>::shiftColumn(Index p, Index l, unsigned int iter) const {
440 const auto a = [p, this](Index i, Index j) { return m_S(p + i - 1, p + j - 1); };
441 const auto b = [p, this](Index i, Index j) { return m_T(p + i - 1, p + j - 1); };
442 const Index m = l - p + 1; // Size of the inner block
443 if (iter > 0 && iter % 10 == 0) {
444 // Break stalled double-shift iterations with a single shift displaced by the trailing subdiagonals.
445 const RealScalar displacement =
446 numext::abs(a(m, m - 1) / b(m - 1, m - 1)) + numext::abs(a(m - 1, m - 2) / b(m - 2, m - 2));
447 const Scalar shift = a(m, m) / b(m, m) + displacement;
448 // (S*T^-1 - shift*I)*e1 has only two nonzero entries.
449 return Vec3(a(1, 1) / b(1, 1) - shift, a(2, 1) / b(1, 1), Scalar(0));
450 }
451 const Scalar W1 = a(m - 1, m - 1) / b(m - 1, m - 1) - a(1, 1) / b(1, 1), W2 = a(m, m) / b(m, m) - a(1, 1) / b(1, 1),
452 W3 = a(m, m - 1) / b(m - 1, m - 1);
453 return Vec3(
454 (W1 * W2 - a(m - 1, m) / b(m, m) * W3 + W3 * b(m - 1, m) / b(m, m) * a(1, 1) / b(1, 1)) * b(1, 1) / a(2, 1) +
455 a(1, 2) / b(2, 2) - a(1, 1) / b(1, 1) * b(1, 2) / b(2, 2),
456 (a(2, 2) / b(2, 2) - a(1, 1) / b(1, 1)) - a(2, 1) / b(1, 1) * b(1, 2) / b(2, 2) - W1 - W2 +
457 W3 * (b(m - 1, m) / b(m, m)),
458 a(3, 2) / b(2, 2));
459}
460
462template <typename MatrixType_>
463void ComplexQZ<MatrixType_>::do_QZ_step(Index f, Index l, unsigned int iter) {
464 // Start at the lowest row p > f where the bulge v spreads S(p, p-1) only into negligible entries (the test of
465 // EISPACK's hqr and LAPACK's xLAHQR, applied to S, with v scaled to |v(0)| + |v(1)| + |v(2)| = 1; rows where that
466 // sum is 0 or not finite are skipped):
467 // |S(p, p-1)| (|v(1)| + |v(2)|) <= eps |v(0)| (|S(p-1, p-1)| + |S(p, p)| + |S(p+1, p+1)|).
468 // From row f the bulge is proportional to S(f+1, f), and a tiny but not negligible entry, e.g. next to zero
469 // eigenvalues, can stall the iteration. A block of three rows has no such p, as in xLAHQR.
470 Index p = f;
471 Vec3 X;
472 for (Index j = l - 2; j > f; --j) {
473 X = shiftColumn(j, l, iter);
474 const RealScalar scale = numext::abs(X(0)) + numext::abs(X(1)) + numext::abs(X(2));
475 if (!(numext::isfinite)(scale) || scale == RealScalar(0)) continue;
476 X /= scale;
477 const RealScalar diagonal =
478 numext::abs(m_S(j - 1, j - 1)) + numext::abs(m_S(j, j)) + numext::abs(m_S(j + 1, j + 1));
479 if (numext::abs(m_S(j, j - 1)) * (numext::abs(X(1)) + numext::abs(X(2))) <=
480 NumTraits<RealScalar>::epsilon() * numext::abs(X(0)) * diagonal) {
481 p = j;
482 break;
483 }
484 }
485 if (p == f) X = shiftColumn(f, l, iter);
486 const Index m = l - p + 1; // Size of the inner block
487 Scalar x = X(0), y = X(1), z = X(2);
488 const PermutationMatrix<3, 3, int> S3(Vector3i(2, 0, 1));
489 for (Index k = p; k < p + m - 2; k++) {
490 X << x, y, z;
491 Vec2 ess;
492 Scalar tau;
493 RealScalar beta;
494 X.makeHouseholder(ess, tau, beta);
495 // The permutations are needed because the makeHouseHolder-method computes
496 // the householder transformation in a way that the vector is reflected to
497 // (1 0 ... 0) instead of (0 ... 0 1)
498 m_S.template middleRows<3>(k)
499 .rightCols((std::min)(m_n, m_n - k + 1))
500 .applyHouseholderOnTheLeft(ess, tau, m_ws.data());
501 if (k > f && k == p) {
502 // The reflector spread the negligible S(p, p-1) into the entries below it, which are dropped.
503 m_S.coeffRef(k + 1, k - 1) = Scalar(0);
504 m_S.coeffRef(k + 2, k - 1) = Scalar(0);
505 }
506 m_T.template middleRows<3>(k).rightCols(m_n - k).applyHouseholderOnTheLeft(ess, tau, m_ws.data());
507 if (m_computeQZ) m_Q.template middleCols<3>(k).applyHouseholderOnTheRight(ess, numext::conj(tau), m_ws.data());
508
509 // Compute Matrix Zk1 s.t. (b(k+2,k) ... b(k+2, k+2)) Zk1 = (0,0,*)
510 Vec3 bprime = (m_T.template block<1, 3>(k + 2, k) * S3).adjoint();
511 bprime.makeHouseholder(ess, tau, beta);
512 auto Sk = m_S.template middleCols<3>(k).topRows((std::min)(k + 4, m_n));
513 auto Tk = m_T.template middleCols<3>(k).topRows((std::min)(k + 3, m_n));
514 // Right multiplication by S3 permutes columns as (2, 0, 1); reverse the swaps for S3^T.
515 Sk.col(0).swap(Sk.col(2));
516 Sk.col(1).swap(Sk.col(2));
517 Sk.applyHouseholderOnTheRight(ess, numext::conj(tau), m_ws.data());
518 Sk.col(1).swap(Sk.col(2));
519 Sk.col(0).swap(Sk.col(2));
520 Tk.col(0).swap(Tk.col(2));
521 Tk.col(1).swap(Tk.col(2));
522 Tk.applyHouseholderOnTheRight(ess, numext::conj(tau), m_ws.data());
523 Tk.col(1).swap(Tk.col(2));
524 Tk.col(0).swap(Tk.col(2));
525 if (m_computeQZ) {
526 auto Zk = m_Z.template middleRows<3>(k);
527 Zk.row(0).swap(Zk.row(2));
528 Zk.row(1).swap(Zk.row(2));
529 Zk.applyHouseholderOnTheLeft(ess, tau, m_ws.data());
530 Zk.row(1).swap(Zk.row(2));
531 Zk.row(0).swap(Zk.row(2));
532 }
533 const JacobiRotation<Scalar> Zk2 = computeZk2(m_T.template block<1, 2>(k + 1, k));
534 m_S.template middleCols<2>(k).topRows((std::min)(k + 4, m_n)).applyOnTheRight(0, 1, Zk2);
535 m_T.template middleCols<2>(k).topRows((std::min)(k + 3, m_n)).applyOnTheRight(0, 1, Zk2);
536
537 if (m_computeQZ) m_Z.template middleRows<2>(k).applyOnTheLeft(0, 1, Zk2.adjoint());
538
539 x = m_S(k + 1, k);
540 y = m_S(k + 2, k);
541 if (k < p + m - 3) {
542 z = m_S(k + 3, k);
543 }
544 }
545
546 // Find a Householder matrix Qn1 s.t. Qn1 (x y)^T = (* 0)
547 JacobiRotation<Scalar> J;
548 J.makeGivens(x, y);
549 m_S.template middleRows<2>(p + m - 2).applyOnTheLeft(0, 1, J.adjoint());
550 m_T.template middleRows<2>(p + m - 2).applyOnTheLeft(0, 1, J.adjoint());
551
552 if (m_computeQZ) m_Q.template middleCols<2>(p + m - 2).applyOnTheRight(0, 1, J);
553
554 // Find a rotation Zn1 s.t. (b(n,n-1) b(n,n)) * Zn1 = (0 *)
555 const JacobiRotation<Scalar> Zn1 = computeZk2(m_T.template block<1, 2>(p + m - 1, p + m - 2));
556 m_S.template middleCols<2>(p + m - 2).applyOnTheRight(0, 1, Zn1);
557 m_T.template middleCols<2>(p + m - 2).applyOnTheRight(0, 1, Zn1);
558
559 if (m_computeQZ) m_Z.template middleRows<2>(p + m - 2).applyOnTheLeft(0, 1, Zn1.adjoint());
560}
561
563template <typename MatrixType_>
565 // We have found a non-zero on the subdiagonal and want to eliminate it
566 Mat2 Si = m_S.template block<2, 2>(i, i), Ti = m_T.template block<2, 2>(i, i);
567 const RealScalar tolT = m_normOfT * NumTraits<RealScalar>::epsilon();
568 if (is_negligible(Ti(0, 0), tolT)) {
570 G.makeGivens(m_S(i, i), m_S(i + 1, i));
571 m_S.applyOnTheLeft(i, i + 1, G.adjoint());
572 m_T.applyOnTheLeft(i, i + 1, G.adjoint());
573
574 if (m_computeQZ) m_Q.applyOnTheRight(i, i + 1, G);
575
576 } else if (is_negligible(Ti(1, 1), tolT)) {
578 G.makeGivens(m_S(i + 1, i + 1), m_S(i + 1, i));
579 m_S.applyOnTheRight(i, i + 1, G.adjoint());
580 m_T.applyOnTheRight(i, i + 1, G.adjoint());
581 if (m_computeQZ) m_Z.applyOnTheLeft(i, i + 1, G);
582 } else {
583 Scalar mu = Si(0, 0) / Ti(0, 0);
584 Scalar a12_bar = Si(0, 1) - mu * Ti(0, 1);
585 Scalar a22_bar = Si(1, 1) - mu * Ti(1, 1);
586 Scalar p = Scalar(0.5) * (a22_bar / Ti(1, 1) - Ti(0, 1) * Si(1, 0) / (Ti(0, 0) * Ti(1, 1)));
587 RealScalar sgn_p = p.real() >= RealScalar(0) ? RealScalar(1) : RealScalar(-1);
588 Scalar q = Si(1, 0) * a12_bar / (Ti(0, 0) * Ti(1, 1));
589 Scalar r = p * p + q;
590 Scalar lambda = mu + p + sgn_p * numext::sqrt(r);
591 Mat2 E = Si - lambda * Ti;
592 Index l;
593 E.rowwise().norm().maxCoeff(&l);
594 JacobiRotation<Scalar> G;
595 G.makeGivens(E(l, 1), E(l, 0));
596 m_S.applyOnTheRight(i, i + 1, G.adjoint());
597 m_T.applyOnTheRight(i, i + 1, G.adjoint());
598
599 if (m_computeQZ) m_Z.applyOnTheLeft(i, i + 1, G);
600
601 // The left rotation from T's first column keeps T triangular; the residual ~eps (|S| + |lambda| |T|) of the null
602 // vector lands in S(i+1, i), where the refinement below removes it.
603 if (numext::abs(m_T(i, i)) + numext::abs(m_T(i + 1, i)) > tolT)
604 G.makeGivens(m_T(i, i), m_T(i + 1, i));
605 else
606 G.makeGivens(m_S(i, i), m_S(i + 1, i));
607 m_S.applyOnTheLeft(i, i + 1, G.adjoint());
608 m_T.applyOnTheLeft(i, i + 1, G.adjoint());
609
610 if (m_computeQZ) m_Q.applyOnTheRight(i, i + 1, G);
611 }
612
613 // Rotations formed from lambda can leave S(i+1, i) well above eps (|S(i, i)| + |S(i+1, i+1)|), e.g. for graded T.
614 // Refine with single-shift QZ steps. With K = T^-1 S = [a b; c d], the Rayleigh quotient shift d = S(i+1, i+1) /
615 // T(i+1, i+1) maps |c| to |c|^2 |b| / (|a - d|^2 + |c|^2): quadratic for separated eigenvalues, but not monotone. Up
616 // to four steps run on a copy of the block. Of the prefixes that pass the final test |S(i+1, i)| <= eps m_normOfS, or
617 // of all if none does, the one with the smallest |S(i+1, i)| / (|S(i, i)| + |S(i+1, i+1)|) is applied.
618 const auto relativeSubdiagonal = [](const Mat2& s) {
619 const RealScalar subdiagonal = numext::abs(s(1, 0));
620 const RealScalar diagonal = numext::abs(s(0, 0)) + numext::abs(s(1, 1));
621 return subdiagonal <= NumTraits<RealScalar>::epsilon() * diagonal ? RealScalar(0) : subdiagonal / diagonal;
622 };
623 JacobiRotation<Scalar> left[4], right[4];
624 Mat2 Sstep = m_S.template block<2, 2>(i, i), Tstep = m_T.template block<2, 2>(i, i);
625 const RealScalar tolS = m_normOfS * NumTraits<RealScalar>::epsilon();
626 RealScalar current = relativeSubdiagonal(Sstep), best = current;
627 bool bestPasses = is_negligible(Sstep(1, 0), tolS);
628 int bestSteps = 0;
629 for (int k = 0; k < 4 && current > RealScalar(0); ++k) {
630 if (is_negligible(Tstep(1, 1), tolT)) {
631 // An infinite eigenvalue: deflate it with a rotation of the columns, as in the branch above.
632 left[k] = JacobiRotation<Scalar>(Scalar(1), Scalar(0));
633 right[k].makeGivens(Sstep(1, 1), Sstep(1, 0));
634 right[k] = right[k].adjoint();
635 } else {
636 const Scalar shift = Sstep(1, 1) / Tstep(1, 1);
637 left[k].makeGivens(Sstep(0, 0) - shift * Tstep(0, 0), Sstep(1, 0));
638 Sstep.applyOnTheLeft(0, 1, left[k].adjoint());
639 Tstep.applyOnTheLeft(0, 1, left[k].adjoint());
640 right[k] = computeZk2(Tstep.row(1));
641 }
642 Sstep.applyOnTheRight(0, 1, right[k]);
643 Tstep.applyOnTheRight(0, 1, right[k]);
644 Tstep(1, 0) = Scalar(0);
645 current = relativeSubdiagonal(Sstep);
646 const bool passes = is_negligible(Sstep(1, 0), tolS);
647 if ((passes && !bestPasses) || (passes == bestPasses && current < best)) {
648 best = current;
649 bestPasses = passes;
650 bestSteps = k + 1;
651 }
652 }
653 for (int k = 0; k < bestSteps; ++k) {
654 m_S.rightCols(m_n - i).applyOnTheLeft(i, i + 1, left[k].adjoint());
655 m_T.rightCols(m_n - i).applyOnTheLeft(i, i + 1, left[k].adjoint());
656 if (m_computeQZ) m_Q.applyOnTheRight(i, i + 1, left[k]);
657 m_S.topRows(i + 2).applyOnTheRight(i, i + 1, right[k]);
658 m_T.topRows(i + 2).applyOnTheRight(i, i + 1, right[k]);
659 m_T(i + 1, i) = Scalar(0);
660 if (m_computeQZ) m_Z.applyOnTheLeft(i, i + 1, right[k].adjoint());
661 }
662
663 if (!is_negligible(m_S(i + 1, i), tolS)) {
665 } else {
666 m_S(i + 1, i) = Scalar(0);
667 m_T(i + 1, i) = Scalar(0);
668 }
669}
670
672template <typename MatrixType_>
673void ComplexQZ<MatrixType_>::push_down_zero_ST(Index k, Index l) {
674 JacobiRotation<Scalar> J;
675 for (Index j = k + 1; j <= l; j++) {
676 // Create a 0 at _T(j, j)
677 J.makeGivens(m_T(j - 1, j), m_T(j, j), &m_T.coeffRef(j - 1, j));
678 if (m_n - j - 1 > 0) {
679 m_T.rightCols(m_n - j - 1).applyOnTheLeft(j - 1, j, J.adjoint());
680 }
681 m_T.coeffRef(j, j) = Scalar(0);
682
683 m_S.applyOnTheLeft(j - 1, j, J.adjoint());
684
685 if (m_computeQZ) m_Q.applyOnTheRight(j - 1, j, J);
686
687 // Delete the non-desired non-zero at _S(j, j-2)
688 if (j > 1) {
689 J.makeGivens(numext::conj(m_S(j, j - 1)), numext::conj(m_S(j, j - 2)));
690 m_S.applyOnTheRight(j - 1, j - 2, J);
691 m_S(j, j - 2) = Scalar(0);
692 m_T.applyOnTheRight(j - 1, j - 2, J);
693 if (m_computeQZ) m_Z.applyOnTheLeft(j - 1, j - 2, J.adjoint());
694 }
695 }
696
697 // Assume we have the desired structure now, up to the non-zero entry at
698 // _S(l, l-1) which we will delete through a last right-jacobi-rotation
699 J.makeGivens(numext::conj(m_S(l, l)), numext::conj(m_S(l, l - 1)));
700 m_S.topRows(l + 1).applyOnTheRight(l, l - 1, J);
701
702 if (!is_negligible(m_S(l, l - 1), m_normOfS * NumTraits<Scalar>::epsilon())) {
704 } else {
705 m_S(l, l - 1) = Scalar(0);
706 }
707 m_T.topRows(l + 1).applyOnTheRight(l, l - 1, J);
708
709 if (m_computeQZ) m_Z.applyOnTheLeft(l, l - 1, J.adjoint());
710
711 // Ensure postconditions, with the same thresholds relative to the norms as the deflation tests.
712 if (!is_negligible(m_T(l, l), m_normOfT * NumTraits<RealScalar>::epsilon()) ||
713 !is_negligible(m_S(l, l - 1), m_normOfS * NumTraits<RealScalar>::epsilon())) {
715 } else {
716 m_T(l, l) = Scalar(0);
717 m_S(l, l - 1) = Scalar(0);
718 }
719}
720
722template <typename MatrixType_>
724 m_normOfS = internal::hessenberg_abs_sum<Upper>(m_S);
725 m_normOfT = internal::triangular_abs_sum<Upper>(m_T);
726}
727
730template <typename MatrixType_>
732 Index res = iu;
733 while (res > 0) {
734 RealScalar s = numext::abs(m_S.coeff(res - 1, res - 1)) + numext::abs(m_S.coeff(res, res));
735 if (s == Scalar(0)) s = m_normOfS;
736 // <=, so that an exact zero deflates also where s is 0, e.g. for S = 0.
737 if (numext::abs(m_S.coeff(res, res - 1)) <= NumTraits<RealScalar>::epsilon() * s) break;
738 res--;
739 }
740 return res;
741}
742
745template <typename MatrixType_>
746inline Index ComplexQZ<MatrixType_>::findSmallDiagEntry(Index f, Index l) {
747 Index res = l;
748 while (res >= f) {
749 if (numext::abs(m_T.coeff(res, res)) <= NumTraits<RealScalar>::epsilon() * m_normOfT) break;
750 res--;
751 }
752 return res;
753}
754
755} // namespace Eigen
756
757#endif // EIGEN_COMPLEX_QZ_H_
Performs a QZ decomposition of a pair of matrices A, B.
Rotation given by a cosine-sine pair.
Definition Jacobi.h:39
JacobiRotation adjoint() const
Definition Jacobi.h:64
void makeGivens(const Scalar &p, const Scalar &q, Scalar *r=0)
Definition Jacobi.h:157
HouseholderSequence< VectorsType, CoeffsType > householderSequence(const VectorsType &v, const CoeffsType &h)
Convenience function for constructing a Householder sequence.
Definition HouseholderSequence.h:739
@ NumericalIssue
Definition Constants.h:459
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Matrix< int, 3, 1 > Vector3i
3×1 vector of type int.
Definition Matrix.h:487