Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
RealQZ.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 Alexey Korepanov <kaikaikai@yandex.ru>
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_REAL_QZ_H
12#define EIGEN_REAL_QZ_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
60
61template <typename MatrixType_>
62class RealQZ {
63 public:
64 using MatrixType = MatrixType_;
65 enum {
66 RowsAtCompileTime = MatrixType::RowsAtCompileTime,
67 ColsAtCompileTime = MatrixType::ColsAtCompileTime,
68 Options = internal::plain_object_options<MatrixType>::value,
69 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
70 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
71 };
72 using Scalar = typename MatrixType::Scalar;
73 using ComplexScalar = internal::make_complex_t<Scalar>;
74 using Index = Eigen::Index;
75
78
83
95 explicit RealQZ(Index size = RowsAtCompileTime == Dynamic ? 1 : RowsAtCompileTime)
96 : m_S(size, size),
97 m_T(size, size),
98 m_Q(size, size),
99 m_Z(size, size),
100 m_workspace(size * 2),
101 m_hCoeffs(size),
102 m_maxIters(400),
103 m_isInitialized(false),
104 m_computeQZ(true) {}
105
114 template <typename InputTypeA, typename InputTypeB>
115 RealQZ(const EigenBase<InputTypeA>& A, const EigenBase<InputTypeB>& B, bool computeQZ = true)
116 : m_S(A.derived()),
117 m_T(B.derived()),
118 m_Q(A.rows(), A.cols()),
119 m_Z(A.rows(), A.cols()),
120 m_workspace(A.rows() * 2),
121 m_hCoeffs(A.rows()),
122 m_maxIters(400),
123 m_isInitialized(false),
124 m_computeQZ(true) {
125 computeInPlace(computeQZ);
126 }
127
138 template <typename InputTypeA, typename InputTypeB>
140 : m_S(A.derived()),
141 m_T(B.derived()),
142 m_Q(A.rows(), A.cols()),
143 m_Z(A.rows(), A.cols()),
144 m_workspace(A.rows() * 2),
145 m_hCoeffs(A.rows()),
146 m_maxIters(400),
147 m_isInitialized(false),
148 m_computeQZ(true) {
149 computeInPlace(computeQZ);
150 }
151
156 const PlainMatrixType& matrixQ() const {
157 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
158 eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition.");
159 return m_Q;
160 }
161
166 const PlainMatrixType& matrixZ() const {
167 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
168 eigen_assert(m_computeQZ && "The matrices Q and Z have not been computed during the QZ decomposition.");
169 return m_Z;
170 }
171
176 const MatrixType& matrixS() const {
177 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
178 return m_S;
179 }
180
185 const MatrixType& matrixT() const {
186 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
187 return m_T;
188 }
189
197 template <typename InputTypeA, typename InputTypeB>
198 RealQZ& compute(const EigenBase<InputTypeA>& A, const EigenBase<InputTypeB>& B, bool computeQZ = true);
199
207 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
208 return m_info;
209 }
210
214 eigen_assert(m_isInitialized && "RealQZ is not initialized.");
215 return m_global_iter;
216 }
217
222 m_maxIters = maxIters;
223 return *this;
224 }
225
226 private:
227 MatrixType m_S, m_T;
228 PlainMatrixType m_Q, m_Z;
229 Matrix<Scalar, Dynamic, 1> m_workspace;
230 ColumnVectorType m_hCoeffs;
231 ComputationInfo m_info;
232 Index m_maxIters;
233 bool m_isInitialized;
234 bool m_computeQZ;
235 Scalar m_normOfT;
236 Index m_global_iter;
237
238 using Vector3s = Matrix<Scalar, 3, 1>;
239 using Vector2s = Matrix<Scalar, 2, 1>;
240 using Matrix2s = Matrix<Scalar, 2, 2>;
241 using JRs = JacobiRotation<Scalar>;
242
243 RealQZ& computeInPlace(bool computeQZ);
244 void hessenbergTriangular();
245 void computeNorms();
246 Index findSmallSubdiagEntry(Index iu);
247 bool hasComplexEigenvalues(Index r) const;
248 Index findSmallDiagEntry(Index f, Index l);
249 void splitOffTwoRows(Index i);
250 void pushDownZero(Index z, Index f, Index l);
251 void step(Index f, Index l, Index iter, internal::inverse_iteration_rng* randomShift);
252
253}; // RealQZ
254
256template <typename MatrixType>
257void RealQZ<MatrixType>::hessenbergTriangular() {
258 const Index dim = m_S.cols();
259
260 // perform QR decomposition of T in place: T holds R above the Householder vectors Q is formed from
261 m_hCoeffs.resize(dim);
262 internal::householder_qr_inplace_blocked<MatrixType, ColumnVectorType>::run(m_T, m_hCoeffs, 48, m_workspace.data());
263 Map<ColumnVectorType> workspace(m_workspace.data(), dim);
264 householderSequence(m_T, m_hCoeffs.conjugate()).evalTo(m_Q, workspace);
265 m_T.template triangularView<StrictlyLower>().setZero();
266 // Z is unused until it is initialized below, so it can hold Q* S without aliasing S.
267 m_Z.noalias() = m_Q.adjoint() * m_S;
268 m_S.swap(m_Z);
269 // init Z as Identity
270 if (m_computeQZ) m_Z = PlainMatrixType::Identity(dim, dim);
271 // reduce S to upper Hessenberg with Givens rotations
272 for (Index j = 0; j <= dim - 3; j++) {
273 for (Index i = dim - 1; i >= j + 2; i--) {
274 JRs G;
275 // kill S(i,j)
276 if (!numext::is_exactly_zero(m_S.coeff(i, j))) {
277 G.makeGivens(m_S.coeff(i - 1, j), m_S.coeff(i, j), &m_S.coeffRef(i - 1, j));
278 m_S.coeffRef(i, j) = Scalar(0.0);
279 m_S.rightCols(dim - j - 1).applyOnTheLeft(i - 1, i, G.adjoint());
280 m_T.rightCols(dim - i + 1).applyOnTheLeft(i - 1, i, G.adjoint());
281 // update Q
282 if (m_computeQZ) m_Q.applyOnTheRight(i - 1, i, G);
283 }
284 // kill T(i,i-1)
285 if (!numext::is_exactly_zero(m_T.coeff(i, i - 1))) {
286 G.makeGivens(m_T.coeff(i, i), m_T.coeff(i, i - 1), &m_T.coeffRef(i, i));
287 m_T.coeffRef(i, i - 1) = Scalar(0.0);
288 m_S.applyOnTheRight(i, i - 1, G);
289 m_T.topRows(i).applyOnTheRight(i, i - 1, G);
290 // update Z
291 if (m_computeQZ) m_Z.applyOnTheLeft(i, i - 1, G.adjoint());
292 }
293 }
294 }
295}
296
298template <typename MatrixType>
299inline void RealQZ<MatrixType>::computeNorms() {
300 m_normOfT = internal::triangular_abs_sum<Upper>(m_T);
301}
302
305template <typename MatrixType>
306inline bool RealQZ<MatrixType>::hasComplexEigenvalues(Index r) const {
307 const Scalar s00 = m_S.coeff(r, r), s01 = m_S.coeff(r, r + 1), s10 = m_S.coeff(r + 1, r),
308 s11 = m_S.coeff(r + 1, r + 1);
309 const Scalar t00 = m_T.coeff(r, r), t01 = m_T.coeff(r, r + 1), t11 = m_T.coeff(r + 1, r + 1);
310 const Scalar c1 = s10 * t01 - s00 * t11 - s11 * t00;
311 return c1 * c1 < Scalar(4) * (t00 * t11) * (s00 * s11 - s01 * s10);
312}
313
315template <typename MatrixType>
316inline Index RealQZ<MatrixType>::findSmallSubdiagEntry(Index iu) {
317 Index res = iu;
318 while (res > 0) {
319 // The diagonal entries of a 2x2 block with complex eigenvalues a +- ib estimate only a. Between two such blocks, at
320 // r = res - 2 and r = res, the scale adds 2 min c, c = sqrt(|S(r+1, r) S(r, r+1)|), as xLAQR3 measures a 2x2
321 // block: between the blocks of a repeated pair +-i the diagonal is rounding noise, and a negligible S(res, res-1)
322 // would otherwise never deflate. For T = I, |b| <= c <= |a +- ib| + min |S(k, k)|, so the smaller block bounds
323 // the term and a graded pencil keeps its small eigenvalues' relative accuracy. A real block has no such bound.
324 Scalar s = numext::abs(m_S.coeff(res - 1, res - 1)) + numext::abs(m_S.coeff(res, res));
325 if (res > 1 && res + 1 < m_S.rows() && hasComplexEigenvalues(res - 2) && hasComplexEigenvalues(res))
326 s += Scalar(2) * numext::mini(numext::sqrt(numext::abs(m_S.coeff(res - 1, res - 2))) *
327 numext::sqrt(numext::abs(m_S.coeff(res - 2, res - 1))),
328 numext::sqrt(numext::abs(m_S.coeff(res + 1, res))) *
329 numext::sqrt(numext::abs(m_S.coeff(res, res + 1))));
330 // Both diagonal entries vanish for a pencil with a checkerboard zero pattern (eigenvalues in +- pairs), and can
331 // stay zero through the iteration. The scale is then twice the geometric mean of the neighboring subdiagonal
332 // entries: in a geometrically graded pencil D H D it has the grade of S(res, res-1), while ||S|| or the larger
333 // neighbor would deflate the subdiagonal of a small block. At either end of the active block that mean is zero,
334 // and eps s underflows for s < realmin / eps: there only an entry below realmin deflates.
335 if (numext::is_exactly_zero(s)) {
336 if (res > 1 && res + 1 < m_S.rows())
337 s = Scalar(2) * numext::sqrt(numext::abs(m_S.coeff(res - 1, res - 2))) *
338 numext::sqrt(numext::abs(m_S.coeff(res + 1, res)));
339 s = numext::maxi<Scalar>(s, (std::numeric_limits<Scalar>::min)() / NumTraits<Scalar>::epsilon());
340 }
341 // <=, so that an exact zero deflates also where s is 0: a Scalar without numeric_limits has no floor.
342 if (numext::abs(m_S.coeff(res, res - 1)) <= NumTraits<Scalar>::epsilon() * s) break;
343 res--;
344 }
345 return res;
346}
347
349template <typename MatrixType>
350inline Index RealQZ<MatrixType>::findSmallDiagEntry(Index f, Index l) {
351 Index res = l;
352 while (res >= f) {
353 if (numext::abs(m_T.coeff(res, res)) <= NumTraits<Scalar>::epsilon() * m_normOfT) break;
354 res--;
355 }
356 return res;
357}
358
360template <typename MatrixType>
361inline void RealQZ<MatrixType>::splitOffTwoRows(Index i) {
362 const Index dim = m_S.cols();
363 if (numext::is_exactly_zero(numext::abs(m_S.coeff(i + 1, i)))) return;
364 Index j = findSmallDiagEntry(i, i + 1);
365 if (j == i - 1) {
366 // As LAPACK's xLAGV2, without S T^-1, which loses accuracy as T nears singularity: for an eigenvalue alpha / beta
367 // of the blocks (A, B), scaled to largest entry 1, the right rotation moves a null vector y of
368 // H ~ beta A - alpha B, orthogonal to the larger row of H, into the first column. Then A y || B y, and the left
369 // rotation zeroes B(1, 0) if |beta| >= |alpha|, otherwise A(1, 0). The eigenvalues come from the shifted pencil
370 // (D, B), after xLAG2:
371 // D = sigma_b A - sigma_a B, sigma_b (beta A - alpha B) = beta D - w B, w = sigma_b alpha - sigma_a beta,
372 // with (sigma_a, sigma_b) = (A, B)(p, q) at the largest entry of B. (D - mu B)(p, q) = -mu sigma_b, |sigma_b| = 1,
373 // so (D, B) is never nearly scalar, which keeps a close pair of eigenvalues accurate, and |sigma_a| <= 1 bounds the
374 // rounding of D by eps (|A| + |B|).
375 const Matrix2s blockS = m_S.template block<2, 2>(i, i);
376 const Matrix2s blockT = m_T.template block<2, 2>(i, i).template triangularView<Upper>();
377 const Matrix2s A = blockS / blockS.cwiseAbs().maxCoeff(), B = blockT / blockT.cwiseAbs().maxCoeff();
378 Index p, q;
379 B.cwiseAbs().maxCoeff(&p, &q);
380 const Scalar sigmaA = A(p, q), sigmaB = B(p, q);
381 Matrix2s D = sigmaB * A - sigmaA * B;
382 D(p, q) = Scalar(0);
383 // det(beta D - w B) = c2 w^2 + c1 w beta + c0 beta^2.
384 const Scalar c2 = B(0, 0) * B(1, 1);
385 const Scalar c1 = D(1, 0) * B(0, 1) - D(0, 0) * B(1, 1) - D(1, 1) * B(0, 0);
386 const Scalar c0 = D(0, 0) * D(1, 1) - D(0, 1) * D(1, 0);
387 const Scalar discriminant = c1 * c1 - Scalar(4) * c2 * c0;
388 if (discriminant >= Scalar(0)) {
389 // The roots (w, beta) = (r, c2) and (c0, r), r = -(c1 + sign(c1) sqrt(discriminant)) / 2, or (0, c2) twice if
390 // r = 0. (r, c2) has the larger w / beta iff sign(c1) c2 < 0: the larger alpha / beta if sigma_b > 0, else the
391 // smaller.
392 const Scalar root = numext::sqrt(discriminant);
393 const bool c1Negative = c1 < Scalar(0);
394 const Scalar r = Scalar(-0.5) * (c1Negative ? c1 - root : c1 + root);
395 const bool firstIsLarger = (c1Negative == (c2 > Scalar(0))) == (sigmaB > Scalar(0));
396 // Deflate first the larger eigenvalue if (S T^-1)(0, 0) >= (S T^-1)(1, 1), otherwise the smaller: a nearly
397 // triangular block then keeps its diagonal order. That difference has the sign of
398 // (A(0, 0) B(1, 1) - A(1, 1) B(0, 0) + A(1, 0) B(0, 1)) c2.
399 const bool deflateLarger = (A(0, 0) * B(1, 1) - A(1, 1) * B(0, 0) + A(1, 0) * B(0, 1)) * c2 >= Scalar(0);
400 Scalar w = r, beta = c2;
401 if (!numext::is_exactly_zero(r) && deflateLarger != firstIsLarger) {
402 w = c0;
403 beta = r;
404 }
405 // The eigenvalue is (alpha, sigma_b beta), |sigma_b| = 1.
406 const Scalar alpha = w + sigmaA * beta;
407 const Matrix2s H = beta * D - w * B;
408
409 JRs G;
410 if (H.row(0).cwiseAbs().maxCoeff() >= H.row(1).cwiseAbs().maxCoeff())
411 G.makeGivens(H(0, 1), -H(0, 0));
412 else
413 G.makeGivens(H(1, 1), -H(1, 0));
414 m_S.topRows(i + 2).applyOnTheRight(i, i + 1, G);
415 m_T.topRows(i + 2).applyOnTheRight(i, i + 1, G);
416 if (m_computeQZ) m_Z.applyOnTheLeft(i, i + 1, G.adjoint());
417
418 if (numext::abs(beta) >= numext::abs(alpha))
419 G.makeGivens(m_T.coeff(i, i), m_T.coeff(i + 1, i));
420 else
421 G.makeGivens(m_S.coeff(i, i), m_S.coeff(i + 1, i));
422 m_S.rightCols(dim - i).applyOnTheLeft(i, i + 1, G.adjoint());
423 m_T.rightCols(dim - i).applyOnTheLeft(i, i + 1, G.adjoint());
424 if (m_computeQZ) m_Q.applyOnTheRight(i, i + 1, G);
425
426 m_S.coeffRef(i + 1, i) = Scalar(0.0);
427 m_T.coeffRef(i + 1, i) = Scalar(0.0);
428 }
429 } else {
430 pushDownZero(j, i, i + 1);
431 }
432}
433
435template <typename MatrixType>
436inline void RealQZ<MatrixType>::pushDownZero(Index z, Index f, Index l) {
437 JRs G;
438 const Index dim = m_S.cols();
439 for (Index zz = z; zz < l; zz++) {
440 // push 0 down
441 Index firstColS = zz > f ? (zz - 1) : zz;
442 G.makeGivens(m_T.coeff(zz, zz + 1), m_T.coeff(zz + 1, zz + 1));
443 m_S.rightCols(dim - firstColS).applyOnTheLeft(zz, zz + 1, G.adjoint());
444 m_T.rightCols(dim - zz).applyOnTheLeft(zz, zz + 1, G.adjoint());
445 m_T.coeffRef(zz + 1, zz + 1) = Scalar(0.0);
446 // update Q
447 if (m_computeQZ) m_Q.applyOnTheRight(zz, zz + 1, G);
448 // kill S(zz+1, zz-1)
449 if (zz > f) {
450 G.makeGivens(m_S.coeff(zz + 1, zz), m_S.coeff(zz + 1, zz - 1));
451 m_S.topRows(zz + 2).applyOnTheRight(zz, zz - 1, G);
452 m_T.topRows(zz + 1).applyOnTheRight(zz, zz - 1, G);
453 m_S.coeffRef(zz + 1, zz - 1) = Scalar(0.0);
454 // update Z
455 if (m_computeQZ) m_Z.applyOnTheLeft(zz, zz - 1, G.adjoint());
456 }
457 }
458 // finally kill S(l,l-1)
459 G.makeGivens(m_S.coeff(l, l), m_S.coeff(l, l - 1));
460 m_S.applyOnTheRight(l, l - 1, G);
461 m_T.applyOnTheRight(l, l - 1, G);
462 m_S.coeffRef(l, l - 1) = Scalar(0.0);
463 // update Z
464 if (m_computeQZ) m_Z.applyOnTheLeft(l, l - 1, G.adjoint());
465}
466
468template <typename MatrixType>
469inline void RealQZ<MatrixType>::step(Index f, Index l, Index iter, internal::inverse_iteration_rng* randomShift) {
470 const Index dim = m_S.cols();
471
472 // x, y, z
473 Scalar x, y, z;
474 if (iter == 10) {
475 // Wilkinson ad hoc shift
476 const Scalar a11 = m_S.coeff(f + 0, f + 0), a12 = m_S.coeff(f + 0, f + 1), a21 = m_S.coeff(f + 1, f + 0),
477 a22 = m_S.coeff(f + 1, f + 1), a32 = m_S.coeff(f + 2, f + 1), b12 = m_T.coeff(f + 0, f + 1),
478 b11i = Scalar(1.0) / m_T.coeff(f + 0, f + 0), b22i = Scalar(1.0) / m_T.coeff(f + 1, f + 1),
479 a87 = m_S.coeff(l - 1, l - 2), a98 = m_S.coeff(l - 0, l - 1),
480 b77i = Scalar(1.0) / m_T.coeff(l - 2, l - 2), b88i = Scalar(1.0) / m_T.coeff(l - 1, l - 1);
481 Scalar ss = numext::abs(a87 * b77i) + numext::abs(a98 * b88i), lpl = Scalar(1.5) * ss, ll = ss * ss;
482 x = ll + a11 * a11 * b11i * b11i - lpl * a11 * b11i + a12 * a21 * b11i * b22i -
483 a11 * a21 * b12 * b11i * b11i * b22i;
484 y = a11 * a21 * b11i * b11i - lpl * a21 * b11i + a21 * a22 * b11i * b22i - a21 * a21 * b12 * b11i * b11i * b22i;
485 z = a21 * a32 * b11i * b22i;
486 } else if (iter == 16) {
487 // another exceptional shift
488 x = m_S.coeff(f, f) / m_T.coeff(f, f) - m_S.coeff(l, l) / m_T.coeff(l, l) +
489 m_S.coeff(l, l - 1) * m_T.coeff(l - 1, l) / (m_T.coeff(l - 1, l - 1) * m_T.coeff(l, l));
490 y = m_S.coeff(f + 1, f) / m_T.coeff(f, f);
491 z = 0;
492 } else if (randomShift) {
493 // extremely exceptional shift
494 x = Scalar(randomShift->next<double>());
495 y = Scalar(randomShift->next<double>());
496 z = Scalar(randomShift->next<double>());
497 } else {
498 // Compute the shifts: (x,y,z,0...) = (AB^-1 - l1 I) (AB^-1 - l2 I) e1
499 // where l1 and l2 are the eigenvalues of the 2x2 matrix C = U V^-1 where
500 // U and V are 2x2 bottom right sub matrices of A and B. Thus:
501 // = AB^-1AB^-1 + l1 l2 I - (l1+l2)(AB^-1)
502 // = AB^-1AB^-1 + det(M) - tr(M)(AB^-1)
503 // Since we are only interested in having x, y, z with a correct ratio, we have:
504 const Scalar a11 = m_S.coeff(f, f), a12 = m_S.coeff(f, f + 1), a21 = m_S.coeff(f + 1, f),
505 a22 = m_S.coeff(f + 1, f + 1), a32 = m_S.coeff(f + 2, f + 1),
506
507 a88 = m_S.coeff(l - 1, l - 1), a89 = m_S.coeff(l - 1, l), a98 = m_S.coeff(l, l - 1),
508 a99 = m_S.coeff(l, l),
509
510 b11 = m_T.coeff(f, f), b12 = m_T.coeff(f, f + 1), b22 = m_T.coeff(f + 1, f + 1),
511
512 b88 = m_T.coeff(l - 1, l - 1), b89 = m_T.coeff(l - 1, l), b99 = m_T.coeff(l, l);
513
514 x = ((a88 / b88 - a11 / b11) * (a99 / b99 - a11 / b11) - (a89 / b99) * (a98 / b88) +
515 (a98 / b88) * (b89 / b99) * (a11 / b11)) *
516 (b11 / a21) +
517 a12 / b22 - (a11 / b11) * (b12 / b22);
518 y = (a22 / b22 - a11 / b11) - (a21 / b11) * (b12 / b22) - (a88 / b88 - a11 / b11) - (a99 / b99 - a11 / b11) +
519 (a98 / b88) * (b89 / b99);
520 z = a32 / b22;
521 // S(f+1, f) is not negligible, but it can be tiny against the rest of the block, and dividing by it then overflows
522 // x. Only the direction of (x, y, z) matters: multiplied by a21 / b11, no term divides by a21.
523 if (!(numext::isfinite)(x)) {
524 const Scalar scale = a21 / b11;
525 x = (a88 / b88 - a11 / b11) * (a99 / b99 - a11 / b11) - (a89 / b99) * (a98 / b88) +
526 (a98 / b88) * (b89 / b99) * (a11 / b11) + (a12 / b22 - (a11 / b11) * (b12 / b22)) * scale;
527 y *= scale;
528 z *= scale;
529 }
530 }
531
532 JRs G;
533
534 for (Index k = f; k <= l - 2; k++) {
535 // variables for Householder reflections
536 Vector2s essential2;
537 Scalar tau, beta;
538
539 Vector3s hr(x, y, z);
540
541 // Q_k to annihilate S(k+1,k-1) and S(k+2,k-1)
542 hr.makeHouseholderInPlace(tau, beta);
543 essential2 = hr.template bottomRows<2>();
544 Index fc = (std::max)(k - 1, Index(0)); // first col to update
545 m_S.template middleRows<3>(k).rightCols(dim - fc).applyHouseholderOnTheLeft(essential2, tau, m_workspace.data());
546 m_T.template middleRows<3>(k).rightCols(dim - fc).applyHouseholderOnTheLeft(essential2, tau, m_workspace.data());
547 if (m_computeQZ) m_Q.template middleCols<3>(k).applyHouseholderOnTheRight(essential2, tau, m_workspace.data());
548 if (k > f) m_S.coeffRef(k + 2, k - 1) = m_S.coeffRef(k + 1, k - 1) = Scalar(0.0);
549
550 // Z_{k1} to annihilate T(k+2,k+1) and T(k+2,k)
551 hr << m_T.coeff(k + 2, k + 2), m_T.coeff(k + 2, k), m_T.coeff(k + 2, k + 1);
552 hr.makeHouseholderInPlace(tau, beta);
553 essential2 = hr.template bottomRows<2>();
554 {
555 Index lr = (std::min)(k + 4, dim); // last row to update
556 Map<Matrix<Scalar, Dynamic, 1> > tmp(m_workspace.data(), lr);
557 // S
558 tmp.noalias() = m_S.template middleCols<2>(k).topRows(lr) * essential2;
559 tmp += m_S.col(k + 2).head(lr);
560 m_S.col(k + 2).head(lr) -= tau * tmp;
561 m_S.template middleCols<2>(k).topRows(lr).noalias() -= (tau * tmp) * essential2.adjoint();
562 // T
563 tmp.noalias() = m_T.template middleCols<2>(k).topRows(lr) * essential2;
564 tmp += m_T.col(k + 2).head(lr);
565 m_T.col(k + 2).head(lr) -= tau * tmp;
566 m_T.template middleCols<2>(k).topRows(lr).noalias() -= (tau * tmp) * essential2.adjoint();
567 }
568 if (m_computeQZ) {
569 // Z
570 Map<Matrix<Scalar, 1, Dynamic> > tmp(m_workspace.data(), dim);
571 tmp.noalias() = essential2.adjoint() * (m_Z.template middleRows<2>(k));
572 tmp += m_Z.row(k + 2);
573 m_Z.row(k + 2) -= tau * tmp;
574 m_Z.template middleRows<2>(k).noalias() -= essential2 * (tau * tmp);
575 }
576 m_T.coeffRef(k + 2, k) = m_T.coeffRef(k + 2, k + 1) = Scalar(0.0);
577
578 // Z_{k2} to annihilate T(k+1,k)
579 G.makeGivens(m_T.coeff(k + 1, k + 1), m_T.coeff(k + 1, k));
580 m_S.applyOnTheRight(k + 1, k, G);
581 m_T.applyOnTheRight(k + 1, k, G);
582 // update Z
583 if (m_computeQZ) m_Z.applyOnTheLeft(k + 1, k, G.adjoint());
584 m_T.coeffRef(k + 1, k) = Scalar(0.0);
585
586 // update x,y,z
587 x = m_S.coeff(k + 1, k);
588 y = m_S.coeff(k + 2, k);
589 if (k < l - 2) z = m_S.coeff(k + 3, k);
590 } // loop over k
591
592 // Q_{n-1} to annihilate y = S(l,l-2)
593 G.makeGivens(x, y);
594 m_S.applyOnTheLeft(l - 1, l, G.adjoint());
595 m_T.applyOnTheLeft(l - 1, l, G.adjoint());
596 if (m_computeQZ) m_Q.applyOnTheRight(l - 1, l, G);
597 m_S.coeffRef(l, l - 2) = Scalar(0.0);
598
599 // Z_{n-1} to annihilate T(l,l-1)
600 G.makeGivens(m_T.coeff(l, l), m_T.coeff(l, l - 1));
601 m_S.applyOnTheRight(l, l - 1, G);
602 m_T.applyOnTheRight(l, l - 1, G);
603 if (m_computeQZ) m_Z.applyOnTheLeft(l, l - 1, G.adjoint());
604 m_T.coeffRef(l, l - 1) = Scalar(0.0);
605}
606
607template <typename MatrixType>
608template <typename InputTypeA, typename InputTypeB>
610 bool computeQZ) {
611 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(A_in, "Need square matrices of the same dimension");
612 EIGEN_INTERNAL_ASSERT_SAME_SHAPE_MSG(A_in, B_in, "Need square matrices of the same dimension");
613 m_S = A_in.derived();
614 m_T = B_in.derived();
615 return computeInPlace(computeQZ);
616}
617
619template <typename MatrixType>
620RealQZ<MatrixType>& RealQZ<MatrixType>::computeInPlace(bool computeQZ) {
621 const Index dim = m_S.cols();
622
623 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_S, "Need square matrices of the same dimension");
624 EIGEN_INTERNAL_ASSERT_SAME_SHAPE_MSG(m_S, m_T, "Need square matrices of the same dimension");
625
626 m_isInitialized = true;
627 m_computeQZ = computeQZ;
628 m_workspace.resize(dim * 2);
629 m_global_iter = 0;
630
631 // Scale S and T separately by powers of two near their largest coefficients, as RealSchur does, so that the iteration
632 // neither overflows nor underflows. The scaling is exact: it leaves Q and Z unchanged and is undone on S and T.
633 using Scaling = internal::safe_scaling<Scalar>;
634 const Scalar maxS =
635 dim == 0 ? Scalar(0) : Scaling::recover_flushed_max_coeff(m_S, m_S.cwiseAbs().template maxCoeff<PropagateNaN>());
636 const Scalar maxT =
637 dim == 0 ? Scalar(0) : Scaling::recover_flushed_max_coeff(m_T, m_T.cwiseAbs().template maxCoeff<PropagateNaN>());
638 const internal::safe_scaling_factors<Scalar> factorsS = Scaling::scale_in_place(m_S, maxS);
639 const internal::safe_scaling_factors<Scalar> factorsT = Scaling::scale_in_place(m_T, maxT);
640
641 // entrance point: hessenberg triangular decomposition
642 hessenbergTriangular();
643 // compute the L1 vector norm of T into m_normOfT
644 computeNorms();
645
646 Index l = dim - 1, f, local_iter = 0;
647 // Pseudo-random shifts from a generator seeded per call, so that the result does not depend on global state. They
648 // are tried every 8 steps from the 24th on, but taken only while the iteration stagnates: while the smaller of the
649 // subdiagonal entries at which the bottom deflates has not shrunk 16-fold over the last 7 steps. A defective
650 // eigenvalue converges linearly, about 4-fold per step, and a random shift would restart it.
651 internal::inverse_iteration_rng shiftRng(1);
652 Scalar bottomAfterTry = NumTraits<Scalar>::highest();
653
654 while (l > 0) {
655 f = findSmallSubdiagEntry(l);
656 // now rows and columns f..l (including) decouple from the rest of the problem
657 if (f > 0) m_S.coeffRef(f, f - 1) = Scalar(0.0);
658 if (f == l) // One root found
659 {
660 l--;
661 local_iter = 0;
662 } else if (f == l - 1) // Two roots found
663 {
664 splitOffTwoRows(f);
665 l -= 2;
666 local_iter = 0;
667 } else // No convergence yet
668 {
669 // The limit is checked before a step rather than before the deflation test, so a deflation the last allowed
670 // step produces is still found.
671 if (local_iter >= m_maxIters) break;
672 const Scalar bottom = numext::mini(numext::abs(m_S.coeff(l, l - 1)), numext::abs(m_S.coeff(l - 1, l - 2)));
673 const bool stagnating = local_iter >= 24 && local_iter % 8 == 0 && !(bottom < bottomAfterTry / Scalar(16));
674 if (local_iter % 8 == 1) bottomAfterTry = bottom;
675 // if there's zero on diagonal of T, we can isolate an eigenvalue with Givens rotations
676 Index z = findSmallDiagEntry(f, l);
677 if (z >= f) {
678 // zero found
679 pushDownZero(z, f, l);
680 } else {
681 // We are sure now that S.block(f,f, l-f+1,l-f+1) is unreduced upper-Hessenberg
682 // and T.block(f,f, l-f+1,l-f+1) is invertible upper-triangular, which allows to
683 // apply a QR-like iteration to rows and columns f..l.
684 step(f, l, local_iter, stagnating ? &shiftRng : nullptr);
685 // count QR-like steps
686 m_global_iter++;
687 }
688 // count iterations toward m_maxIters
689 local_iter++;
690 }
691 }
692 m_info = l > 0 ? NoConvergence : Success;
693
694 // For each non triangular 2x2 diagonal block of S,
695 // reduce the respective 2x2 diagonal block of T to positive diagonal form using 2x2 SVD.
696 // This step is not mandatory for QZ, but it does help further extraction of eigenvalues/eigenvectors,
697 // and is in par with Lapack/Matlab QZ.
698 if (m_info == Success) {
699 for (Index i = 0; i < dim - 1; ++i) {
700 if (!numext::is_exactly_zero(m_S.coeff(i + 1, i))) {
701 JacobiRotation<Scalar> j_left, j_right;
702 internal::real_2x2_jacobi_svd(m_T, i, i + 1, &j_left, &j_right);
703
704 // Apply resulting Jacobi rotations
705 m_S.applyOnTheLeft(i, i + 1, j_left);
706 m_S.applyOnTheRight(i, i + 1, j_right);
707 m_T.applyOnTheLeft(i, i + 1, j_left);
708 m_T.applyOnTheRight(i, i + 1, j_right);
709 m_T(i + 1, i) = m_T(i, i + 1) = Scalar(0);
710
711 if (m_computeQZ) {
712 m_Q.applyOnTheRight(i, i + 1, j_left.transpose());
713 m_Z.applyOnTheLeft(i, i + 1, j_right.transpose());
714 }
715
716 i++;
717 }
718 }
719 }
720
721 // The QZ sweep restores T's triangularity only up to rounding, so its strictly lower triangle
722 // can retain entries of order eps*||T||. matrixT() is documented upper triangular; make it so,
723 // as the deflation above already does for the subdiagonal of S.
724 m_T.template triangularView<StrictlyLower>().setZero();
725
726 Scaling::unscale_in_place(m_S, maxS, factorsS);
727 Scaling::unscale_in_place(m_T, maxT, factorsT);
728 // Where Q^T A Z or Q^T B Z is not representable, unscaling overflows; Success has to mean that S and T are usable.
729 if (m_info == Success && !(m_S.allFinite() && m_T.allFinite())) m_info = NumericalIssue;
730 return *this;
731} // end compute
732
733} // end namespace Eigen
734
735#endif // EIGEN_REAL_QZ_H
Rotation given by a cosine-sine pair.
Definition Jacobi.h:39
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Performs a real QZ decomposition of a pair of square matrices.
Definition RealQZ.h:62
RealQZ(EigenBase< InputTypeA > &A, EigenBase< InputTypeB > &B, bool computeQZ=true)
Constructor for inplace decomposition .
Definition RealQZ.h:139
const MatrixType & matrixT() const
Returns matrix S in the QZ decomposition.
Definition RealQZ.h:185
const MatrixType & matrixS() const
Returns matrix S in the QZ decomposition.
Definition RealQZ.h:176
Index iterations() const
Returns number of performed QR-like iterations.
Definition RealQZ.h:213
Eigen::Index Index
Definition RealQZ.h:74
const PlainMatrixType & matrixQ() const
Returns matrix Q in the QZ decomposition.
Definition RealQZ.h:156
ComputationInfo info() const
Reports whether previous computation was successful.
Definition RealQZ.h:206
Matrix< Scalar, RowsAtCompileTime, ColsAtCompileTime, Options, MaxRowsAtCompileTime, MaxColsAtCompileTime > PlainMatrixType
Type of the matrices returned by matrixQ() and matrixZ(): a plain matrix with the shape and storage o...
Definition RealQZ.h:81
const PlainMatrixType & matrixZ() const
Returns matrix Z in the QZ decomposition.
Definition RealQZ.h:166
RealQZ & compute(const EigenBase< InputTypeA > &A, const EigenBase< InputTypeB > &B, bool computeQZ=true)
Computes QZ decomposition of given matrix.
RealQZ(Index size=RowsAtCompileTime==Dynamic ? 1 :RowsAtCompileTime)
Default constructor.
Definition RealQZ.h:95
RealQZ(const EigenBase< InputTypeA > &A, const EigenBase< InputTypeB > &B, bool computeQZ=true)
Constructor; computes real QZ decomposition of given matrices.
Definition RealQZ.h:115
RealQZ & setMaxIterations(Index maxIters)
Definition RealQZ.h:221
HouseholderSequence< VectorsType, CoeffsType > householderSequence(const VectorsType &v, const CoeffsType &h)
Convenience function for constructing a Householder sequence.
Definition HouseholderSequence.h:739
ComputationInfo
Definition Constants.h:455
@ PropagateNaN
Definition Constants.h:343
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34