NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
generalized.hpp
Go to the documentation of this file.
1
8#ifndef NUMERICAL_GENERALIZED_HPP
9#define NUMERICAL_GENERALIZED_HPP
10
11#include <algorithm>
12#include <array>
13#include <cmath>
14#include <complex>
15#include <concepts>
16#include <cstddef>
17#include <functional>
18#include <initializer_list>
19#include <limits>
20#include <optional>
21#include <stdexcept>
22#include <string>
23#include <type_traits>
24#include <utility>
25#include <vector>
26
27#include "matrix_functions.hpp"
28#include "svd.hpp"
29
30namespace numerical {
31
32 namespace detail {
33
35 [[nodiscard]] inline double modulus_one(const std::complex<double>& z)
36 {
37 return std::abs(z.real()) + std::abs(z.imag());
38 }
39
44 struct qz_form
45 {
46 std::size_t n {0};
51
53 [[nodiscard]] std::complex<double>& h(std::size_t i,
54 std::size_t j)
55 {
56 return s[((i - 1) * n) + (j - 1)];
57 }
58
60 [[nodiscard]] std::complex<double>& b(std::size_t i,
61 std::size_t j)
62 {
63 return t[((i - 1) * n) + (j - 1)];
64 }
65
67 static void rotate_rows(buffer<std::complex<double>>& m,
68 std::size_t n,
69 std::size_t i,
70 std::size_t first,
71 std::size_t last,
72 double c,
73 const std::complex<double>& sine)
74 {
75 if (first <= last) {
76 rotate_pair(m.data() + ((i - 1) * n) + (first - 1), m.data() + (i * n) + (first - 1), last - first + 1, 1, c, sine);
77 }
78 }
79
82 static void rotate_columns(buffer<std::complex<double>>& m,
83 std::size_t n,
84 std::size_t j,
85 std::size_t k,
86 std::size_t first,
87 std::size_t last,
88 double c,
89 const std::complex<double>& sine)
90 {
91 rotate_pair(m.data() + ((first - 1) * n) + (j - 1), m.data() + ((first - 1) * n) + (k - 1), last - first + 1, n, c, sine);
92 }
93
96 static void rotate_vectors(buffer<std::complex<double>>& mt,
97 std::size_t n,
98 std::size_t j,
99 std::size_t k,
100 double c,
101 const std::complex<double>& sine)
102 {
103 rotate_pair(mt.data() + ((j - 1) * n), mt.data() + ((k - 1) * n), n, 1, c, sine);
104 }
105 };
106
113 [[nodiscard]] inline qz_form hessenberg_triangular(const matrix<std::complex<double>>& a,
114 const matrix<std::complex<double>>& b)
115 {
116 using C = std::complex<double>;
117 const std::size_t n {a.rows()};
118 const qr_decomposition<C> factor {b, qr_mode::complete};
119 const matrix<C> q {factor.q()};
120 const matrix<C> r {factor.r()};
122 form.n = n;
123 form.t = buffer<C>(r.begin(), r.end());
124 const matrix<C> s {adjoint_of(q) * a};
125 form.s = buffer<C>(s.begin(), s.end());
126 const matrix<C> qt {transpose(q)};
127 form.qt = buffer<C>(qt.begin(), qt.end());
128 form.zt = buffer<C>(n * n, C {});
129 for (std::size_t i {0}; i < n; ++i) {
130 form.zt[(i * n) + i] = C {1.0};
131 }
132 for (std::size_t column {1}; column + 2 <= n; ++column) {
133 for (std::size_t row {n}; row >= column + 2; --row) {
134 // rows row − 1 and row take out A(row, column)
135 const plane_rotation<C> g {givens(form.h(row - 1, column), form.h(row, column))};
136 form.h(row - 1, column) = g.r;
137 form.h(row, column) = C {};
138 qz_form::rotate_rows(form.s, n, row - 1, column + 1, n, g.c, g.s);
139 qz_form::rotate_rows(form.t, n, row - 1, row - 1, n, g.c, g.s);
140 qz_form::rotate_vectors(form.qt, n, row - 1, row, g.c, std::conj(g.s));
141 // columns row and row − 1 take out the fill B(row, row − 1)
142 const plane_rotation<C> h {givens(form.b(row, row), form.b(row, row - 1))};
143 form.b(row, row) = h.r;
144 form.b(row, row - 1) = C {};
145 qz_form::rotate_columns(form.s, n, row, row - 1, 1, n, h.c, h.s);
146 qz_form::rotate_columns(form.t, n, row, row - 1, 1, row - 1, h.c, h.s);
147 qz_form::rotate_vectors(form.zt, n, row, row - 1, h.c, h.s);
148 }
149 }
150 return form;
151 }
152
155 inline std::pair<std::complex<double>, std::complex<double>> standardize(qz_form& f,
156 std::size_t j)
157 {
158 using C = std::complex<double>;
159 const std::size_t n {f.n};
160 const double size {std::abs(f.b(j, j))};
161 if (size > std::numeric_limits<double>::min()) {
162 const C sign {std::conj(f.b(j, j) / size)};
163 f.b(j, j) = C {size};
164 for (std::size_t i {1}; i < j; ++i) {
165 f.b(i, j) *= sign;
166 }
167 for (std::size_t i {1}; i <= j; ++i) {
168 f.h(i, j) *= sign;
169 }
170 for (std::size_t i {1}; i <= n; ++i) {
171 f.zt[((j - 1) * n) + (i - 1)] *= sign;
172 }
173 }
174 else {
175 f.b(j, j) = C {};
176 }
177 return {f.h(j, j), f.b(j, j)};
178 }
179
189 [[nodiscard]] inline std::vector<std::pair<std::complex<double>, std::complex<double>>> qz_iteration(qz_form& f,
190 std::size_t steps)
191 {
192 using C = std::complex<double>;
193 const std::size_t n {f.n};
194 std::vector<std::pair<C, C>> values(n);
195 if (n == 0) {
196 return values;
197 }
198 const double safmin {std::numeric_limits<double>::min()};
199 const double ulp {std::numeric_limits<double>::epsilon()};
200 double anorm {0.0};
201 double bnorm {0.0};
202 for (std::size_t i {1}; i <= n; ++i) {
203 for (std::size_t j {i > 1 ? i - 1 : 1}; j <= n; ++j) {
204 anorm += std::norm(f.h(i, j));
205 }
206 for (std::size_t j {i}; j <= n; ++j) {
207 bnorm += std::norm(f.b(i, j));
208 }
209 }
210 anorm = std::sqrt(anorm);
211 bnorm = std::sqrt(bnorm);
212 const double atol {std::max(safmin, ulp * anorm)};
213 const double btol {std::max(safmin, ulp * bnorm)};
214 const double ascale {1.0 / std::max(safmin, anorm)};
215 const double bscale {1.0 / std::max(safmin, bnorm)};
216 std::size_t ilast {n};
217 std::size_t ifirst {1};
218 std::size_t iiter {0};
219 C eshift {};
220 const auto rotation_left = [&](std::size_t row, std::size_t first, double c, const C& sine) { // rows row, row + 1 of S and T
221 qz_form::rotate_rows(f.s, n, row, first, n, c, sine);
222 qz_form::rotate_rows(f.t, n, row, first, n, c, sine);
223 qz_form::rotate_vectors(f.qt, n, row, row + 1, c, std::conj(sine));
224 };
225 for (std::size_t jiter {0}; jiter < steps; ++jiter) {
226 // the case to take: 0 a QZ step on ifirst…ilast, 1 T(ilast, ilast) zero, 2 a 1 × 1 block split at ilast
227 int action {0};
228 if (ilast == 1) {
229 action = 2;
230 }
231 else if (modulus_one(f.h(ilast, ilast - 1)) <= std::max(safmin, ulp * (modulus_one(f.h(ilast, ilast)) + modulus_one(f.h(ilast - 1, ilast - 1))))) {
232 f.h(ilast, ilast - 1) = C {};
233 action = 2;
234 }
235 else if (std::abs(f.b(ilast, ilast)) <= btol) {
236 f.b(ilast, ilast) = C {};
237 action = 1;
238 }
239 else {
240 for (std::size_t j {ilast - 1};; --j) { // every case ends the search at j = 1 at the latest
241 bool ilazro {false};
242 if (j == 1) {
243 ilazro = true;
244 }
245 else if (modulus_one(f.h(j, j - 1)) <= std::max(safmin, ulp * (modulus_one(f.h(j, j)) + modulus_one(f.h(j - 1, j - 1))))) {
246 f.h(j, j - 1) = C {};
247 ilazro = true;
248 }
249 if (std::abs(f.b(j, j)) < btol) {
250 f.b(j, j) = C {};
251 bool ilazr2 {false};
252 if (!ilazro && modulus_one(f.h(j, j - 1)) * (ascale * modulus_one(f.h(j + 1, j))) <= modulus_one(f.h(j, j)) * (ascale * atol)) {
253 ilazr2 = true;
254 }
255 if (ilazro || ilazr2) { // split a 1 × 1 block off at the top, the zero of T chased down
256 bool settled {false};
257 for (std::size_t jch {j}; jch < ilast; ++jch) {
258 const plane_rotation<C> g {givens(f.h(jch, jch), f.h(jch + 1, jch))};
259 f.h(jch, jch) = g.r;
260 f.h(jch + 1, jch) = C {};
261 qz_form::rotate_rows(f.s, n, jch, jch + 1, n, g.c, g.s);
262 qz_form::rotate_rows(f.t, n, jch, jch + 1, n, g.c, g.s);
263 qz_form::rotate_vectors(f.qt, n, jch, jch + 1, g.c, std::conj(g.s));
264 if (ilazr2) {
265 f.h(jch, jch - 1) *= g.c;
266 }
267 ilazr2 = false;
268 if (modulus_one(f.b(jch + 1, jch + 1)) >= btol) {
269 if (jch + 1 >= ilast) {
270 action = 2;
271 }
272 else {
273 ifirst = jch + 1;
274 action = 0;
275 }
276 settled = true;
277 break;
278 }
279 f.b(jch + 1, jch + 1) = C {};
280 }
281 if (!settled) {
282 action = 1;
283 }
284 break;
285 }
286 // only T(j, j) zero: chase it to T(ilast, ilast)
287 for (std::size_t jch {j}; jch < ilast; ++jch) {
288 const plane_rotation<C> g {givens(f.b(jch, jch + 1), f.b(jch + 1, jch + 1))};
289 f.b(jch, jch + 1) = g.r;
290 f.b(jch + 1, jch + 1) = C {};
291 qz_form::rotate_rows(f.t, n, jch, jch + 2, n, g.c, g.s);
292 qz_form::rotate_rows(f.s, n, jch, jch - 1, n, g.c, g.s);
293 qz_form::rotate_vectors(f.qt, n, jch, jch + 1, g.c, std::conj(g.s));
294 const plane_rotation<C> h {givens(f.h(jch + 1, jch), f.h(jch + 1, jch - 1))};
295 f.h(jch + 1, jch) = h.r;
296 f.h(jch + 1, jch - 1) = C {};
297 qz_form::rotate_columns(f.s, n, jch, jch - 1, 1, jch, h.c, h.s);
298 qz_form::rotate_columns(f.t, n, jch, jch - 1, 1, jch - 1, h.c, h.s);
299 qz_form::rotate_vectors(f.zt, n, jch, jch - 1, h.c, h.s);
300 }
301 action = 1;
302 break;
303 }
304 if (ilazro) { // only S's subdivision: a QZ step on j…ilast
305 ifirst = j;
306 action = 0;
307 break;
308 }
309 }
310 }
311 if (action == 1) { // T(ilast, ilast) zero: clear S(ilast, ilast − 1) to split a 1 × 1 block
312 const plane_rotation<C> g {givens(f.h(ilast, ilast), f.h(ilast, ilast - 1))};
313 f.h(ilast, ilast) = g.r;
314 f.h(ilast, ilast - 1) = C {};
315 qz_form::rotate_columns(f.s, n, ilast, ilast - 1, 1, ilast - 1, g.c, g.s);
316 qz_form::rotate_columns(f.t, n, ilast, ilast - 1, 1, ilast - 1, g.c, g.s);
317 qz_form::rotate_vectors(f.zt, n, ilast, ilast - 1, g.c, g.s);
318 action = 2;
319 }
320 if (action == 2) { // a 1 × 1 block: its eigenvalue, then the next block
321 values[ilast - 1] = standardize(f, ilast);
322 if (ilast == 1) {
323 return values;
324 }
325 --ilast;
326 iiter = 0;
327 eshift = C {};
328 continue;
329 }
330 // a QZ step on ifirst…ilast
331 ++iiter;
332 C shift {};
333 if (iiter % 10 != 0) { // the eigenvalue of the trailing 2 × 2 of S T⁻¹ nearer its corner
334 const C u12 {(bscale * f.b(ilast - 1, ilast)) / (bscale * f.b(ilast, ilast))};
335 const C ad11 {(ascale * f.h(ilast - 1, ilast - 1)) / (bscale * f.b(ilast - 1, ilast - 1))};
336 const C ad21 {(ascale * f.h(ilast, ilast - 1)) / (bscale * f.b(ilast - 1, ilast - 1))};
337 const C ad12 {(ascale * f.h(ilast - 1, ilast)) / (bscale * f.b(ilast, ilast))};
338 const C ad22 {(ascale * f.h(ilast, ilast)) / (bscale * f.b(ilast, ilast))};
339 const C abi22 {ad22 - (u12 * ad21)};
340 const C abi12 {ad12 - (u12 * ad11)};
341 shift = abi22;
342 const C ctemp {std::sqrt(abi12) * std::sqrt(ad21)};
343 double temp {modulus_one(ctemp)};
344 if (ctemp != C {}) {
345 const C x {0.5 * (ad11 - shift)};
346 const double temp2 {modulus_one(x)};
347 temp = std::max(temp, temp2);
348 C y {temp * std::sqrt(((x / temp) * (x / temp)) + ((ctemp / temp) * (ctemp / temp)))};
349 if (temp2 > 0.0 && ((x / temp2).real() * y.real()) + ((x / temp2).imag() * y.imag()) < 0.0) {
350 y = -y;
351 }
352 shift -= ctemp * (ctemp / (x + y));
353 }
354 }
355 else { // exceptional
356 // zhgeqz also asks bscale |T(ilast, ilast)| > safmin here: |T(ilast, ilast)| > btol was found this iteration,
357 // so it is above ulp
358 if (iiter % 20 == 0) {
359 eshift += (ascale * f.h(ilast, ilast)) / (bscale * f.b(ilast, ilast));
360 }
361 else {
362 eshift += (ascale * f.h(ilast, ilast - 1)) / (bscale * f.b(ilast - 1, ilast - 1));
363 }
364 shift = eshift;
365 }
366 // two consecutive small subdiagonal entries: start the sweep below them
367 std::size_t istart {ifirst};
368 C ctemp {(ascale * f.h(ifirst, ifirst)) - (shift * (bscale * f.b(ifirst, ifirst)))};
369 for (std::size_t j {ilast - 1}; j > ifirst; --j) {
370 const C trial {(ascale * f.h(j, j)) - (shift * (bscale * f.b(j, j)))};
371 double temp {modulus_one(trial)};
372 double temp2 {ascale * modulus_one(f.h(j + 1, j))};
373 const double tempr {std::max(temp, temp2)};
374 if (tempr < 1.0) { // tempr > 0: the search just found S(j + 1, j) not negligible (zhgeqz also asks it)
375 temp /= tempr;
376 temp2 /= tempr;
377 }
378 if (modulus_one(f.h(j, j - 1)) * temp2 <= temp * atol) {
379 istart = j;
380 ctemp = trial;
381 break;
382 }
383 }
384 // the implicit-shift sweep
385 const plane_rotation<C> first {givens(ctemp, ascale * f.h(istart + 1, istart))};
386 double c {first.c};
387 C sine {first.s};
388 for (std::size_t j {istart}; j < ilast; ++j) {
389 if (j > istart) {
390 const plane_rotation<C> g {givens(f.h(j, j - 1), f.h(j + 1, j - 1))};
391 f.h(j, j - 1) = g.r;
392 f.h(j + 1, j - 1) = C {};
393 c = g.c;
394 sine = g.s;
395 }
396 rotation_left(j, j, c, sine);
397 const plane_rotation<C> g {givens(f.b(j + 1, j + 1), f.b(j + 1, j))};
398 f.b(j + 1, j + 1) = g.r;
399 f.b(j + 1, j) = C {};
400 qz_form::rotate_columns(f.s, n, j + 1, j, 1, std::min(j + 2, ilast), g.c, g.s);
401 qz_form::rotate_columns(f.t, n, j + 1, j, 1, j, g.c, g.s);
402 qz_form::rotate_vectors(f.zt, n, j + 1, j, g.c, g.s);
403 }
404 }
405 throw convergence_error("QZ: the iterations did not converge (zhgeqz's info)");
406 }
407
409 [[nodiscard]] inline double frobenius_two(const std::array<std::complex<double>, 4>& m)
410 {
411 return std::hypot(std::hypot(std::abs(m[0]), std::abs(m[1])), std::hypot(std::abs(m[2]), std::abs(m[3])));
412 }
413
424 std::size_t j)
425 {
426 using C = std::complex<double>;
427 using block = std::array<C, 4>; // (1,1) (1,2) (2,1) (2,2)
428 const std::size_t n {f.n};
429 const block s0 {f.h(j, j), f.h(j, j + 1), f.h(j + 1, j), f.h(j + 1, j + 1)};
430 const block t0 {f.b(j, j), f.b(j, j + 1), f.b(j + 1, j), f.b(j + 1, j + 1)};
431 const double smlnum {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
432 const double thresha {std::max(20.0 * std::numeric_limits<double>::epsilon() * frobenius_two(s0), smlnum)};
433 const double threshb {std::max(20.0 * std::numeric_limits<double>::epsilon() * frobenius_two(t0), smlnum)};
434 const C ff {(s0[3] * t0[0]) - (t0[3] * s0[0])};
435 const C gg {(s0[3] * t0[1]) - (t0[3] * s0[1])};
436 const plane_rotation<C> z {givens(gg, ff)};
437 const C zs {std::conj(-z.s)};
438 // a block's columns turned by (c, s): column 1 ← c·column 1 + s·column 2, column 2 ← c·column 2 − s̄·column 1
439 const auto columns = [](const block& m, double c, const C& sine) {
440 return block {(c * m[0]) + (sine * m[1]), (c * m[1]) - (std::conj(sine) * m[0]),
441 (c * m[2]) + (sine * m[3]), (c * m[3]) - (std::conj(sine) * m[2])};
442 };
443 // its rows turned by (c, s): row 1 ← c·row 1 + s·row 2, row 2 ← c·row 2 − s̄·row 1
444 const auto rows = [](const block& m, double c, const C& sine) {
445 return block {(c * m[0]) + (sine * m[2]), (c * m[1]) + (sine * m[3]),
446 (c * m[2]) - (std::conj(sine) * m[0]), (c * m[3]) - (std::conj(sine) * m[1])};
447 };
448 const block s1 {columns(s0, z.c, zs)};
449 const block t1 {columns(t0, z.c, zs)};
450 const bool from_s {std::abs(s0[3]) * std::abs(t0[0]) >= std::abs(s0[0]) * std::abs(t0[3])};
451 const plane_rotation<C> q {from_s ? givens(s1[0], s1[2]) : givens(t1[0], t1[2])};
452 const block s2 {rows(s1, q.c, q.s)};
453 const block t2 {rows(t1, q.c, q.s)};
454 if (!(std::abs(s2[2]) <= thresha && std::abs(t2[2]) <= threshb)) { // NaN fails, as LAPACK
455 return false;
456 }
457 const auto residue = [&](const block& now, const block& was) {
458 const block back {columns(rows(now, q.c, -q.s), z.c, -zs)};
459 return frobenius_two(block {back[0] - was[0], back[1] - was[1], back[2] - was[2], back[3] - was[3]});
460 };
461 if (!(residue(s2, s0) <= thresha && residue(t2, t0) <= threshb)) {
462 return false;
463 }
464 qz_form::rotate_columns(f.s, n, j, j + 1, 1, j + 1, z.c, zs);
465 qz_form::rotate_columns(f.t, n, j, j + 1, 1, j + 1, z.c, zs);
466 qz_form::rotate_vectors(f.zt, n, j, j + 1, z.c, zs);
467 qz_form::rotate_rows(f.s, n, j, j, n, q.c, q.s);
468 qz_form::rotate_rows(f.t, n, j, j, n, q.c, q.s);
469 qz_form::rotate_vectors(f.qt, n, j, j + 1, q.c, std::conj(q.s));
470 f.h(j + 1, j) = C {};
471 f.b(j + 1, j) = C {};
472 return true;
473 }
474
480 {
481 std::size_t n {0};
486
488 [[nodiscard]] double& h(std::size_t i,
489 std::size_t j)
490 {
491 return s[((i - 1) * n) + (j - 1)];
492 }
493
495 [[nodiscard]] double& b(std::size_t i,
496 std::size_t j)
497 {
498 return t[((i - 1) * n) + (j - 1)];
499 }
500
504 std::size_t n,
505 std::size_t i,
506 std::size_t k,
507 std::size_t first,
508 std::size_t last,
509 double c,
510 double sine)
511 {
512 for (std::size_t j {first}; j <= last; ++j) {
513 double& x {m[((i - 1) * n) + (j - 1)]};
514 double& y {m[((k - 1) * n) + (j - 1)]};
515 const double t {(c * x) + (sine * y)};
516 y = (c * y) - (sine * x);
517 x = t;
518 }
519 }
520
524 std::size_t n,
525 std::size_t j,
526 std::size_t k,
527 std::size_t first,
528 std::size_t last,
529 double c,
530 double sine)
531 {
532 for (std::size_t i {first}; i <= last; ++i) {
533 double& x {m[((i - 1) * n) + (j - 1)]};
534 double& y {m[((i - 1) * n) + (k - 1)]};
535 const double t {(c * x) + (sine * y)};
536 y = (c * y) - (sine * x);
537 x = t;
538 }
539 }
540 };
541
544 {
545 double ssmin {0.0};
546 double ssmax {0.0};
547 double snr {0.0};
548 double csr {1.0};
549 double snl {0.0};
550 double csl {1.0};
551 };
552
558 double g,
559 double h)
560 {
561 double ft {f};
562 double fa {std::abs(ft)};
563 double ht {h};
564 double ha {std::abs(h)};
565 int pmax {1};
566 const bool swap {ha > fa};
567 if (swap) {
568 pmax = 3;
569 std::swap(ft, ht);
570 std::swap(fa, ha);
571 }
572 const double gt {g};
573 const double ga {std::abs(gt)};
574 double ssmin {0.0};
575 double ssmax {0.0};
576 double clt {1.0};
577 double crt {1.0};
578 double slt {0.0};
579 double srt {0.0};
580 if (ga == 0.0) {
581 ssmin = ha;
582 ssmax = fa;
583 }
584 else {
585 bool gasmal {true};
586 if (ga > fa) {
587 pmax = 2;
588 if (fa / ga < std::numeric_limits<double>::epsilon()) {
589 gasmal = false;
590 ssmax = ga;
591 ssmin = ha > 1.0 ? fa / (ga / ha) : (fa / ga) * ha;
592 clt = 1.0;
593 slt = ht / gt;
594 srt = 1.0;
595 crt = ft / gt;
596 }
597 }
598 if (gasmal) {
599 const double d {fa - ha};
600 double l {d == fa ? 1.0 : d / fa};
601 const double m {gt / ft};
602 double t {2.0 - l};
603 const double mm {m * m};
604 const double tt {t * t};
605 const double s {std::sqrt(tt + mm)};
606 const double r {l == 0.0 ? std::abs(m) : std::sqrt((l * l) + mm)};
607 const double a {0.5 * (s + r)};
608 ssmin = ha / a;
609 ssmax = fa * a;
610 if (mm == 0.0) {
611 t = l == 0.0 ? std::copysign(2.0, ft) * std::copysign(1.0, gt) : (gt / std::copysign(d, ft)) + (m / t);
612 }
613 else {
614 t = ((m / (s + t)) + (m / (r + l))) * (1.0 + a);
615 }
616 l = std::sqrt((t * t) + 4.0);
617 crt = 2.0 / l;
618 srt = t / l;
619 clt = (crt + (srt * m)) / a;
620 slt = (ht / ft) * srt / a;
621 }
622 }
623 triangle_svd out;
624 if (swap) {
625 out.csl = srt;
626 out.snl = crt;
627 out.csr = slt;
628 out.snr = clt;
629 }
630 else {
631 out.csl = clt;
632 out.snl = slt;
633 out.csr = crt;
634 out.snr = srt;
635 }
636 double tsign {1.0};
637 if (pmax == 1) {
638 tsign = std::copysign(1.0, out.csr) * std::copysign(1.0, out.csl) * std::copysign(1.0, f);
639 }
640 else if (pmax == 2) {
641 tsign = std::copysign(1.0, out.snr) * std::copysign(1.0, out.csl) * std::copysign(1.0, g);
642 }
643 else {
644 tsign = std::copysign(1.0, out.snr) * std::copysign(1.0, out.snl) * std::copysign(1.0, h);
645 }
646 out.ssmax = std::copysign(ssmax, tsign);
647 out.ssmin = std::copysign(ssmin, tsign * std::copysign(1.0, f) * std::copysign(1.0, h));
648 return out;
649 }
650
654 {
655 double scale1 {1.0};
656 double scale2 {1.0};
657 double wr1 {0.0};
658 double wr2 {0.0};
659 double wi {0.0};
660 };
661
664 {
665 double floor {0.0};
666 double c2 {0.0};
667 double c3 {0.0};
668 double c4 {0.0};
669 double c5 {0.0};
670 };
671
673 [[nodiscard]] inline double pencil_wsize(const pencil_bounds& b,
674 double w) noexcept
675 {
676 constexpr double fuzzy1 {1.0 + 1.0e-5};
677 return std::max(b.floor, std::max(fuzzy1 * ((w * b.c2) + b.c3), std::min(b.c4, 0.5 * std::max(w, b.c5))));
678 }
679
686 double a12,
687 double a21,
688 double a22,
689 double b11,
690 double b12,
691 double b22,
692 double safmin)
693 {
694 const double rtmin {std::sqrt(safmin)};
695 const double rtmax {1.0 / rtmin};
696 const double safmax {1.0 / safmin};
697 const double anorm {std::max({std::abs(a11) + std::abs(a21), std::abs(a12) + std::abs(a22), safmin})};
698 const double ascale {1.0 / anorm};
699 a11 *= ascale;
700 a21 *= ascale;
701 a12 *= ascale;
702 a22 *= ascale;
703 const double bmin {rtmin * std::max({std::abs(b11), std::abs(b12), std::abs(b22), rtmin})};
704 if (std::abs(b11) < bmin) {
705 b11 = std::copysign(bmin, b11);
706 }
707 if (std::abs(b22) < bmin) {
708 b22 = std::copysign(bmin, b22);
709 }
710 const double bnorm {std::max({std::abs(b11), std::abs(b12) + std::abs(b22), safmin})};
711 const double bsize {std::max(std::abs(b11), std::abs(b22))};
712 const double bscale {1.0 / bsize};
713 b11 *= bscale;
714 b12 *= bscale;
715 b22 *= bscale;
716 const double binv11 {1.0 / b11};
717 const double binv22 {1.0 / b22};
718 const double s1 {a11 * binv11};
719 const double s2 {a22 * binv22};
720 double as12 {0.0};
721 double ss {0.0};
722 double abi22 {0.0};
723 double pp {0.0};
724 double shift {0.0};
725 if (std::abs(s1) <= std::abs(s2)) {
726 as12 = a12 - (s1 * b12);
727 const double as22 {a22 - (s1 * b22)};
728 ss = a21 * (binv11 * binv22);
729 abi22 = (as22 * binv22) - (ss * b12);
730 pp = 0.5 * abi22;
731 shift = s1;
732 }
733 else {
734 as12 = a12 - (s2 * b12);
735 const double as11 {a11 - (s2 * b11)};
736 ss = a21 * (binv11 * binv22);
737 abi22 = -ss * b12;
738 pp = 0.5 * ((as11 * binv11) + abi22);
739 shift = s2;
740 }
741 const double qq {ss * as12};
742 double discr {0.0};
743 double r {0.0};
744 if (std::abs(pp * rtmin) >= 1.0) {
745 discr = ((rtmin * pp) * (rtmin * pp)) + (qq * safmin);
746 r = std::sqrt(std::abs(discr)) * rtmax;
747 }
748 else if ((pp * pp) + std::abs(qq) <= safmin) {
749 discr = ((rtmax * pp) * (rtmax * pp)) + (qq * safmax);
750 r = std::sqrt(std::abs(discr)) * rtmin;
751 }
752 else {
753 discr = (pp * pp) + qq;
754 r = std::sqrt(std::abs(discr));
755 }
756 pencil_pair out;
757 if (discr >= 0.0) { // dlag2 also takes r = 0, which is discr = 0: no square root above underflows to 0
758 const double sum {pp + std::copysign(r, pp)};
759 const double diff {pp - std::copysign(r, pp)};
760 const double wbig {shift + sum};
761 double wsmall {shift + diff};
762 if (0.5 * std::abs(wbig) > std::max(std::abs(wsmall), safmin)) {
763 const double wdet {((a11 * a22) - (a12 * a21)) * (binv11 * binv22)};
764 wsmall = wdet / wbig;
765 }
766 if (pp > abi22) {
767 out.wr1 = std::min(wbig, wsmall);
768 out.wr2 = std::max(wbig, wsmall);
769 }
770 else {
771 out.wr1 = std::max(wbig, wsmall);
772 out.wr2 = std::min(wbig, wsmall);
773 }
774 out.wi = 0.0;
775 }
776 else {
777 out.wr1 = shift + pp;
778 out.wr2 = out.wr1;
779 out.wi = r;
780 }
781 const double c1 {bsize * (safmin * std::max(1.0, ascale))};
782 const double c2 {safmin * std::max(1.0, bnorm)};
783 const double c3 {bsize * safmin};
784 const double c4 {ascale <= 1.0 && bsize <= 1.0 ? std::min(1.0, (ascale / safmin) * bsize) : 1.0};
785 const double c5 {ascale <= 1.0 || bsize <= 1.0 ? std::min(1.0, ascale * bsize) : 1.0};
786 const pencil_bounds bounds {.floor = std::max(safmin, c1), .c2 = c2, .c3 = c3, .c4 = c4, .c5 = c5};
787 const double wabs {std::abs(out.wr1) + std::abs(out.wi)};
788 double wsize {pencil_wsize(bounds, wabs)};
789 if (wsize != 1.0) {
790 const double wscale {1.0 / wsize};
791 out.scale1 = wsize > 1.0 ? (std::max(ascale, bsize) * wscale) * std::min(ascale, bsize) : (std::min(ascale, bsize) * wscale) * std::max(ascale, bsize);
792 out.wr1 *= wscale;
793 if (out.wi != 0.0) {
794 out.wi *= wscale;
795 out.wr2 = out.wr1;
796 out.scale2 = out.scale1;
797 }
798 }
799 else {
800 out.scale1 = ascale * bsize;
801 out.scale2 = out.scale1;
802 }
803 if (out.wi == 0.0) {
804 wsize = pencil_wsize(bounds, std::abs(out.wr2));
805 if (wsize != 1.0) {
806 const double wscale {1.0 / wsize};
807 out.scale2 = wsize > 1.0 ? (std::max(ascale, bsize) * wscale) * std::min(ascale, bsize) : (std::min(ascale, bsize) * wscale) * std::max(ascale, bsize);
808 out.wr2 *= wscale;
809 }
810 else {
811 out.scale2 = ascale * bsize;
812 }
813 }
814 return out;
815 }
816
819 {
820 double alphar {0.0};
821 double alphai {0.0};
822 double beta {0.0};
823 };
824
826 [[nodiscard]] inline double hypot3(double x,
827 double y,
828 double z)
829 {
830 return std::hypot(std::hypot(x, y), z);
831 }
832
838 [[nodiscard]] inline std::pair<real_pencil_value, real_pencil_value> pair_values(real_qz_form& f,
839 std::size_t ilast,
840 const pencil_pair& pair,
841 double b11,
842 double b22)
843 {
844 const double safmin {std::numeric_limits<double>::min()};
845 const double s1 {pair.scale1};
846 const double wr {pair.wr1};
847 const double wi {pair.wi};
848 const double s1inv {1.0 / s1};
849 const double a11 {f.h(ilast - 1, ilast - 1)};
850 const double a21 {f.h(ilast, ilast - 1)};
851 const double a12 {f.h(ilast - 1, ilast)};
852 const double a22 {f.h(ilast, ilast)};
853 const double c11r {(s1 * a11) - (wr * b11)};
854 const double c11i {-wi * b11};
855 const double c12 {s1 * a12};
856 const double c21 {s1 * a21};
857 const double c22r {(s1 * a22) - (wr * b22)};
858 const double c22i {-wi * b22};
859 double cz {0.0};
860 double szr {0.0};
861 double szi {0.0};
862 if (std::abs(c11r) + std::abs(c11i) + std::abs(c12) > std::abs(c21) + std::abs(c22r) + std::abs(c22i)) {
863 const double t1 {hypot3(c12, c11r, c11i)};
864 cz = c12 / t1;
865 szr = -c11r / t1;
866 szi = -c11i / t1;
867 }
868 else {
869 cz = std::hypot(c22r, c22i);
870 if (cz <= safmin) {
871 cz = 0.0;
872 szr = 1.0;
873 szi = 0.0;
874 }
875 else {
876 const double tempr {c22r / cz};
877 const double tempi {c22i / cz};
878 const double t1 {std::hypot(cz, c21)};
879 cz /= t1;
880 szr = -c21 * tempr / t1;
881 szi = c21 * tempi / t1;
882 }
883 }
884 const double an {std::abs(a11) + std::abs(a12) + std::abs(a21) + std::abs(a22)};
885 const double bn {std::abs(b11) + std::abs(b22)};
886 const double wabs {std::abs(wr) + std::abs(wi)};
887 double cq {0.0};
888 double sqr {0.0};
889 double sqi {0.0};
890 if (s1 * an > wabs * bn) {
891 cq = cz * b11;
892 sqr = szr * b22;
893 sqi = -szi * b22;
894 }
895 else {
896 const double a1r {(cz * a11) + (szr * a12)};
897 const double a1i {szi * a12};
898 const double a2r {(cz * a21) + (szr * a22)};
899 const double a2i {szi * a22};
900 cq = std::hypot(a1r, a1i);
901 if (cq <= safmin) {
902 cq = 0.0;
903 sqr = 1.0;
904 sqi = 0.0;
905 }
906 else {
907 const double tempr {a1r / cq};
908 const double tempi {a1i / cq};
909 sqr = (tempr * a2r) + (tempi * a2i);
910 sqi = (tempi * a2r) - (tempr * a2i);
911 }
912 }
913 const double t1 {hypot3(cq, sqr, sqi)};
914 cq /= t1;
915 sqr /= t1;
916 sqi /= t1;
917 const double tempr {(sqr * szr) - (sqi * szi)};
918 const double tempi {(sqr * szi) + (sqi * szr)};
919 const double b1a {std::hypot((cq * cz * b11) + (tempr * b22), tempi * b22)};
920 const double b2a {std::hypot((cq * cz * b22) + (tempr * b11), -tempi * b11)};
921 return {real_pencil_value {(wr * b1a) * s1inv, (wi * b1a) * s1inv, b1a}, real_pencil_value {(wr * b2a) * s1inv, -(wi * b2a) * s1inv, b2a}};
922 }
923
931 std::size_t ifirst,
932 std::size_t ilast,
933 double ascale,
934 double bscale,
935 double safmin)
936 {
937 using form = real_qz_form;
938 const std::size_t n {f.n};
939 const double ad11 {(ascale * f.h(ilast - 1, ilast - 1)) / (bscale * f.b(ilast - 1, ilast - 1))};
940 const double ad21 {(ascale * f.h(ilast, ilast - 1)) / (bscale * f.b(ilast - 1, ilast - 1))};
941 const double ad12 {(ascale * f.h(ilast - 1, ilast)) / (bscale * f.b(ilast, ilast))};
942 const double ad22 {(ascale * f.h(ilast, ilast)) / (bscale * f.b(ilast, ilast))};
943 const double u12 {f.b(ilast - 1, ilast) / f.b(ilast, ilast)};
944 const double ad11l {(ascale * f.h(ifirst, ifirst)) / (bscale * f.b(ifirst, ifirst))};
945 const double ad21l {(ascale * f.h(ifirst + 1, ifirst)) / (bscale * f.b(ifirst, ifirst))};
946 const double ad12l {(ascale * f.h(ifirst, ifirst + 1)) / (bscale * f.b(ifirst + 1, ifirst + 1))};
947 const double ad22l {(ascale * f.h(ifirst + 1, ifirst + 1)) / (bscale * f.b(ifirst + 1, ifirst + 1))};
948 const double ad32l {(ascale * f.h(ifirst + 2, ifirst + 1)) / (bscale * f.b(ifirst + 1, ifirst + 1))};
949 const double u12l {f.b(ifirst, ifirst + 1) / f.b(ifirst + 1, ifirst + 1)};
950 double v[3] {((ad11 - ad11l) * (ad22 - ad11l)) - (ad12 * ad21) + (ad21 * u12 * ad11l) + ((ad12l - (ad11l * u12l)) * ad21l),
951 ((ad22l - ad11l) - (ad21l * u12l) - (ad11 - ad11l) - (ad22 - ad11l) + (ad21 * u12)) * ad21l, ad32l * ad21l};
952 double tau {small_reflector(v, 3)};
953 v[0] = 1.0;
954 for (std::size_t j {ifirst}; j + 2 <= ilast; ++j) {
955 if (j > ifirst) {
956 v[0] = f.h(j, j - 1);
957 v[1] = f.h(j + 1, j - 1);
958 v[2] = f.h(j + 2, j - 1);
959 tau = small_reflector(v, 3);
960 f.h(j, j - 1) = v[0];
961 v[0] = 1.0;
962 f.h(j + 1, j - 1) = 0.0;
963 f.h(j + 2, j - 1) = 0.0;
964 }
965 const double t2 {tau * v[1]};
966 const double t3 {tau * v[2]};
967 for (std::size_t jc {j}; jc <= n; ++jc) { // the reflection of rows j … j + 2 of S and T
968 const double temp {f.h(j, jc) + (v[1] * f.h(j + 1, jc)) + (v[2] * f.h(j + 2, jc))};
969 f.h(j, jc) -= temp * tau;
970 f.h(j + 1, jc) -= temp * t2;
971 f.h(j + 2, jc) -= temp * t3;
972 const double temp2 {f.b(j, jc) + (v[1] * f.b(j + 1, jc)) + (v[2] * f.b(j + 2, jc))};
973 f.b(j, jc) -= temp2 * tau;
974 f.b(j + 1, jc) -= temp2 * t2;
975 f.b(j + 2, jc) -= temp2 * t3;
976 }
977 double* const q0 {f.qt.data() + ((j - 1) * n)}; // Q's columns j … j + 2, rows of Qᵀ
978 double* const q1 {q0 + n};
979 double* const q2 {q1 + n};
980 for (std::size_t r {0}; r < n; ++r) {
981 const double temp {q0[r] + (v[1] * q1[r]) + (v[2] * q2[r])};
982 q0[r] -= temp * tau;
983 q1[r] -= temp * t2;
984 q2[r] -= temp * t3;
985 }
986 // the reflection of columns j … j + 2 that takes T(j + 1 … j + 2, j) out: from the null vector of T's 2 × 2 below
987 bool ilpivt {false};
988 double scale {1.0};
989 double u1 {1.0};
990 double u2 {0.0};
991 const double top {std::max(std::abs(f.b(j + 1, j + 1)), std::abs(f.b(j + 1, j + 2)))};
992 const double bottom {std::max(std::abs(f.b(j + 2, j + 1)), std::abs(f.b(j + 2, j + 2)))};
993 if (std::max(top, bottom) < safmin) {
994 scale = 0.0;
995 u1 = 1.0;
996 u2 = 0.0;
997 }
998 else {
999 double w11 {0.0};
1000 double w21 {0.0};
1001 double w12 {0.0};
1002 double w22 {0.0};
1003 if (top >= bottom) {
1004 w11 = f.b(j + 1, j + 1);
1005 w21 = f.b(j + 2, j + 1);
1006 w12 = f.b(j + 1, j + 2);
1007 w22 = f.b(j + 2, j + 2);
1008 u1 = f.b(j + 1, j);
1009 u2 = f.b(j + 2, j);
1010 }
1011 else {
1012 w21 = f.b(j + 1, j + 1);
1013 w11 = f.b(j + 2, j + 1);
1014 w22 = f.b(j + 1, j + 2);
1015 w12 = f.b(j + 2, j + 2);
1016 u2 = f.b(j + 1, j);
1017 u1 = f.b(j + 2, j);
1018 }
1019 if (std::abs(w12) > std::abs(w11)) {
1020 ilpivt = true;
1021 std::swap(w11, w12);
1022 std::swap(w21, w22);
1023 }
1024 const double ratio {w21 / w11};
1025 u2 -= ratio * u1;
1026 w22 -= ratio * w12;
1027 if (std::abs(w22) < safmin) {
1028 scale = 0.0;
1029 u2 = 1.0;
1030 u1 = -w12 / w11;
1031 }
1032 else {
1033 if (std::abs(w22) < std::abs(u2)) {
1034 scale = std::abs(w22 / u2);
1035 }
1036 if (std::abs(w11) < std::abs(u1)) {
1037 scale = std::min(scale, std::abs(w11 / u1));
1038 }
1039 u2 = (scale * u2) / w22;
1040 u1 = ((scale * u1) - (w12 * u2)) / w11;
1041 }
1042 }
1043 if (ilpivt) {
1044 std::swap(u1, u2);
1045 }
1046 const double t1 {std::sqrt((scale * scale) + (u1 * u1) + (u2 * u2))};
1047 const double tau2 {1.0 + (scale / t1)};
1048 const double vs {-1.0 / (scale + t1)};
1049 const double w2 {vs * u1};
1050 const double w3 {vs * u2};
1051 const double c2 {tau2 * w2};
1052 const double c3 {tau2 * w3};
1053 const auto reflect_columns = [&](buffer<double>& m, std::size_t first, std::size_t last) {
1054 for (std::size_t r {first}; r <= last; ++r) {
1055 double* const row {m.data() + ((r - 1) * n) + (j - 1)};
1056 const double temp {row[0] + (w2 * row[1]) + (w3 * row[2])};
1057 row[0] -= temp * tau2;
1058 row[1] -= temp * c2;
1059 row[2] -= temp * c3;
1060 }
1061 };
1062 reflect_columns(f.s, 1, std::min(j + 3, ilast));
1063 reflect_columns(f.t, 1, j + 2);
1064 double* const z0 {f.zt.data() + ((j - 1) * n)}; // Z's columns j … j + 2, rows of Zᵀ
1065 double* const z1 {z0 + n};
1066 double* const z2 {z1 + n};
1067 for (std::size_t r {0}; r < n; ++r) {
1068 const double temp {z0[r] + (w2 * z1[r]) + (w3 * z2[r])};
1069 z0[r] -= temp * tau2;
1070 z1[r] -= temp * c2;
1071 z2[r] -= temp * c3;
1072 }
1073 f.b(j + 1, j) = 0.0;
1074 f.b(j + 2, j) = 0.0;
1075 }
1076 // the last step: rotations of rows ilast − 1, ilast and of their columns
1077 const std::size_t j {ilast - 1};
1078 const plane_rotation<double> g {givens(f.h(j, j - 1), f.h(j + 1, j - 1))};
1079 f.h(j, j - 1) = g.r;
1080 f.h(j + 1, j - 1) = 0.0;
1081 form::rotate_rows(f.s, n, j, j + 1, j, n, g.c, g.s);
1082 form::rotate_rows(f.t, n, j, j + 1, j, n, g.c, g.s);
1083 form::rotate_rows(f.qt, n, j, j + 1, 1, n, g.c, g.s);
1084 const plane_rotation<double> h {givens(f.b(j + 1, j + 1), f.b(j + 1, j))};
1085 f.b(j + 1, j + 1) = h.r;
1086 f.b(j + 1, j) = 0.0;
1087 form::rotate_columns(f.s, n, j + 1, j, 1, ilast, h.c, h.s);
1088 form::rotate_columns(f.t, n, j + 1, j, 1, ilast - 1, h.c, h.s);
1089 form::rotate_rows(f.zt, n, j + 1, j, 1, n, h.c, h.s);
1090 }
1091
1099 const matrix<double>& b)
1100 {
1101 const std::size_t n {a.rows()};
1103 const matrix<double> q {factor.q()};
1104 const matrix<double> r {factor.r()};
1106 form.n = n;
1107 form.t = buffer<double>(r.begin(), r.end());
1108 const matrix<double> s {transpose(q) * a};
1109 form.s = buffer<double>(s.begin(), s.end());
1110 const matrix<double> qt {transpose(q)};
1111 form.qt = buffer<double>(qt.begin(), qt.end());
1112 form.zt = buffer<double>(n * n, 0.0);
1113 for (std::size_t i {0}; i < n; ++i) {
1114 form.zt[(i * n) + i] = 1.0;
1115 for (std::size_t j {0}; j < i; ++j) { // R's zeros below its diagonal, as the factorisation leaves them
1116 form.t[(i * n) + j] = 0.0;
1117 }
1118 }
1119 for (std::size_t column {1}; column + 2 <= n; ++column) {
1120 for (std::size_t row {n}; row >= column + 2; --row) {
1121 // rows row − 1 and row take out A(row, column)
1122 const plane_rotation<double> g {givens(form.h(row - 1, column), form.h(row, column))};
1123 form.h(row - 1, column) = g.r;
1124 form.h(row, column) = 0.0;
1125 real_qz_form::rotate_rows(form.s, n, row - 1, row, column + 1, n, g.c, g.s);
1126 real_qz_form::rotate_rows(form.t, n, row - 1, row, row - 1, n, g.c, g.s);
1127 real_qz_form::rotate_rows(form.qt, n, row - 1, row, 1, n, g.c, g.s);
1128 // columns row and row − 1 take out the fill B(row, row − 1)
1129 const plane_rotation<double> h {givens(form.b(row, row), form.b(row, row - 1))};
1130 form.b(row, row) = h.r;
1131 form.b(row, row - 1) = 0.0;
1132 real_qz_form::rotate_columns(form.s, n, row, row - 1, 1, n, h.c, h.s);
1133 real_qz_form::rotate_columns(form.t, n, row, row - 1, 1, row - 1, h.c, h.s);
1134 real_qz_form::rotate_rows(form.zt, n, row, row - 1, 1, n, h.c, h.s);
1135 }
1136 }
1137 return form;
1138 }
1139
1150 [[nodiscard]] inline std::vector<real_pencil_value> real_qz_iteration(real_qz_form& f,
1151 std::size_t steps)
1152 {
1153 using form = real_qz_form;
1154 const std::size_t n {f.n};
1155 std::vector<real_pencil_value> values(n);
1156 if (n == 0) {
1157 return values;
1158 }
1159 constexpr double safety {1.0e2};
1160 const double safmin {std::numeric_limits<double>::min()};
1161 const double safmax {1.0 / safmin};
1162 const double ulp {std::numeric_limits<double>::epsilon()};
1163 double anorm {0.0};
1164 double bnorm {0.0};
1165 for (std::size_t i {1}; i <= n; ++i) { // dlanhs('F'): the Hessenberg part of each
1166 for (std::size_t j {i > 1 ? i - 1 : 1}; j <= n; ++j) {
1167 anorm = std::hypot(anorm, f.h(i, j));
1168 bnorm = std::hypot(bnorm, f.b(i, j));
1169 }
1170 }
1171 const double atol {std::max(safmin, ulp * anorm)};
1172 const double btol {std::max(safmin, ulp * bnorm)};
1173 const double ascale {1.0 / std::max(safmin, anorm)};
1174 const double bscale {1.0 / std::max(safmin, bnorm)};
1175 const double maxit {static_cast<double>(steps)};
1176 std::size_t ilast {n};
1177 std::size_t ifirst {1};
1178 std::size_t iiter {0};
1179 double eshift {0.0};
1180 // a 1 × 1 block at ilast: T(ilast, ilast) made non-negative, the eigenvalue recorded
1181 const auto one_by_one = [&](std::size_t j) {
1182 if (f.b(j, j) < 0.0) {
1183 for (std::size_t i {1}; i <= j; ++i) {
1184 f.h(i, j) = -f.h(i, j);
1185 f.b(i, j) = -f.b(i, j);
1186 }
1187 for (std::size_t i {0}; i < n; ++i) {
1188 f.zt[((j - 1) * n) + i] = -f.zt[((j - 1) * n) + i];
1189 }
1190 }
1191 values[j - 1] = {f.h(j, j), 0.0, f.b(j, j)};
1192 };
1193 const auto negligible_below = [&](std::size_t j) { // S(j, j − 1) against its diagonal neighbours
1194 return std::abs(f.h(j, j - 1)) <= std::max(safmin, ulp * (std::abs(f.h(j, j)) + std::abs(f.h(j - 1, j - 1))));
1195 };
1196 for (std::size_t jiter {0}; jiter < steps; ++jiter) {
1197 // 0 a QZ step on ifirst…ilast; 1 T(ilast, ilast) zero (label 70); 2 a 1 × 1 block at ilast (label 80)
1198 int action {0};
1199 if (ilast == 1) {
1200 action = 2;
1201 }
1202 else if (negligible_below(ilast)) {
1203 f.h(ilast, ilast - 1) = 0.0;
1204 action = 2;
1205 }
1206 else if (std::abs(f.b(ilast, ilast)) <= btol) {
1207 f.b(ilast, ilast) = 0.0;
1208 action = 1;
1209 }
1210 else {
1211 for (std::size_t j {ilast - 1};; --j) { // every case ends the search at j = 1 at the latest
1212 bool ilazro {false};
1213 if (j == 1) {
1214 ilazro = true;
1215 }
1216 else if (negligible_below(j)) {
1217 f.h(j, j - 1) = 0.0;
1218 ilazro = true;
1219 }
1220 if (std::abs(f.b(j, j)) < btol) {
1221 f.b(j, j) = 0.0;
1222 bool ilazr2 {false};
1223 if (!ilazro) {
1224 double temp {std::abs(f.h(j, j - 1))};
1225 double temp2 {std::abs(f.h(j, j))};
1226 const double tempr {std::max(temp, temp2)};
1227 if (tempr < 1.0) { // tempr > 0: S(j, j − 1) was found not negligible (dhgeqz also asks it)
1228 temp /= tempr;
1229 temp2 /= tempr;
1230 }
1231 ilazr2 = temp * (ascale * std::abs(f.h(j + 1, j))) <= temp2 * (ascale * atol);
1232 }
1233 if (ilazro || ilazr2) { // split a 1 × 1 block off at the top, the zero of T chased down
1234 bool settled {false};
1235 for (std::size_t jch {j}; jch < ilast; ++jch) {
1236 const plane_rotation<double> g {givens(f.h(jch, jch), f.h(jch + 1, jch))};
1237 f.h(jch, jch) = g.r;
1238 f.h(jch + 1, jch) = 0.0;
1239 form::rotate_rows(f.s, n, jch, jch + 1, jch + 1, n, g.c, g.s);
1240 form::rotate_rows(f.t, n, jch, jch + 1, jch + 1, n, g.c, g.s);
1241 form::rotate_rows(f.qt, n, jch, jch + 1, 1, n, g.c, g.s);
1242 if (ilazr2) {
1243 f.h(jch, jch - 1) *= g.c;
1244 }
1245 ilazr2 = false;
1246 if (std::abs(f.b(jch + 1, jch + 1)) >= btol) {
1247 if (jch + 1 >= ilast) {
1248 action = 2;
1249 }
1250 else {
1251 ifirst = jch + 1;
1252 action = 0;
1253 }
1254 settled = true;
1255 break;
1256 }
1257 f.b(jch + 1, jch + 1) = 0.0;
1258 }
1259 if (!settled) {
1260 action = 1;
1261 }
1262 break;
1263 }
1264 // only T(j, j) zero: chase it to T(ilast, ilast)
1265 for (std::size_t jch {j}; jch < ilast; ++jch) {
1266 const plane_rotation<double> g {givens(f.b(jch, jch + 1), f.b(jch + 1, jch + 1))};
1267 f.b(jch, jch + 1) = g.r;
1268 f.b(jch + 1, jch + 1) = 0.0;
1269 if (jch + 1 < n) {
1270 form::rotate_rows(f.t, n, jch, jch + 1, jch + 2, n, g.c, g.s);
1271 }
1272 form::rotate_rows(f.s, n, jch, jch + 1, jch - 1, n, g.c, g.s);
1273 form::rotate_rows(f.qt, n, jch, jch + 1, 1, n, g.c, g.s);
1274 const plane_rotation<double> h {givens(f.h(jch + 1, jch), f.h(jch + 1, jch - 1))};
1275 f.h(jch + 1, jch) = h.r;
1276 f.h(jch + 1, jch - 1) = 0.0;
1277 form::rotate_columns(f.s, n, jch, jch - 1, 1, jch, h.c, h.s);
1278 form::rotate_columns(f.t, n, jch, jch - 1, 1, jch - 1, h.c, h.s); // jch ≥ 2: j = 1 sets ilazro
1279 form::rotate_rows(f.zt, n, jch, jch - 1, 1, n, h.c, h.s);
1280 }
1281 action = 1;
1282 break;
1283 }
1284 if (ilazro) { // only S's subdivision: a QZ step on j…ilast
1285 ifirst = j;
1286 action = 0;
1287 break;
1288 }
1289 }
1290 }
1291 if (action == 1) { // T(ilast, ilast) zero: clear S(ilast, ilast − 1) to split a 1 × 1 block
1292 const plane_rotation<double> g {givens(f.h(ilast, ilast), f.h(ilast, ilast - 1))};
1293 f.h(ilast, ilast) = g.r;
1294 f.h(ilast, ilast - 1) = 0.0;
1295 form::rotate_columns(f.s, n, ilast, ilast - 1, 1, ilast - 1, g.c, g.s);
1296 form::rotate_columns(f.t, n, ilast, ilast - 1, 1, ilast - 1, g.c, g.s);
1297 form::rotate_rows(f.zt, n, ilast, ilast - 1, 1, n, g.c, g.s);
1298 action = 2;
1299 }
1300 if (action == 2) {
1302 if (ilast == 1) {
1303 return values;
1304 }
1305 --ilast;
1306 iiter = 0;
1307 eshift = 0.0;
1308 continue;
1309 }
1310 // a QZ step on ifirst…ilast (label 110)
1311 ++iiter;
1312 double s1 {1.0};
1313 double wr {0.0};
1314 bool complex_shifts {false};
1315 if (iiter % 10 == 0) { // exceptional
1316 if ((maxit * safmin) * std::abs(f.h(ilast, ilast - 1)) < std::abs(f.b(ilast - 1, ilast - 1))) {
1317 eshift = f.h(ilast, ilast - 1) / f.b(ilast - 1, ilast - 1);
1318 }
1319 else {
1320 eshift += 1.0 / (safmin * maxit);
1321 }
1322 s1 = 1.0;
1323 wr = eshift;
1324 }
1325 else {
1326 pencil_pair shifts {pencil_eigenvalues(f.h(ilast - 1, ilast - 1), f.h(ilast - 1, ilast), f.h(ilast, ilast - 1), f.h(ilast, ilast),
1327 f.b(ilast - 1, ilast - 1), f.b(ilast - 1, ilast), f.b(ilast, ilast), safmin * safety)};
1328 if (std::abs(((shifts.wr1 / shifts.scale1) * f.b(ilast, ilast)) - f.h(ilast, ilast))
1329 > std::abs(((shifts.wr2 / shifts.scale2) * f.b(ilast, ilast)) - f.h(ilast, ilast))) {
1330 std::swap(shifts.wr1, shifts.wr2);
1331 std::swap(shifts.scale1, shifts.scale2);
1332 }
1333 s1 = shifts.scale1;
1334 wr = shifts.wr1;
1335 complex_shifts = shifts.wi != 0.0;
1336 }
1337 if (!complex_shifts) { // a single real shift: the implicit sweep of rotations
1338 double temp {std::min(ascale, 1.0) * (0.5 * safmax)};
1339 double scale {s1 > temp ? temp / s1 : 1.0};
1340 temp = std::min(bscale, 1.0) * (0.5 * safmax);
1341 if (std::abs(wr) > temp) {
1342 scale = std::min(scale, temp / std::abs(wr));
1343 }
1344 s1 *= scale;
1345 wr *= scale;
1346 std::size_t istart {ifirst};
1347 for (std::size_t j {ilast - 1}; j > ifirst; --j) { // two consecutive small subdiagonal entries
1348 double small {std::abs(s1 * f.h(j, j - 1))};
1349 double diag {std::abs((s1 * f.h(j, j)) - (wr * f.b(j, j)))};
1350 const double tempr {std::max(small, diag)};
1351 if (tempr < 1.0) { // dhgeqz also asks tempr ≠ 0, where both stay 0 and the test holds: as here past safmin
1352 small /= std::max(tempr, std::numeric_limits<double>::min());
1353 diag /= std::max(tempr, std::numeric_limits<double>::min());
1354 }
1355 if (std::abs((ascale * f.h(j + 1, j)) * small) <= (ascale * atol) * diag) {
1356 istart = j;
1357 break;
1358 }
1359 }
1360 const plane_rotation<double> first {givens((s1 * f.h(istart, istart)) - (wr * f.b(istart, istart)), s1 * f.h(istart + 1, istart))};
1361 double c {first.c};
1362 double sine {first.s};
1363 for (std::size_t j {istart}; j < ilast; ++j) {
1364 if (j > istart) {
1365 const plane_rotation<double> g {givens(f.h(j, j - 1), f.h(j + 1, j - 1))};
1366 f.h(j, j - 1) = g.r;
1367 f.h(j + 1, j - 1) = 0.0;
1368 c = g.c;
1369 sine = g.s;
1370 }
1371 form::rotate_rows(f.s, n, j, j + 1, j, n, c, sine);
1372 form::rotate_rows(f.t, n, j, j + 1, j, n, c, sine);
1373 form::rotate_rows(f.qt, n, j, j + 1, 1, n, c, sine);
1374 const plane_rotation<double> g {givens(f.b(j + 1, j + 1), f.b(j + 1, j))};
1375 f.b(j + 1, j + 1) = g.r;
1376 f.b(j + 1, j) = 0.0;
1377 form::rotate_columns(f.s, n, j + 1, j, 1, std::min(j + 2, ilast), g.c, g.s);
1378 form::rotate_columns(f.t, n, j + 1, j, 1, j, g.c, g.s);
1379 form::rotate_rows(f.zt, n, j + 1, j, 1, n, g.c, g.s);
1380 }
1381 continue;
1382 }
1383 if (ifirst + 1 == ilast) { // label 200: a 2 × 2 block of a conjugate pair, standardized and split off
1384 triangle_svd svd {svd_of_triangle(f.b(ilast - 1, ilast - 1), f.b(ilast - 1, ilast), f.b(ilast, ilast))};
1385 double b22 {svd.ssmin};
1386 double b11 {svd.ssmax};
1387 if (b11 < 0.0) {
1388 svd.csr = -svd.csr;
1389 svd.snr = -svd.snr;
1390 b11 = -b11;
1391 b22 = -b22;
1392 }
1393 form::rotate_rows(f.s, n, ilast - 1, ilast, ilast - 1, n, svd.csl, svd.snl);
1394 form::rotate_columns(f.s, n, ilast - 1, ilast, 1, ilast, svd.csr, svd.snr);
1395 if (ilast < n) {
1396 form::rotate_rows(f.t, n, ilast - 1, ilast, ilast + 1, n, svd.csl, svd.snl);
1397 }
1398 if (ilast > 2) {
1399 form::rotate_columns(f.t, n, ilast - 1, ilast, 1, ilast - 2, svd.csr, svd.snr);
1400 }
1401 form::rotate_rows(f.qt, n, ilast - 1, ilast, 1, n, svd.csl, svd.snl);
1402 form::rotate_rows(f.zt, n, ilast - 1, ilast, 1, n, svd.csr, svd.snr);
1403 f.b(ilast - 1, ilast - 1) = b11;
1404 f.b(ilast - 1, ilast) = 0.0;
1405 f.b(ilast, ilast - 1) = 0.0;
1406 f.b(ilast, ilast) = b22;
1407 if (b22 < 0.0) {
1408 for (std::size_t i {1}; i <= ilast; ++i) {
1409 f.h(i, ilast) = -f.h(i, ilast);
1410 f.b(i, ilast) = -f.b(i, ilast);
1411 }
1412 for (std::size_t i {0}; i < n; ++i) {
1413 f.zt[((ilast - 1) * n) + i] = -f.zt[((ilast - 1) * n) + i];
1414 }
1415 b22 = -b22;
1416 }
1417 const pencil_pair pair {pencil_eigenvalues(f.h(ilast - 1, ilast - 1), f.h(ilast - 1, ilast), f.h(ilast, ilast - 1), f.h(ilast, ilast),
1418 f.b(ilast - 1, ilast - 1), f.b(ilast - 1, ilast), f.b(ilast, ilast), safmin * safety)};
1419 if (pair.wi == 0.0) { // real after all: the next iteration splits the block
1420 continue;
1421 }
1422 const auto [first_value, second_value] {pair_values(f, ilast, pair, b11, b22)};
1423 values[ilast - 2] = first_value;
1424 values[ilast - 1] = second_value;
1425 ilast = ifirst - 1;
1426 if (ilast == 0) {
1427 return values;
1428 }
1429 iiter = 0;
1430 eshift = 0.0;
1431 continue;
1432 }
1434 }
1435 throw convergence_error("QZ: the iterations did not converge (dhgeqz's info)");
1436 }
1437
1440 {
1441 std::array<double, 16> e {};
1442
1444 [[nodiscard]] double& operator()(std::size_t i,
1445 std::size_t j)
1446 {
1447 return e[(i * 4) + j];
1448 }
1449
1451 [[nodiscard]] double operator()(std::size_t i,
1452 std::size_t j) const
1453 {
1454 return e[(i * 4) + j];
1455 }
1456
1458 [[nodiscard]] static small_square identity(std::size_t m)
1459 {
1460 small_square out;
1461 for (std::size_t i {0}; i < m; ++i) {
1462 out(i, i) = 1.0;
1463 }
1464 return out;
1465 }
1466 };
1467
1470 bool tx,
1471 const small_square& y,
1472 bool ty,
1473 std::size_t m)
1474 {
1475 small_square out;
1476 for (std::size_t i {0}; i < m; ++i) {
1477 for (std::size_t j {0}; j < m; ++j) {
1478 double sum {0.0};
1479 for (std::size_t k {0}; k < m; ++k) {
1480 sum += (tx ? x(k, i) : x(i, k)) * (ty ? y(j, k) : y(k, j));
1481 }
1482 out(i, j) = sum;
1483 }
1484 }
1485 return out;
1486 }
1487
1489 [[nodiscard]] inline double small_norm(const small_square& x,
1490 std::size_t r0,
1491 std::size_t r1,
1492 std::size_t c0,
1493 std::size_t c1)
1494 {
1495 double norm {0.0};
1496 for (std::size_t i {r0}; i < r1; ++i) {
1497 for (std::size_t j {c0}; j < c1; ++j) {
1498 norm = std::hypot(norm, x(i, j));
1499 }
1500 }
1501 return norm;
1502 }
1503
1510 std::size_t m,
1511 std::size_t k)
1512 {
1514 for (std::size_t j {0}; j < k; ++j) {
1515 double rest {0.0};
1516 for (std::size_t i {j + 1}; i < m; ++i) {
1517 rest = std::hypot(rest, x(i, j));
1518 }
1519 if (rest == 0.0) {
1520 continue;
1521 }
1522 const double alpha {x(j, j)};
1523 const double beta {-std::copysign(std::hypot(alpha, rest), alpha)};
1524 const double tau {(beta - alpha) / beta};
1525 std::array<double, 4> v {};
1526 v[j] = 1.0;
1527 for (std::size_t i {j + 1}; i < m; ++i) {
1528 v[i] = x(i, j) / (alpha - beta);
1529 }
1530 for (std::size_t c {j}; c < m; ++c) { // x ← (I − τ v vᵀ) x
1531 double dot {0.0};
1532 for (std::size_t i {j}; i < m; ++i) {
1533 dot += v[i] * x(i, c);
1534 }
1535 for (std::size_t i {j}; i < m; ++i) {
1536 x(i, c) -= tau * v[i] * dot;
1537 }
1538 }
1539 for (std::size_t r {0}; r < m; ++r) { // Q ← Q (I − τ v vᵀ)
1540 double dot {0.0};
1541 for (std::size_t i {j}; i < m; ++i) {
1542 dot += q(r, i) * v[i];
1543 }
1544 for (std::size_t i {j}; i < m; ++i) {
1545 q(r, i) -= tau * dot * v[i];
1546 }
1547 }
1548 }
1549 return q;
1550 }
1551
1554 {
1555 double csl {1.0};
1556 double snl {0.0};
1557 double csr {1.0};
1558 double snr {0.0};
1559 };
1560
1565 [[nodiscard]] inline pencil_rotations standardize_pencil(std::array<std::array<double, 2>, 2>& a,
1566 std::array<std::array<double, 2>, 2>& b)
1567 {
1568 const double safmin {std::numeric_limits<double>::min()};
1569 const double ulp {std::numeric_limits<double>::epsilon()};
1570 const double anorm {std::max({std::abs(a[0][0]) + std::abs(a[1][0]), std::abs(a[0][1]) + std::abs(a[1][1]), safmin})};
1571 const double bnorm {std::max({std::abs(b[0][0]), std::abs(b[0][1]) + std::abs(b[1][1]), safmin})};
1572 for (auto& row : a) {
1573 for (double& x : row) {
1574 x *= 1.0 / anorm;
1575 }
1576 }
1577 b[0][0] *= 1.0 / bnorm;
1578 b[0][1] *= 1.0 / bnorm;
1579 b[1][1] *= 1.0 / bnorm;
1580 // rows by (c, s): row 0 ← c row 0 + s row 1, row 1 ← c row 1 − s row 0; columns likewise
1581 const auto rows = [](std::array<std::array<double, 2>, 2>& m, double c, double s) {
1582 for (std::size_t j {0}; j < 2; ++j) {
1583 const double t {(c * m[0][j]) + (s * m[1][j])};
1584 m[1][j] = (c * m[1][j]) - (s * m[0][j]);
1585 m[0][j] = t;
1586 }
1587 };
1588 const auto columns = [](std::array<std::array<double, 2>, 2>& m, double c, double s) {
1589 for (std::size_t i {0}; i < 2; ++i) {
1590 const double t {(c * m[i][0]) + (s * m[i][1])};
1591 m[i][1] = (c * m[i][1]) - (s * m[i][0]);
1592 m[i][0] = t;
1593 }
1594 };
1595 pencil_rotations out;
1596 if (std::abs(a[1][0]) <= ulp) {
1597 a[1][0] = 0.0;
1598 b[1][0] = 0.0;
1599 }
1600 else if (std::abs(b[0][0]) <= ulp) {
1601 const plane_rotation<double> g {givens(a[0][0], a[1][0])};
1602 out.csl = g.c;
1603 out.snl = g.s;
1604 rows(a, out.csl, out.snl);
1605 rows(b, out.csl, out.snl);
1606 a[1][0] = 0.0;
1607 b[0][0] = 0.0;
1608 b[1][0] = 0.0;
1609 }
1610 else if (std::abs(b[1][1]) <= ulp) {
1611 const plane_rotation<double> g {givens(a[1][1], a[1][0])};
1612 out.csr = g.c;
1613 out.snr = -g.s;
1614 columns(a, out.csr, out.snr);
1615 columns(b, out.csr, out.snr);
1616 a[1][0] = 0.0;
1617 b[1][0] = 0.0;
1618 b[1][1] = 0.0;
1619 }
1620 else {
1621 const pencil_pair pair {pencil_eigenvalues(a[0][0], a[0][1], a[1][0], a[1][1], b[0][0], b[0][1], b[1][1], safmin)};
1622 if (pair.wi == 0.0) {
1623 const double h1 {(pair.scale1 * a[0][0]) - (pair.wr1 * b[0][0])};
1624 const double h2 {(pair.scale1 * a[0][1]) - (pair.wr1 * b[0][1])};
1625 const double h3 {(pair.scale1 * a[1][1]) - (pair.wr1 * b[1][1])};
1626 const double rr {std::hypot(h1, h2)};
1627 const double qq {std::hypot(pair.scale1 * a[1][0], h3)};
1628 const plane_rotation<double> g {rr > qq ? givens(h2, h1) : givens(h3, pair.scale1 * a[1][0])};
1629 out.csr = g.c;
1630 out.snr = -g.s;
1631 columns(a, out.csr, out.snr);
1632 columns(b, out.csr, out.snr);
1633 const double ha {std::max(std::abs(a[0][0]) + std::abs(a[0][1]), std::abs(a[1][0]) + std::abs(a[1][1]))};
1634 const double hb {std::max(std::abs(b[0][0]) + std::abs(b[0][1]), std::abs(b[1][0]) + std::abs(b[1][1]))};
1635 const plane_rotation<double> h {pair.scale1 * ha >= std::abs(pair.wr1) * hb ? givens(b[0][0], b[1][0]) : givens(a[0][0], a[1][0])};
1636 out.csl = h.c;
1637 out.snl = h.s;
1638 rows(a, out.csl, out.snl);
1639 rows(b, out.csl, out.snl);
1640 a[1][0] = 0.0;
1641 b[1][0] = 0.0;
1642 }
1643 else {
1644 const triangle_svd svd {svd_of_triangle(b[0][0], b[0][1], b[1][1])};
1645 out.csl = svd.csl;
1646 out.snl = svd.snl;
1647 out.csr = svd.csr;
1648 out.snr = svd.snr;
1649 rows(a, out.csl, out.snl);
1650 rows(b, out.csl, out.snl);
1651 columns(a, out.csr, out.snr);
1652 columns(b, out.csr, out.snr);
1653 b[1][0] = 0.0;
1654 b[0][1] = 0.0;
1655 }
1656 }
1657 for (auto& row : a) {
1658 for (double& x : row) {
1659 x *= anorm;
1660 }
1661 }
1662 for (auto& row : b) {
1663 for (double& x : row) {
1664 x *= bnorm;
1665 }
1666 }
1667 return out;
1668 }
1669
1676 [[nodiscard]] inline std::optional<std::pair<small_square, small_square>> generalized_sylvester(const small_square& s,
1677 const small_square& t,
1678 std::size_t n1,
1679 std::size_t n2)
1680 {
1681 const std::size_t k {n1 * n2};
1682 const std::size_t size {2 * k};
1683 std::array<std::array<double, 9>, 8> z {}; // the system and its right-hand side, column size
1684 for (std::size_t i {0}; i < n1; ++i) {
1685 for (std::size_t j {0}; j < n2; ++j) {
1686 const std::size_t row {(i * n2) + j};
1687 for (std::size_t p {0}; p < n1; ++p) { // S₁₁ R and T₁₁ R
1688 z[row][(p * n2) + j] += s(i, p);
1689 z[row + k][(p * n2) + j] += t(i, p);
1690 }
1691 for (std::size_t q {0}; q < n2; ++q) { // − L S₂₂ and − L T₂₂
1692 z[row][k + (i * n2) + q] -= s(n1 + q, n1 + j);
1693 z[row + k][k + (i * n2) + q] -= t(n1 + q, n1 + j);
1694 }
1695 z[row][size] = s(i, n1 + j);
1696 z[row + k][size] = t(i, n1 + j);
1697 }
1698 }
1699 double largest {0.0};
1700 for (std::size_t r {0}; r < size; ++r) {
1701 for (std::size_t c {0}; c < size; ++c) {
1702 largest = std::max(largest, std::abs(z[r][c]));
1703 }
1704 }
1705 const double smin {std::max(std::numeric_limits<double>::epsilon() * largest, std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon())};
1706 std::array<std::size_t, 8> order {};
1707 for (std::size_t c {0}; c < size; ++c) {
1708 order[c] = c;
1709 }
1710 for (std::size_t p {0}; p < size; ++p) { // complete pivoting, as dgetc2
1711 std::size_t pr {p};
1712 std::size_t pc {p};
1713 for (std::size_t r {p}; r < size; ++r) {
1714 for (std::size_t c {p}; c < size; ++c) {
1715 if (std::abs(z[r][c]) > std::abs(z[pr][pc])) {
1716 pr = r;
1717 pc = c;
1718 }
1719 }
1720 }
1721 if (!(std::abs(z[pr][pc]) >= smin)) {
1722 return std::nullopt;
1723 }
1724 std::swap(z[p], z[pr]);
1725 for (std::size_t r {0}; r < size; ++r) {
1726 std::swap(z[r][p], z[r][pc]);
1727 }
1728 std::swap(order[p], order[pc]);
1729 for (std::size_t r {p + 1}; r < size; ++r) {
1730 const double factor {z[r][p] / z[p][p]};
1731 for (std::size_t c {p}; c <= size; ++c) {
1732 z[r][c] -= factor * z[p][c];
1733 }
1734 }
1735 }
1736 std::array<double, 8> x {};
1737 for (std::size_t p {size}; p-- > 0;) {
1738 double sum {z[p][size]};
1739 for (std::size_t c {p + 1}; c < size; ++c) {
1740 sum -= z[p][c] * x[c];
1741 }
1742 x[p] = sum / z[p][p];
1743 }
1744 small_square r;
1745 small_square l;
1746 for (std::size_t c {0}; c < size; ++c) {
1747 const std::size_t unknown {order[c]};
1748 if (!std::isfinite(x[c])) {
1749 return std::nullopt;
1750 }
1751 if (unknown < k) {
1752 r(unknown / n2, unknown % n2) = x[c];
1753 }
1754 else {
1755 l((unknown - k) / n2, (unknown - k) % n2) = x[c];
1756 }
1757 }
1758 return std::pair {r, l};
1759 }
1760
1770
1776 [[nodiscard]] inline std::optional<block_exchange> plan_single_exchange(small_square s,
1777 small_square t,
1778 double thresha,
1779 double threshb)
1780 {
1781 const double ff {(s(1, 1) * t(0, 0)) - (t(1, 1) * s(0, 0))};
1782 const double gg {(s(1, 1) * t(0, 1)) - (t(1, 1) * s(0, 1))};
1783 const double sa {std::abs(s(1, 1)) * std::abs(t(0, 0))};
1784 const double sb {std::abs(s(0, 0)) * std::abs(t(1, 1))};
1785 const plane_rotation<double> z {givens(ff, gg)}; // dtgex2's IR(1, 2) = c, IR(1, 1) = s: columns by (s, −c)
1786 small_square ir;
1787 ir(0, 0) = z.s;
1788 ir(1, 0) = -z.c;
1789 ir(0, 1) = z.c;
1790 ir(1, 1) = z.s;
1791 s = small_product(s, false, ir, false, 2);
1792 t = small_product(t, false, ir, false, 2);
1793 const plane_rotation<double> q {sa >= sb ? givens(s(0, 0), s(1, 0)) : givens(t(0, 0), t(1, 0))};
1794 small_square li; // rows by (c, s): S' = LIᵀ S
1795 li(0, 0) = q.c;
1796 li(1, 0) = q.s;
1797 li(0, 1) = -q.s;
1798 li(1, 1) = q.c;
1799 s = small_product(li, true, s, false, 2);
1800 t = small_product(li, true, t, false, 2);
1801 if (!(std::abs(s(1, 0)) <= thresha && std::abs(t(1, 0)) <= threshb)) { // NaN fails it
1802 return std::nullopt;
1803 }
1804 return block_exchange {s, t, li, ir}; // the entries below the diagonal, within the weak test's bounds, kept for the strong one
1805 }
1806
1814 [[nodiscard]] inline std::optional<block_exchange> plan_block_exchange(small_square s,
1815 small_square t,
1816 std::size_t n1,
1817 std::size_t n2,
1818 double thresha)
1819 {
1820 const std::size_t m {n1 + n2};
1821 const std::optional<std::pair<small_square, small_square>> solved {generalized_sylvester(s, t, n1, n2)};
1822 if (!solved) {
1823 return std::nullopt;
1824 }
1825 const auto& [r, l] {*solved};
1826 small_square lbasis; // [−L; I] (m × n2)
1827 for (std::size_t j {0}; j < n2; ++j) {
1828 for (std::size_t i {0}; i < n1; ++i) {
1829 lbasis(i, j) = -l(i, j);
1830 }
1831 lbasis(n1 + j, j) = 1.0;
1832 }
1833 small_square li {small_qr(lbasis, m, n2)}; // its first n2 columns span [−L; I]
1834 small_square rbasis; // [I R]ᵀ (m × n1)
1835 for (std::size_t i {0}; i < n1; ++i) {
1836 rbasis(i, i) = 1.0;
1837 for (std::size_t j {0}; j < n2; ++j) {
1838 rbasis(n1 + j, i) = r(i, j);
1839 }
1840 }
1841 const small_square qn {small_qr(rbasis, m, n1)};
1842 small_square ir; // by rows: the last n1 span those of [I R], the first n2 their complement
1843 for (std::size_t c {0}; c < m; ++c) {
1844 for (std::size_t i {0}; i < n1; ++i) {
1845 ir(n2 + i, c) = qn(c, i);
1846 }
1847 for (std::size_t i {0}; i < n2; ++i) {
1848 ir(i, c) = qn(c, n1 + i);
1849 }
1850 }
1851 s = small_product(small_product(li, true, s, false, m), false, ir, true, m);
1852 t = small_product(small_product(li, true, t, false, m), false, ir, true, m);
1853 // T triangular again: by RQ (T = R Q: S ← S Qᵀ, IR ← Q IR) or by QR (T = Q R: S ← Qᵀ S, LI ← LI Q)
1854 small_square flipped; // J Tᵀ J, whose QR gives T's RQ
1855 for (std::size_t i {0}; i < m; ++i) {
1856 for (std::size_t j {0}; j < m; ++j) {
1857 flipped(i, j) = t(m - 1 - j, m - 1 - i);
1858 }
1859 }
1860 const small_square qf {small_qr(flipped, m, m)};
1861 small_square qrq; // Q of T = R Q: J Q_fᵀ J
1862 for (std::size_t i {0}; i < m; ++i) {
1863 for (std::size_t j {0}; j < m; ++j) {
1864 qrq(i, j) = qf(m - 1 - j, m - 1 - i);
1865 }
1866 }
1867 const small_square qt {small_qr(t, m, m)};
1868 const small_square s_rq {small_product(s, false, qrq, true, m)};
1869 const small_square s_qr {small_product(qt, true, s, false, m)};
1870 const double brqa21 {small_norm(s_rq, n2, m, 0, n2)};
1871 const double bqra21 {small_norm(s_qr, n2, m, 0, n2)};
1872 if (bqra21 <= brqa21 && bqra21 <= thresha) {
1873 s = s_qr;
1874 t = small_product(qt, true, t, false, m);
1875 li = small_product(li, false, qt, false, m);
1876 }
1877 else if (!(brqa21 < thresha)) { // NaN fails it
1878 return std::nullopt;
1879 }
1880 else {
1881 s = s_rq;
1882 t = small_product(t, false, qrq, true, m);
1883 ir = small_product(qrq, false, ir, false, m);
1884 }
1885 // T's below its diagonal (S's below the blocks kept for the strong test), over the whole 4 × 4, whose rows and
1886 // columns past m are zero: bounded by m, GCC 13 cannot tell the rows stay within it (-Warray-bounds)
1887 for (std::size_t i {1}; i < 4; ++i) {
1888 for (std::size_t j {0}; j < i; ++j) {
1889 t(i, j) = 0.0;
1890 }
1891 }
1892 // each 2 × 2 block standardized: the left rotations gathered in `left` (its transpose applied), the right in `right`
1895 const auto standardize_at = [&](std::size_t at) {
1896 std::array<std::array<double, 2>, 2> a {{{s(at, at), s(at, at + 1)}, {s(at + 1, at), s(at + 1, at + 1)}}};
1897 std::array<std::array<double, 2>, 2> b {{{t(at, at), t(at, at + 1)}, {t(at + 1, at), t(at + 1, at + 1)}}};
1898 const pencil_rotations g {standardize_pencil(a, b)};
1899 for (std::size_t i {0}; i < 2; ++i) {
1900 for (std::size_t j {0}; j < 2; ++j) {
1901 s(at + i, at + j) = a[i][j];
1902 t(at + i, at + j) = b[i][j];
1903 }
1904 }
1905 left(at, at) = g.csl;
1906 left(at + 1, at) = g.snl;
1907 left(at, at + 1) = -g.snl;
1908 left(at + 1, at + 1) = g.csl;
1909 right(at, at) = g.csr;
1910 right(at + 1, at) = g.snr;
1911 right(at, at + 1) = -g.snr;
1912 right(at + 1, at + 1) = g.csr;
1913 };
1914 if (n2 > 1) {
1915 standardize_at(0);
1916 }
1917 if (n1 > 1) {
1919 }
1920 // the block between them: leftᵀ on its rows, right on its columns
1921 const small_square s_rest {small_product(small_product(left, true, s, false, m), false, right, false, m)};
1922 const small_square t_rest {small_product(small_product(left, true, t, false, m), false, right, false, m)};
1923 for (std::size_t i {0}; i < n2; ++i) {
1924 for (std::size_t j {n2}; j < m; ++j) {
1925 s(i, j) = s_rest(i, j);
1926 t(i, j) = t_rest(i, j);
1927 }
1928 }
1929 return block_exchange {s, t, small_product(li, false, left, false, m), small_product(ir, true, right, false, m)};
1930 }
1931
1942 std::size_t j1,
1943 std::size_t n1,
1944 std::size_t n2)
1945 {
1946 const std::size_t n {f.n};
1947 const std::size_t m {n1 + n2};
1948 small_square s;
1949 small_square t;
1950 for (std::size_t i {0}; i < m; ++i) {
1951 for (std::size_t j {0}; j < m; ++j) {
1952 s(i, j) = f.h(j1 + i, j1 + j);
1953 t(i, j) = f.b(j1 + i, j1 + j);
1954 }
1955 }
1956 const double eps {std::numeric_limits<double>::epsilon()};
1957 const double smlnum {std::numeric_limits<double>::min() / eps};
1958 const double thresha {std::max(20.0 * eps * small_norm(s, 0, m, 0, m), smlnum)};
1959 const double threshb {std::max(20.0 * eps * small_norm(t, 0, m, 0, m), smlnum)};
1960 const std::optional<block_exchange> plan {m == 2 ? plan_single_exchange(s, t, thresha, threshb) : plan_block_exchange(s, t, n1, n2, thresha)};
1961 if (!plan) {
1962 return false;
1963 }
1964 for (const bool of_s : {true, false}) { // the strong test
1965 const small_square rebuilt {small_product(small_product(plan->li, false, of_s ? plan->s : plan->t, false, m), false, plan->ir, true, m)};
1967 for (std::size_t i {0}; i < m; ++i) {
1968 for (std::size_t j {0}; j < m; ++j) {
1969 gap(i, j) = rebuilt(i, j) - (of_s ? s(i, j) : t(i, j));
1970 }
1971 }
1972 if (!(small_norm(gap, 0, m, 0, m) <= (of_s ? thresha : threshb))) {
1973 return false;
1974 }
1975 }
1976 const small_square& li {plan->li};
1977 const small_square& ir {plan->ir};
1978 const std::size_t lead {m == 2 ? 1 : n2}; // the new leading block's order
1979 for (std::size_t i {0}; i < m; ++i) {
1980 for (std::size_t j {0}; j < m; ++j) {
1981 const bool below {i >= lead && j < lead};
1982 f.h(j1 + i, j1 + j) = below ? 0.0 : plan->s(i, j);
1983 f.b(j1 + i, j1 + j) = below ? 0.0 : plan->t(i, j);
1984 }
1985 }
1986 const auto right_times = [&](buffer<double>& x, std::size_t rows_last) { // columns j1 … of rows 1 … rows_last
1987 for (std::size_t row {1}; row <= rows_last; ++row) {
1988 std::array<double, 4> v {};
1989 for (std::size_t c {0}; c < m; ++c) {
1990 for (std::size_t k {0}; k < m; ++k) {
1991 v[c] += x[((row - 1) * n) + (j1 - 1 + k)] * ir(k, c);
1992 }
1993 }
1994 for (std::size_t c {0}; c < m; ++c) {
1995 x[((row - 1) * n) + (j1 - 1 + c)] = v[c];
1996 }
1997 }
1998 };
1999 const auto left_times = [&](buffer<double>& x) { // LIᵀ on rows j1 … of the columns past the blocks
2000 for (std::size_t col {j1 + m}; col <= n; ++col) {
2001 std::array<double, 4> v {};
2002 for (std::size_t r2 {0}; r2 < m; ++r2) {
2003 for (std::size_t k {0}; k < m; ++k) {
2004 v[r2] += li(k, r2) * x[((j1 - 1 + k) * n) + (col - 1)];
2005 }
2006 }
2007 for (std::size_t r2 {0}; r2 < m; ++r2) {
2008 x[((j1 - 1 + r2) * n) + (col - 1)] = v[r2];
2009 }
2010 }
2011 };
2012 right_times(f.s, j1 - 1);
2013 right_times(f.t, j1 - 1);
2014 left_times(f.s);
2015 left_times(f.t);
2016 const auto times_transposed = [&](buffer<double>& xt, const small_square& factor) { // X ← X F on Xᵀ's rows j1 …
2017 for (std::size_t row {1}; row <= n; ++row) {
2018 std::array<double, 4> v {};
2019 for (std::size_t c {0}; c < m; ++c) {
2020 for (std::size_t k {0}; k < m; ++k) {
2021 v[c] += xt[((j1 - 1 + k) * n) + (row - 1)] * factor(k, c);
2022 }
2023 }
2024 for (std::size_t c {0}; c < m; ++c) {
2025 xt[((j1 - 1 + c) * n) + (row - 1)] = v[c];
2026 }
2027 }
2028 };
2029 times_transposed(f.zt, ir);
2030 times_transposed(f.qt, li);
2031 return true;
2032 }
2033
2036 std::size_t j1,
2037 std::size_t n1,
2038 std::size_t n2)
2039 {
2040 if (!exchange_real_blocks(f, j1, n1, n2)) {
2041 throw convergence_error("generalized Schur form: eigenvalues could not be separated for reordering");
2042 }
2043 }
2044
2053 std::size_t ifst,
2054 std::size_t ilst)
2055 {
2056 const std::size_t n {f.n};
2057 if (ifst > 1 && f.h(ifst, ifst - 1) != 0.0) {
2058 --ifst;
2059 }
2060 std::size_t nbf {ifst < n && f.h(ifst + 1, ifst) != 0.0 ? std::size_t {2} : std::size_t {1}};
2061 if (ilst > 1 && f.h(ilst, ilst - 1) != 0.0) {
2062 --ilst;
2063 }
2064 std::size_t here {ifst};
2065 while (here > ilst) {
2066 const std::size_t nbnext {here >= 3 && f.h(here - 1, here - 2) != 0.0 ? std::size_t {2} : std::size_t {1}};
2067 if (nbf != 3) {
2069 here -= nbnext;
2070 if (nbf == 2 && f.h(here + 1, here) == 0.0) { // the block split in two real eigenvalues
2071 nbf = 3;
2072 }
2073 continue;
2074 }
2075 // two 1 × 1 blocks, here and here + 1: the upper one past the block above, then the lower one
2077 if (nbnext == 1) {
2078 exchange_or_refuse(f, here, 1, 1);
2079 --here;
2080 }
2081 else if (f.h(here, here - 1) != 0.0) {
2082 exchange_or_refuse(f, here - 1, 2, 1);
2083 here -= 2;
2084 }
2085 else { // the block above split in passing: its two halves past the lower one in turn
2086 exchange_or_refuse(f, here, 1, 1);
2087 --here;
2088 exchange_or_refuse(f, here, 1, 1);
2089 --here;
2090 }
2091 }
2092 }
2093
2099 [[nodiscard]] inline std::vector<real_pencil_value> real_values(real_qz_form& f)
2100 {
2101 const std::size_t n {f.n};
2102 std::vector<real_pencil_value> values(n);
2103 for (std::size_t k {1}; k <= n; ++k) {
2104 if (k < n && f.h(k + 1, k) != 0.0) {
2105 const pencil_pair pair {pencil_eigenvalues(f.h(k, k), f.h(k, k + 1), f.h(k + 1, k), f.h(k + 1, k + 1), f.b(k, k), f.b(k, k + 1), f.b(k + 1, k + 1),
2106 std::numeric_limits<double>::min())};
2107 values[k - 1] = {pair.wr1, pair.wi, pair.scale1};
2108 values[k] = {pair.wr2, -pair.wi, pair.scale2};
2109 ++k;
2110 continue;
2111 }
2112 if (std::signbit(f.b(k, k))) {
2113 for (std::size_t i {1}; i <= n; ++i) {
2114 f.h(k, i) = -f.h(k, i);
2115 f.b(k, i) = -f.b(k, i);
2116 f.qt[((k - 1) * n) + (i - 1)] = -f.qt[((k - 1) * n) + (i - 1)];
2117 }
2118 }
2119 values[k - 1] = {f.h(k, k), 0.0, f.b(k, k)};
2120 }
2121 return values;
2122 }
2123 } // namespace detail
2124
2125 namespace detail {
2131 template <typename T>
2132 [[nodiscard]] std::pair<matrix<T>, double> pencil_operand_in_range(const matrix<T>& m)
2133 {
2134 const double smlnum {std::sqrt(std::numeric_limits<double>::min()) / std::numeric_limits<double>::epsilon()};
2135 const double bignum {1.0 / smlnum};
2136 double norm {0.0};
2137 for (const T& x : m) {
2138 norm = std::max(norm, static_cast<double>(std::abs(x)));
2139 }
2140 const double to {norm > 0.0 && norm < smlnum ? smlnum : norm > bignum ? bignum : norm};
2141 if (to == norm) {
2142 return {m, 1.0};
2143 }
2144 const double factor {to / norm};
2145 buffer<T> entries(m.begin(), m.end());
2146 for (T& x : entries) {
2147 x *= factor;
2148 }
2149 return {matrix<T> {m.rows(), m.cols(), std::move(entries)}, norm / to};
2150 }
2151
2153 template <typename T>
2155 std::size_t n,
2156 double factor)
2157 {
2158 buffer<T> entries {m};
2159 for (T& x : entries) {
2160 x *= factor;
2161 }
2162 return matrix<T> {n, n, std::move(entries)};
2163 }
2164 } // namespace detail
2165
2175 {
2176 public:
2177
2179 using selection = std::function<bool (const std::complex<double>&, const std::complex<double>&)>;
2180
2187 generalized_schur(const matrix<std::complex<double>>& a,
2188 const matrix<std::complex<double>>& b)
2190 b,
2191 30 * std::max<std::size_t>(a.rows(), 1))
2192 {}
2193
2195 generalized_schur(const matrix<std::complex<double>>& a,
2196 const matrix<std::complex<double>>& b,
2197 std::size_t steps)
2198 {
2199 const std::size_t n {a.rows()};
2200 if (a.cols() != n || b.rows() != n || b.cols() != n) {
2201 throw dimension_error("the generalized Schur decomposition requires two square matrices of one order");
2202 }
2203 detail::require_finite(a, "generalized Schur decomposition");
2204 detail::require_finite(b, "generalized Schur decomposition");
2205 // as zgges: each operand within the range of its largest magnitude, S and T and the eigenvalues taken back
2208 a_back_ = a_back;
2209 b_back_ = b_back;
2212 }
2213
2219
2225
2228 {
2229 return transpose(matrix<std::complex<double>> {form_.n, form_.n, form_.qt});
2230 }
2231
2234 {
2235 return transpose(matrix<std::complex<double>> {form_.n, form_.n, form_.zt});
2236 }
2237
2239 [[nodiscard]] const std::vector<std::pair<std::complex<double>, std::complex<double>>>& values() const noexcept
2240 {
2241 return values_;
2242 }
2243
2252 std::size_t reorder(const std::vector<bool>& chosen)
2253 {
2254 const std::size_t n {form_.n};
2255 if (chosen.size() != n) {
2256 throw dimension_error("generalized Schur reordering requires one choice per eigenvalue");
2257 }
2258 detail::qz_form work {form_};
2259 std::size_t moved {0};
2260 for (std::size_t k {0}; k < n; ++k) {
2261 if (!chosen[k]) {
2262 continue;
2263 }
2264 for (std::size_t j {k}; j > moved; --j) { // from place k up to place moved, a swap at a time
2265 if (!detail::exchange_pencil_diagonal(work, j)) {
2266 throw convergence_error("generalized Schur form: eigenvalues could not be separated for reordering");
2267 }
2268 }
2269 ++moved;
2270 }
2271 std::vector<std::pair<std::complex<double>, std::complex<double>>> standardized(n);
2272 for (std::size_t k {1}; k <= n; ++k) {
2273 standardized[k - 1] = detail::standardize(work, k);
2274 }
2275 values_ = unscaled(std::move(standardized));
2276 form_ = std::move(work);
2277 return moved;
2278 }
2279
2282 std::size_t sort(const selection& select)
2283 {
2284 std::vector<bool> chosen(values_.size());
2285 for (std::size_t k {0}; k < values_.size(); ++k) {
2286 chosen[k] = select(values_[k].first, values_[k].second);
2287 }
2288 return reorder(chosen);
2289 }
2290
2291 private:
2292
2294 [[nodiscard]] std::vector<std::pair<std::complex<double>, std::complex<double>>> unscaled(
2295 std::vector<std::pair<std::complex<double>, std::complex<double>>> raw) const
2296 {
2297 for (auto& [alpha, beta] : raw) {
2298 alpha *= a_back_;
2299 beta *= b_back_;
2300 }
2301 return raw;
2302 }
2303
2305 std::vector<std::pair<std::complex<double>, std::complex<double>>> values_;
2306 double a_back_ {1.0};
2307 double b_back_ {1.0};
2308 };
2309
2310 namespace detail {
2311
2322 [[nodiscard]] inline matrix<std::complex<double>> triangular_pencil_vectors(const matrix<std::complex<double>>& s,
2323 const matrix<std::complex<double>>& t,
2324 const std::vector<std::pair<std::complex<double>, std::complex<double>>>& values,
2325 const matrix<std::complex<double>>& basis,
2326 bool left)
2327 {
2328 using C = std::complex<double>;
2329 const std::size_t n {s.rows()};
2330 double s_norm {0.0};
2331 double t_norm {0.0};
2332 for (const C& x : s) {
2333 s_norm = std::max(s_norm, std::abs(x));
2334 }
2335 for (const C& x : t) {
2336 t_norm = std::max(t_norm, std::abs(x));
2337 }
2338 buffer<C> solved(n * n, C {}); // column k the substitution's x: rows 0 … k for a right vector, k … n − 1 a left
2339 parallel_for(n, n * n / 2, [&](std::size_t k) {
2340 const C alpha {values[k].first};
2341 const C beta {values[k].second};
2342 C* x {solved.data() + k}; // x[i] at x + i n
2343 x[k * n] = C {1.0};
2344 if (std::abs(alpha) <= std::numeric_limits<double>::min() && std::abs(beta) <= std::numeric_limits<double>::min()) {
2345 return;
2346 }
2347 // ztgevc's SMIN, at least the smallest normal number: of a zero S or T (`A` or `B` zero) it was 0, and
2348 // each zero pivot divided 0 by 0
2349 const double smallest {std::max(std::numeric_limits<double>::epsilon() * ((std::abs(beta) * s_norm) + (std::abs(alpha) * t_norm)),
2350 std::numeric_limits<double>::min())};
2351 const auto entry = [&](std::size_t i, std::size_t j) { return (beta * s(i, j)) - (alpha * t(i, j)); }; // β S − α T
2352 const auto pivot = [&](std::size_t i) {
2353 const C m {entry(i, i)};
2354 return std::abs(m) < smallest ? C {smallest} : m;
2355 };
2356 // ztgevc's guard against overflow: past 2²⁵⁶ the entries found so far (rows first … last) are brought
2357 // near 1 by a power of 2, exactly, which the unit norm at the end takes back out (a non-normal
2358 // pencil's components grew past the doubles, and its vectors came out ∞ and NaN). Kept below 2²⁵⁷, an
2359 // entry over its pivot (at least ε (|β| ‖S‖ + |α| ‖T‖), of the entries' scale) stays below n 2³⁰⁹
2360 const auto contained = [x, n](std::size_t at, std::size_t first, std::size_t last) {
2361 const double size {std::max(std::abs(x[at * n].real()), std::abs(x[at * n].imag()))};
2362 if (size > 0x1p256) {
2363 const double down {std::ldexp(1.0, -std::ilogb(size))};
2364 for (std::size_t r {first}; r <= last; ++r) {
2365 x[r * n] *= down;
2366 }
2367 }
2368 };
2369 if (!left) { // rows k − 1 … 0 of the upper triangular system
2370 for (std::size_t i {k}; i-- > 0;) {
2371 C sum {};
2372 for (std::size_t j {i + 1}; j <= k; ++j) {
2373 sum += entry(i, j) * x[j * n];
2374 }
2375 x[i * n] = -sum / pivot(i);
2376 contained(i, i, k);
2377 }
2378 }
2379 else { // yᴴ M = 0: (Mᴴ y)_i = 0 for i > k, Mᴴ lower triangular
2380 for (std::size_t i {k + 1}; i < n; ++i) {
2381 C sum {};
2382 for (std::size_t j {k}; j < i; ++j) {
2383 sum += std::conj(entry(j, i)) * x[j * n];
2384 }
2385 x[i * n] = -sum / std::conj(pivot(i));
2386 contained(i, k, i);
2387 }
2388 }
2389 });
2390 const matrix<C> product {basis * matrix<C> {n, n, std::move(solved)}}; // the zeros of each x add nothing
2391 buffer<C> out(product.begin(), product.end());
2392 for (std::size_t k {0}; k < n; ++k) {
2393 double norm {0.0};
2394 for (std::size_t r {0}; r < n; ++r) {
2395 norm = std::hypot(norm, std::abs(out[(r * n) + k]));
2396 }
2397 for (std::size_t r {0}; r < n; ++r) {
2398 out[(r * n) + k] /= norm;
2399 }
2400 }
2401 return matrix<C> {n, n, std::move(out)};
2402 }
2403 } // namespace detail
2404
2415 bool left)
2416 {
2417 return detail::triangular_pencil_vectors(d.s(), d.t(), d.values(), left ? d.q() : d.z(), left);
2418 }
2419
2427 {
2428 public:
2429
2437 const matrix<double>& b)
2439 b,
2440 30 * std::max<std::size_t>(a.rows(), 1))
2441 {}
2442
2445 const matrix<double>& b,
2446 std::size_t steps)
2447 {
2448 const std::size_t n {a.rows()};
2449 if (a.cols() != n || b.rows() != n || b.cols() != n) {
2450 throw dimension_error("the generalized Schur decomposition requires two square matrices of one order");
2451 }
2452 detail::require_finite(a, "generalized Schur decomposition");
2453 detail::require_finite(b, "generalized Schur decomposition");
2454 // as dgges: each operand within the range of its largest magnitude, S and T and the eigenvalues taken back
2457 a_back_ = a_back;
2458 b_back_ = b_back;
2461 }
2462
2465 {
2467 }
2468
2471 {
2473 }
2474
2477 {
2479 }
2480
2483 {
2485 }
2486
2488 [[nodiscard]] const std::vector<detail::real_pencil_value>& values() const noexcept
2489 {
2490 return values_;
2491 }
2492
2494 using selection = std::function<bool (const std::complex<double>&, const std::complex<double>&)>;
2495
2505 std::size_t reorder(const std::vector<bool>& chosen)
2506 {
2507 const std::size_t n {form_.n};
2508 if (chosen.size() != n) {
2509 throw dimension_error("generalized Schur reordering requires one choice per eigenvalue");
2510 }
2512 std::size_t moved {0};
2513 for (std::size_t k {1}; k <= n; ++k) {
2514 const bool pair {k < n && work.h(k + 1, k) != 0.0};
2515 if (chosen[k - 1] || (pair && chosen[k])) {
2516 detail::move_real_block_up(work, k, moved + 1);
2517 moved += pair ? 2 : 1;
2518 }
2519 k += pair ? 1 : 0;
2520 }
2522 form_ = std::move(work);
2523 return moved;
2524 }
2525
2528 std::size_t sort(const selection& select)
2529 {
2530 std::vector<bool> chosen(values_.size());
2531 for (std::size_t k {0}; k < values_.size(); ++k) {
2532 chosen[k] = select(std::complex<double> {values_[k].alphar, values_[k].alphai}, std::complex<double> {values_[k].beta});
2533 }
2534 return reorder(chosen);
2535 }
2536
2537 private:
2538
2544 [[nodiscard]] std::vector<detail::real_pencil_value> unscaled(std::vector<detail::real_pencil_value> raw) const
2545 {
2546 const double safmin {std::numeric_limits<double>::min()};
2547 const double safmax {1.0 / safmin};
2548 const auto rescale = [](detail::real_pencil_value& v, double w) {
2549 v.beta *= w;
2550 v.alphar *= w;
2551 v.alphai *= w;
2552 };
2553 const std::size_t n {form_.n};
2554 for (std::size_t i {0}; i < raw.size(); ++i) {
2556 if (v.alphai == 0.0) {
2557 continue;
2558 }
2559 const double s_ii {form_.s[(i * n) + i]};
2560 if (a_back_ != 1.0) {
2561 if (v.alphar != 0.0 && ((v.alphar / safmax) > (1.0 / a_back_) || (safmin / v.alphar) > a_back_)) {
2562 rescale(v, std::abs(s_ii / v.alphar));
2563 }
2564 else if ((v.alphai / safmax) > (1.0 / a_back_) || (safmin / v.alphai) > a_back_) { // αi > 0: the pair's first
2565 rescale(v, std::abs(form_.s[(i * n) + i + 1] / v.alphai));
2566 }
2567 }
2568 if (b_back_ != 1.0 && ((v.beta / safmax) > (1.0 / b_back_) || (safmin / v.beta) > b_back_)) {
2569 rescale(v, std::abs(form_.t[(i * n) + i] / v.beta));
2570 }
2571 }
2572 for (detail::real_pencil_value& v : raw) {
2573 v.alphar *= a_back_;
2574 v.alphai *= a_back_;
2575 v.beta *= b_back_;
2576 }
2577 return raw;
2578 }
2579
2581 std::vector<detail::real_pencil_value> values_;
2582 double a_back_ {1.0};
2583 double b_back_ {1.0};
2584 };
2585
2594 bool left)
2595 {
2596 using C = std::complex<double>;
2597 const matrix<double> real_s {d.s()};
2598 const matrix<double> real_t {d.t()};
2599 const matrix<double> real_basis {left ? d.q() : d.z()};
2600 const std::size_t n {real_s.rows()};
2601 buffer<C> s(real_s.begin(), real_s.end()); // row-major, S(i, j) at i n + j
2602 buffer<C> t(real_t.begin(), real_t.end());
2603 buffer<C> basis(real_basis.begin(), real_basis.end());
2604 // Rows k and k + 1 of m, from column k, by Uᴴ for U = [u, (−ū1, ū0)].
2605 const auto rows_by = [n](buffer<C>& m, std::size_t k, const C& u0, const C& u1) {
2606 for (std::size_t j {k}; j < n; ++j) {
2607 const C a {m[(k * n) + j]};
2608 const C b {m[((k + 1) * n) + j]};
2609 m[(k * n) + j] = (std::conj(u0) * a) + (std::conj(u1) * b);
2610 m[((k + 1) * n) + j] = (-u1 * a) + (u0 * b);
2611 }
2612 };
2613 // Columns k and k + 1 of m's first `rows` rows by V = [v, (−v̄1, v̄0)].
2614 const auto columns_by = [n](buffer<C>& m, std::size_t k, std::size_t rows, const C& v0, const C& v1) {
2615 for (std::size_t i {0}; i < rows; ++i) {
2616 const C a {m[(i * n) + k]};
2617 const C b {m[(i * n) + k + 1]};
2618 m[(i * n) + k] = (a * v0) + (b * v1);
2619 m[(i * n) + k + 1] = (-a * std::conj(v1)) + (b * std::conj(v0));
2620 }
2621 };
2622 std::size_t k {0};
2623 while (k + 1 < n) {
2624 if (s[((k + 1) * n) + k] == C {}) { // a real eigenvalue's 1 × 1 block
2625 ++k;
2626 continue;
2627 }
2628 // (S_b − λ T_b) v = 0 by the larger row of the 2 × 2 block; u along T_b v, which S_b v is λ times
2629 const detail::real_pencil_value& value {d.values()[k]};
2630 const C lambda {C {value.alphar, value.alphai} / value.beta};
2631 const auto m = [&](std::size_t i, std::size_t j) { return s[(i * n) + j] - (lambda * t[(i * n) + j]); };
2632 const bool upper {std::hypot(std::abs(m(k, k)), std::abs(m(k, k + 1))) >= std::hypot(std::abs(m(k + 1, k)), std::abs(m(k + 1, k + 1)))};
2633 C v0 {upper ? m(k, k + 1) : m(k + 1, k + 1)};
2634 C v1 {upper ? -m(k, k) : -m(k + 1, k)};
2635 const double v_norm {std::hypot(std::abs(v0), std::abs(v1))};
2636 v0 /= v_norm;
2637 v1 /= v_norm;
2638 C u0 {(t[(k * n) + k] * v0) + (t[(k * n) + k + 1] * v1)};
2639 C u1 {t[((k + 1) * n) + k + 1] * v1};
2640 const double u_norm {std::hypot(std::abs(u0), std::abs(u1))};
2641 u0 /= u_norm;
2642 u1 /= u_norm;
2643 rows_by(s, k, u0, u1);
2644 rows_by(t, k, u0, u1);
2645 columns_by(s, k, k + 2, v0, v1);
2646 columns_by(t, k, k + 2, v0, v1);
2647 s[((k + 1) * n) + k] = C {};
2648 t[((k + 1) * n) + k] = C {};
2649 if (left) {
2650 columns_by(basis, k, n, u0, u1);
2651 }
2652 else {
2653 columns_by(basis, k, n, v0, v1);
2654 }
2655 k += 2;
2656 }
2657 std::vector<std::pair<C, C>> diagonal(n);
2658 for (std::size_t i {0}; i < n; ++i) {
2659 diagonal[i] = {s[(i * n) + i], t[(i * n) + i]};
2660 }
2661 return detail::triangular_pencil_vectors(matrix<C> {n, n, std::move(s)}, matrix<C> {n, n, std::move(t)}, diagonal,
2662 matrix<C> {n, n, std::move(basis)}, left);
2663 }
2664
2665 namespace detail {
2666
2674 std::size_t n)
2675 {
2676 constexpr double radix {2.0};
2677 const double sfmin1 {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
2678 const double sfmax1 {1.0 / sfmin1};
2679 const double sfmin2 {sfmin1 * radix};
2680 const double sfmax2 {1.0 / sfmin2};
2681 buffer<double> scale(n, 1.0);
2682 for (bool unbalanced {true}; unbalanced;) {
2683 unbalanced = false;
2684 for (std::size_t i {0}; i < n; ++i) {
2685 double c {0.0};
2686 double r {0.0};
2687 double ca {0.0};
2688 double ra {0.0};
2689 for (std::size_t k {0}; k < n; ++k) {
2690 c = std::hypot(c, m[(k * n) + i]);
2691 r = std::hypot(r, m[(i * n) + k]);
2692 ca = std::max(ca, m[(k * n) + i]);
2693 ra = std::max(ra, m[(i * n) + k]);
2694 }
2695 if (c == 0.0 || r == 0.0) {
2696 continue;
2697 }
2698 const double before {c + r};
2699 double f {1.0};
2700 double g {r / radix};
2701 while (c < g && std::max({f, c, ca}) < sfmax2 && std::min({r, g, ra}) > sfmin2) {
2702 f *= radix;
2703 c *= radix;
2704 ca *= radix;
2705 r /= radix;
2706 g /= radix;
2707 ra /= radix;
2708 }
2709 g = c / radix;
2710 while (g >= r && std::max(r, ra) < sfmax2 && std::min({f, c, g, ca}) > sfmin2) {
2711 f /= radix;
2712 c /= radix;
2713 g /= radix;
2714 ca /= radix;
2715 r *= radix;
2716 ra *= radix;
2717 }
2718 const bool too_small {f < 1.0 && scale[i] < 1.0 && f * scale[i] <= sfmin1};
2719 const bool too_large {f > 1.0 && scale[i] > 1.0 && scale[i] >= sfmax1 / f};
2720 if (c + r >= 0.95 * before || too_small || too_large) {
2721 continue;
2722 }
2723 scale[i] *= f;
2724 unbalanced = true;
2725 for (std::size_t k {0}; k < n; ++k) {
2726 m[(i * n) + k] /= f;
2727 m[(k * n) + i] *= f;
2728 }
2729 }
2730 }
2731 return scale;
2732 }
2733
2735 template <typename T>
2736 [[nodiscard]] double norm_one(const matrix<T>& a)
2737 {
2738 double largest {0.0};
2739 for (std::size_t j {0}; j < a.cols(); ++j) {
2740 double sum {0.0};
2741 for (std::size_t i {0}; i < a.rows(); ++i) {
2742 sum += std::abs(a(i, j));
2743 }
2744 largest = std::max(largest, sum);
2745 }
2746 return largest;
2747 }
2748
2750 template <typename T>
2752 {
2753 const matrix<T>& a;
2754 const matrix<T>& b;
2755 const matrix<T>& q;
2756 const matrix<T>& r;
2757 const matrix<T>* e;
2758 const matrix<T>* s;
2759 };
2760
2763
2767 {
2768 throw convergence_error(continuous ? "The associated Hamiltonian pencil has eigenvalues too close to the imaginary axis"
2769 : "The associated symplectic pencil has eigenvalues too close to the unit circle");
2770 }
2771
2780 template <typename T>
2782 const matrix<T>& bottom,
2783 bool continuous)
2784 {
2785 const std::size_t m {top.rows()};
2786 const matrix<T> factors {lu_decomposition<T> {top}.factors()};
2787 buffer<T> upper(m * m, T {});
2788 for (std::size_t i {0}; i < m; ++i) {
2789 for (std::size_t k {i}; k < m; ++k) {
2790 upper[(i * m) + k] = factors(i, k);
2791 }
2792 }
2793 const vector<double> sigma {singular_values(matrix<T> {m, m, std::move(upper)})};
2794 if (!(sigma[m - 1] > std::numeric_limits<double>::epsilon() * sigma[0])) { // 1/cond ≤ ε, as SciPy (a zero U too)
2795 throw singular_matrix_error("Failed to find a finite solution.");
2796 }
2798 const double tolerance {std::max(std::ldexp(1.0, -43), 0.1 * norm_one(product))};
2801 }
2803 }
2804
2809 template <typename T>
2810 [[nodiscard]] std::pair<buffer<T>, buffer<T>> riccati_pencil(const riccati_operands<T>& terms,
2811 bool continuous)
2812 {
2813 const std::size_t m {terms.a.rows()};
2814 const std::size_t n {terms.b.cols()};
2815 const std::size_t order {(2 * m) + n};
2816 buffer<T> h(order * order, T {});
2817 buffer<T> j(order * order, T {});
2818 const auto e_at = [&terms](std::size_t row, std::size_t col) {
2819 return terms.e != nullptr ? (*terms.e)(row, col) : T {row == col ? 1.0 : 0.0};
2820 };
2821 for (std::size_t i {0}; i < m; ++i) {
2822 for (std::size_t k {0}; k < m; ++k) {
2823 h[(i * order) + k] = terms.a(i, k);
2824 h[((m + i) * order) + k] = -terms.q(i, k);
2825 j[(i * order) + k] = e_at(i, k);
2826 h[((m + i) * order) + m + k] = continuous ? -conj_of(terms.a(k, i)) : conj_of(e_at(k, i));
2827 j[((m + i) * order) + m + k] = continuous ? conj_of(e_at(k, i)) : conj_of(terms.a(k, i));
2828 }
2829 for (std::size_t k {0}; k < n; ++k) {
2830 h[(i * order) + (2 * m) + k] = terms.b(i, k);
2831 if (continuous) {
2832 h[(((2 * m) + k) * order) + m + i] = conj_of(terms.b(i, k));
2833 }
2834 else {
2835 j[(((2 * m) + k) * order) + m + i] = -conj_of(terms.b(i, k));
2836 }
2837 if (terms.s != nullptr) {
2838 h[((m + i) * order) + (2 * m) + k] = -(*terms.s)(i, k);
2839 h[(((2 * m) + k) * order) + i] = conj_of((*terms.s)(i, k));
2840 }
2841 }
2842 }
2843 for (std::size_t i {0}; i < n; ++i) {
2844 for (std::size_t k {0}; k < n; ++k) {
2845 h[(((2 * m) + i) * order) + (2 * m) + k] = terms.r(i, k);
2846 }
2847 }
2848 return {std::move(h), std::move(j)};
2849 }
2850
2857 template <typename T>
2859 buffer<T>& j,
2860 std::size_t m,
2861 std::size_t order)
2862 {
2863 buffer<double> magnitudes(order * order, 0.0);
2864 for (std::size_t i {0}; i < order; ++i) {
2865 for (std::size_t k {0}; k < order; ++k) {
2866 magnitudes[(i * order) + k] = i == k ? 0.0 : std::abs(h[(i * order) + k]) + std::abs(j[(i * order) + k]);
2867 }
2868 }
2870 buffer<double> scale(order, 1.0);
2871 if (std::all_of(found.begin(), found.end(), [](double v) { return std::abs(v - 1.0) <= 1e-8 + 1e-5; })) {
2872 return scale;
2873 }
2874 for (std::size_t i {0}; i < m; ++i) {
2875 const double half {std::nearbyint((std::log2(found[m + i]) - std::log2(found[i])) / 2.0)};
2876 scale[i] = std::exp2(half);
2877 scale[m + i] = std::exp2(-half);
2878 }
2879 std::copy(found.begin() + static_cast<std::ptrdiff_t>(2 * m), found.end(),
2880 scale.begin() + static_cast<std::ptrdiff_t>(2 * m));
2881 for (std::size_t i {0}; i < order; ++i) {
2882 for (std::size_t k {0}; k < order; ++k) {
2883 h[(i * order) + k] *= scale[i] / scale[k];
2884 j[(i * order) + k] *= scale[i] / scale[k];
2885 }
2886 }
2887 return scale;
2888 }
2889
2905 template <typename T>
2907 bool continuous,
2908 bool balanced)
2909 {
2910 using form = std::conditional_t<std::is_same_v<T, double>, real_generalized_schur, generalized_schur>;
2911 const std::size_t m {terms.a.rows()};
2912 const std::size_t n {terms.b.cols()};
2913 const std::size_t order {(2 * m) + n};
2914 auto [h, j] = riccati_pencil(terms, continuous);
2915 const buffer<double> scale {balanced ? balance_pencil(h, j, m, order) : buffer<double>(order, 1.0)};
2916 buffer<T> last(order * n);
2917 for (std::size_t i {0}; i < order; ++i) {
2918 std::copy_n(h.data() + (i * order) + (2 * m), n, last.data() + (i * n));
2919 }
2920 const matrix<T> deflation {qr_decomposition<T> {matrix<T> {order, n, std::move(last)}, qr_mode::complete}.q()};
2921 buffer<T> kept(order * 2 * m); // the columns past the first n: Q₂
2922 buffer<T> h_left(order * 2 * m);
2923 buffer<T> j_left(order * 2 * m);
2924 for (std::size_t t {0}; t < order; ++t) {
2925 std::copy_n(&deflation(t, n), 2 * m, kept.data() + (t * 2 * m));
2926 std::copy_n(h.data() + (t * order), 2 * m, h_left.data() + (t * 2 * m));
2927 std::copy_n(j.data() + (t * order), 2 * m, j_left.data() + (t * 2 * m));
2928 }
2929 const matrix<T> q2 {adjoint_of(matrix<T> {order, 2 * m, std::move(kept)})};
2930 form pencil {q2 * matrix<T> {order, 2 * m, std::move(h_left)}, q2 * matrix<T> {order, 2 * m, std::move(j_left)}};
2931 const std::size_t chosen {continuous ? pencil.sort([](const std::complex<double>& alpha, const std::complex<double>& beta) {
2932 return (alpha * std::conj(beta)).real() < 0.0;
2933 })
2934 : pencil.sort([](const std::complex<double>& alpha, const std::complex<double>& beta) {
2935 return std::abs(alpha) < std::abs(beta);
2936 })};
2937 if (chosen != m) { // a stable half of other than m eigenvalues: some on the boundary, where a real pencil's
2938 refuse_boundary(continuous); // conjugate pair moves whole and its basis passes the symmetry test
2939 }
2940 matrix<T> u {pencil.z()};
2941 if (terms.e != nullptr) { // [D₁ E D₁⁻¹ U₀₀; U₁₀], E scaled as the balancing scaled the pencil
2942 buffer<T> scaled_e(m * m);
2943 buffer<T> upper(m * m);
2944 for (std::size_t i {0}; i < m; ++i) {
2945 for (std::size_t t {0}; t < m; ++t) {
2946 scaled_e[(i * m) + t] = (*terms.e)(i, t) * (scale[i] / scale[t]);
2947 upper[(i * m) + t] = u(i, t);
2948 }
2949 }
2950 const matrix<T> top {matrix<T> {m, m, std::move(scaled_e)} *matrix<T> {m, m, std::move(upper)}};
2951 buffer<T> stacked(2 * m * m);
2952 std::copy(top.begin(), top.end(), stacked.begin());
2953 for (std::size_t i {0}; i < m; ++i) {
2954 for (std::size_t k {0}; k < m; ++k) {
2955 stacked[((m + i) * m) + k] = u(m + i, k);
2956 }
2957 }
2958 u = qr_decomposition<T> {matrix<T> {2 * m, m, std::move(stacked)}, qr_mode::complete}.q();
2959 }
2960 buffer<T> u00(m * m);
2961 buffer<T> u10(m * m);
2962 for (std::size_t i {0}; i < m; ++i) {
2963 for (std::size_t k {0}; k < m; ++k) {
2964 u00[(i * m) + k] = u(i, k);
2965 u10[(i * m) + k] = u(m + i, k);
2966 }
2967 }
2968 const matrix<T> x {stabilising_solution(matrix<T> {m, m, std::move(u00)}, matrix<T> {m, m, std::move(u10)}, continuous)};
2969 buffer<T> out(m * m);
2970 for (std::size_t i {0}; i < m; ++i) {
2971 for (std::size_t k {0}; k < m; ++k) {
2972 out[(i * m) + k] = (x(i, k) + conj_of(x(k, i))) * (scale[i] * scale[k] / 2.0);
2973 }
2974 }
2975 return matrix<T> {m, m, std::move(out)};
2976 }
2977
2983 const matrix<std::complex<double>>& x,
2984 matrix<std::complex<double>>& closed)
2985 {
2986 using C = std::complex<double>;
2987 const matrix<C> xe {terms.e != nullptr ? x * *terms.e : x};
2988 matrix<C> coupling {adjoint_of(terms.b) * xe};
2989 if (terms.s != nullptr) {
2990 coupling = coupling + adjoint_of(*terms.s);
2991 }
2992 const matrix<C> gain {solve(terms.r, coupling)}; // r nonsingular: checked as SciPy checks it
2993 const matrix<C> product {adjoint_of(terms.a) * xe};
2994 closed = terms.a - (terms.b * gain);
2995 return ((product + adjoint_of(product)) - (adjoint_of(coupling) * gain)) + terms.q;
2996 }
2997
2999 [[nodiscard]] inline bool entries_finite(std::initializer_list<const matrix<std::complex<double>>*> xs)
3000 {
3001 return std::all_of(xs.begin(), xs.end(), [](const matrix<std::complex<double>>* x) {
3002 return std::all_of(x->begin(), x->end(), [](const std::complex<double>& z) { return is_finite_entry(z); });
3003 });
3004 }
3005
3011 [[nodiscard]] inline double continuous_backward_error(const riccati_terms& terms,
3012 const matrix<std::complex<double>>& x)
3013 {
3014 using C = std::complex<double>;
3016 const matrix<C> residual {continuous_residual(terms, x, closed)};
3017 matrix<C> coupling {adjoint_of(terms.b) * x};
3018 if (terms.s != nullptr) {
3019 coupling = coupling + adjoint_of(*terms.s);
3020 }
3021 const double size {(2.0 * norm_one(terms.a) * norm_one(x)) + (norm_one(coupling) * norm_one(solve(terms.r, coupling))) + norm_one(terms.q)};
3022 const double error {norm_one(residual) / size};
3023 return std::isfinite(error) ? error : std::numeric_limits<double>::infinity();
3024 }
3025
3034 matrix<std::complex<double>>&& x)
3035 {
3036 using C = std::complex<double>;
3038 const matrix<C> residual {continuous_residual(terms, x, closed)};
3039 const matrix<C> f {terms.e != nullptr ? solve(*terms.e, closed) : closed};
3040 if (!entries_finite({&residual, &f})) { // a term past the doubles (an X near 1e154): no step, the solver refuses it
3041 return std::move(x);
3042 }
3043 const matrix<C> y {solve_sylvester(adjoint_of(f), f, C {-1.0} *residual)};
3044 const matrix<C> delta {terms.e != nullptr ? adjoint_of(solve(adjoint_of(*terms.e), adjoint_of(solve(adjoint_of(*terms.e), y))))
3045 : y};
3046 const std::size_t m {x.rows()};
3047 buffer<C> stepped(m * m);
3048 for (std::size_t i {0}; i < m; ++i) {
3049 for (std::size_t k {0}; k < m; ++k) {
3050 stepped[(i * m) + k] = x(i, k) + ((delta(i, k) + std::conj(delta(k, i))) / 2.0);
3051 }
3052 }
3053 matrix<C> refined {m, m, std::move(stepped)};
3056 return refined;
3057 }
3058 return std::move(x);
3059 }
3060 } // namespace detail
3061
3062 namespace detail {
3063
3065 [[nodiscard]] inline matrix<std::complex<double>> answer_like(matrix<std::complex<double>>&& x,
3066 const matrix<std::complex<double>>& /*like*/)
3067 {
3068 return std::move(x);
3069 }
3070
3072 [[nodiscard]] inline matrix<double> answer_like(const matrix<std::complex<double>>& x,
3073 const matrix<double>& /*like*/)
3074 {
3075 buffer<double> real(x.rows() * x.cols());
3076 std::transform(x.begin(), x.end(), real.begin(), [](const std::complex<double>& z) { return z.real(); });
3077 return matrix<double> {x.rows(), x.cols(), std::move(real)};
3078 }
3079
3085 inline void require_hermitian(const matrix<std::complex<double>>& x,
3086 const char* name)
3087 {
3088 const double size {norm_one(x)};
3089 if (norm_one(x - adjoint_of(x)) > 100.0 * (std::nextafter(size, std::numeric_limits<double>::infinity()) - size)) {
3090 throw argument_error(std::string {"Matrix "} + name + " should be symmetric/hermitian.");
3091 }
3092 }
3093
3102 template <typename T>
3104 std::size_t m)
3105 {
3106 const std::size_t order {2 * m};
3107 buffer<double> d(m, 1.0);
3108 const auto at {[&h, order](std::size_t i, std::size_t j) { return std::abs(h[(i * order) + j]); }};
3109 for (bool moved {true}; moved;) {
3110 moved = false;
3111 for (std::size_t i {0}; i < m; ++i) {
3112 const std::size_t pair {m + i};
3113 double grown {0.0}; // column i and row m + i, but their common entry
3114 double shrunk {0.0}; // row i and column m + i, but theirs
3115 const double grown_twice {at(pair, i)};
3116 const double shrunk_twice {at(i, pair)};
3117 for (std::size_t k {0}; k < order; ++k) {
3118 if (k != i && k != pair) {
3119 grown += at(k, i) + at(pair, k);
3120 shrunk += at(i, k) + at(k, pair);
3121 }
3122 }
3123 if (!(std::min(grown + grown_twice, shrunk + shrunk_twice) > 0.0)) {
3124 continue; // a side with nothing: no power of 2 is least
3125 }
3126 const auto sum {[grown, grown_twice, shrunk, shrunk_twice](double f) { return (grown * f) + (grown_twice * f * f) + (shrunk / f) + (shrunk_twice / (f * f)); }};
3127 double f {1.0};
3128 while (sum(2.0 * f) < sum(f)) {
3129 f *= 2.0;
3130 }
3131 while (sum(0.5 * f) < sum(f)) {
3132 f *= 0.5;
3133 }
3134 if (!(sum(f) < 0.95 * sum(1.0))) {
3135 continue;
3136 }
3137 for (std::size_t k {0}; k < order; ++k) {
3138 h[(i * order) + k] /= f;
3139 h[(pair * order) + k] *= f;
3140 }
3141 for (std::size_t k {0}; k < order; ++k) {
3142 h[(k * order) + i] *= f;
3143 h[(k * order) + pair] /= f;
3144 }
3145 d[i] *= f;
3146 moved = true;
3147 }
3148 }
3149 return d;
3150 }
3151
3164 template <typename T>
3166 const matrix<T>& b,
3167 const matrix<T>& q,
3168 const matrix<T>& r,
3169 const matrix<T>* s,
3170 bool balanced)
3171 {
3172 const std::size_t m {a.rows()};
3173 const matrix<T> g {b * solve(r, adjoint_of(b))};
3174 matrix<T> shift {a};
3175 matrix<T> weight {q};
3176 if (s != nullptr) {
3177 const matrix<T> cross {solve(r, adjoint_of(*s))}; // R⁻¹ Sᴴ
3178 shift = a - (b * cross);
3179 weight = q - (*s * cross);
3180 }
3181 const std::size_t order {2 * m};
3182 buffer<T> h(order * order);
3183 for (std::size_t i {0}; i < m; ++i) {
3184 for (std::size_t j {0}; j < m; ++j) {
3185 h[(i * order) + j] = shift(i, j);
3186 h[(i * order) + m + j] = -(g(i, j) + conj_of(g(j, i))) / 2.0;
3187 h[((m + i) * order) + j] = -(weight(i, j) + conj_of(weight(j, i))) / 2.0;
3188 h[((m + i) * order) + m + j] = -conj_of(shift(j, i));
3189 }
3190 }
3191 const buffer<double> d {balanced ? balance_hamiltonian(h, m) : buffer<double>(m, 1.0)};
3192 schur_decomposition<T> form {matrix<T> {order, order, std::move(h)}};
3193 const std::vector<std::complex<double>> values {form.values()};
3194 std::vector<bool> chosen(order);
3195 for (std::size_t k {0}; k < order; ++k) {
3196 chosen[k] = values[k].real() < 0.0;
3197 }
3198 if (form.reorder(chosen) != m) {
3199 throw convergence_error("The associated Hamiltonian matrix has eigenvalues too close to the imaginary axis");
3200 }
3201 buffer<T> u11(m * m);
3202 buffer<T> u21(m * m);
3203 for (std::size_t i {0}; i < m; ++i) {
3204 for (std::size_t k {0}; k < m; ++k) {
3205 u11[(i * m) + k] = form.z()(i, k);
3206 u21[(i * m) + k] = form.z()(m + i, k);
3207 }
3208 }
3209 const matrix<T> x {stabilising_solution(matrix<T> {m, m, std::move(u11)}, matrix<T> {m, m, std::move(u21)}, true)};
3210 buffer<T> out(m * m);
3211 for (std::size_t i {0}; i < m; ++i) {
3212 for (std::size_t k {0}; k < m; ++k) {
3213 out[(i * m) + k] = (x(i, k) + conj_of(x(k, i))) / (2.0 * d[i] * d[k]); // D⁻¹ X̃ D⁻¹, exact
3214 }
3215 }
3216 return matrix<T> {m, m, std::move(out)};
3217 }
3218
3223 template <typename T>
3224 [[nodiscard]] matrix<T> solve_are(const matrix<T>& a,
3225 const matrix<T>& b,
3226 const matrix<T>& q,
3227 const matrix<T>& r,
3228 const matrix<T>* e,
3229 const matrix<T>* s,
3230 bool balanced,
3231 bool continuous)
3232 {
3233 const char* name {continuous ? "solve_continuous_are" : "solve_discrete_are"};
3234 const std::size_t m {a.rows()};
3235 const std::size_t n {b.cols()};
3236 const bool e_fits {e == nullptr || (e->rows() == m && e->cols() == m)};
3237 const bool s_fits {s == nullptr || (s->rows() == m && s->cols() == n)};
3238 if (m == 0 || n == 0 || a.cols() != m || b.rows() != m || q.rows() != m || q.cols() != m || r.rows() != n
3239 || r.cols() != n || !e_fits || !s_fits) {
3240 throw dimension_error(std::string {name}
3241 + " requires a square a (m × m, m ≥ 1), b (m × n, n ≥ 1), q (m × m), r (n × n), "
3242 "e (m × m) and s (m × n)");
3243 }
3244 for (const matrix<T>* operand : {&a, &b, &q, &r, e, s}) {
3245 if (operand != nullptr) {
3246 require_finite(*operand, name);
3247 }
3248 }
3249 const auto& ca {as_complex(a)};
3250 const auto& cb {as_complex(b)};
3251 const auto& cq {as_complex(q)};
3252 const auto& cr {as_complex(r)};
3253 require_hermitian(cq, "q");
3254 require_hermitian(cr, "r");
3255 bool hamiltonian {false};
3256 if (continuous) { // R⁻¹ is the equation's: SciPy refuses a numerically singular r
3257 const vector<double> sigma {singular_values(cr)};
3258 if (!(sigma[n - 1] >= std::numeric_limits<double>::epsilon() * norm_one(cr)) || sigma[n - 1] == 0.0) {
3259 throw argument_error("Matrix r is numerically singular.");
3260 }
3261 // a well-conditioned R (within √ε of singular) and no E: the Hamiltonian's Schur form, else the pencil's
3262 hamiltonian = e == nullptr && sigma[n - 1] >= std::sqrt(std::numeric_limits<double>::epsilon()) * sigma[0];
3263 }
3264 std::optional<matrix<std::complex<double>>> ce;
3265 std::optional<matrix<std::complex<double>>> cs;
3266 if (e != nullptr) {
3267 ce.emplace(as_complex(*e));
3268 const vector<double> sigma {singular_values(*ce)};
3269 if (!(sigma[0] * std::numeric_limits<double>::epsilon() < sigma[m - 1])) {
3270 throw singular_matrix_error("Matrix e is numerically singular.");
3271 }
3272 }
3273 if (s != nullptr) {
3274 cs.emplace(as_complex(*s));
3275 }
3276 const riccati_terms terms {ca, cb, cq, cr, ce ? &*ce : nullptr, cs ? &*cs : nullptr};
3277 // a real equation's pencil in real arithmetic, real_generalized_schur's double shifts, as SciPy's dgges
3278 if (!continuous) { // no step of Newton's (Hewer's): its residual, rounded at ε ‖A‖² ‖X‖ where the continuous one
3279 // is at ε ‖A‖ ‖X‖, steers the step away from X wherever A is large or graded
3280 return answer_like(matrix<std::complex<double>> {as_complex(riccati(riccati_operands<T> {a, b, q, r, e, s}, false, balanced))}, a);
3281 }
3282 // the Hamiltonian's G = B R⁻¹ Bᴴ, formed, loses what the pencil keeps (a Q of 10⁹ beside a B of rank one, its
3283 // residual at 10⁻⁵ where the pencil's is at 10⁻⁹): past 64 m ε of its terms, the pencil's answer instead
3284 if (hamiltonian) {
3285 matrix<std::complex<double>> fast {newton_refined(terms, matrix<std::complex<double>> {as_complex(hamiltonian_riccati(a, b, q, r, s, balanced))})};
3286 if (continuous_backward_error(terms, fast) <= 64.0 * static_cast<double>(m) * std::numeric_limits<double>::epsilon()) {
3287 return answer_like(std::move(fast), a);
3288 }
3289 }
3290 return answer_like(newton_refined(terms, matrix<std::complex<double>> {as_complex(riccati(riccati_operands<T> {a, b, q, r, e, s}, true, balanced))}), a);
3291 }
3292 } // namespace detail
3293
3318 template <typename T>
3319 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3321 const matrix<T>& b,
3322 const matrix<T>& q,
3323 const matrix<T>& r,
3324 const std::type_identity_t<matrix<T>>* e = nullptr,
3325 const std::type_identity_t<matrix<T>>* s = nullptr,
3326 bool balanced = true)
3327 {
3328 return detail::solve_are(a, b, q, r, e, s, balanced, true);
3329 }
3330
3352 template <typename T>
3353 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3355 const matrix<T>& b,
3356 const matrix<T>& q,
3357 const matrix<T>& r,
3358 const std::type_identity_t<matrix<T>>* e = nullptr,
3359 const std::type_identity_t<matrix<T>>* s = nullptr,
3360 bool balanced = true)
3361 {
3362 return detail::solve_are(a, b, q, r, e, s, balanced, false);
3363 }
3364} // namespace numerical
3365
3366#endif // NUMERICAL_GENERALIZED_HPP
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Definition vector.hpp:87
Thrown when an iterative algorithm has not converged within its bound of sweeps.
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
Definition vector.hpp:40
The generalized Schur decomposition of a complex pencil A − λ B, A = Q S Zᴴ and B = Q T Zᴴ,...
std::vector< std::pair< std::complex< double >, std::complex< double > > > unscaled(std::vector< std::pair< std::complex< double >, std::complex< double > > > raw) const
The eigenvalues of the scaled form raw taken back: α by A's factor, β by B's.
std::vector< std::pair< std::complex< double >, std::complex< double > > > values_
The eigenvalues as (α, β).
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen are set to the leading diagonal places,...
const std::vector< std::pair< std::complex< double >, std::complex< double > > > & values() const noexcept
The eigenvalues as (α, β), in the diagonals' order: α = S(k, k), β = T(k, k).
generalized_schur(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b)
Decomposes the pencil of a and b.
matrix< std::complex< double > > s() const
S, upper triangular.
std::function< bool(const std::complex< double > &, const std::complex< double > &)> selection
The selection scipy.linalg.ordqz takes: true for (α, β) to lead.
generalized_schur(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b, std::size_t steps)
Decomposes the pencil within steps QZ iterations (zhgeqz's bound 30 n by default).
matrix< std::complex< double > > t() const
T, upper triangular, its diagonal real and non-negative.
detail::qz_form form_
S, T, Q and Z, of the scaled pencil.
matrix< std::complex< double > > q() const
Q, unitary: A = Q S Zᴴ.
double a_back_
The factor taking S back to A's scale.
std::size_t sort(const selection &select)
The eigenvalues select holds moved first (reorder), as scipy.linalg.ordqz(…, sort=…) sorts them.
matrix< std::complex< double > > z() const
Z, unitary.
An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of ...
matrix< T > factors() const &
L and U in one matrix, as LAPACK's dgetrf leaves them: U on and above the diagonal,...
A dense, row-major matrix of T with value semantics.
Definition matrix.hpp:36
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
Definition matrix.hpp:139
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
Definition matrix.hpp:133
std::size_t rows() const noexcept
The number of rows.
Definition matrix.hpp:108
std::size_t cols() const noexcept
The number of columns.
Definition matrix.hpp:114
A QR factorisation A = Q R of an m × n matrix, as NumPy's qr, reduced by default.
The generalized real Schur decomposition of a real pencil A − λ B, A = Q S Zᵀ and B = Q T Zᵀ,...
matrix< double > t() const
T, upper triangular, its diagonal non-negative.
double a_back_
The factor taking S back to A's scale.
std::size_t sort(const selection &select)
The eigenvalues select holds moved first (reorder), as scipy.linalg.ordqz(…, sort=…) sorts them.
const std::vector< detail::real_pencil_value > & values() const noexcept
The eigenvalues as (αr, αi, β), in the diagonal's order.
std::function< bool(const std::complex< double > &, const std::complex< double > &)> selection
The selection scipy.linalg.ordqz takes: true for (α, β) to lead, α = αr + i αi.
matrix< double > s() const
S, quasi-triangular.
matrix< double > z() const
Z, orthogonal.
detail::real_qz_form form_
S, T, Q and Z, of the scaled pencil.
real_generalized_schur(const matrix< double > &a, const matrix< double > &b, std::size_t steps)
Decomposes the pencil within steps QZ iterations (dhgeqz's bound 30 n by default).
matrix< double > q() const
Q, orthogonal: A = Q S Zᵀ.
real_generalized_schur(const matrix< double > &a, const matrix< double > &b)
Decomposes the pencil of a and b.
std::vector< detail::real_pencil_value > unscaled(std::vector< detail::real_pencil_value > raw) const
The eigenvalues of the scaled form raw taken back, as dgges takes them: α by A's factor,...
std::vector< detail::real_pencil_value > values_
The eigenvalues.
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen are set to the leading diagonal places,...
The Schur decomposition A = Z T Zᴴ of a square matrix, as scipy.linalg.schur (LAPACK's dgees/zgees): ...
Definition eigen.hpp:3501
Thrown when a matrix has no unique solution (it is singular).
A dense vector of T with value semantics.
Definition vector.hpp:171
Functions of a square matrix and the matrix equations solved through Schur forms: the exponential,...
std::pair< matrix< T >, double > pencil_operand_in_range(const matrix< T > &m)
m brought into the range [√safmin / ε, ε / √safmin] of its largest magnitude where it lies outside,...
double pencil_wsize(const pencil_bounds &b, double w) noexcept
dlag2's WSIZE: the divisor that keeps an eigenvalue of magnitude w in range.
void exchange_or_refuse(real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
exchange_real_blocks, a refusal thrown as real_generalized_schur::reorder reports it.
std::optional< std::pair< small_square, small_square > > generalized_sylvester(const small_square &s, const small_square &t, std::size_t n1, std::size_t n2)
The solution (R, L) (n1 × n2 each) of the generalized Sylvester equations S₁₁ R − L S₂₂ = S₁₂,...
small_square small_product(const small_square &x, bool tx, const small_square &y, bool ty, std::size_t m)
op(x) op(y) of order m, op the transpose where tx (ty).
std::optional< block_exchange > plan_single_exchange(small_square s, small_square t, double thresha, double threshb)
Two 1 × 1 blocks' exchange, as LAPACK's dtgex2 makes it: columns turned onto the second eigenvalue's ...
real_qz_form real_hessenberg_triangular(const matrix< double > &a, const matrix< double > &b)
The real a and b to Hessenberg-triangular form, as LAPACK's dgges begins: B = Q R by the QR factorisa...
double norm_one(const matrix< T > &a)
The 1-norm of a: its largest column sum of moduli.
matrix< std::complex< double > > triangular_pencil_vectors(const matrix< std::complex< double > > &s, const matrix< std::complex< double > > &t, const std::vector< std::pair< std::complex< double >, std::complex< double > > > &values, const matrix< std::complex< double > > &basis, bool left)
The right (or, where left, the left) eigenvectors of the triangular pencil (s, t) whose diagonal is v...
buffer< double > scaling_balance(buffer< double > &m, std::size_t n)
The scaling of LAPACK's ‘dgebal('S’)for the non-negativen × n\p m (row-major, scaled in place): rows ...
matrix< T > scaled_back(const buffer< T > &m, std::size_t n, double factor)
The entries of m multiplied by factor, n × n row-major (the scaled form taken back).
std::optional< block_exchange > plan_block_exchange(small_square s, small_square t, std::size_t n1, std::size_t n2, double thresha)
The exchange of blocks of orders n1 and n2 (one of them 2), as LAPACK's dtgex2 makes it: orthogonal b...
double modulus_one(const std::complex< double > &z)
|Re z| + |Im z|, LAPACK's ABS1.
pencil_pair pencil_eigenvalues(double a11, double a12, double a21, double a22, double b11, double b12, double b22, double safmin)
The eigenvalues of the pencil A − w B, A (a11 a12 / a21 a22) and the upper triangular B (b11 b12 / 0 ...
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
void reflect_columns(T *panel, std::size_t height, const buffer< T > &v, std::size_t first, std::size_t from, std::size_t to, const T &s=T {2})
Applies I − s v vᴴ from the left (s 2 for a unit v) to the columns from…to-1 of the column-major pane...
matrix< std::complex< double > > answer_like(matrix< std::complex< double > > &&x, const matrix< std::complex< double > > &)
x itself, for complex operands like.
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::vector< real_pencil_value > real_values(real_qz_form &f)
The eigenvalues of the real generalized Schur form f after a reordering, as LAPACK's dtgsen gives the...
matrix< std::complex< double > > continuous_residual(const riccati_terms &terms, const matrix< std::complex< double > > &x, matrix< std::complex< double > > &closed)
The residual Aᴴ X E + Eᴴ X A − (Eᴴ X B + S) R⁻¹ (Bᴴ X E + Sᴴ) + Q of the continuous equation at the H...
qz_form hessenberg_triangular(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b)
a and b (n × n, row-major) to Hessenberg-triangular form, as LAPACK's zgges begins: B = Q R by the QR...
std::pair< std::complex< double >, std::complex< double > > standardize(qz_form &f, std::size_t j)
T(j, j) made real and non-negative, as zhgeqz standardises it: row j of T and S above the diagonal an...
double frobenius_two(const std::array< std::complex< double >, 4 > &m)
The Frobenius norm of the 2 × 2 block m.
bool exchange_real_blocks(real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
Exchanges the adjacent diagonal blocks of orders n1 and n2 (1 or 2) at j1 (from 1) of the real genera...
void move_real_block_up(real_qz_form &f, std::size_t ifst, std::size_t ilst)
Moves the diagonal block at ifst (from 1) of the real generalized Schur form f up to ilst,...
matrix< std::complex< double > > newton_refined(const riccati_terms &terms, matrix< std::complex< double > > &&x)
One step of Newton's method on the continuous equation from the Schur method's x (Kleinman,...
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
void double_shift_sweep(real_qz_form &f, std::size_t ifirst, std::size_t ilast, double ascale, double bscale, double safmin)
One double-shift QZ sweep (Moler and Stewart) on rows and columns ifirst … ilast of f,...
plane_rotation< double > givens(double f, double g)
The rotation that takes (f, g) to (r, 0), as LAPACK's dlartg: r of f's sign.
Definition eigen.hpp:1315
double continuous_backward_error(const riccati_terms &terms, const matrix< std::complex< double > > &x)
The residual at x of the continuous equation without E (the Hamiltonian's), relative to its terms: ‖R...
double small_reflector(double(&v)[3], std::size_t count)
The Householder reflection I − τ v vᵀ, v = (1, x…), that takes (α, x…) to (β, 0…),...
Definition eigen.hpp:647
std::vector< std::pair< std::complex< double >, std::complex< double > > > qz_iteration(qz_form &f, std::size_t steps)
The Hessenberg-triangular f to generalized Schur form, as LAPACK's zhgeqz (Schur form,...
void standardize_at(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index j)
The standard form of the 2 × 2 block at j of the quasi-triangular t, its rotation carried to the rest...
Definition eigen.hpp:1494
buffer< double > balance_pencil(buffer< T > &h, buffer< T > &j, std::size_t m, std::size_t order)
Balances the pencil (H, J) of order 2m + n as SciPy does: ‘dgebal('S’)scaling of|H| + |J|off the diag...
bool exchange_pencil_diagonal(qz_form &f, std::size_t j)
Exchanges the diagonal entries j and j + 1 (from 1) of the triangular pencil f, as LAPACK's ztgex2: c...
const matrix< std::complex< double > > & as_complex(const matrix< std::complex< double > > &a)
a itself: already complex.
std::pair< buffer< T >, buffer< T > > riccati_pencil(const riccati_operands< T > &terms, bool continuous)
The extended pencil (H, J) of order 2m + n of SciPy's solve_continuous_are (continuous) or solve_disc...
small_square small_qr(small_square x, std::size_t m, std::size_t k)
The orthogonal Q (order m) of the Householder QR factorisation of the first k columns of x (m × k,...
void require_hermitian(const matrix< std::complex< double > > &x, const char *name)
Refuses x (named name in the message) unless Hermitian, as SciPy's _are_validate_args: ‖X − Xᴴ‖₁ with...
buffer< double > balance_hamiltonian(buffer< T > &h, std::size_t m)
The diagonal D of a symplectic balancing of the Hamiltonian h of order 2m (row-major,...
pencil_rotations standardize_pencil(std::array< std::array< double, 2 >, 2 > &a, std::array< std::array< double, 2 >, 2 > &b)
The 2 × 2 pencil (a, b), b upper triangular, standardized, as LAPACK's dlagv2: two real eigenvalues m...
std::pair< real_pencil_value, real_pencil_value > pair_values(real_qz_form &f, std::size_t ilast, const pencil_pair &pair, double b11, double b22)
The conjugate pair of the standardized 2 × 2 block ending at ilast of f (T diagonal,...
void refuse_boundary(bool continuous)
Refuses a Riccati equation whose pencil has eigenvalues on (or too close to) the boundary.
bool entries_finite(std::initializer_list< const matrix< std::complex< double > > * > xs)
Whether every entry of the matrices xs is finite.
void rotate_pair(T *x, T *y, std::size_t count, std::size_t stride, double c, const T &s)
(x, y) ← (c x + s y, c y − s̄ x) over count pairs stride apart.
Definition eigen.hpp:1347
double hypot3(double x, double y, double z)
√(x² + y² + z²) without overflow, LAPACK's dlapy3.
matrix< T > riccati(const riccati_operands< T > &terms, bool continuous, bool balanced)
The stabilising solution of the continuous (continuous) or discrete algebraic Riccati equation by Sci...
std::vector< real_pencil_value > real_qz_iteration(real_qz_form &f, std::size_t steps)
The Hessenberg-triangular f to generalized real Schur form, as LAPACK's dhgeqz (Schur form,...
triangle_svd svd_of_triangle(double f, double g, double h)
The SVD of the upper triangular [f g; 0 h], as LAPACK's dlasv2: [csl snl; −snl csl] [f g; 0 h] [csr −...
matrix< T > stabilising_solution(const matrix< T > &top, const matrix< T > &bottom, bool continuous)
X = U₂₁ U₁₁⁻¹ from the m leading Schur vectors' halves top (U₁₁) and bottom (U₂₁) of a Riccati equati...
double small_norm(const small_square &x, std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1)
The Frobenius norm of rows r0 … r1 − 1 and columns c0 … c1 − 1 of x.
matrix< T > adjoint_of(const matrix< T > &m)
Mᴴ: the transpose, conjugated.
matrix< T > hamiltonian_riccati(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *s, bool balanced)
The stabilising solution of the continuous equation without E from the Schur form of the Hamiltonian ...
matrix< T > solve_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *e, const matrix< T > *s, bool balanced, bool continuous)
The checks of SciPy's _are_validate_args, then riccati on complex operands, the answer real for real ...
The NumericAL public API.
Definition amx.hpp:44
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
matrix< std::complex< double > > generalized_eigenvectors(const generalized_schur &d, bool left)
The right (or, where left, the left) eigenvectors of the pencil d decomposes, as LAPACK's ztgevc and ...
T dot(const vector< T > &a, const vector< T > &b)
Dot product.
Definition vector.hpp:275
vector< T > solve(matrix< T > a, const vector< T > &b)
Solves the linear system A x = b for a square A.
tensor< T > diag(const tensor< T > &v, std::ptrdiff_t k)
The square matrix with the vector v on its k diagonal (above the main one for a positive k) and zeros...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
T max(const tensor< T > &t)
The largest element (a NaN, if there is one), of a transpose's elements as they lie (in any order the...
@ complete
Q is m × m, its columns past k a basis of the complement of A's column space; R is m × n.
tensor< T > diagonal(const tensor< T > &t, std::ptrdiff_t offset)
The offset diagonal of each matrix of t (its last two axes), as numpy.linalg.diagonal: above the main...
matrix< T > solve_continuous_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
The stabilising solution X of the continuous algebraic Riccati equation Aᴴ X E + Eᴴ X A − (Eᴴ X B + S...
vector< double > singular_values(const matrix< T > &a)
The singular values of a, descending, without its singular vectors, as numpy.linalg....
Definition svd.hpp:2274
matrix< T > solve_sylvester(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q)
The solution X (m × n) of the Sylvester equation A X + X B = Q, as scipy.linalg.solve_sylvester: by B...
matrix< T > solve_discrete_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
The stabilising solution X of the discrete algebraic Riccati equation Aᴴ X A − Eᴴ X E − (Aᴴ X B + S) ...
An exchange of two diagonal blocks as exchange_real_blocks plans it: the blocks after it,...
small_square li
The rows' transform: ‘S’ = LIᵀ S IR,Q ← Q LI`.
small_square ir
The columns': Z ← Z IR.
small_square s
The m × m block of S after the exchange.
The bounds of dlag2's WSIZE (pencil_wsize), fixed by the pencil's scales.
double c5
The eigenvalue's least size counted.
double c2
safmin · max(1, bnorm).
double floor
The divisor's least value.
double c4
The divisor's cap before the eigenvalue's own size.
The eigenvalues of a 2 × 2 pencil, scaled (pencil_eigenvalues): wr1 / scale1 and wr2 / scale2,...
double scale1
The first's scale.
double wr1
The first's scaled real part.
double wi
The pair's scaled imaginary part, non-negative; 0 for real ones.
The rotations dlagv2 applies to a 2 × 2 pencil: [csl snl; −snl csl] (A, B) [csr −snr; snr csr].
A plane rotation [c s; −s̄ c] and what it leaves of its first argument.
Definition eigen.hpp:1308
A complex pencil in generalized Schur form being formed: S and T (n × n, row-major) with A = Q S Zᴴ a...
buffer< std::complex< double > > s
S, upper Hessenberg, then triangular.
static void rotate_columns(buffer< std::complex< double > > &m, std::size_t n, std::size_t j, std::size_t k, std::size_t first, std::size_t last, double c, const std::complex< double > &sine)
Columns j and k (from 1) of m over the rows from first to last (from 1), first ≤ last: every caller's...
std::complex< double > & h(std::size_t i, std::size_t j)
S(i, j), from 1.
buffer< std::complex< double > > qt
Qᵀ by rows: Q's columns, each contiguous for the rotations.
std::size_t n
The order.
buffer< std::complex< double > > t
T, upper triangular.
static void rotate_rows(buffer< std::complex< double > > &m, std::size_t n, std::size_t i, std::size_t first, std::size_t last, double c, const std::complex< double > &sine)
Rows i and i + 1 (from 1) of m over the columns from first (from 1) to last.
std::complex< double > & b(std::size_t i, std::size_t j)
T(i, j), from 1.
buffer< std::complex< double > > zt
Zᵀ by rows.
static void rotate_vectors(buffer< std::complex< double > > &mt, std::size_t n, std::size_t j, std::size_t k, double c, const std::complex< double > &sine)
Columns j and k (from 1) of Q or Z whole, rows j and k of mt, its transpose: rotate_columns's arithme...
A generalized eigenvalue (αr + i αi) / β of a real pencil, as LAPACK's dgges gives it.
double alphai
Its imaginary part: of opposite signs within a conjugate pair, the first positive.
double beta
β ≥ 0, 0 for an infinite eigenvalue.
double alphar
The real part of α.
A real pencil in generalized real Schur form being formed: S and T (n × n, row-major) with A = Q S Zᵀ...
static void rotate_rows(buffer< double > &m, std::size_t n, std::size_t i, std::size_t k, std::size_t first, std::size_t last, double c, double sine)
LAPACK's drot on rows i and k (from 1) of m over the columns first … last: x ← c x + s y,...
double & h(std::size_t i, std::size_t j)
S(i, j), from 1.
buffer< double > t
T, upper triangular.
double & b(std::size_t i, std::size_t j)
T(i, j), from 1.
buffer< double > s
S, upper Hessenberg, then quasi-triangular.
buffer< double > qt
Qᵀ by rows: Q's columns, each contiguous for the rotations and reflections.
buffer< double > zt
Zᵀ by rows.
static void rotate_columns(buffer< double > &m, std::size_t n, std::size_t j, std::size_t k, std::size_t first, std::size_t last, double c, double sine)
LAPACK's drot on columns j and k (from 1) of m over the rows first … last: x ← c x + s y,...
The operands of an algebraic Riccati equation in the arithmetic of T, e and s absent when null.
A square of order 4 at most, row-major in a fixed stride: the blocks dtgex2 exchanges and its transfo...
double & operator()(std::size_t i, std::size_t j)
The entry (i, j), from 0.
double operator()(std::size_t i, std::size_t j) const
The entry (i, j), from 0.
static small_square identity(std::size_t m)
The identity of order m.
std::array< double, 16 > e
The entries, (i, j) at 4 i + j.
The singular value decomposition of the upper triangular [f g; 0 h] (svd_of_triangle).
double ssmin
The smaller singular value, signed.
double ssmax
The larger, signed.
double snr
The right rotation's sine.
double snl
The left rotation's sine.
The singular value decomposition and what it answers: the singular values, least squares,...