NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
eigen.hpp
Go to the documentation of this file.
1
17#ifndef NUMERICAL_EIGEN_HPP
18#define NUMERICAL_EIGEN_HPP
19
20#include <algorithm>
21#include <array>
22#include <cmath>
23#include <complex>
24#include <concepts>
25#include <cstddef>
26#include <exception>
27#include <functional>
28#include <limits>
29#include <type_traits>
30#include <utility>
31#include <vector>
32
33#include "concepts.hpp"
34#include "decomposition.hpp"
35
36namespace numerical {
37
38 namespace detail {
39
41 inline constexpr double schur_ulp {std::numeric_limits<double>::epsilon()};
42
44 inline constexpr std::size_t schur_steps_per_order {30};
45
49 inline constexpr double balance_limit {0x1p256};
50
53 inline constexpr double back_substitution_limit {0x1p400};
54
56 [[nodiscard]] inline double modulus_1(double x)
57 {
58 return std::abs(x);
59 }
60
62 [[nodiscard]] inline double modulus_1(const std::complex<double>& x)
63 {
64 return std::abs(x.real()) + std::abs(x.imag());
65 }
66
68 template <typename A,
69 typename B>
70 [[nodiscard]] auto times(const A& a,
71 const B& b)
72 {
73 return a * b;
74 }
75
79 [[nodiscard]] inline std::complex<double> times(const std::complex<double>& a,
80 const std::complex<double>& b)
81 {
82 return {(a.real() * b.real()) - (a.imag() * b.imag()), (a.real() * b.imag()) + (a.imag() * b.real())};
83 }
84
86 [[nodiscard]] inline double largest_part(double x)
87 {
88 return std::abs(x);
89 }
90
92 [[nodiscard]] inline double largest_part(const std::complex<double>& x)
93 {
94 return std::max(std::abs(x.real()), std::abs(x.imag()));
95 }
96
99 struct balancing
100 {
101 std::size_t low {0};
102 std::size_t high {0};
103 std::vector<std::pair<std::size_t, std::size_t>> swaps;
105 };
106
108 template <typename T>
110 std::size_t n,
111 std::size_t i,
112 std::size_t j)
113 {
114 for (std::size_t c {0}; c < n; ++c) {
115 std::swap(a[(i * n) + c], a[(j * n) + c]);
116 }
117 for (std::size_t r {0}; r < n; ++r) {
118 std::swap(a[(r * n) + i], a[(r * n) + j]);
119 }
120 }
121
129 template <typename T>
131 std::size_t n,
132 bool permute = true,
133 bool scale = true)
134 {
135 balancing out;
136 out.scale = buffer<double>(n, 1.0);
137 out.high = n;
138 for (bool moved {permute}; moved;) {
139 moved = false;
140 for (std::size_t i {out.high}; i-- > out.low;) {
141 bool alone {true};
142 for (std::size_t j {out.low}; j < out.high && alone; ++j) {
143 alone = j == i || a[(i * n) + j] == T {};
144 }
145 if (alone) {
146 exchange(a, n, i, out.high - 1);
147 out.swaps.emplace_back(i, out.high - 1);
148 --out.high;
149 moved = true;
150 break;
151 }
152 }
153 }
154 for (bool moved {permute}; moved;) {
155 moved = false;
156 for (std::size_t j {out.low}; j < out.high; ++j) {
157 bool alone {true};
158 for (std::size_t i {out.low}; i < out.high && alone; ++i) {
159 alone = i == j || a[(i * n) + j] == T {};
160 }
161 if (alone) {
162 exchange(a, n, j, out.low);
163 out.swaps.emplace_back(j, out.low);
164 ++out.low;
165 moved = true;
166 break;
167 }
168 }
169 }
170 buffer<T> gathered(out.high - out.low);
171 for (bool unbalanced {scale}; unbalanced;) {
172 unbalanced = false;
173 for (std::size_t i {out.low}; i < out.high; ++i) {
174 for (std::size_t k {out.low}; k < out.high; ++k) { // the column gathered: scaled_norm's sums run contiguous
175 gathered[k - out.low] = a[(k * n) + i];
176 }
177 double column {scaled_norm(gathered)};
178 double row {scaled_norm(a.data() + (i * n) + out.low, out.high - out.low)};
179 // Both are positive: the exchanges left every row and column of the block an off-diagonal entry in it.
180 const double before {column + row};
181 double f {1.0};
182 while (2.0 * column < row && out.scale[i] * f < balance_limit) {
183 f *= 2.0;
184 column *= 2.0;
185 row /= 2.0;
186 }
187 while (column >= 2.0 * row && out.scale[i] * f > 1.0 / balance_limit) {
188 f /= 2.0;
189 column /= 2.0;
190 row *= 2.0;
191 }
192 // f back at 1 is no step, whatever the sums say: halving a sum near the subnormals to 0 and doubling it back
193 // reads as a gain (a 6 × 6 matrix scaled to 10±150, divided by its largest power of 2, swept forever)
194 if (f == 1.0 || column + row >= 0.95 * before) {
195 continue;
196 }
197 out.scale[i] *= f;
198 unbalanced = true;
199 for (std::size_t k {out.low}; k < n; ++k) {
200 a[(i * n) + k] /= f;
201 }
202 for (std::size_t k {0}; k < out.high; ++k) {
203 a[(k * n) + i] *= f;
204 }
205 }
206 }
207 return out;
208 }
209
214 template <typename T>
216 std::size_t n)
217 {
218 return balance(a, n, true, false);
219 }
220
233 template <typename T>
235 std::size_t n,
236 std::size_t low,
237 std::size_t high,
238 bool form)
239 {
240 std::vector<buffer<T>> reflectors(n); // reflectors[k] acts on rows (and columns) k + 1 … high − 1
241 for (std::size_t k {low}; k + 2 < high; ++k) {
242 buffer<T> v(high - k - 1, T {});
243 for (std::size_t i {k + 1}; i < high; ++i) {
244 v[i - k - 1] = a[(i * n) + k];
245 }
246 if (scaled_norm(v.data() + 1, v.size() - 1) == 0.0) {
247 continue;
248 }
249 (void)rescale_tiny(v); // the same reflector at any scale
250 const double norm {scaled_norm(v)};
251 v[0] += phase_of(v[0]) * from_carried<T>(norm);
252 const T length {from_carried<T>(scaled_norm(v))};
253 for (T& element : v) {
254 element /= length;
255 }
256 buffer<T> w(n - k, T {}); // the rows times (I − 2 v vᴴ) from the left: w = vᴴ A over columns k …
257 for (std::size_t i {0}; i < v.size(); ++i) {
258 const T weight {conj_of(v[i])};
259 const T* row {a.data() + ((k + 1 + i) * n) + k};
260 for (std::size_t c {0}; c < w.size(); ++c) {
261 w[c] += times(weight, row[c]);
262 }
263 }
264 for (std::size_t i {0}; i < v.size(); ++i) {
265 const T twice {static_cast<T>(2) * v[i]};
266 T* row {a.data() + ((k + 1 + i) * n) + k};
267 for (std::size_t c {0}; c < w.size(); ++c) {
268 row[c] -= times(twice, w[c]);
269 }
270 }
271 for (std::size_t r {0}; r < high; ++r) { // A (I − 2 v vᴴ) on columns k + 1 …; rows below are zero there
272 T* row {a.data() + (r * n) + k + 1};
273 T s {};
274 for (std::size_t j {0}; j < v.size(); ++j) {
275 s += times(row[j], v[j]);
276 }
277 s *= static_cast<T>(2);
278 for (std::size_t j {0}; j < v.size(); ++j) {
279 row[j] -= times(s, conj_of(v[j]));
280 }
281 }
282 for (std::size_t i {k + 2}; i < high; ++i) {
283 a[(i * n) + k] = T {};
284 }
285 reflectors[k] = std::move(v);
286 }
287 if (!form) {
288 return {};
289 }
290 buffer<T> q(n * n, T {});
291 for (std::size_t i {0}; i < n; ++i) {
292 q[(i * n) + i] = T {1};
293 }
294 for (std::size_t k {n}; k-- > 0;) { // Q = P_low … P_high−3, accumulated backward: each acts on rows k + 1 …
295 const buffer<T>& v {reflectors[k]};
296 if (v.empty()) {
297 continue;
298 }
299 buffer<T> w(v.size(), T {});
300 for (std::size_t i {0}; i < v.size(); ++i) {
301 const T weight {conj_of(v[i])};
302 const T* row {q.data() + ((k + 1 + i) * n) + k + 1};
303 for (std::size_t c {0}; c < w.size(); ++c) {
304 w[c] += times(weight, row[c]);
305 }
306 }
307 for (std::size_t i {0}; i < v.size(); ++i) {
308 const T twice {static_cast<T>(2) * v[i]};
309 T* row {q.data() + ((k + 1 + i) * n) + k + 1};
310 for (std::size_t c {0}; c < w.size(); ++c) {
311 row[c] -= times(twice, w[c]);
312 }
313 }
314 }
315 buffer<T> qt(n * n, T {});
316 for (std::size_t i {0}; i < n; ++i) {
317 for (std::size_t j {0}; j < n; ++j) {
318 qt[(j * n) + i] = q[(i * n) + j];
319 }
320 }
321 return qt;
322 }
323
325 inline constexpr std::size_t hessenberg_block {32};
326
328 inline constexpr std::size_t hessenberg_crossover {128};
329
331 [[nodiscard]] inline bool already_reduced(double /*alpha*/,
332 double rest)
333 {
334 return rest == 0.0;
335 }
336
338 [[nodiscard]] inline bool already_reduced(const std::complex<double>& alpha,
339 double rest)
340 {
341 return rest == 0.0 && alpha.imag() == 0.0;
342 }
343
349 template <typename T>
351 T* x,
352 std::size_t count)
353 {
354 double rest {scaled_norm(x, count)};
355 if (already_reduced(alpha, rest)) {
356 return T {};
357 }
358 // Everything tiny is scaled up first, exactly, as dlarfg does: from subnormal entries `1 / (α − β)` overflows.
359 // The same reflector at any scale; `β` scaled back.
360 const double factor {rescue_factor<T>(std::max(static_cast<double>(std::abs(alpha)), rest))};
361 if (factor != 1.0) {
362 alpha *= from_carried<T>(factor);
363 for (std::size_t i {0}; i < count; ++i) {
364 x[i] *= from_carried<T>(factor);
365 }
366 rest = scaled_norm(x, count);
367 }
368 const double beta {-std::copysign(std::hypot(static_cast<double>(std::abs(alpha)), rest), real_part(alpha))};
369 const T tau {(from_carried<T>(beta) - alpha) / from_carried<T>(beta)};
370 const T scale {T {1} / (alpha - from_carried<T>(beta))};
371 for (std::size_t i {0}; i < count; ++i) {
372 x[i] *= scale;
373 }
374 alpha = from_carried<T>(beta / factor);
375 return tau;
376 }
377
380 {
382
384 [[nodiscard]] double dot(const double* row) const
385 {
386 return dot_product(row, v.data(), v.size());
387 }
388 };
389
394 {
397
399 [[nodiscard]] std::complex<double> dot(const std::complex<double>* row) const
400 {
401 const auto* const parts {reinterpret_cast<const double*>(row)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the layout guarantee above
402 return {dot_product(parts, real_side.data(), real_side.size()), dot_product(parts, imaginary_side.data(), imaginary_side.size())};
403 }
404 };
405
407 [[nodiscard]] inline real_operand operand_of(const double* v,
408 std::size_t stride,
409 std::size_t count)
410 {
411 real_operand out {buffer<double>(count)};
412 for (std::size_t l {0}; l < count; ++l) {
413 out.v[l] = v[l * stride];
414 }
415 return out;
416 }
417
419 [[nodiscard]] inline complex_operand operand_of(const std::complex<double>* v,
420 std::size_t stride,
421 std::size_t count)
422 {
423 complex_operand out {buffer<double>(2 * count), buffer<double>(2 * count)};
424 for (std::size_t l {0}; l < count; ++l) {
425 const std::complex<double> x {v[l * stride]};
426 out.real_side[2 * l] = x.real();
427 out.real_side[(2 * l) + 1] = -x.imag();
428 out.imaginary_side[2 * l] = x.imag();
429 out.imaginary_side[(2 * l) + 1] = x.real();
430 }
431 return out;
432 }
433
435 template <typename T>
437 {
438 std::size_t first {0};
439 std::size_t width {0};
442 };
443
450 template <typename T>
452 std::size_t n,
453 std::size_t low,
454 std::size_t high,
455 bool form)
456 {
457 std::vector<hessenberg_panel<T>> panels;
458 for (std::size_t k {low}; k + 2 < high;) {
459 const std::size_t b {std::min(hessenberg_block, high - 2 - k)};
460 const std::size_t m {high - k - 1}; // the rows k + 1 … high − 1
461 buffer<T> v(m * b, T {});
462 buffer<T> t(b * b, T {});
463 buffer<T> y(high * b, T {}); // Y = A V T, row-major, rows 0 … high − 1
464 buffer<T> column(m, T {});
465 buffer<T> w(b, T {});
466 for (std::size_t i {0}; i < b; ++i) {
467 const std::size_t j {k + i};
468 for (std::size_t r {0}; r < m; ++r) {
469 column[r] = a[((k + 1 + r) * n) + j];
470 }
471 if (i > 0) {
472 for (std::size_t r {0}; r < m; ++r) { // A Q: the column less Y Vᴴ e_j
473 T sum {};
474 for (std::size_t p {0}; p < i; ++p) {
475 sum += times(y[((k + 1 + r) * b) + p], conj_of(v[((i - 1) * b) + p]));
476 }
477 column[r] -= sum;
478 }
479 for (std::size_t p {0}; p < i; ++p) { // then Qᴴ from the left: w = Tᴴ Vᴴ column, column −= V w
480 T sum {};
481 for (std::size_t r {p}; r < m; ++r) {
482 sum += times(conj_of(v[(r * b) + p]), column[r]);
483 }
484 w[p] = sum;
485 }
486 for (std::size_t p {i}; p-- > 0;) {
487 T sum {};
488 for (std::size_t q {0}; q <= p; ++q) {
489 sum += times(conj_of(t[(q * b) + p]), w[q]);
490 }
491 w[p] = sum;
492 }
493 for (std::size_t r {0}; r < m; ++r) {
494 T sum {};
495 for (std::size_t p {0}; p < std::min(i, r + 1); ++p) {
496 sum += times(v[(r * b) + p], w[p]);
497 }
498 column[r] -= sum;
499 }
500 }
501 T alpha {column[i]};
502 const T tau {reflector_tau(alpha, column.data() + i + 1, m - i - 1)};
503 v[(i * b) + i] = T {1};
504 for (std::size_t r {i + 1}; r < m; ++r) {
505 v[(r * b) + i] = column[r];
506 }
507 for (std::size_t r {0}; r < m; ++r) {
508 a[((k + 1 + r) * n) + j] = r < i ? column[r] : (r == i ? alpha : T {});
509 }
510 // Y's column: τ (A v − Y Vᴴ v), A's columns past j as the panel found them, each row against v by dot_product
511 const auto against_v {operand_of(v.data() + (i * b) + i, b, m - i)};
512 parallel_for(m, high - j, [&](std::size_t r) {
513 y[((k + 1 + r) * b) + i] = against_v.dot(a.data() + ((k + 1 + r) * n) + j + 1);
514 });
515 for (std::size_t p {0}; p < i; ++p) {
516 T sum {};
517 for (std::size_t r {i}; r < m; ++r) {
518 sum += times(conj_of(v[(r * b) + p]), v[(r * b) + i]);
519 }
520 w[p] = sum;
521 }
522 for (std::size_t r {0}; r < m; ++r) {
523 T sum {};
524 for (std::size_t p {0}; p < i; ++p) {
525 sum += times(y[((k + 1 + r) * b) + p], w[p]);
526 }
527 y[((k + 1 + r) * b) + i] = tau * (y[((k + 1 + r) * b) + i] - sum);
528 }
529 for (std::size_t p {0}; p < i; ++p) { // T's column: −τ T w
530 T sum {};
531 for (std::size_t q {p}; q < i; ++q) {
532 sum += times(t[(p * b) + q], w[q]);
533 }
534 t[(p * b) + i] = -tau * sum;
535 }
536 t[(i * b) + i] = tau;
537 }
538 buffer<T> top((k + 1) * b, T {}); // Y's rows 0 … k: A(0 … k, k + 1 …) V T
539 gemm(k + 1, b, m, a.data() + k + 1, n, v.data(), b, top.data(), b);
540 for (std::size_t r {0}; r <= k; ++r) {
541 for (std::size_t p {b}; p-- > 0;) {
542 T sum {};
543 for (std::size_t q {0}; q <= p; ++q) {
544 sum += times(top[(r * b) + q], t[(q * b) + p]);
545 }
546 y[(r * b) + p] = sum;
547 }
548 }
549 for (std::size_t r {0}; r <= k; ++r) { // the panel's columns above it: A − Y Vᴴ
550 for (std::size_t i {1}; i < b; ++i) {
551 T sum {};
552 for (std::size_t p {0}; p < i; ++p) {
553 sum += times(y[(r * b) + p], conj_of(v[((i - 1) * b) + p]));
554 }
555 a[(r * n) + k + i] -= sum;
556 }
557 }
558 const std::size_t rest {high - k - b}; // the columns k + b … high − 1, from the right
559 buffer<T> minus_y(high * b);
560 for (std::size_t e {0}; e < high * b; ++e) {
561 minus_y[e] = -y[e];
562 }
563 buffer<T> v_adjoint(b * m);
564 for (std::size_t r {0}; r < m; ++r) {
565 for (std::size_t p {0}; p < b; ++p) {
566 v_adjoint[(p * m) + r] = conj_of(v[(r * b) + p]);
567 }
568 }
569 gemm(high, rest, b, minus_y.data(), b, v_adjoint.data() + b - 1, m, a.data() + k + b, n);
570 const std::size_t columns {n - k - b}; // then rows k + 1 … high − 1, columns k + b …, from the left
571 buffer<T> product(b * columns, T {});
572 gemm(b, columns, m, v_adjoint.data(), m, a.data() + ((k + 1) * n) + k + b, n, product.data(), columns);
573 buffer<T> scaled(b * columns, T {});
574 for (std::size_t p {0}; p < b; ++p) {
575 for (std::size_t q {0}; q <= p; ++q) {
576 const T factor {-conj_of(t[(q * b) + p])};
577 for (std::size_t c {0}; c < columns; ++c) {
578 scaled[(p * columns) + c] += times(factor, product[(q * columns) + c]);
579 }
580 }
581 }
582 gemm(m, columns, b, v.data(), b, scaled.data(), columns, a.data() + ((k + 1) * n) + k + b, n);
583 if (form) {
584 panels.push_back({k, b, std::move(v), std::move(t)});
585 }
586 k += b;
587 }
588 if (!form) {
589 return {};
590 }
591 buffer<T> q(n * n, T {});
592 for (std::size_t i {0}; i < n; ++i) {
593 q[(i * n) + i] = T {1};
594 }
595 for (std::size_t s {panels.size()}; s-- > 0;) { // Q = Q₁ … Q_p, backward: Q ← (I − V T Vᴴ) Q on rows first + 1 …
596 const hessenberg_panel<T>& panel {panels[s]};
597 const std::size_t m {high - panel.first - 1};
598 const std::size_t b {panel.width};
599 T* const block {q.data() + ((panel.first + 1) * n) + panel.first + 1};
600 buffer<T> v_adjoint(b * m);
601 for (std::size_t r {0}; r < m; ++r) {
602 for (std::size_t p {0}; p < b; ++p) {
603 v_adjoint[(p * m) + r] = conj_of(panel.v[(r * b) + p]);
604 }
605 }
606 buffer<T> product(b * m, T {});
607 gemm(b, m, m, v_adjoint.data(), m, block, n, product.data(), m);
608 buffer<T> scaled(b * m, T {});
609 for (std::size_t p {0}; p < b; ++p) {
610 for (std::size_t r {p}; r < b; ++r) {
611 const T factor {-panel.t[(p * b) + r]};
612 for (std::size_t c {0}; c < m; ++c) {
613 scaled[(p * m) + c] += times(factor, product[(r * m) + c]);
614 }
615 }
616 }
617 gemm(m, m, b, panel.v.data(), b, scaled.data(), m, block, n);
618 }
619 buffer<T> qt(n * n, T {});
620 for (std::size_t i {0}; i < n; ++i) {
621 for (std::size_t j {0}; j < n; ++j) {
622 qt[(j * n) + i] = q[(i * n) + j];
623 }
624 }
625 return qt;
626 }
627
629 template <typename T>
631 std::size_t n,
632 std::size_t low,
633 std::size_t high,
634 bool form)
635 {
636 if (high - low >= hessenberg_crossover) {
637 return hessenberg_blocked(a, n, low, high, form);
638 }
639 return hessenberg_unblocked(a, n, low, high, form);
640 }
641
647 [[nodiscard]] inline double small_reflector(double (&v)[3],
648 std::size_t count)
649 {
650 double rest {count == 3 ? std::hypot(v[1], v[2]) : std::abs(v[1])};
651 if (rest == 0.0) {
652 return 0.0;
653 }
654 // Everything tiny is scaled up first, exactly, as dlarfg does: from subnormal entries (a bulge on a matrix of
655 // zero diagonal leaves them) `1 / (α − β)` overflows. The same reflector at any scale; `β` scaled back.
656 const double factor {rescue_factor<double>(std::max(std::abs(v[0]), rest))};
657 if (factor != 1.0) {
658 for (std::size_t i {0}; i < count; ++i) {
659 v[i] *= factor;
660 }
661 rest = count == 3 ? std::hypot(v[1], v[2]) : std::abs(v[1]);
662 }
663 const double beta {-std::copysign(std::hypot(v[0], rest), v[0])};
664 const double tau {(beta - v[0]) / beta};
665 const double scale {1.0 / (v[0] - beta)};
666 for (std::size_t i {1}; i < count; ++i) {
667 v[i] *= scale;
668 }
669 v[0] = beta / factor;
670 return tau;
671 }
672
678 [[nodiscard]] inline std::complex<double> complex_reflector(std::complex<double> (&v)[2])
679 {
680 if (modulus_1(v[1]) == 0.0 && v[0].imag() == 0.0) {
681 return {};
682 }
683 // Everything tiny is scaled up first, exactly, as zlarfg does: from subnormal entries `1 / (α − β)` overflows.
684 const double factor {rescue_factor<std::complex<double>>(std::max(std::abs(v[0]), std::abs(v[1])))};
685 v[0] *= factor;
686 v[1] *= factor;
687 const double beta {-std::copysign(std::hypot(std::abs(v[0]), std::abs(v[1])), v[0].real())};
688 const std::complex<double> tau {(beta - v[0].real()) / beta, -v[0].imag() / beta};
689 v[1] = v[1] / (v[0] - beta);
690 v[0] = beta / factor;
691 return tau;
692 }
693
696 {
697 double cs {1.0};
698 double sn {0.0};
699 double re1 {0.0};
700 double im1 {0.0};
701 double re2 {0.0};
702 double im2 {0.0};
703 };
704
711 double& b,
712 double& c,
713 double& d)
714 {
715 standard_block out;
716 if (b == 0.0 && c != 0.0) { // lower triangular: exchange the rows and the columns
717 out.cs = 0.0;
718 out.sn = 1.0;
719 std::swap(a, d);
720 b = -c;
721 c = 0.0;
722 }
723 else if (c != 0.0 && (a - d != 0.0 || std::signbit(b) == std::signbit(c))) { // not yet triangular nor standard
724 const double temp {a - d};
725 double p {0.5 * temp};
726 const double bcmax {std::max(std::abs(b), std::abs(c))};
727 const double bcmis {std::min(std::abs(b), std::abs(c)) * std::copysign(1.0, b) * std::copysign(1.0, c)};
728 const double scale {std::max(std::abs(p), bcmax)};
729 double z {((p / scale) * p) + ((bcmax / scale) * bcmis)};
730 if (z >= 4.0 * schur_ulp) { // real eigenvalues: the triangular form
731 z = p + std::copysign(std::sqrt(scale) * std::sqrt(z), p);
732 a = d + z;
733 d -= (bcmax / z) * bcmis;
734 const double tau {std::hypot(c, z)};
735 out.cs = z / tau;
736 out.sn = c / tau;
737 b -= c;
738 c = 0.0;
739 }
740 else { // complex or nearly equal real eigenvalues: equal diagonal entries first
741 const double sigma {b + c};
742 const double tau {std::hypot(sigma, temp)};
743 out.cs = std::sqrt(0.5 * (1.0 + (std::abs(sigma) / tau)));
744 out.sn = -(0.5 * (temp / tau) / out.cs) * std::copysign(1.0, sigma);
745 const double aa {(a * out.cs) + (b * out.sn)};
746 const double bb {(-a * out.sn) + (b * out.cs)};
747 const double cc {(c * out.cs) + (d * out.sn)};
748 const double dd {(-c * out.sn) + (d * out.cs)};
749 a = (aa * out.cs) + (cc * out.sn);
750 b = (bb * out.cs) + (dd * out.sn);
751 c = (-aa * out.sn) + (cc * out.cs);
752 d = (-bb * out.sn) + (dd * out.cs);
753 p = 0.5 * (a + d);
754 a = p;
755 d = p;
756 if (c != 0.0 && b != 0.0 && std::signbit(b) == std::signbit(c)) { // real after all: triangular
757 const double sab {std::sqrt(std::abs(b))};
758 const double sac {std::sqrt(std::abs(c))};
759 const double root {std::copysign(sab * sac, c)};
760 const double inverse {1.0 / std::sqrt(std::abs(b + c))};
761 a = p + root;
762 d = p - root;
763 b -= c;
764 c = 0.0;
765 const double cs1 {sab * inverse};
766 const double sn1 {sac * inverse};
767 const double cs {(out.cs * cs1) - (out.sn * sn1)};
768 out.sn = (out.cs * sn1) + (out.sn * cs1);
769 out.cs = cs;
770 }
771 else if (c != 0.0 && b == 0.0) {
772 b = -c;
773 c = 0.0;
774 const double cs {out.cs};
775 out.cs = -out.sn;
776 out.sn = cs;
777 }
778 }
779 }
780 out.re1 = a;
781 out.re2 = d;
782 if (c != 0.0) {
783 out.im1 = std::sqrt(std::abs(b)) * std::sqrt(std::abs(c));
784 out.im2 = -out.im1;
785 }
786 return out;
787 }
788
790 template <typename T>
791 void rotate(T* x,
792 T* y,
793 std::size_t count,
794 std::size_t stride,
795 double cs,
796 double sn)
797 {
798 for (std::size_t i {0}; i < count; ++i) {
799 const T xi {x[i * stride]};
800 const T yi {y[i * stride]};
801 x[i * stride] = (cs * xi) + (sn * yi);
802 y[i * stride] = (cs * yi) - (sn * xi);
803 }
804 }
805
811 template <typename T>
813 T* r2,
814 T* r3,
815 std::size_t from,
816 std::size_t to,
817 const T& tau,
818 const T& v2,
819 const T& v3,
820 bool adjoint)
821 {
822 const T f {adjoint ? conj_of(tau) : tau};
823 const T a2 {adjoint ? conj_of(v2) : v2};
824 const T a3 {adjoint ? conj_of(v3) : v3};
825 const T b2 {adjoint ? v2 : conj_of(v2)};
826 const T b3 {adjoint ? v3 : conj_of(v3)};
827 for (std::size_t j {from}; j < to; ++j) {
828 const T sum {times(f, r1[j] + times(a2, r2[j]) + times(a3, r3[j]))};
829 r1[j] -= sum;
830 r2[j] -= times(sum, b2);
831 r3[j] -= times(sum, b3);
832 }
833 }
834
837 template <typename T>
839 T* r2,
840 std::size_t from,
841 std::size_t to,
842 const T& tau,
843 const T& v2,
844 bool adjoint)
845 {
846 const T f {adjoint ? conj_of(tau) : tau};
847 const T a2 {adjoint ? conj_of(v2) : v2};
848 const T b2 {adjoint ? v2 : conj_of(v2)};
849 for (std::size_t j {from}; j < to; ++j) {
850 const T sum {times(f, r1[j] + times(a2, r2[j]))};
851 r1[j] -= sum;
852 r2[j] -= times(sum, b2);
853 }
854 }
855
861 template <typename T>
863 std::size_t rows,
864 std::size_t ld,
865 const T& tau,
866 const T& v2,
867 const T& v3)
868 {
869 const T w2 {conj_of(v2)};
870 const T w3 {conj_of(v3)};
871 for (std::size_t r {0}; r < rows; ++r) {
872 T* const x {first + (r * ld)};
873 const T sum {times(tau, x[0] + times(v2, x[1]) + times(v3, x[2]))};
874 x[0] -= sum;
875 x[1] -= times(sum, w2);
876 x[2] -= times(sum, w3);
877 }
878 }
879
881 template <typename T>
883 std::size_t rows,
884 std::size_t ld,
885 const T& tau,
886 const T& v2)
887 {
888 const T w2 {conj_of(v2)};
889 for (std::size_t r {0}; r < rows; ++r) {
890 T* const x {first + (r * ld)};
891 const T sum {times(tau, x[0] + times(v2, x[1]))};
892 x[0] -= sum;
893 x[1] -= times(sum, w2);
894 }
895 }
896
898 template <typename T>
900 {
901 buffer<T>* h {nullptr};
902 std::size_t n {0};
903 std::size_t low {0};
904 std::size_t high {0};
905 bool full {false};
906 buffer<T>* zt {nullptr};
907 };
908
920 inline void real_schur(const schur_target<double>& t,
921 buffer<double>& re,
922 buffer<double>& im,
923 std::size_t steps)
924 {
925 buffer<double>& h {*t.h};
926 const std::size_t n {t.n};
927 const auto at {[&h, n](std::size_t i, std::size_t j) -> double& { return h[(i * n) + j]; }};
928 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(t.high - t.low) / schur_ulp)};
929 std::size_t since_deflation {0};
930 for (std::size_t end {t.high}; end > t.low;) {
931 const std::size_t i {end - 1};
932 std::size_t l {t.low};
933 bool converged {false};
934 for (std::size_t its {0}; its <= steps; ++its) {
935 std::size_t k {i};
936 for (; k > l; --k) {
937 const double sub {std::abs(at(k, k - 1))};
938 if (sub <= smallest) {
939 break;
940 }
941 double test {std::abs(at(k - 1, k - 1)) + std::abs(at(k, k))};
942 if (test == 0.0) {
943 if (k >= t.low + 2) {
944 test += std::abs(at(k - 1, k - 2));
945 }
946 if (k + 1 < t.high) {
947 test += std::abs(at(k + 1, k));
948 }
949 }
950 if (sub <= schur_ulp * test) {
951 const double ab {std::max(sub, std::abs(at(k - 1, k)))};
952 const double ba {std::min(sub, std::abs(at(k - 1, k)))};
953 const double aa {std::max(std::abs(at(k, k)), std::abs(at(k - 1, k - 1) - at(k, k)))};
954 const double bb {std::min(std::abs(at(k, k)), std::abs(at(k - 1, k - 1) - at(k, k)))};
955 const double s {aa + ab};
956 if (ba * (ab / s) <= std::max(smallest, schur_ulp * (bb * (aa / s)))) {
957 break;
958 }
959 }
960 }
961 l = k;
962 if (l > t.low) {
963 at(l, l - 1) = 0.0;
964 }
965 if (l + 1 >= i) {
966 converged = true;
967 break;
968 }
970 const std::size_t first {t.full ? 0 : l}; // the columns the right reflections update start here
971 const std::size_t last {t.full ? n : i + 1}; // the rows the left reflections update end before here
972 double h11 {};
973 double h12 {};
974 double h21 {};
975 double h22 {};
976 if (since_deflation % 20 == 0) {
977 const double s {std::abs(at(i, i - 1)) + std::abs(at(i - 1, i - 2))};
978 h11 = (0.75 * s) + at(i, i);
979 h12 = -0.4375 * s;
980 h21 = s;
981 h22 = h11;
982 }
983 else if (since_deflation % 10 == 0) {
984 const double s {std::abs(at(l + 1, l)) + std::abs(at(l + 2, l + 1))};
985 h11 = (0.75 * s) + at(l, l);
986 h12 = -0.4375 * s;
987 h21 = s;
988 h22 = h11;
989 }
990 else {
991 h11 = at(i - 1, i - 1);
992 h21 = at(i, i - 1);
993 h12 = at(i - 1, i);
994 h22 = at(i, i);
995 }
996 const double s {std::abs(h11) + std::abs(h12) + std::abs(h21) + std::abs(h22)}; // > 0: h21 is not negligible
997 h11 /= s;
998 h21 /= s;
999 h12 /= s;
1000 h22 /= s;
1001 const double trace {(h11 + h22) / 2.0};
1002 const double det {((h11 - trace) * (h22 - trace)) - (h12 * h21)};
1003 const double root {std::sqrt(std::abs(det))};
1004 double rt1r {trace * s};
1005 double rt2r {rt1r};
1006 double rt1i {root * s};
1007 double rt2i {-rt1i};
1008 if (det < 0.0) { // real shifts: the one nearer h22, twice
1009 rt1r = trace + root;
1010 rt2r = trace - root;
1011 rt1r = (std::abs(rt1r - h22) <= std::abs(rt2r - h22) ? rt1r : rt2r) * s;
1012 rt2r = rt1r;
1013 rt1i = 0.0;
1014 rt2i = 0.0;
1015 }
1016 std::size_t m {i - 2};
1017 double v[3] {};
1018 for (;; --m) { // where two consecutive small subdiagonals let the sweep start
1019 const double h21s {at(m + 1, m) / (std::abs(at(m, m) - rt2r) + std::abs(rt2i) + std::abs(at(m + 1, m)))};
1020 const double scale {std::abs(at(m, m) - rt2r) + std::abs(rt2i) + std::abs(at(m + 1, m))};
1021 v[0] = (h21s * at(m, m + 1)) + ((at(m, m) - rt1r) * ((at(m, m) - rt2r) / scale)) - (rt1i * (rt2i / scale));
1022 v[1] = h21s * (at(m, m) + at(m + 1, m + 1) - rt1r - rt2r);
1023 v[2] = h21s * at(m + 2, m + 1);
1024 const double sum {std::abs(v[0]) + std::abs(v[1]) + std::abs(v[2])};
1025 v[0] /= sum;
1026 v[1] /= sum;
1027 v[2] /= sum;
1028 if (m == l) {
1029 break;
1030 }
1031 const double above {std::abs(at(m, m - 1)) * (std::abs(v[1]) + std::abs(v[2]))};
1032 const double here {std::abs(v[0]) * (std::abs(at(m - 1, m - 1)) + std::abs(at(m, m)) + std::abs(at(m + 1, m + 1)))};
1033 if (above <= schur_ulp * here) {
1034 break;
1035 }
1036 }
1037 for (std::size_t k2 {m}; k2 < i; ++k2) { // the bulge chased down the diagonal
1038 const std::size_t count {std::min<std::size_t>(3, i - k2 + 1)};
1039 if (k2 > m) {
1040 v[0] = at(k2, k2 - 1);
1041 v[1] = at(k2 + 1, k2 - 1);
1042 v[2] = count == 3 ? at(k2 + 2, k2 - 1) : 0.0;
1043 }
1044 const double t1 {small_reflector(v, count)};
1045 if (k2 > m) {
1046 at(k2, k2 - 1) = v[0];
1047 at(k2 + 1, k2 - 1) = 0.0;
1048 if (count == 3) {
1049 at(k2 + 2, k2 - 1) = 0.0;
1050 }
1051 }
1052 else if (m > l) {
1053 at(k2, k2 - 1) *= 1.0 - t1;
1054 }
1055 const double v2 {v[1]};
1056 const double v3 {count == 3 ? v[2] : 0.0};
1057 const double t2 {t1 * v2};
1058 const double t3 {t1 * v3};
1059 const std::size_t third {count == 3 ? std::size_t {2} : std::size_t {1}}; // two rows: the third is the second, t3 = 0 leaves it
1060 double* a1 {&at(k2, 0)};
1061 double* a2 {a1 + n};
1062 double* a3 {a1 + (third * n)};
1063 for (std::size_t j {k2}; j < last; ++j) {
1064 const double sum {a1[j] + (v2 * a2[j]) + (v3 * a3[j])};
1065 a1[j] -= sum * t1;
1066 a2[j] -= sum * t2;
1067 a3[j] -= sum * t3;
1068 }
1069 for (std::size_t j {first}; j <= std::min(k2 + 3, i); ++j) {
1070 double* row {&at(j, k2)};
1071 const double sum {row[0] + (v2 * row[1]) + (v3 * row[third])};
1072 row[0] -= sum * t1;
1073 row[1] -= sum * t2;
1074 row[third] -= sum * t3;
1075 }
1076 if (t.zt != nullptr) { // Z's columns k2 …, rows of Zᵀ
1077 buffer<double>& zt {*t.zt};
1078 double* r1 {zt.data() + (k2 * n)};
1079 double* r2 {r1 + n};
1080 double* r3 {r1 + (third * n)};
1081 for (std::size_t j {t.low}; j < t.high; ++j) {
1082 const double sum {r1[j] + (v2 * r2[j]) + (v3 * r3[j])};
1083 r1[j] -= sum * t1;
1084 r2[j] -= sum * t2;
1085 r3[j] -= sum * t3; // r3 is r2 and t3 0 for two rows
1086 }
1087 }
1088 }
1089 }
1090 if (!converged) {
1091 throw convergence_error("eigendecomposition: the QR iterations did not converge");
1092 }
1093 if (l == i) {
1094 re[i] = at(i, i);
1095 im[i] = 0.0;
1096 }
1097 else { // a 2 × 2 block: its standard form, the rotation carried to the rest of the Schur form and Z
1098 const standard_block block {standardize_block(at(i - 1, i - 1), at(i - 1, i), at(i, i - 1), at(i, i))};
1099 re[i - 1] = block.re1;
1100 im[i - 1] = block.im1;
1101 re[i] = block.re2;
1102 im[i] = block.im2;
1103 if (t.full) {
1104 rotate(&at(i - 1, i + 1 < n ? i + 1 : i), &at(i, i + 1 < n ? i + 1 : i), n - i - 1, 1, block.cs, block.sn);
1105 rotate(&at(0, i - 1), &at(0, i), i - 1, n, block.cs, block.sn);
1106 }
1107 if (t.zt != nullptr) {
1108 buffer<double>& zt {*t.zt};
1109 rotate(zt.data() + ((i - 1) * n) + t.low, zt.data() + (i * n) + t.low, t.high - t.low, 1, block.cs, block.sn);
1110 }
1111 }
1112 since_deflation = 0;
1113 end = l;
1114 }
1115 }
1116
1126 inline void complex_schur(const schur_target<std::complex<double>>& t,
1127 buffer<std::complex<double>>& values,
1128 std::size_t steps)
1129 {
1130 using C = std::complex<double>;
1131 buffer<C>& h {*t.h};
1132 const std::size_t n {t.n};
1133 const auto at {[&h, n](std::size_t i, std::size_t j) -> C& { return h[(i * n) + j]; }};
1134 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(t.high - t.low) / schur_ulp)};
1135 std::size_t since_deflation {0};
1136 for (std::size_t end {t.high}; end > t.low;) {
1137 const std::size_t i {end - 1};
1138 std::size_t l {t.low};
1139 bool converged {false};
1140 for (std::size_t its {0}; its <= steps; ++its) {
1141 std::size_t k {i};
1142 for (; k > l; --k) {
1143 const double sub {modulus_1(at(k, k - 1))};
1144 if (sub <= smallest) {
1145 break;
1146 }
1147 double test {modulus_1(at(k - 1, k - 1)) + modulus_1(at(k, k))};
1148 if (test == 0.0) {
1149 if (k >= t.low + 2) {
1150 test += modulus_1(at(k - 1, k - 2));
1151 }
1152 if (k + 1 < t.high) {
1153 test += modulus_1(at(k + 1, k));
1154 }
1155 }
1156 if (sub <= schur_ulp * test) {
1157 const double ab {std::max(sub, modulus_1(at(k - 1, k)))};
1158 const double ba {std::min(sub, modulus_1(at(k - 1, k)))};
1159 const double aa {std::max(modulus_1(at(k, k)), modulus_1(at(k - 1, k - 1) - at(k, k)))};
1160 const double bb {std::min(modulus_1(at(k, k)), modulus_1(at(k - 1, k - 1) - at(k, k)))};
1161 const double s {aa + ab};
1162 if (ba * (ab / s) <= std::max(smallest, schur_ulp * (bb * (aa / s)))) {
1163 break;
1164 }
1165 }
1166 }
1167 l = k;
1168 if (l > t.low) {
1169 at(l, l - 1) = C {};
1170 }
1171 if (l >= i) {
1172 converged = true;
1173 break;
1174 }
1176 const std::size_t first {t.full ? 0 : l};
1177 const std::size_t last {t.full ? n : i + 1};
1178 C shift {};
1179 if (since_deflation % 20 == 0) {
1180 shift = (0.75 * modulus_1(at(i, i - 1))) + at(i, i);
1181 }
1182 else if (since_deflation % 10 == 0) {
1183 shift = (0.75 * modulus_1(at(l + 1, l))) + at(l, l);
1184 }
1185 else { // Wilkinson's: the eigenvalue of the trailing 2 × 2 nearer its last diagonal entry
1186 shift = at(i, i);
1187 const C u {std::sqrt(at(i - 1, i)) * std::sqrt(at(i, i - 1))};
1188 if (modulus_1(u) != 0.0) {
1189 const C x {0.5 * (at(i - 1, i - 1) - shift)};
1190 const double sx {modulus_1(x)};
1191 const double s {std::max(modulus_1(u), sx)};
1192 C y {s * std::sqrt(((x / s) * (x / s)) + ((u / s) * (u / s)))};
1193 if (sx > 0.0 && ((x / sx).real() * y.real()) + ((x / sx).imag() * y.imag()) < 0.0) {
1194 y = -y;
1195 }
1196 shift -= u * (u / (x + y));
1197 }
1198 }
1199 std::size_t m {i - 1};
1200 C v[2] {};
1201 for (;; --m) {
1202 const C h11 {at(m, m)};
1203 const C h22 {at(m + 1, m + 1)};
1204 const C h21 {at(m + 1, m)};
1205 const double s {modulus_1(h11 - shift) + modulus_1(h21)};
1206 v[0] = (h11 - shift) / s;
1207 v[1] = h21 / s;
1208 if (m == l) {
1209 break;
1210 }
1211 if (modulus_1(at(m, m - 1)) * modulus_1(v[1]) <= schur_ulp * (modulus_1(v[0]) * (modulus_1(h11) + modulus_1(h22)))) {
1212 break;
1213 }
1214 }
1215 for (std::size_t k2 {m}; k2 < i; ++k2) {
1216 if (k2 > m) {
1217 v[0] = at(k2, k2 - 1);
1218 v[1] = at(k2 + 1, k2 - 1);
1219 }
1220 const C t1 {complex_reflector(v)};
1221 if (k2 > m) {
1222 at(k2, k2 - 1) = v[0];
1223 at(k2 + 1, k2 - 1) = C {};
1224 }
1225 else if (m > l) {
1226 at(k2, k2 - 1) *= 1.0 - std::conj(t1);
1227 }
1228 const C v2 {v[1]};
1229 reflect_two_rows(&at(k2, 0), &at(k2 + 1, 0), k2, last, t1, v2, true);
1230 reflect_two_columns(&at(first, k2), std::min(k2 + 2, i) - first + 1, n, t1, v2);
1231 if (t.zt != nullptr) {
1232 C* const r1 {t.zt->data() + (k2 * n)};
1233 reflect_two_rows(r1, r1 + n, t.low, t.high, t1, v2, false);
1234 }
1235 }
1236 }
1237 if (!converged) {
1238 throw convergence_error("eigendecomposition: the QR iterations did not converge");
1239 }
1240 values[i] = at(i, i);
1241 since_deflation = 0;
1242 end = l;
1243 }
1244 }
1245
1248 using lapack_index = std::ptrdiff_t;
1249
1251 template <typename T>
1253 {
1255 one_based(T* first,
1257 : data(first), ld(distance)
1258 {}
1259
1262
1265 lapack_index j) const
1266 {
1267 return data[((i - 1) * ld) + (j - 1)];
1268 }
1269 };
1270
1272 [[nodiscard]] inline std::size_t count_of(lapack_index count)
1273 {
1274 return static_cast<std::size_t>(count);
1275 }
1276
1279 inline constexpr lapack_index multishift_crossover {75};
1280
1284 [[nodiscard]] constexpr lapack_index multishift_from(double /*real*/)
1285 {
1286 return 200;
1287 }
1288
1291 [[nodiscard]] constexpr lapack_index multishift_from(const std::complex<double>& /*complex*/)
1292 {
1293 return 100;
1294 }
1295
1297 inline constexpr lapack_index window_growth {5};
1298
1300 inline constexpr lapack_index exceptional_after {6};
1301
1303 inline constexpr lapack_index nibble {14};
1304
1306 template <typename T>
1308 {
1309 double c {1.0};
1310 T s {};
1311 T r {};
1312 };
1313
1316 double g)
1317 {
1318 if (g == 0.0) {
1319 return {1.0, 0.0, f};
1320 }
1321 if (f == 0.0) {
1322 return {0.0, std::copysign(1.0, g), std::abs(g)};
1323 }
1324 const double r {std::copysign(std::hypot(f, g), f)};
1325 return {std::abs(f) / std::abs(r), g / r, r};
1326 }
1327
1329 [[nodiscard]] inline plane_rotation<std::complex<double>> givens(const std::complex<double>& f,
1330 const std::complex<double>& g)
1331 {
1332 using C = std::complex<double>;
1333 if (g == C {}) {
1334 return {1.0, C {}, f};
1335 }
1336 if (f == C {}) {
1337 return {0.0, std::conj(g) / std::abs(g), C {std::abs(g)}};
1338 }
1339 const double size {std::abs(f)};
1340 const double d {std::hypot(size, std::abs(g))};
1341 const C phase {f / size};
1342 return {size / d, phase * std::conj(g) / d, phase * d};
1343 }
1344
1346 template <typename T>
1348 T* y,
1349 std::size_t count,
1350 std::size_t stride,
1351 double c,
1352 const T& s)
1353 {
1354 for (std::size_t i {0}; i < count; ++i) {
1355 const T xi {x[i * stride]};
1356 const T yi {y[i * stride]};
1357 x[i * stride] = (c * xi) + times(s, yi);
1358 y[i * stride] = (c * yi) - times(conj_of(s), xi);
1359 }
1360 }
1361
1367 template <typename T>
1369 one_based<T> qt,
1370 lapack_index n,
1371 lapack_index k)
1372 {
1373 const T t11 {t(k, k)};
1374 const T t22 {t(k + 1, k + 1)};
1375 const plane_rotation<T> g {givens(t(k, k + 1), t22 - t11)};
1376 if (k + 2 <= n) {
1377 rotate_pair(&t(k, k + 2), &t(k + 1, k + 2), count_of(n - k - 1), 1, g.c, g.s);
1378 }
1379 rotate_pair(&t(1, k), &t(1, k + 1), count_of(k - 1), count_of(t.ld), g.c, conj_of(g.s));
1380 t(k, k) = t22;
1381 t(k + 1, k + 1) = t11;
1382 rotate_pair(&qt(k, 1), &qt(k + 1, 1), count_of(n), 1, g.c, conj_of(g.s));
1383 }
1384
1386 inline void reflect_rows_3(const std::array<double, 3>& u,
1387 double tau,
1388 double * t,
1389 std::size_t ld,
1390 std::size_t count)
1391 {
1392 for (std::size_t c {0}; c < count; ++c) {
1393 const double sum {(u[0] * t[c]) + (u[1] * t[ld + c]) + (u[2] * t[(2 * ld) + c])};
1394 t[c] -= tau * sum * u[0];
1395 t[ld + c] -= tau * sum * u[1];
1396 t[(2 * ld) + c] -= tau * sum * u[2];
1397 }
1398 }
1399
1401 inline void reflect_columns_3(const std::array<double, 3>& u,
1402 double tau,
1403 double * t,
1404 std::size_t ld,
1405 std::size_t count)
1406 {
1407 for (std::size_t r {0}; r < count; ++r) {
1408 double* const row {t + (r * ld)};
1409 const double sum {(row[0] * u[0]) + (row[1] * u[1]) + (row[2] * u[2])};
1410 row[0] -= tau * sum * u[0];
1411 row[1] -= tau * sum * u[1];
1412 row[2] -= tau * sum * u[2];
1413 }
1414 }
1415
1422 const one_based<double>& tr,
1423 const one_based<double>& b,
1424 lapack_index n1,
1426 double (&x)[4])
1427 {
1428 const std::size_t size {count_of(n1 * n2)};
1429 double k[4][4] {};
1430 double rhs[4] {};
1431 double largest {0.0};
1432 for (lapack_index i {1}; i <= n1; ++i) {
1433 for (lapack_index j {1}; j <= n2; ++j) {
1434 const std::size_t row {count_of(((i - 1) * n2) + (j - 1))};
1435 rhs[row] = b(i, j);
1436 for (lapack_index p {1}; p <= n1; ++p) {
1437 k[row][count_of(((p - 1) * n2) + (j - 1))] += tl(i, p);
1438 }
1439 for (lapack_index q {1}; q <= n2; ++q) {
1440 k[row][count_of(((i - 1) * n2) + (q - 1))] -= tr(q, j);
1441 }
1442 }
1443 }
1444 for (std::size_t r {0}; r < size; ++r) {
1445 for (std::size_t c {0}; c < size; ++c) {
1446 largest = std::max(largest, std::abs(k[r][c]));
1447 }
1448 }
1449 const double floor {std::max(schur_ulp * largest, std::numeric_limits<double>::min())};
1450 std::size_t column_of[4] {0, 1, 2, 3};
1451 for (std::size_t s {0}; s < size; ++s) {
1452 std::size_t pr {s};
1453 std::size_t pc {s};
1454 for (std::size_t r {s}; r < size; ++r) {
1455 for (std::size_t c {s}; c < size; ++c) {
1456 if (std::abs(k[r][c]) > std::abs(k[pr][pc])) {
1457 pr = r;
1458 pc = c;
1459 }
1460 }
1461 }
1462 std::swap(k[s], k[pr]);
1463 std::swap(rhs[s], rhs[pr]);
1464 for (std::size_t r {0}; r < size; ++r) {
1465 std::swap(k[r][s], k[r][pc]);
1466 }
1467 std::swap(column_of[s], column_of[pc]);
1468 if (std::abs(k[s][s]) < floor) {
1469 k[s][s] = floor;
1470 }
1471 for (std::size_t r {s + 1}; r < size; ++r) {
1472 const double factor {k[r][s] / k[s][s]};
1473 for (std::size_t c {s}; c < size; ++c) {
1474 k[r][c] -= factor * k[s][c];
1475 }
1476 rhs[r] -= factor * rhs[s];
1477 }
1478 }
1479 double y[4] {};
1480 for (std::size_t s {size}; s-- > 0;) {
1481 double sum {rhs[s]};
1482 for (std::size_t c {s + 1}; c < size; ++c) {
1483 sum -= k[s][c] * y[c];
1484 }
1485 y[s] = sum / k[s][s];
1486 }
1487 for (std::size_t s {0}; s < size; ++s) {
1488 x[column_of[s]] = y[s];
1489 }
1490 }
1491
1496 lapack_index n,
1497 lapack_index j)
1498 {
1499 const standard_block block {standardize_block(t(j, j), t(j, j + 1), t(j + 1, j), t(j + 1, j + 1))};
1500 if (j + 2 <= n) {
1501 rotate(&t(j, j + 2), &t(j + 1, j + 2), count_of(n - j - 1), 1, block.cs, block.sn);
1502 }
1503 rotate(&t(1, j), &t(1, j + 1), count_of(j - 1), count_of(t.ld), block.cs, block.sn);
1504 rotate(&qt(j, 1), &qt(j + 1, 1), count_of(n), 1, block.cs, block.sn);
1505 }
1506
1514 lapack_index n,
1516 lapack_index n1,
1518 {
1519 if (n1 == 1 && n2 == 1) {
1520 exchange_diagonal(t, qt, n, j1);
1521 return true;
1522 }
1523 const lapack_index j2 {j1 + 1};
1524 const lapack_index j3 {j1 + 2};
1525 const lapack_index j4 {j1 + 3};
1526 const lapack_index nd {n1 + n2};
1527 std::array<double, 16> d {};
1528 const one_based<double> dd {d.data(), 4};
1529 double norm {0.0};
1530 for (lapack_index i {1}; i <= nd; ++i) {
1531 for (lapack_index j {1}; j <= nd; ++j) {
1532 dd(i, j) = t(j1 + i - 1, j1 + j - 1);
1533 norm = std::max(norm, std::abs(dd(i, j)));
1534 }
1535 }
1536 const double thresh {std::max(10.0 * schur_ulp * norm, std::numeric_limits<double>::min() / schur_ulp)};
1537 double x[4] {};
1538 small_sylvester(dd, one_based<double> {&dd(n1 + 1, n1 + 1), 4}, one_based<double> {&dd(1, n1 + 1), 4}, n1, n2, x);
1539 const auto at {[&x, n2](lapack_index i, lapack_index j) { return x[count_of(((i - 1) * n2) + (j - 1))]; }};
1540 const std::size_t tld {count_of(t.ld)};
1541 std::array<double, 3> u1 {};
1542 std::array<double, 3> u2 {};
1543 double tau1 {};
1544 double tau2 {};
1545 double residue {};
1546 const double t11 {t(j1, j1)};
1547 const double t33 {t(j1 + nd - 1, j1 + nd - 1)};
1548 if (n1 == 1) { // and n2 == 2: one reflection, tried on the block first
1549 u1[0] = 1.0;
1550 u1[1] = at(1, 1);
1551 u1[2] = at(1, 2);
1552 double alpha {u1[2]};
1553 tau1 = reflector_tau(alpha, u1.data(), 2);
1554 u1[2] = 1.0;
1555 reflect_rows_3(u1, tau1, d.data(), 4, 3);
1556 reflect_columns_3(u1, tau1, d.data(), 4, 3);
1557 residue = std::max({std::abs(dd(3, 1)), std::abs(dd(3, 2)), std::abs(dd(3, 3) - t11)});
1558 }
1559 else if (n2 == 1) { // n1 == 2
1560 u1[0] = -at(1, 1);
1561 u1[1] = -at(2, 1);
1562 u1[2] = 1.0;
1563 double alpha {u1[0]};
1564 tau1 = reflector_tau(alpha, u1.data() + 1, 2);
1565 u1[0] = 1.0;
1566 reflect_rows_3(u1, tau1, d.data(), 4, 3);
1567 reflect_columns_3(u1, tau1, d.data(), 4, 3);
1568 residue = std::max({std::abs(dd(2, 1)), std::abs(dd(3, 1)), std::abs(dd(1, 1) - t33)});
1569 }
1570 else { // two 2 × 2 blocks: two reflections
1571 u1[0] = -at(1, 1);
1572 u1[1] = -at(2, 1);
1573 u1[2] = 1.0;
1574 double alpha1 {u1[0]};
1575 tau1 = reflector_tau(alpha1, u1.data() + 1, 2);
1576 u1[0] = 1.0;
1577 const double temp {-tau1 * (at(1, 2) + (u1[1] * at(2, 2)))};
1578 u2[0] = (-temp * u1[1]) - at(2, 2);
1579 u2[1] = -temp * u1[2];
1580 u2[2] = 1.0;
1581 double alpha2 {u2[0]};
1582 tau2 = reflector_tau(alpha2, u2.data() + 1, 2);
1583 u2[0] = 1.0;
1584 reflect_rows_3(u1, tau1, d.data(), 4, 4);
1585 reflect_columns_3(u1, tau1, d.data(), 4, 4);
1586 reflect_rows_3(u2, tau2, &dd(2, 1), 4, 4);
1587 reflect_columns_3(u2, tau2, &dd(1, 2), 4, 4);
1588 residue = std::max({std::abs(dd(3, 1)), std::abs(dd(3, 2)), std::abs(dd(4, 1)), std::abs(dd(4, 2))});
1589 }
1590 if (residue > thresh) { // the swap would not leave the blocks apart: refused, T as it was
1591 return false;
1592 }
1593 if (n1 == 1) {
1594 reflect_rows_3(u1, tau1, &t(j1, j1), tld, count_of(n - j1 + 1));
1595 reflect_columns_3(u1, tau1, &t(1, j1), tld, count_of(j2));
1596 t(j3, j1) = 0.0;
1597 t(j3, j2) = 0.0;
1598 t(j3, j3) = t11;
1599 reflect_rows_3(u1, tau1, &qt(j1, 1), count_of(qt.ld), count_of(n));
1600 }
1601 else if (n2 == 1) {
1602 reflect_columns_3(u1, tau1, &t(1, j1), tld, count_of(j3));
1603 reflect_rows_3(u1, tau1, &t(j1, j2), tld, count_of(n - j1));
1604 t(j1, j1) = t33;
1605 t(j2, j1) = 0.0;
1606 t(j3, j1) = 0.0;
1607 reflect_rows_3(u1, tau1, &qt(j1, 1), count_of(qt.ld), count_of(n));
1608 }
1609 else {
1610 reflect_rows_3(u1, tau1, &t(j1, j1), tld, count_of(n - j1 + 1));
1611 reflect_columns_3(u1, tau1, &t(1, j1), tld, count_of(j4));
1612 reflect_rows_3(u2, tau2, &t(j2, j1), tld, count_of(n - j1 + 1));
1613 reflect_columns_3(u2, tau2, &t(1, j2), tld, count_of(j4));
1614 t(j3, j1) = 0.0;
1615 t(j3, j2) = 0.0;
1616 t(j4, j1) = 0.0;
1617 t(j4, j2) = 0.0;
1618 reflect_rows_3(u1, tau1, &qt(j1, 1), count_of(qt.ld), count_of(n));
1619 reflect_rows_3(u2, tau2, &qt(j2, 1), count_of(qt.ld), count_of(n));
1620 }
1621 if (n2 == 2) {
1622 standardize_at(t, qt, n, j1);
1623 }
1624 if (n1 == 2) {
1625 standardize_at(t, qt, n, j1 + n2);
1626 }
1627 return true;
1628 }
1629
1633 lapack_index n,
1634 lapack_index j)
1635 {
1636 return j < n && t(j + 1, j) != 0.0 ? 2 : 1;
1637 }
1638
1646 lapack_index n,
1649 {
1650 if (ifst > 1 && t(ifst, ifst - 1) != 0.0) {
1651 --ifst;
1652 }
1654 if (ilst > 1 && t(ilst, ilst - 1) != 0.0) {
1655 --ilst;
1656 }
1657 const lapack_index nbl {block_order(t, n, ilst)};
1658 if (ifst == ilst) {
1659 return true;
1660 }
1661 struct refused : std::exception // an exchange refused: the block stays where it got to
1662 {};
1663 const auto exchange {[&t, &qt, n](lapack_index j1, lapack_index n1, lapack_index n2) {
1664 if (!exchange_blocks(t, qt, n, j1, n1, n2)) {
1665 throw refused {};
1666 }
1667 }};
1669 try {
1670 if (ifst < ilst) {
1671 if (nbf == 2 && nbl == 1) {
1672 --ilst;
1673 }
1674 if (nbf == 1 && nbl == 2) {
1675 ++ilst;
1676 }
1677 while (here < ilst) {
1678 if (nbf != 3) { // the block, 1 × 1 or 2 × 2, past the next one
1679 const lapack_index next {here + nbf + 1 <= n && t(here + nbf + 1, here + nbf) != 0.0 ? 2 : 1};
1680 exchange(here, nbf, next);
1681 here += next;
1682 if (nbf == 2 && t(here + 1, here) == 0.0) {
1683 nbf = 3; // the 2 × 2 block split into two 1 × 1
1684 }
1685 }
1686 else { // two 1 × 1 blocks, each past the next block
1687 const lapack_index next {here + 3 <= n && t(here + 3, here + 2) != 0.0 ? 2 : 1};
1688 exchange(here + 1, 1, next);
1689 if (next == 2 && t(here + 2, here + 1) == 0.0) { // the next block split too: the first past both pieces
1690 exchange(here, 1, 1);
1691 exchange(here + 1, 1, 1);
1692 here += 2;
1693 }
1694 else {
1695 exchange(here, 1, next);
1696 here += next;
1697 }
1698 }
1699 }
1700 }
1701 else {
1702 while (here > ilst) {
1703 if (nbf != 3) {
1704 const lapack_index next {here >= 3 && t(here - 1, here - 2) != 0.0 ? 2 : 1};
1705 exchange(here - next, next, nbf);
1706 here -= next;
1707 if (nbf == 2 && t(here + 1, here) == 0.0) {
1708 nbf = 3;
1709 }
1710 }
1711 else {
1712 const lapack_index next {here >= 3 && t(here - 1, here - 2) != 0.0 ? 2 : 1};
1713 exchange(here - next, next, 1);
1714 if (next == 2 && t(here, here - 1) == 0.0) {
1715 exchange(here, 1, 1);
1716 exchange(here - 1, 1, 1);
1717 here -= 2;
1718 }
1719 else {
1720 exchange(here - next + 1, next, 1);
1721 here -= next;
1722 }
1723 }
1724 }
1725 }
1726 }
1727 catch (const refused&) {
1728 ilst = here;
1729 return false;
1730 }
1731 ilst = here;
1732 return true;
1733 }
1734
1737 inline bool reorder(one_based<std::complex<double>> t,
1738 one_based<std::complex<double>> qt,
1739 lapack_index n,
1742 {
1743 for (lapack_index k {ifst}; k < ilst; ++k) {
1744 exchange_diagonal(t, qt, n, k);
1745 }
1746 for (lapack_index k {ifst - 1}; k >= ilst; --k) {
1747 exchange_diagonal(t, qt, n, k);
1748 }
1749 return true;
1750 }
1751
1757 lapack_index count,
1758 const std::complex<double>& s1,
1759 const std::complex<double>& s2,
1760 double* v)
1761 {
1762 const double sr1 {s1.real()};
1763 const double si1 {s1.imag()};
1764 const double sr2 {s2.real()};
1765 const double si2 {s2.imag()};
1766 if (count == 2) {
1767 const double s {std::abs(h(1, 1) - sr2) + std::abs(si2) + std::abs(h(2, 1))};
1768 if (s == 0.0) {
1769 v[0] = 0.0;
1770 v[1] = 0.0;
1771 return;
1772 }
1773 const double h21s {h(2, 1) / s};
1774 v[0] = (h21s * h(1, 2)) + ((h(1, 1) - sr1) * ((h(1, 1) - sr2) / s)) - (si1 * (si2 / s));
1775 v[1] = h21s * (h(1, 1) + h(2, 2) - sr1 - sr2);
1776 return;
1777 }
1778 const double s {std::abs(h(1, 1) - sr2) + std::abs(si2) + std::abs(h(2, 1)) + std::abs(h(3, 1))};
1779 if (s == 0.0) {
1780 v[0] = 0.0;
1781 v[1] = 0.0;
1782 v[2] = 0.0;
1783 return;
1784 }
1785 const double h21s {h(2, 1) / s};
1786 const double h31s {h(3, 1) / s};
1787 v[0] = ((h(1, 1) - sr1) * ((h(1, 1) - sr2) / s)) - (si1 * (si2 / s)) + (h(1, 2) * h21s) + (h(1, 3) * h31s);
1788 v[1] = (h21s * (h(1, 1) + h(2, 2) - sr1 - sr2)) + (h(2, 3) * h31s);
1789 v[2] = (h31s * (h(1, 1) + h(3, 3) - sr1 - sr2)) + (h21s * h(3, 2));
1790 }
1791
1793 inline void bulge_column(one_based<std::complex<double>> h,
1794 lapack_index count,
1795 const std::complex<double>& s1,
1796 const std::complex<double>& s2,
1797 std::complex<double>* v)
1798 {
1799 using C = std::complex<double>;
1800 if (count == 2) {
1801 const double s {modulus_1(h(1, 1) - s2) + modulus_1(h(2, 1))};
1802 if (s == 0.0) {
1803 v[0] = C {};
1804 v[1] = C {};
1805 return;
1806 }
1807 const C h21s {h(2, 1) / s};
1808 v[0] = (h21s * h(1, 2)) + ((h(1, 1) - s1) * ((h(1, 1) - s2) / s));
1809 v[1] = h21s * (h(1, 1) + h(2, 2) - s1 - s2);
1810 return;
1811 }
1812 const double s {modulus_1(h(1, 1) - s2) + modulus_1(h(2, 1)) + modulus_1(h(3, 1))};
1813 if (s == 0.0) {
1814 v[0] = C {};
1815 v[1] = C {};
1816 v[2] = C {};
1817 return;
1818 }
1819 const C h21s {h(2, 1) / s};
1820 const C h31s {h(3, 1) / s};
1821 v[0] = ((h(1, 1) - s1) * ((h(1, 1) - s2) / s)) + (h21s * h(1, 2)) + (h31s * h(1, 3));
1822 v[1] = (h21s * (h(1, 1) + h(2, 2) - s1 - s2)) + (h31s * h(2, 3));
1823 v[2] = (h31s * (h(1, 1) + h(3, 3) - s1 - s2)) + (h21s * h(3, 2));
1824 }
1825
1828 inline void pair_shifts(std::complex<double>* s,
1829 lapack_index count,
1830 double /*real*/)
1831 {
1832 for (lapack_index i {0}; i + 2 < count; i += 2) {
1833 if (s[i].imag() != -s[i + 1].imag()) {
1834 const std::complex<double> first {s[i]};
1835 s[i] = s[i + 1];
1836 s[i + 1] = s[i + 2];
1837 s[i + 2] = first;
1838 }
1839 }
1840 }
1841
1843 inline void pair_shifts(std::complex<double>* /*s*/,
1844 lapack_index /*count*/,
1845 const std::complex<double>& /*complex*/)
1846 {
1847 }
1848
1850 [[nodiscard]] inline double as_scalar(const std::complex<double>& s,
1851 double /*real*/)
1852 {
1853 return s.real();
1854 }
1855
1857 [[nodiscard]] inline std::complex<double> as_scalar(const std::complex<double>& s,
1858 const std::complex<double>& /*complex*/)
1859 {
1860 return s;
1861 }
1862
1865 template <typename T>
1867 lapack_index k,
1870 double smallest)
1871 {
1872 if (h(k + 1, k) == T {}) {
1873 return;
1874 }
1875 double test {modulus_1(h(k, k)) + modulus_1(h(k + 1, k + 1))};
1876 if (test == 0.0) {
1877 for (lapack_index d {1}; d <= 3; ++d) {
1878 if (k >= ktop + d) {
1879 test += std::abs(real_part(h(k, k - d)));
1880 }
1881 if (k <= kbot - d - 1) {
1882 test += std::abs(real_part(h(k + d + 1, k + 1)));
1883 }
1884 }
1885 }
1886 if (modulus_1(h(k + 1, k)) > std::max(smallest, schur_ulp * test)) {
1887 return;
1888 }
1889 const double h12 {std::max(modulus_1(h(k + 1, k)), modulus_1(h(k, k + 1)))};
1890 const double h21 {std::min(modulus_1(h(k + 1, k)), modulus_1(h(k, k + 1)))};
1891 const double h11 {std::max(modulus_1(h(k + 1, k + 1)), modulus_1(h(k, k) - h(k + 1, k + 1)))};
1892 const double h22 {std::min(modulus_1(h(k + 1, k + 1)), modulus_1(h(k, k) - h(k + 1, k + 1)))};
1893 const double scale {h11 + h12};
1894 const double test2 {h22 * (h11 / scale)};
1895 if (test2 == 0.0 || h21 * (h12 / scale) <= std::max(smallest, schur_ulp * test2)) {
1896 h(k + 1, k) = T {};
1897 }
1898 }
1899
1902 template <typename T>
1904 std::size_t stride,
1905 const T& tau,
1906 const T& v2,
1907 const T& v3)
1908 {
1909 const T sum {times(conj_of(tau), x[0] + times(conj_of(v2), x[stride]) + times(conj_of(v3), x[2 * stride]))};
1910 x[0] -= sum;
1911 x[stride] -= times(sum, v2);
1912 x[2 * stride] -= times(sum, v3);
1913 }
1914
1923 template <typename T>
1927 std::complex<double>* s,
1928 lapack_index count,
1929 bool accumulate)
1930 {
1931 const lapack_index n {static_cast<lapack_index>(target.n)};
1932 const one_based<T> h {target.h->data(), n};
1933 pair_shifts(s, count, T {});
1934 const lapack_index ns {count - (count % 2)};
1935 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(n) / schur_ulp)};
1936 if (ktop + 2 <= kbot) {
1937 h(ktop + 2, ktop) = T {};
1938 }
1939 const lapack_index nbmps {ns / 2};
1940 const lapack_index kdu {4 * nbmps};
1942 const one_based<T> ut {u_store.data(), kdu}; // Uᵀ: the accumulation updates columns of U, contiguous in it
1943 buffer<T> v_store(count_of(3 * nbmps), T {});
1944 const auto v {[&v_store](lapack_index i, lapack_index m) -> T& { return v_store[count_of(((m - 1) * 3) + (i - 1))]; }};
1945 const lapack_index low {static_cast<lapack_index>(target.low) + 1};
1946 const lapack_index high {static_cast<lapack_index>(target.high)};
1947 for (lapack_index incol {ktop - (2 * nbmps) + 1}; incol <= kbot - 2; incol += 2 * nbmps) {
1948 const lapack_index ndcol {incol + kdu};
1949 const lapack_index jtop {accumulate ? std::max(ktop, incol) : (target.full ? 1 : ktop)};
1950 const lapack_index jbot {accumulate ? std::min(ndcol, kbot) : (target.full ? n : kbot)};
1951 const auto to_z {[&](lapack_index k, lapack_index m, std::size_t entries) { // Z ← Z H, on Zᵀ's rows
1952 if (accumulate || target.zt == nullptr) {
1953 return;
1954 }
1955 const one_based<T> zt {target.zt->data(), n};
1956 if (entries == 3) {
1957 reflect_three_rows(&zt(k + 1, 1), &zt(k + 2, 1), &zt(k + 3, 1), count_of(low - 1), count_of(high), v(1, m), v(2, m), v(3, m), false);
1958 }
1959 else {
1960 reflect_two_rows(&zt(k + 1, 1), &zt(k + 2, 1), count_of(low - 1), count_of(high), v(1, m), v(2, m), false);
1961 }
1962 }};
1963 std::fill(u_store.begin(), u_store.end(), T {});
1964 for (lapack_index d {1}; d <= kdu; ++d) {
1965 ut(d, d) = T {1};
1966 }
1967 for (lapack_index krcol {incol}; krcol <= std::min(incol + (2 * nbmps) - 1, kbot - 2); ++krcol) {
1968 const lapack_index mtop {std::max<lapack_index>(1, ((ktop - krcol) / 2) + 1)};
1969 const lapack_index mbot {std::min(nbmps, (kbot - krcol - 1) / 2)};
1970 const lapack_index m22 {mbot + 1};
1971 const bool bmp22 {mbot < nbmps && krcol + (2 * (m22 - 1)) == kbot - 2};
1972 if (bmp22) { // a 2 × 2 reflection at the bottom
1973 const lapack_index k {krcol + (2 * (m22 - 1))};
1974 if (k == ktop - 1) {
1975 std::array<T, 2> column {};
1976 bulge_column(one_based<T> {&h(k + 1, k + 1), n}, 2, s[(2 * m22) - 2], s[(2 * m22) - 1], column.data());
1977 T beta {column[0]};
1978 v(2, m22) = column[1];
1979 v(1, m22) = reflector_tau(beta, &v(2, m22), 1);
1980 }
1981 else {
1982 T beta {h(k + 1, k)};
1983 v(2, m22) = h(k + 2, k);
1984 v(1, m22) = reflector_tau(beta, &v(2, m22), 1);
1985 h(k + 1, k) = beta;
1986 h(k + 2, k) = T {};
1987 }
1988 reflect_two_columns(&h(jtop, k + 1), count_of(std::min(kbot, k + 3) - jtop + 1), count_of(n), v(1, m22), v(2, m22));
1989 reflect_two_rows(&h(k + 1, 1), &h(k + 2, 1), count_of(k), count_of(jbot), v(1, m22), v(2, m22), true);
1990 if (k >= ktop) {
1992 }
1993 const lapack_index kms {k - incol};
1994 if (accumulate) {
1995 const std::size_t from {count_of(std::max<lapack_index>(1, ktop - incol) - 1)};
1996 reflect_two_rows(&ut(kms + 1, 1), &ut(kms + 2, 1), from, count_of(kdu), v(1, m22), v(2, m22), false);
1997 }
1998 to_z(k, m22, 2);
1999 }
2000 for (lapack_index m {mbot}; m >= mtop; --m) { // the chain of 3 × 3 reflections
2001 const lapack_index k {krcol + (2 * (m - 1))};
2002 if (k == ktop - 1) {
2003 std::array<T, 3> column {};
2004 bulge_column(one_based<T> {&h(ktop, ktop), n}, 3, s[(2 * m) - 2], s[(2 * m) - 1], column.data());
2005 T alpha {column[0]};
2006 v(2, m) = column[1];
2007 v(3, m) = column[2];
2008 v(1, m) = reflector_tau(alpha, &v(2, m), 2);
2009 }
2010 else {
2011 // the row below the bulge takes the previous reflection, its first two entries being zero
2012 const T sum {v(1, m) * v(3, m) * h(k + 3, k + 2)};
2013 h(k + 3, k) = -sum;
2014 h(k + 3, k + 1) = -sum * conj_of(v(2, m));
2015 h(k + 3, k + 2) -= sum * conj_of(v(3, m));
2016 T beta {h(k + 1, k)};
2017 v(2, m) = h(k + 2, k);
2018 v(3, m) = h(k + 3, k);
2019 v(1, m) = reflector_tau(beta, &v(2, m), 2);
2020 // A bulge collapses (vigilant deflation, or destructive underflow) where the row below it holds only its
2021 // last entry: then a bulge started afresh from the shifts replaces it where its fill would be negligible
2022 // (the fill of none is infinite).
2023 double fill {std::numeric_limits<double>::infinity()};
2024 std::array<T, 3> fresh {};
2025 T fresh_tau {};
2026 T fresh_sum {};
2027 if (h(k + 3, k) == T {} && h(k + 3, k + 2) != T {}) { // the entry between is −sum v̄₂: zero with it
2028 bulge_column(one_based<T> {&h(k + 1, k + 1), n}, 3, s[(2 * m) - 2], s[(2 * m) - 1], fresh.data());
2029 T alpha {fresh[0]};
2030 fresh_tau = reflector_tau(alpha, fresh.data() + 1, 2);
2031 fresh_sum = conj_of(fresh_tau) * (h(k + 1, k) + (conj_of(fresh[1]) * h(k + 2, k)));
2032 fill = modulus_1(h(k + 2, k) - (fresh_sum * fresh[1])) + modulus_1(fresh_sum * fresh[2])
2033 - (schur_ulp * (modulus_1(h(k, k)) + modulus_1(h(k + 1, k + 1)) + modulus_1(h(k + 2, k + 2))));
2034 }
2035 if (fill <= 0.0) {
2036 h(k + 1, k) -= fresh_sum;
2037 v(1, m) = fresh_tau;
2038 v(2, m) = fresh[1];
2039 v(3, m) = fresh[2];
2040 }
2041 else {
2042 h(k + 1, k) = beta;
2043 }
2044 h(k + 2, k) = T {};
2045 h(k + 3, k) = T {};
2046 }
2047 reflect_three_columns(&h(jtop, k + 1), count_of(std::min(kbot, k + 3) - jtop + 1), count_of(n), v(1, m), v(2, m), v(3, m));
2048 reflect_from_left(&h(k + 1, k + 1), count_of(n), v(1, m), v(2, m), v(3, m));
2049 if (k >= ktop) {
2051 }
2052 }
2053 for (lapack_index m {mbot}; m >= mtop; --m) { // the rest of the left reflections, within the slab
2054 const lapack_index k {krcol + (2 * (m - 1))};
2055 reflect_three_rows(&h(k + 1, 1), &h(k + 2, 1), &h(k + 3, 1), count_of(std::max(ktop, krcol + (2 * m)) - 1), count_of(jbot), v(1, m),
2056 v(2, m), v(3, m), true);
2057 }
2058 for (lapack_index m {mbot}; m >= mtop; --m) { // accumulated in U
2059 const lapack_index k {krcol + (2 * (m - 1))};
2060 const lapack_index kms {k - incol};
2061 const lapack_index i2 {std::max({lapack_index {1}, ktop - incol, kms - (krcol - incol) + 1})};
2062 const lapack_index i4 {std::min(kdu, krcol + (2 * (mbot - 1)) - incol + 5)};
2063 if (accumulate) {
2064 reflect_three_rows(&ut(kms + 1, 1), &ut(kms + 2, 1), &ut(kms + 3, 1), count_of(i2 - 1), count_of(i4), v(1, m), v(2, m), v(3, m), false);
2065 }
2066 to_z(k, m, 3);
2067 }
2068 }
2069 if (!accumulate) {
2070 continue;
2071 }
2072 // U to the rest of the matrix: the rows right of the slab, the columns above it, and Z
2073 const lapack_index jtop_far {target.full ? 1 : ktop};
2074 const lapack_index jbot_far {target.full ? n : kbot};
2075 const lapack_index k1 {std::max<lapack_index>(1, ktop - incol)};
2076 const lapack_index nu {(kdu - std::max<lapack_index>(0, ndcol - kbot)) - k1 + 1}; // ≥ kbot − ktop + 1
2079 for (lapack_index i {1}; i <= nu; ++i) {
2080 for (lapack_index j {1}; j <= nu; ++j) {
2081 u_block[count_of(((i - 1) * nu) + (j - 1))] = ut(k1 + j - 1, k1 + i - 1);
2082 u_adjoint[count_of(((j - 1) * nu) + (i - 1))] = conj_of(ut(k1 + j - 1, k1 + i - 1));
2083 }
2084 }
2085 const lapack_index first_column {std::min(ndcol, kbot) + 1};
2086 if (first_column <= jbot_far) {
2087 const std::size_t width {count_of(jbot_far - first_column + 1)};
2088 buffer<T> product(count_of(nu) * width, T {});
2089 gemm(count_of(nu), width, count_of(nu), u_adjoint.data(), count_of(nu), &h(incol + k1, first_column), count_of(n), product.data(), width);
2090 for (lapack_index i {1}; i <= nu; ++i) {
2091 std::copy_n(product.data() + (count_of(i - 1) * width), width, &h(incol + k1 + i - 1, first_column));
2092 }
2093 }
2094 const lapack_index last_row {std::max(ktop, incol) - 1};
2095 if (jtop_far <= last_row) {
2096 const std::size_t rows {count_of(last_row - jtop_far + 1)};
2097 buffer<T> product(rows * count_of(nu), T {});
2098 gemm(rows, count_of(nu), count_of(nu), &h(jtop_far, incol + k1), count_of(n), u_block.data(), count_of(nu), product.data(), count_of(nu));
2099 for (std::size_t r {0}; r < rows; ++r) {
2100 std::copy_n(product.data() + (r * count_of(nu)), count_of(nu), &h(jtop_far + static_cast<lapack_index>(r), incol + k1));
2101 }
2102 }
2103 if (target.zt != nullptr) { // (Z U)ᵀ = Uᵀ Zᵀ, on Zᵀ's rows
2105 for (lapack_index i {1}; i <= nu; ++i) {
2106 for (lapack_index j {1}; j <= nu; ++j) {
2107 u_transpose[count_of(((j - 1) * nu) + (i - 1))] = ut(k1 + j - 1, k1 + i - 1);
2108 }
2109 }
2110 const one_based<T> zt {target.zt->data(), n};
2111 const std::size_t width {count_of(high - low + 1)};
2112 buffer<T> product(count_of(nu) * width, T {});
2113 gemm(count_of(nu), width, count_of(nu), u_transpose.data(), count_of(nu), &zt(incol + k1, low), count_of(n), product.data(), width);
2114 for (lapack_index i {1}; i <= nu; ++i) {
2115 std::copy_n(product.data() + (count_of(i - 1) * width), width, &zt(incol + k1 + i - 1, low));
2116 }
2117 }
2118 }
2119 }
2120
2121 template <typename T>
2123 std::complex<double>* w,
2124 bool recursive,
2125 lapack_index steps = 0);
2126
2128 inline void plain_schur(const schur_target<double>& t,
2129 std::complex<double>* w)
2130 {
2131 buffer<double> re(t.n, 0.0);
2132 buffer<double> im(t.n, 0.0);
2133 real_schur(t, re, im, schur_steps_per_order * std::max<std::size_t>(10, t.high - t.low));
2134 for (std::size_t i {t.low}; i < t.high; ++i) {
2135 w[i] = std::complex<double> {re[i], im[i]};
2136 }
2137 }
2138
2140 inline void plain_schur(const schur_target<std::complex<double>>& t,
2141 std::complex<double>* w)
2142 {
2143 buffer<std::complex<double>> values(t.n);
2144 complex_schur(t, values, schur_steps_per_order * std::max<std::size_t>(10, t.high - t.low));
2145 std::copy(values.begin() + static_cast<std::ptrdiff_t>(t.low), values.begin() + static_cast<std::ptrdiff_t>(t.high), w + t.low);
2146 }
2147
2157 double s,
2158 double smallest,
2159 std::complex<double>* w)
2160 {
2161 const auto size {[&t](lapack_index i, lapack_index k) {
2162 return k == i + 1 ? std::abs(t(i, i)) : std::abs(t(i, i)) + (std::sqrt(std::abs(t(i + 1, i))) * std::sqrt(std::abs(t(i, i + 1))));
2163 }};
2164 lapack_index ns {jw};
2165 lapack_index ilst {1};
2166 while (ilst <= ns) {
2167 const lapack_index order {ns > 1 && t(ns, ns - 1) != 0.0 ? 2 : 1};
2168 double foo {order == 1 ? std::abs(t(ns, ns)) : size(ns - 1, ns + 1)};
2169 if (foo == 0.0) {
2170 foo = std::abs(s);
2171 }
2172 const double spike {order == 1 ? std::abs(s * vt(ns, 1)) : std::max(std::abs(s * vt(ns, 1)), std::abs(s * vt(ns - 1, 1)))};
2173 if (spike <= std::max(smallest, schur_ulp * foo)) {
2174 ns -= order;
2175 }
2176 else {
2177 (void)reorder(t, vt, jw, ns, ilst);
2178 ilst += order;
2179 }
2180 }
2181 if (ns < jw) { // bubble sort of the undeflated blocks, larger first
2182 bool sorted {false};
2183 lapack_index i {ns + 1};
2184 const auto next {[&t](lapack_index from, lapack_index end) { return from == end || t(from + 1, from) == 0.0 ? from + 1 : from + 2; }};
2185 while (!sorted) {
2186 sorted = true;
2187 const lapack_index kend {i - 1};
2188 i = 1;
2189 lapack_index k {next(i, ns)};
2190 while (k <= kend) {
2191 const double evi {size(i, k)};
2192 const double evk {k == kend ? std::abs(t(k, k)) : size(k, next(k, kend))};
2193 if (evi >= evk) {
2194 i = k;
2195 }
2196 else {
2197 sorted = false;
2198 lapack_index last {k};
2199 i = reorder(t, vt, jw, i, last) ? last : k;
2200 }
2201 k = next(i, kend);
2202 }
2203 }
2204 }
2205 for (lapack_index i {jw}; i >= 1;) {
2206 if (i == 1 || t(i, i - 1) == 0.0) {
2207 w[i - 1] = std::complex<double> {t(i, i), 0.0};
2208 --i;
2209 }
2210 else {
2211 double a {t(i - 1, i - 1)};
2212 double b {t(i - 1, i)};
2213 double c {t(i, i - 1)};
2214 double d {t(i, i)};
2215 const standard_block block {standardize_block(a, b, c, d)};
2216 w[i - 2] = std::complex<double> {block.re1, block.im1};
2217 w[i - 1] = std::complex<double> {block.re2, block.im2};
2218 i -= 2;
2219 }
2220 }
2221 return ns;
2222 }
2223
2225 inline lapack_index undeflated(one_based<std::complex<double>> t,
2226 one_based<std::complex<double>> vt,
2228 const std::complex<double>& s,
2229 double smallest,
2230 std::complex<double>* w)
2231 {
2232 lapack_index ns {jw};
2233 lapack_index ilst {1};
2234 for (lapack_index count {1}; count <= jw; ++count) {
2235 double foo {modulus_1(t(ns, ns))};
2236 if (foo == 0.0) {
2237 foo = modulus_1(s);
2238 }
2239 if (modulus_1(s) * modulus_1(vt(ns, 1)) <= std::max(smallest, schur_ulp * foo)) {
2240 --ns;
2241 }
2242 else {
2243 (void)reorder(t, vt, jw, ns, ilst);
2244 ++ilst;
2245 }
2246 }
2247 if (ns < jw) {
2248 for (lapack_index i {1}; i <= ns; ++i) {
2249 lapack_index first {i};
2250 for (lapack_index j {i + 1}; j <= ns; ++j) {
2251 first = modulus_1(t(j, j)) > modulus_1(t(first, first)) ? j : first;
2252 }
2253 lapack_index last {i};
2254 (void)reorder(t, vt, jw, first, last);
2255 }
2256 }
2257 for (lapack_index i {1}; i <= jw; ++i) {
2258 w[i - 1] = t(i, i);
2259 }
2260 return ns;
2261 }
2262
2269
2278 template <typename T>
2283 std::complex<double>* w,
2284 bool recursive)
2285 {
2286 const lapack_index n {static_cast<lapack_index>(target.n)};
2287 const one_based<T> h {target.h->data(), n};
2288 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(n) / schur_ulp)};
2289 const lapack_index jw {std::min(nw, kbot - ktop + 1)};
2290 const lapack_index kwtop {kbot - jw + 1};
2291 T s {kwtop == ktop ? T {} : h(kwtop, kwtop - 1)};
2292 if (kbot == kwtop) { // a 1 × 1 window: the whole active block (a window has two rows otherwise), so s = 0
2293 w[kwtop - 1] = h(kwtop, kwtop);
2294 return {0, 1};
2295 }
2296 const std::size_t width {count_of(jw)};
2297 buffer<T> t_store(width * width, T {});
2298 buffer<T> vt_store(width * width, T {});
2299 const one_based<T> t {t_store.data(), jw};
2300 const one_based<T> vt {vt_store.data(), jw};
2301 for (lapack_index i {1}; i <= jw; ++i) {
2302 for (lapack_index j {std::max<lapack_index>(1, i - 1)}; j <= jw; ++j) {
2303 t(i, j) = h(kwtop + i - 1, kwtop + j - 1);
2304 }
2305 vt(i, i) = T {1};
2306 }
2308 const schur_target<T> window {&t_store, width, 0, width, true, &vt_store};
2309 if (recursive && jw >= multishift_from(T {})) {
2310 multishift_schur(window, local.data(), false);
2311 }
2312 else {
2313 plain_schur(window, local.data());
2314 }
2315 for (lapack_index j {1}; j + 3 <= jw; ++j) { // the exchanges need a clean margin below the diagonal
2316 t(j + 2, j) = T {};
2317 t(j + 3, j) = T {};
2318 }
2319 if (jw > 2) {
2320 t(jw, jw - 2) = T {};
2321 }
2322 const lapack_index ns {undeflated(t, vt, jw, s, smallest, w + kwtop - 1)};
2323 if (ns == 0) {
2324 s = T {};
2325 }
2326 if (ns == jw) { // nothing deflated (s ≠ 0 then: s = 0 deflates everything): H as it was
2327 return {ns, 0};
2328 }
2329 if (ns > 1) { // the spike reflected back into the first column, then Hessenberg form above
2330 buffer<T> v(count_of(ns));
2331 for (lapack_index i {1}; i <= ns; ++i) {
2332 v[count_of(i - 1)] = conj_of(vt(i, 1));
2333 }
2334 T beta {v[0]};
2335 const T tau {reflector_tau(beta, v.data() + 1, count_of(ns - 1))};
2336 v[0] = T {1};
2337 for (lapack_index i {3}; i <= jw; ++i) {
2338 for (lapack_index j {1}; j + 2 <= i; ++j) {
2339 t(i, j) = T {};
2340 }
2341 }
2342 for (lapack_index c {1}; c <= jw; ++c) { // (I − τ̄ v vᴴ) on rows 1 … ns
2343 T sum {};
2344 for (lapack_index r {1}; r <= ns; ++r) {
2345 sum += times(conj_of(v[count_of(r - 1)]), t(r, c));
2346 }
2347 for (lapack_index r {1}; r <= ns; ++r) {
2348 t(r, c) -= times(times(conj_of(tau), v[count_of(r - 1)]), sum);
2349 }
2350 }
2351 for (lapack_index r {1}; r <= ns; ++r) { // (I − τ v vᴴ) on columns 1 … ns
2352 T sum {};
2353 for (lapack_index c {1}; c <= ns; ++c) {
2354 sum += times(t(r, c), v[count_of(c - 1)]);
2355 }
2356 for (lapack_index c {1}; c <= ns; ++c) {
2357 t(r, c) -= times(times(tau, sum), conj_of(v[count_of(c - 1)]));
2358 }
2359 }
2360 for (lapack_index c {1}; c <= jw; ++c) { // V ← V (I − τ v vᴴ): Vᵀ's rows 1 … ns
2361 T sum {};
2362 for (lapack_index r {1}; r <= ns; ++r) {
2363 sum += times(v[count_of(r - 1)], vt(r, c));
2364 }
2365 for (lapack_index r {1}; r <= ns; ++r) {
2366 vt(r, c) -= times(times(tau, conj_of(v[count_of(r - 1)])), sum);
2367 }
2368 }
2369 const buffer<T> qt {hessenberg(t_store, width, 0, count_of(ns), true)};
2370 buffer<T> rows(count_of(ns) * width, T {});
2371 gemm(count_of(ns), width, count_of(ns), qt.data(), width, vt_store.data(), width, rows.data(), width);
2372 std::copy(rows.begin(), rows.end(), vt_store.begin());
2373 }
2374 if (kwtop > 1) {
2375 h(kwtop, kwtop - 1) = s * conj_of(vt(1, 1));
2376 }
2377 for (lapack_index i {1}; i <= jw; ++i) {
2378 for (lapack_index j {std::max<lapack_index>(1, i - 1)}; j <= jw; ++j) {
2379 h(kwtop + i - 1, kwtop + j - 1) = t(i, j);
2380 }
2381 }
2382 buffer<T> v(width * width);
2383 buffer<T> v_adjoint(width * width);
2384 for (lapack_index i {1}; i <= jw; ++i) {
2385 for (lapack_index j {1}; j <= jw; ++j) {
2386 v[count_of(((j - 1) * jw) + (i - 1))] = vt(i, j);
2387 v_adjoint[count_of(((i - 1) * jw) + (j - 1))] = conj_of(vt(i, j));
2388 }
2389 }
2390 const lapack_index ltop {target.full ? 1 : ktop};
2391 if (ltop < kwtop) { // the rows above the window: H V
2392 const std::size_t rows {count_of(kwtop - ltop)};
2393 buffer<T> product(rows * width, T {});
2394 gemm(rows, width, width, &h(ltop, kwtop), count_of(n), v.data(), width, product.data(), width);
2395 for (std::size_t r {0}; r < rows; ++r) {
2396 std::copy_n(product.data() + (r * width), width, &h(ltop + static_cast<lapack_index>(r), kwtop));
2397 }
2398 }
2399 if (target.full && kbot < n) { // the columns right of it: Vᴴ H
2400 const std::size_t columns {count_of(n - kbot)};
2401 buffer<T> product(width * columns, T {});
2402 gemm(width, columns, width, v_adjoint.data(), width, &h(kwtop, kbot + 1), count_of(n), product.data(), columns);
2403 for (std::size_t r {0}; r < width; ++r) {
2404 std::copy_n(product.data() + (r * columns), columns, &h(kwtop + static_cast<lapack_index>(r), kbot + 1));
2405 }
2406 }
2407 if (target.zt != nullptr) { // (Z V)ᵀ = Vᵀ Zᵀ
2408 const one_based<T> zt {target.zt->data(), n};
2409 const lapack_index low {static_cast<lapack_index>(target.low) + 1};
2410 const std::size_t columns {target.high - target.low};
2411 buffer<T> product(width * columns, T {});
2412 gemm(width, columns, width, vt_store.data(), width, &zt(kwtop, low), count_of(n), product.data(), columns);
2413 for (std::size_t r {0}; r < width; ++r) {
2414 std::copy_n(product.data() + (r * columns), columns, &zt(kwtop + static_cast<lapack_index>(r), low));
2415 }
2416 }
2417 return {ns, jw - ns};
2418 }
2419
2422 {
2423 lapack_index ns {2};
2424 if (nh >= 6000) {
2425 ns = 256;
2426 }
2427 else if (nh >= 3000) {
2428 ns = 128;
2429 }
2430 else if (nh >= 590) {
2431 ns = 64;
2432 }
2433 else if (nh >= 150) {
2434 ns = std::max<lapack_index>(10, nh / static_cast<lapack_index>(std::lround(std::log2(static_cast<double>(nh)))));
2435 }
2436 else if (nh >= 60) {
2437 ns = 10;
2438 }
2439 else if (nh >= 30) {
2440 ns = 4;
2441 }
2442 return std::max<lapack_index>(2, ns - (ns % 2));
2443 }
2444
2448 {
2449 return nh <= 500 ? ns : 3 * ns / 2;
2450 }
2451
2455 std::complex<double>* w,
2459 {
2460 for (lapack_index i {kbot}; i >= std::max(ks + 1, ktop + 2); i -= 2) {
2461 const double ss {std::abs(h(i, i - 1)) + std::abs(h(i - 1, i - 2))};
2462 double a {(0.75 * ss) + h(i, i)};
2463 double b {ss};
2464 double c {-0.4375 * ss};
2465 double d {a};
2466 const standard_block block {standardize_block(a, b, c, d)};
2467 w[i - 2] = std::complex<double> {block.re1, block.im1};
2468 w[i - 1] = std::complex<double> {block.re2, block.im2};
2469 }
2470 // LAPACK's case ks = ktop cannot arise: a sweep's active block has three rows at least (one of two deflates whole
2471 // in its window), and ns ≤ kbot − ktop.
2472 }
2473
2475 inline void exceptional_shifts(one_based<std::complex<double>> h,
2476 std::complex<double>* w,
2479 lapack_index /*ktop*/)
2480 {
2481 for (lapack_index i {kbot}; i >= ks + 1; i -= 2) {
2482 w[i - 1] = h(i, i) + (0.75 * modulus_1(h(i, i - 1)));
2483 w[i - 2] = w[i - 1];
2484 }
2485 }
2486
2489 inline void pair_for_sweep(std::complex<double>* w,
2492 double /*real*/)
2493 {
2494 for (lapack_index i {kbot}; i >= ks + 2; i -= 2) {
2495 if (w[i - 1].imag() != -w[i - 2].imag()) {
2496 const std::complex<double> last {w[i - 1]};
2497 w[i - 1] = w[i - 2];
2498 w[i - 2] = w[i - 3];
2499 w[i - 3] = last;
2500 }
2501 }
2502 }
2503
2505 inline void pair_for_sweep(std::complex<double>* /*w*/,
2506 lapack_index /*ks*/,
2507 lapack_index /*kbot*/,
2508 const std::complex<double>& /*complex*/)
2509 {
2510 }
2511
2513 [[nodiscard]] inline bool two_real_shifts(const std::complex<double>* w,
2516 double /*real*/)
2517 {
2518 return kbot - ks + 1 == 2 && w[kbot - 1].imag() == 0.0;
2519 }
2520
2522 [[nodiscard]] inline bool two_real_shifts(const std::complex<double>* /*w*/,
2525 const std::complex<double>& /*complex*/)
2526 {
2527 return kbot - ks + 1 == 2;
2528 }
2529
2543 template <typename T>
2545 std::complex<double>* w,
2546 bool recursive,
2547 lapack_index steps)
2548 {
2549 const lapack_index n {static_cast<lapack_index>(target.n)};
2550 const one_based<T> h {target.h->data(), n};
2551 const lapack_index ilo {static_cast<lapack_index>(target.low) + 1};
2552 const lapack_index ihi {static_cast<lapack_index>(target.high)};
2553 const lapack_index nh {ihi - ilo + 1};
2555 const bool accumulate {recommended >= 14};
2556 const lapack_index nwr {std::min({nh, (n - 1) / 3, std::max<lapack_index>(2, recommended_window(nh, recommended))})};
2557 lapack_index nsr {std::min({recommended, (n - 3) / 6, ihi - ilo})};
2558 nsr = std::max<lapack_index>(2, nsr - (nsr % 2));
2559 const lapack_index nwmax {(n - 1) / 3};
2560 const lapack_index nsmax {((n - 3) / 6) - (((n - 3) / 6) % 2)};
2562 lapack_index ndfl {1};
2563 lapack_index ndec {-1};
2565 const lapack_index itmax {steps > 0 ? steps : 30 * std::max<lapack_index>(10, nh)};
2566 for (lapack_index it {1}; it <= itmax; ++it) {
2567 if (kbot < ilo) {
2568 return;
2569 }
2571 while (ktop > ilo && h(ktop, ktop - 1) != T {}) {
2572 --ktop;
2573 }
2574 const lapack_index active {kbot - ktop + 1};
2575 const lapack_index nwupbd {std::min(active, nwmax)};
2576 nw = ndfl < window_growth ? std::min(nwupbd, nwr) : std::min(nwupbd, 2 * nw);
2577 if (nw < nwmax) {
2578 if (nw >= active - 1) {
2579 nw = active;
2580 }
2581 else if (modulus_1(h(kbot - nw + 1, kbot - nw)) > modulus_1(h(kbot - nw, kbot - nw - 1))) {
2582 ++nw;
2583 }
2584 }
2585 if (ndfl < window_growth) {
2586 ndec = -1;
2587 }
2588 else if (ndec >= 0 || nw >= nwupbd) {
2589 ++ndec;
2590 if (nw - ndec < 2) {
2591 ndec = 0;
2592 }
2593 nw -= ndec;
2594 }
2596 kbot -= found.deflated;
2597 lapack_index ks {kbot - found.shifts + 1};
2598 if (found.deflated == 0 || (100 * found.deflated <= nw * nibble && kbot - ktop + 1 > std::min(multishift_crossover, nwmax))) {
2599 lapack_index ns {std::min({nsmax, nsr, std::max<lapack_index>(2, kbot - ktop)})};
2600 ns -= ns % 2;
2601 if (ndfl % exceptional_after == 0) {
2602 ks = kbot - ns + 1;
2603 exceptional_shifts(h, w, ks, kbot, ktop);
2604 }
2605 else {
2606 if (kbot - ks + 1 <= ns / 2) { // too few: the eigenvalues of the trailing ns × ns
2607 ks = kbot - ns + 1;
2608 buffer<T> trailing(count_of(ns * ns), T {});
2609 const one_based<T> lower {trailing.data(), ns};
2610 for (lapack_index i {1}; i <= ns; ++i) {
2611 for (lapack_index j {std::max<lapack_index>(1, i - 1)}; j <= ns; ++j) {
2612 lower(i, j) = h(ks + i - 1, ks + j - 1);
2613 }
2614 }
2615 // by the single-shift iterations: LAPACK's dlaqr4 serves only past order 3000, where ns exceeds 75
2616 plain_schur(schur_target<T> {&trailing, count_of(ns), 0, count_of(ns), false, nullptr}, w + ks - 1);
2617 }
2618 if (kbot - ks + 1 > ns) { // bubble sort, larger first: a real matrix's pairs stay together
2619 bool sorted {false};
2620 for (lapack_index k {kbot}; k > ks && !sorted; --k) {
2621 sorted = true;
2622 for (lapack_index i {ks}; i < k; ++i) {
2623 if (modulus_1(w[i - 1]) < modulus_1(w[i])) {
2624 std::swap(w[i - 1], w[i]);
2625 sorted = false;
2626 }
2627 }
2628 }
2629 }
2630 pair_for_sweep(w, ks, kbot, T {});
2631 }
2632 if (two_real_shifts(w, ks, kbot, T {})) {
2633 // two shifts, real for a real matrix: the one nearer the corner, twice
2634 const T corner {h(kbot, kbot)};
2635 if (modulus_1(as_scalar(w[kbot - 1], T {}) - corner) < modulus_1(as_scalar(w[kbot - 2], T {}) - corner)) {
2636 w[kbot - 2] = w[kbot - 1];
2637 }
2638 else {
2639 w[kbot - 1] = w[kbot - 2];
2640 }
2641 }
2642 ns = std::min(ns, kbot - ks + 1);
2643 ns -= ns % 2;
2644 ks = kbot - ns + 1;
2645 chase_bulges(target, ktop, kbot, w + ks - 1, ns, accumulate);
2646 }
2647 ndfl = found.deflated > 0 ? 1 : ndfl + 1;
2648 }
2649 throw convergence_error("eigendecomposition: the QR iterations did not converge");
2650 }
2651
2654 inline void schur_form(const schur_target<double>& t,
2655 buffer<double>& re,
2656 buffer<double>& im,
2657 std::size_t steps)
2658 {
2659 if (t.high - t.low < count_of(multishift_from(0.0))) {
2660 real_schur(t, re, im, steps);
2661 return;
2662 }
2664 multishift_schur(t, w.data(), true);
2665 for (std::size_t i {t.low}; i < t.high; ++i) {
2666 re[i] = w[i].real();
2667 im[i] = w[i].imag();
2668 }
2669 }
2670
2672 inline void schur_form(const schur_target<std::complex<double>>& t,
2673 buffer<std::complex<double>>& values,
2674 std::size_t steps)
2675 {
2676 if (t.high - t.low < count_of(multishift_from(std::complex<double> {}))) {
2677 complex_schur(t, values, steps);
2678 return;
2679 }
2680 multishift_schur(t, values.data(), true);
2681 }
2682
2688 template <typename S>
2689 [[nodiscard]] double solve_block(const S (&m)[4],
2690 S (&r)[2],
2691 double floor)
2692 {
2693 std::size_t p {0};
2694 for (std::size_t q {1}; q < 4; ++q) {
2695 p = modulus_1(m[q]) > modulus_1(m[p]) ? q : p;
2696 }
2697 const std::size_t pr {p / 2};
2698 const std::size_t pc {p % 2};
2699 const S u11 {modulus_1(m[p]) < floor ? S {floor} : m[p]};
2700 const S l21 {m[((1 - pr) * 2) + pc] / u11};
2701 const S u12 {m[(pr * 2) + 1 - pc]};
2702 S u22 {m[((1 - pr) * 2) + 1 - pc] - (l21 * u12)};
2703 if (modulus_1(u22) < floor) {
2704 u22 = S {floor};
2705 }
2706 const double rmax {std::max(modulus_1(r[0]), modulus_1(r[1]))};
2707 const double pivot {std::min(modulus_1(u11), modulus_1(u22))};
2708 double factor {1.0};
2709 if (4.0 * rmax > back_substitution_limit * pivot) {
2710 factor = back_substitution_limit * pivot / (4.0 * rmax);
2711 r[0] *= factor;
2712 r[1] *= factor;
2713 }
2714 const S rp {r[pr]};
2715 const S ro {r[1 - pr] - (l21 * rp)};
2716 r[1 - pc] = ro / u22;
2717 r[pc] = (rp - (u12 * r[1 - pc])) / u11;
2718 return factor;
2719 }
2720
2723 template <typename S>
2725 {
2727 double factor;
2728 };
2729
2732 template <typename S, typename P>
2734 P pivot,
2735 double floor)
2736 {
2737 const double size {modulus_1(pivot) < floor ? floor : modulus_1(pivot)};
2738 const P divisor {modulus_1(pivot) < floor ? P {floor} : pivot};
2739 double factor {1.0};
2740 if (modulus_1(r) > back_substitution_limit * size) {
2741 factor = back_substitution_limit * size / (2.0 * modulus_1(r));
2742 r *= factor;
2743 }
2744 return {r / divisor, factor};
2745 }
2746
2749 {
2750 using scalar = double;
2751
2753
2755 [[nodiscard]] double dot(const double* row,
2756 std::size_t from,
2757 std::size_t to) const
2758 {
2759 return dot_product(row + from, x.data() + from, to - from + 1);
2760 }
2761
2763 void set(std::size_t j,
2764 double value)
2765 {
2766 x[j] = value;
2767 }
2768
2770 void scale(std::size_t from,
2771 std::size_t to,
2772 double factor)
2773 {
2774 for (std::size_t l {from}; l <= to; ++l) {
2775 x[l] *= factor;
2776 }
2777 }
2778 };
2779
2783 {
2784 using scalar = std::complex<double>;
2785
2788
2790 [[nodiscard]] std::complex<double> dot(const double* row,
2791 std::size_t from,
2792 std::size_t to) const
2793 {
2794 return {dot_product(row + from, re.data() + from, to - from + 1), dot_product(row + from, im.data() + from, to - from + 1)};
2795 }
2796
2798 void set(std::size_t j,
2799 const std::complex<double>& value)
2800 {
2801 re[j] = value.real();
2802 im[j] = value.imag();
2803 }
2804
2806 void scale(std::size_t from,
2807 std::size_t to,
2808 double factor)
2809 {
2810 for (std::size_t l {from}; l <= to; ++l) {
2811 re[l] *= factor;
2812 im[l] *= factor;
2813 }
2814 }
2815 };
2816
2821 {
2822 using scalar = std::complex<double>;
2823
2826
2828 [[nodiscard]] std::complex<double> dot(const std::complex<double>* row,
2829 std::size_t from,
2830 std::size_t to) const
2831 {
2832 const auto* const parts {reinterpret_cast<const double*>(row)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the layout guarantee above
2833 const std::size_t count {2 * (to - from + 1)};
2834 return {dot_product(parts + (2 * from), real_side.data() + (2 * from), count),
2835 dot_product(parts + (2 * from), imaginary_side.data() + (2 * from), count)};
2836 }
2837
2839 void set(std::size_t j,
2840 const std::complex<double>& value)
2841 {
2842 real_side[2 * j] = value.real();
2843 real_side[(2 * j) + 1] = -value.imag();
2844 imaginary_side[2 * j] = value.imag();
2845 imaginary_side[(2 * j) + 1] = value.real();
2846 }
2847
2849 [[nodiscard]] std::complex<double> get(std::size_t j) const
2850 {
2851 return {real_side[2 * j], imaginary_side[2 * j]};
2852 }
2853
2855 void scale(std::size_t from,
2856 std::size_t to,
2857 double factor)
2858 {
2859 for (std::size_t l {2 * from}; l <= (2 * to) + 1; ++l) {
2860 real_side[l] *= factor;
2861 imaginary_side[l] *= factor;
2862 }
2863 }
2864 };
2865
2868 inline void normalize_vector(std::complex<double>* v,
2869 std::size_t n,
2870 bool signed_real)
2871 {
2872 const double norm {scaled_norm(v, n)};
2873 std::size_t largest {0};
2874 for (std::size_t r {0}; r < n; ++r) {
2875 v[r] /= norm;
2876 largest = std::norm(v[r]) > std::norm(v[largest]) ? r : largest;
2877 }
2878 std::complex<double> turn {std::conj(v[largest]) / std::abs(v[largest])};
2879 if (signed_real && std::signbit(v[largest].real())) {
2880 turn = -turn;
2881 }
2882 for (std::size_t r {0}; r < n; ++r) {
2883 v[r] = times(v[r], turn);
2884 }
2885 v[largest] = std::complex<double> {v[largest].real(), 0.0};
2886 }
2887
2894 template <typename T, typename X>
2896 std::size_t n,
2897 std::size_t k,
2898 std::size_t top,
2899 typename X::scalar lambda,
2900 double floor,
2901 X& x)
2902 {
2903 using S = typename X::scalar;
2904 for (std::size_t j {k}; j > 0;) {
2905 if constexpr (std::is_floating_point_v<T>) {
2906 if (j >= 2 && t[((j - 1) * n) + j - 2] != 0.0) { // a 2 × 2 block, rows j − 2 and j − 1
2907 const S m[4] {S {t[((j - 2) * n) + j - 2]} - lambda, S {t[((j - 2) * n) + j - 1]}, S {t[((j - 1) * n) + j - 2]},
2908 S {t[((j - 1) * n) + j - 1]} - lambda};
2909 S r[2] {-x.dot(t.data() + ((j - 2) * n), j, top), -x.dot(t.data() + ((j - 1) * n), j, top)};
2910 const double factor {solve_block(m, r, floor)};
2911 if (factor != 1.0) {
2912 x.scale(j, top, factor);
2913 }
2914 x.set(j - 2, r[0]);
2915 x.set(j - 1, r[1]);
2916 j -= 2;
2917 continue;
2918 }
2919 }
2920 const auto [value, factor] {divided(-x.dot(t.data() + ((j - 1) * n), j, top), S {t[((j - 1) * n) + j - 1]} - lambda, floor)};
2921 if (factor != 1.0) {
2922 x.scale(j, top, factor);
2923 }
2924 x.set(j - 1, value);
2925 --j;
2926 }
2927 }
2928
2931 [[nodiscard]] inline std::size_t vector_work(std::size_t n) noexcept
2932 {
2933 return std::max<std::size_t>(1, (n * n) / 6);
2934 }
2935
2938 [[nodiscard]] inline std::size_t balanced_index(std::size_t task,
2939 std::size_t n) noexcept
2940 {
2941 return task % 2 == 0 ? task / 2 : n - 1 - (task / 2);
2942 }
2943
2948 [[nodiscard]] inline buffer<std::complex<double>> complex_vectors(const buffer<std::complex<double>>& t,
2949 std::size_t n)
2950 {
2951 using C = std::complex<double>;
2952 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(n) / schur_ulp)};
2953 buffer<C> xt(n * n, C {});
2954 parallel_for(n, vector_work(n), [&](std::size_t task) {
2955 const std::size_t k {balanced_index(task, n)};
2956 interleaved_components x {buffer<double>(2 * (k + 1), 0.0), buffer<double>(2 * (k + 1), 0.0)};
2957 const C lambda {t[(k * n) + k]};
2958 x.set(k, C {1.0});
2959 solve_upward(t, n, k, k, lambda, std::max(schur_ulp * modulus_1(lambda), smallest), x);
2960 for (std::size_t l {0}; l <= k; ++l) {
2961 xt[(k * n) + l] = x.get(l);
2962 }
2963 });
2964 return xt;
2965 }
2966
2973
2980 const buffer<double>& re,
2981 const buffer<double>& im,
2982 std::size_t n)
2983 {
2984 using C = std::complex<double>;
2985 const double smallest {std::numeric_limits<double>::min() * (static_cast<double>(n) / schur_ulp)};
2986 real_eigenvectors out {buffer<double>(n * n, 0.0), buffer<double>(n * n, 0.0)};
2987 parallel_for(n, vector_work(n), [&](std::size_t task) {
2988 const std::size_t k {balanced_index(task, n)};
2989 const double floor {std::max(schur_ulp * (std::abs(re[k]) + std::abs(im[k])), smallest)};
2990 double* row_re {out.re.data() + (k * n)};
2991 double* row_im {out.im.data() + (k * n)};
2992 if (im[k] == 0.0) {
2993 real_components x {buffer<double>(k + 1, 0.0)};
2994 x.set(k, 1.0);
2995 solve_upward(t, n, k, k, re[k], floor, x);
2996 std::copy(x.x.begin(), x.x.begin() + static_cast<std::ptrdiff_t>(k + 1), row_re);
2997 }
2998 else if (im[k] > 0.0) { // the pair's block is rows k, k + 1; the second's row written here
2999 split_components y {buffer<double>(k + 2, 0.0), buffer<double>(k + 2, 0.0)};
3000 const double b {t[(k * n) + k + 1]};
3001 const double c {t[((k + 1) * n) + k]};
3002 y.set(k, std::abs(b) >= std::abs(c) ? C {1.0} : C {-im[k] / c});
3003 y.set(k + 1, std::abs(b) >= std::abs(c) ? C {0.0, im[k] / b} : C {0.0, 1.0});
3004 solve_upward(t, n, k, k + 1, C {re[k], im[k]}, floor, y);
3005 for (std::size_t l {0}; l <= k + 1; ++l) {
3006 row_re[l] = y.re[l];
3007 row_im[l] = y.im[l];
3008 row_re[l + n] = y.re[l];
3009 row_im[l + n] = -y.im[l];
3010 }
3011 }
3012 });
3013 return out;
3014 }
3015
3017 template <typename T>
3019 const buffer<T>& zt,
3020 std::size_t n)
3021 {
3022 buffer<T> vt(n * n, T {});
3023 if (n > 0) {
3024 gemm(n, n, n, xt.data(), n, zt.data(), n, vt.data(), n);
3025 }
3026 return vt;
3027 }
3028
3035 template <typename T>
3037 std::size_t n)
3038 {
3039 buffer<T> s(n * n);
3040 for (std::size_t p {0}; p < n; ++p) {
3041 for (std::size_t q {0}; q < n; ++q) {
3042 s[(p * n) + q] = conj_of(t[((n - 1 - q) * n) + (n - 1 - p)]);
3043 }
3044 }
3045 return s;
3046 }
3047
3050 template <typename T>
3052 std::size_t n)
3053 {
3054 buffer<T> out(n * n);
3055 for (std::size_t j {0}; j < n; ++j) {
3056 for (std::size_t l {0}; l < n; ++l) {
3057 out[(j * n) + l] = w[((n - 1 - j) * n) + (n - 1 - l)];
3058 }
3059 }
3060 return out;
3061 }
3062 } // namespace detail
3063
3065 template <typename T>
3067 {
3070 std::vector<std::size_t> permutation;
3071 };
3072
3081 template <typename T>
3083 bool permute = true,
3084 bool scale = true)
3085 {
3086 const std::size_t n {a.rows()};
3087 if (a.cols() != n) {
3088 throw dimension_error("matrix_balance: the matrix is not square");
3089 }
3090 detail::require_finite(a, "matrix_balance");
3091 buffer<T> b {a.begin(), a.end()};
3092 const detail::balancing balanced {detail::balance(b, n, permute, scale)};
3093 std::vector<std::size_t> permutation(n);
3094 for (std::size_t c {0}; c < n; ++c) { // P = S₁ S₂ … S_k, the swaps in the order applied: the last first on e_c
3095 std::size_t at {c};
3096 for (auto swap {balanced.swaps.rbegin()}; swap != balanced.swaps.rend(); ++swap) {
3097 at = at == swap->first ? swap->second : at == swap->second ? swap->first : at;
3098 }
3099 permutation[c] = at;
3100 }
3101 return {matrix<T> {n, n, std::move(b)}, vector<double> {balanced.scale}, std::move(permutation)};
3102 }
3103
3111 template <double_field T>
3113 {
3114 public:
3115
3126 bool vectors = true,
3127 bool left = false)
3129 vectors,
3130 left)
3131 {}
3132
3144 bool vectors = true,
3145 bool left = false)
3146 : n_(input.rows())
3147 {
3148 if (input.cols() != n_) {
3149 throw dimension_error("eigendecomposition requires a square matrix");
3150 }
3151 detail::require_finite(input, "eigendecomposition");
3152 double largest {0.0}; // the largest part of an entry: within √2 of its modulus, and no hypot per entry
3153 for (std::size_t i {0}; i < n_; ++i) {
3154 for (std::size_t j {0}; j < n_; ++j) {
3155 largest = std::max(largest, detail::largest_part(input(i, j)));
3156 }
3157 }
3158 // A power of two near the largest magnitude: dividing by it is exact, and keeps the iterations' sums of squares
3159 // and the back-substitution's growth in range.
3160 const double scale {largest == 0.0 ? 1.0 : std::ldexp(1.0, std::ilogb(largest))};
3161 buffer<T> a {std::move(input).elements()};
3162 for (T& entry : a) {
3164 }
3166 const bool basis {vectors || left}; // Z, and the whole Schur form, for either side's vectors
3168 const std::size_t steps {detail::schur_steps_per_order * std::max<std::size_t>(10, balanced.high - balanced.low)};
3169 // The whole Schur form past the multishift crossover even for the eigenvalues alone: the sweeps' products then
3170 // have the same shapes as with the vectors, and the eigenvalues the same bits (2–4 % of the iterations from order
3171 // 256 on); below it the single-shift iterations give them either way.
3172 const bool whole {basis || balanced.high - balanced.low >= detail::count_of(detail::multishift_from(T {}))};
3173 const detail::schur_target<T> target {&a, n_, balanced.low, balanced.high, whole, basis ? &z : nullptr}; // z is Zᵀ
3175 buffer<std::complex<double>> vt; // Vᵀ: each vector a row
3176 buffer<std::complex<double>> ut; // Uᵀ: each left vector a row
3177 if constexpr (std::is_floating_point_v<T>) {
3178 buffer<double> re(n_, 0.0);
3179 buffer<double> im(n_, 0.0);
3180 for (std::size_t i {0}; i < n_; ++i) {
3181 re[i] = a[(i * n_) + i]; // the isolated ones; the active block's are overwritten
3182 }
3183 detail::schur_form(target, re, im, steps);
3184 for (std::size_t i {0}; i < n_; ++i) {
3185 values[i] = std::complex<double> {re[i] * scale, im[i] * scale};
3186 real_ = real_ && im[i] == 0.0;
3187 }
3188 const auto rows_of = [&](const detail::real_eigenvectors& x) { // Xᵀ to Vᵀ = Xᵀ Zᵀ, complex
3190 const buffer<double> vim {real_ ? buffer<double>(n_ * n_, 0.0) : detail::back_transformed(x.im, z, n_)};
3192 for (std::size_t e {0}; e < n_ * n_; ++e) {
3193 rows[e] = std::complex<double> {vre[e], vim[e]};
3194 }
3195 return rows;
3196 };
3197 if (vectors) {
3198 vt = rows_of(detail::real_vectors(a, re, im, n_));
3199 }
3200 if (left) { // S's eigenvalues t's reversed and conjugated: a pair's positive part still first
3203 for (std::size_t k {0}; k < n_; ++k) {
3204 reversed_re[k] = re[n_ - 1 - k];
3205 reversed_im[k] = -im[n_ - 1 - k];
3206 }
3209 }
3210 }
3211 else {
3212 for (std::size_t i {0}; i < n_; ++i) {
3213 values[i] = a[(i * n_) + i];
3214 }
3216 for (std::size_t i {0}; i < n_; ++i) {
3217 values[i] *= scale;
3218 }
3219 real_ = false;
3220 if (vectors) {
3222 }
3223 if (left) {
3225 }
3226 }
3228 if (vectors) {
3229 vectors_ = finished(std::move(vt), balanced, false);
3230 }
3231 if (left) {
3232 left_vectors_ = finished(std::move(ut), balanced, true);
3233 }
3234 }
3235
3238 {
3239 return values_;
3240 }
3241
3251
3254 {
3255 return vectors_;
3256 }
3257
3260 {
3261 return std::move(vectors_);
3262 }
3263
3267 {
3268 return real_;
3269 }
3270
3271 private:
3272
3276 void finish(std::complex<double>* row,
3277 const std::complex<double>& value,
3278 double /*real*/) const
3279 {
3280 if (value.imag() == 0.0) {
3281 const double norm {detail::scaled_norm(row, n_)};
3282 for (std::size_t r {0}; r < n_; ++r) {
3283 row[r] = std::complex<double> {row[r].real() / norm, 0.0};
3284 }
3285 }
3286 else if (value.imag() > 0.0) {
3288 }
3289 }
3290
3293 void conjugate_second(std::complex<double>* row,
3294 const std::complex<double>& value,
3295 double /*real*/) const
3296 {
3297 if (value.imag() < 0.0) {
3298 const std::complex<double>* first {row - n_};
3299 for (std::size_t r {0}; r < n_; ++r) {
3300 row[r] = std::conj(first[r]);
3301 }
3302 }
3303 }
3304
3306 void conjugate_second(std::complex<double>* /*row*/,
3307 const std::complex<double>& /*value*/,
3308 const std::complex<double>& /*complex*/) const noexcept
3309 {
3310 }
3311
3314 void finish(std::complex<double>* row,
3315 const std::complex<double>& /*value*/,
3316 const std::complex<double>& /*complex*/) const
3317 {
3319 }
3320
3327 [[nodiscard]] matrix<std::complex<double>> finished(buffer<std::complex<double>> rows,
3329 bool left) const
3330 {
3331 detail::parallel_for(n_, detail::memory_element_weight * 4 * n_, [&](std::size_t c) {
3332 std::complex<double>* row {rows.data() + (c * n_)};
3333 for (std::size_t i {balanced.low}; i < balanced.high; ++i) {
3334 row[i] = left ? row[i] / balanced.scale[i] : row[i] * balanced.scale[i];
3335 }
3336 for (std::size_t s {balanced.swaps.size()}; s-- > 0;) {
3337 std::swap(row[balanced.swaps[s].first], row[balanced.swaps[s].second]);
3338 }
3339 finish(row, values_[c], T {});
3340 });
3341 detail::parallel_for(n_, detail::memory_element_weight * n_, [&](std::size_t c) { conjugate_second(rows.data() + (c * n_), values_[c], T {}); });
3342 return transpose(matrix<std::complex<double>> {n_, n_, std::move(rows)});
3343 }
3344
3345 std::size_t n_;
3349 bool real_ {true};
3350 };
3351
3352 namespace detail {
3353
3356 std::size_t steps)
3357 {
3358 buffer<double> re(t.n, 0.0);
3359 buffer<double> im(t.n, 0.0);
3360 schur_form(t, re, im, steps);
3361 }
3362
3364 inline void whole_schur_form(const schur_target<std::complex<double>>& t,
3365 std::size_t steps)
3366 {
3367 buffer<std::complex<double>> values(t.n);
3368 schur_form(t, values, steps);
3369 }
3370 } // namespace detail
3371
3372 namespace detail {
3373
3376 [[nodiscard]] inline std::vector<std::complex<double>> schur_values(const double* t,
3377 std::size_t n)
3378 {
3379 std::vector<std::complex<double>> values(n);
3380 for (std::size_t k {0}; k < n; ++k) {
3381 const double a {t[(k * n) + k]};
3382 if (k + 1 < n && t[((k + 1) * n) + k] != 0.0) {
3383 const double im {std::sqrt(std::abs(t[(k * n) + k + 1])) * std::sqrt(std::abs(t[((k + 1) * n) + k]))};
3384 values[k] = std::complex<double> {a, im};
3385 values[k + 1] = std::complex<double> {a, -im};
3386 ++k;
3387 }
3388 else {
3389 values[k] = std::complex<double> {a, 0.0};
3390 }
3391 }
3392 return values;
3393 }
3394
3396 [[nodiscard]] inline std::vector<std::complex<double>> schur_values(const std::complex<double>* t,
3397 std::size_t n)
3398 {
3399 std::vector<std::complex<double>> values(n);
3400 for (std::size_t k {0}; k < n; ++k) {
3401 values[k] = t[(k * n) + k];
3402 }
3403 return values;
3404 }
3405
3407 using eigenvalue_selection = std::function<bool (const std::complex<double>&)>;
3408
3410 [[nodiscard]] inline lapack_index block_order(one_based<std::complex<double>> /*t*/,
3411 lapack_index /*n*/,
3412 lapack_index /*j*/)
3413 {
3414 return 1;
3415 }
3416
3418 [[nodiscard]] inline std::size_t selected_leading(const std::vector<std::complex<double>>& /*after*/,
3419 const eigenvalue_selection& /*select*/,
3420 std::size_t moved,
3421 std::type_identity<std::complex<double>> /*form*/)
3422 {
3423 return moved;
3424 }
3425
3431 [[nodiscard]] inline std::size_t selected_leading(const std::vector<std::complex<double>>& after,
3433 std::size_t /*moved*/,
3434 std::type_identity<double> /*form*/)
3435 {
3436 std::size_t count {0};
3437 bool last {true};
3438 for (std::size_t k {0}; k < after.size(); ++k) {
3439 bool current {select(after[k])};
3440 const bool pair {after[k].imag() != 0.0};
3441 if (pair) {
3442 current = current || select(after[k + 1]);
3443 }
3444 if (current && !last) {
3445 throw convergence_error("Schur form: leading eigenvalues do not satisfy the selection");
3446 }
3447 count += current ? (pair ? 2 : 1) : 0;
3448 last = current;
3449 k += pair ? 1 : 0;
3450 }
3451 return count;
3452 }
3453
3461 template <typename T>
3462 std::size_t move_leading(buffer<T>& t,
3463 buffer<T>& qt,
3464 std::size_t n,
3465 const std::vector<bool>& chosen)
3466 {
3467 const one_based<T> at {t.data(), static_cast<lapack_index>(n)};
3468 const one_based<T> rows {qt.data(), static_cast<lapack_index>(n)};
3469 const auto order {static_cast<lapack_index>(n)};
3470 lapack_index moved {0};
3471 for (lapack_index k {1}; k <= order; ++k) {
3472 bool take {chosen[count_of(k - 1)]};
3473 const lapack_index size {block_order(at, order, k)};
3474 if (size == 2) {
3475 take = take || chosen[count_of(k)];
3476 }
3477 if (take) {
3478 lapack_index place {moved + 1};
3479 if (k != place && !reorder(at, rows, order, k, place)) {
3480 throw convergence_error("Schur form: eigenvalues could not be separated for reordering");
3481 }
3482 moved += size;
3483 }
3484 k += size - 1;
3485 }
3486 return count_of(moved);
3487 }
3488 } // namespace detail
3489
3499 template <double_field T>
3501 {
3502 public:
3503
3513
3516 {
3517 const std::size_t n {input.rows()};
3518 if (input.cols() != n) {
3519 throw dimension_error("Schur decomposition requires a square matrix");
3520 }
3521 detail::require_finite(input, "Schur decomposition");
3522 double largest {0.0};
3523 for (std::size_t i {0}; i < n; ++i) {
3524 for (std::size_t j {0}; j < n; ++j) {
3525 largest = std::max(largest, detail::largest_part(input(i, j)));
3526 }
3527 }
3528 // A power of two: the division exact, the iterations' sums of squares in range.
3529 const double scale {largest == 0.0 ? 1.0 : std::ldexp(1.0, std::ilogb(largest))};
3530 buffer<T> a {std::move(input).elements()};
3531 for (T& entry : a) {
3533 }
3534 const detail::balancing isolated {detail::isolate(a, n)}; // A' = Pᵀ A P
3535 buffer<T> zt {detail::hessenberg(a, n, isolated.low, isolated.high, true)};
3536 const std::size_t steps {detail::schur_steps_per_order * std::max<std::size_t>(10, isolated.high - isolated.low)};
3537 const detail::schur_target<T> target {&a, n, isolated.low, isolated.high, true, &zt};
3539 for (T& entry : a) { // zero below the subdiagonal (the diagonal, complex) as the reduction and the sweeps leave it
3541 }
3542 for (std::size_t s {isolated.swaps.size()}; s-- > 0;) { // Z = P Z': the exchanges undone, the last first, on
3543 const auto [i, j] {isolated.swaps[s]}; // the columns of Zᵀ
3544 for (std::size_t c {0}; c < n; ++c) {
3545 std::swap(zt[(c * n) + i], zt[(c * n) + j]);
3546 }
3547 }
3548 t_ = matrix<T> {n, n, std::move(a)};
3549 z_ = transpose(matrix<T> {n, n, std::move(zt)});
3550 }
3551
3559 template <typename Select>
3560 requires std::predicate<Select&, const std::complex<double>&>
3565
3567 [[nodiscard]] std::vector<std::complex<double>> values() const
3568 {
3569 return detail::schur_values(std::to_address(t_.begin()), t_.rows());
3570 }
3571
3580 std::size_t reorder(const std::vector<bool>& chosen)
3581 {
3582 const std::size_t n {t_.rows()};
3583 if (chosen.size() != n) {
3584 throw dimension_error("Schur reordering requires one choice per eigenvalue");
3585 }
3586 buffer<T> t {std::move(t_).elements()};
3587 buffer<T> zt {transpose(z_).elements()};
3588 std::size_t moved {0};
3589 try {
3590 moved = detail::move_leading(t, zt, n, chosen);
3591 }
3592 catch (...) {
3593 t_ = matrix<T> {n, n, std::move(t)};
3594 z_ = transpose(matrix<T> {n, n, std::move(zt)});
3595 throw;
3596 }
3597 t_ = matrix<T> {n, n, std::move(t)};
3598 z_ = transpose(matrix<T> {n, n, std::move(zt)});
3599 return moved;
3600 }
3601
3609 {
3610 const std::vector<std::complex<double>> before {values()};
3611 std::vector<bool> chosen(before.size());
3612 for (std::size_t k {0}; k < before.size(); ++k) {
3613 chosen[k] = select(before[k]);
3614 }
3615 const std::size_t moved {reorder(chosen)};
3616 return detail::selected_leading(values(), select, moved, std::type_identity<T> {});
3617 }
3618
3621 {
3622 return leading_;
3623 }
3624
3627 {
3628 return t_;
3629 }
3630
3633 {
3634 return std::move(t_);
3635 }
3636
3639 {
3640 return z_;
3641 }
3642
3645 {
3646 return std::move(z_);
3647 }
3648
3649 private:
3650
3653 {
3656 std::size_t leading;
3657 };
3658
3662 {
3663 const std::size_t leading {s.sort(select)};
3664 return {std::move(s.t_), std::move(s.z_), leading};
3665 }
3666
3669 : t_(std::move(form.t)),
3670 z_(std::move(form.z)),
3671 leading_(form.leading)
3672 {}
3673
3676 std::size_t leading_ {0};
3677 };
3678
3685 template <field T>
3687 {
3688 return eigen_decomposition<T> {a, false}.values();
3689 }
3690
3691 namespace detail {
3694 template <typename T>
3696 {
3697 public:
3698
3700 explicit band_work(const matrix<T>& lower)
3701 : n_(lower.cols()), width_(lower.rows() - 1), data_((width_ + 2) * n_, T {})
3702 {
3703 for (std::size_t d {0}; d <= width_; ++d) {
3704 for (std::size_t j {0}; j + d < n_; ++j) {
3705 data_[(d * n_) + j] = lower(d, j);
3706 }
3707 }
3708 }
3709
3712 [[nodiscard]] T get(std::size_t i,
3713 std::size_t k) const
3714 {
3715 return data_[((i - k) * n_) + k];
3716 }
3717
3719 void set(std::size_t i,
3720 std::size_t k,
3721 const T& value)
3722 {
3723 data_[((i - k) * n_) + k] = value;
3724 }
3725
3726 [[nodiscard]] std::size_t order() const noexcept
3727 {
3728 return n_;
3729 }
3730
3731 [[nodiscard]] std::size_t width() const noexcept
3732 {
3733 return width_;
3734 }
3735
3736 private:
3737
3738 std::size_t n_;
3739 std::size_t width_;
3741 };
3742
3746 template <typename T>
3748 std::size_t p,
3749 double c,
3750 const T& s,
3751 buffer<T>& turned)
3752 {
3753 const std::size_t n {a.order()};
3754 const std::size_t q {p + 1};
3755 for (std::size_t k {p >= a.width() ? p - a.width() : 0}; k < p; ++k) {
3756 const T x {a.get(p, k)};
3757 const T y {a.get(q, k)};
3758 a.set(p, k, (c * x) + times(s, y));
3759 a.set(q, k, (c * y) - times(conj_of(s), x));
3760 }
3761 for (std::size_t k {q + 1}; k <= std::min(n - 1, q + a.width()); ++k) {
3762 const T x {a.get(k, p)};
3763 const T y {a.get(k, q)};
3764 a.set(k, p, (c * x) + times(conj_of(s), y));
3765 a.set(k, q, (c * y) - times(s, x));
3766 }
3767 const double app {real_part(a.get(p, p))};
3768 const double aqq {real_part(a.get(q, q))};
3769 const T b {a.get(q, p)};
3770 const double cross {2.0 * c * real_part(times(s, b))};
3771 const double ss {real_part(times(s, conj_of(s)))};
3772 a.set(p, p, T {(c * c * app) + cross + (ss * aqq)});
3773 a.set(q, q, T {(ss * app) - cross + (c * c * aqq)});
3774 a.set(q, p, (c * c * b) - times(times(conj_of(s), conj_of(s)), conj_of(b)) + (c * times(conj_of(s), T {aqq - app})));
3775 if (!turned.empty()) { // Mᴴ ← Mᴴ Gᴴ: its columns p and q (stored as rows) by the conjugate rotation
3776 rotate_pair(turned.data() + (p * n), turned.data() + (q * n), n, 1, c, conj_of(s));
3777 }
3778 }
3779 } // namespace detail
3780
3783 template <typename T>
3790
3800 template <typename T>
3802 bool basis)
3803 {
3804 if (lower.rows() == 0) {
3805 throw dimension_error("band_tridiagonal: a band of at least one diagonal");
3806 }
3807 const std::size_t n {lower.cols()};
3808 const std::size_t u {std::min(lower.rows() - 1, n == 0 ? std::size_t {0} : n - 1)};
3809 matrix<T> trimmed {u + 1, n, buffer<T>(lower.begin(), lower.begin() + static_cast<std::ptrdiff_t>((u + 1) * n))};
3810 detail::band_work<T> a {trimmed};
3811 buffer<T> turned(basis ? n * n : 0, T {});
3812 for (std::size_t i {0}; basis && i < n; ++i) {
3813 turned[(i * n) + i] = T {1};
3814 }
3815 const auto annihilate = [&](std::size_t row, std::size_t column) { // (row, column) by rows row − 1 and row
3816 const detail::plane_rotation<T> g {detail::givens(a.get(row - 1, column), a.get(row, column))};
3817 detail::rotate_band(a, row - 1, g.c, g.s, turned);
3818 a.set(row - 1, column, g.r);
3819 a.set(row, column, T {});
3820 };
3821 for (std::size_t j {0}; u > 1 && j + 2 < n; ++j) {
3822 for (std::size_t k {std::min(u, n - 1 - j)}; k >= 2; --k) {
3823 annihilate(j + k, j);
3824 for (std::size_t row {j + k + u}, column {j + k - 1}; row < n; column = row - 1, row += u) { // the bulge
3825 annihilate(row, column);
3826 }
3827 }
3828 }
3830 buffer<double> off_diagonal(n == 0 ? 0 : n - 1);
3831 T phase {1};
3832 for (std::size_t j {0}; j < n; ++j) {
3833 diagonal[j] = detail::real_part(a.get(j, j));
3834 if (basis) { // W = Mᴴ D: column j by the phase that makes T's off-diagonal real
3835 for (std::size_t i {0}; i < n; ++i) {
3836 turned[(j * n) + i] = detail::times(turned[(j * n) + i], phase);
3837 }
3838 }
3839 if (j + 1 < n) {
3840 const T off {a.get(j + 1, j)};
3841 const double size {std::abs(off)};
3842 off_diagonal[j] = size;
3843 if (size != 0.0) {
3844 phase = detail::times(phase, off / size);
3845 }
3846 }
3847 }
3848 band_tridiagonal_form<T> form {vector<double>(std::move(diagonal)), vector<double>(std::move(off_diagonal)), matrix<T> {}};
3849 if (basis) { // turned holds W's columns as rows
3850 buffer<T> w(n * n);
3851 for (std::size_t i {0}; i < n; ++i) {
3852 for (std::size_t k {0}; k < n; ++k) {
3853 w[(i * n) + k] = turned[(k * n) + i];
3854 }
3855 }
3856 form.w = matrix<T> {n, n, std::move(w)};
3857 }
3858 return form;
3859 }
3860} // namespace numerical
3861
3862#endif // NUMERICAL_EIGEN_HPP
Thrown when an iterative algorithm has not converged within its bound of sweeps.
The lower band of a symmetric or Hermitian matrix of order n and half-bandwidth width,...
Definition eigen.hpp:3696
std::size_t width() const noexcept
< The half-bandwidth.
Definition eigen.hpp:3731
std::size_t order() const noexcept
< The order n.
Definition eigen.hpp:3726
T get(std::size_t i, std::size_t k) const
Entry (i, k) of the lower triangle, within the bulge's diagonal (0 ≤ i − k ≤ width + 1: all a reducti...
Definition eigen.hpp:3712
void set(std::size_t i, std::size_t k, const T &value)
Sets entry (i, k) of the lower triangle (i ≥ k, within the bulge's diagonal).
Definition eigen.hpp:3719
band_work(const matrix< T > &lower)
The band of lower, its (d, j) entry the matrix's (j + d, j), the bulge's diagonal zero.
Definition eigen.hpp:3700
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
The eigenvalues, and optionally the right eigenvectors, of a general square matrix,...
Definition eigen.hpp:3113
void finish(std::complex< double > *row, const std::complex< double > &value, double) const
Normalises the eigenvector row (a row of Vᵀ) of a real matrix's eigenvalue value, as dgeev: a real on...
Definition eigen.hpp:3276
matrix< std::complex< double > > left_vectors_
The left eigenvectors as columns.
Definition eigen.hpp:3348
matrix< std::complex< double > > vectors_
The eigenvectors as columns.
Definition eigen.hpp:3347
bool real_
Whether all eigenvalues are real.
Definition eigen.hpp:3349
matrix< std::complex< double > > finished(buffer< std::complex< double > > rows, const detail::balancing &balanced, bool left) const
The vectors of the rows rows (each a vector of the balanced matrix) in the input's basis,...
Definition eigen.hpp:3327
eigen_decomposition(const matrix< T > &input, bool vectors=true, bool left=false)
Decomposes input.
Definition eigen.hpp:3125
const vector< std::complex< double > > & values() const noexcept
The eigenvalues, in the order of the Schur form.
Definition eigen.hpp:3237
const matrix< std::complex< double > > & left_vectors() const noexcept
The left eigenvectors as columns, ordered to match values (empty where they were not computed): colum...
Definition eigen.hpp:3247
void conjugate_second(std::complex< double > *, const std::complex< double > &, const std::complex< double > &) const noexcept
No pairs in a complex matrix's eigenvectors.
Definition eigen.hpp:3306
const matrix< std::complex< double > > & vectors() const &noexcept
The eigenvectors as columns, ordered to match values (empty where they were not computed).
Definition eigen.hpp:3253
void finish(std::complex< double > *row, const std::complex< double > &, const std::complex< double > &) const
Normalises the eigenvector row of a complex matrix, as zgeev: to unit norm, its largest component rea...
Definition eigen.hpp:3314
void conjugate_second(std::complex< double > *row, const std::complex< double > &value, double) const
A real matrix's pair's second eigenvector row (value's imaginary part negative): the first's,...
Definition eigen.hpp:3293
bool real() const noexcept
Whether every eigenvalue is real (a real matrix's whose Schur form has no 2 × 2 block): its vectors a...
Definition eigen.hpp:3266
std::size_t n_
The matrix order.
Definition eigen.hpp:3345
vector< std::complex< double > > values_
The eigenvalues.
Definition eigen.hpp:3346
matrix< std::complex< double > > vectors() &&
The eigenvectors, moved out of an expiring decomposition.
Definition eigen.hpp:3259
eigen_decomposition(matrix< T > &&input, bool vectors=true, bool left=false)
Decomposes input in its own storage, an expiring matrix's elements taken over: its scaled copy is mad...
Definition eigen.hpp:3143
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
The Schur decomposition A = Z T Zᴴ of a square matrix, as scipy.linalg.schur (LAPACK's dgees/zgees): ...
Definition eigen.hpp:3501
std::vector< std::complex< double > > values() const
The eigenvalues, in T's order: its diagonal, a real 2 × 2 block a conjugate pair, the positive first.
Definition eigen.hpp:3567
matrix< T > t_
The Schur form.
Definition eigen.hpp:3674
matrix< T > z() &&
Z, moved out of an expiring decomposition.
Definition eigen.hpp:3644
matrix< T > z_
The Schur vectors.
Definition eigen.hpp:3675
matrix< T > t() &&
T, moved out of an expiring decomposition.
Definition eigen.hpp:3632
schur_decomposition(const matrix< T > &input)
Decomposes input.
Definition eigen.hpp:3510
schur_decomposition(const matrix< T > &input, Select select)
Decomposes input, then moves the eigenvalues for which select holds to the leading block of T (sort),...
Definition eigen.hpp:3561
schur_decomposition(matrix< T > &&input)
Decomposes input in its own storage, an expiring matrix's elements taken over.
Definition eigen.hpp:3515
const matrix< T > & t() const &noexcept
T, upper quasi-triangular (real) or triangular (complex).
Definition eigen.hpp:3626
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen (one per eigenvalue, in values's order) are set to the ...
Definition eigen.hpp:3580
std::size_t leading() const noexcept
The eigenvalues the selecting constructor moved to the leading block (its sdim); 0 otherwise.
Definition eigen.hpp:3620
const matrix< T > & z() const &noexcept
Z, the Schur vectors as columns.
Definition eigen.hpp:3638
std::size_t sort(const detail::eigenvalue_selection &select)
The eigenvalues for which select holds moved to the leading block (reorder), as dgees/zgees sort them...
Definition eigen.hpp:3608
schur_decomposition(sorted_form form)
The decomposition form holds.
Definition eigen.hpp:3668
static sorted_form sorted(schur_decomposition s, const detail::eigenvalue_selection &select)
s sorted by select (sort), taken apart for the constructor that holds the count.
Definition eigen.hpp:3660
A dense vector of T with value semantics.
Definition vector.hpp:171
The scalar types NumericAL's factorisations and solvers take: a field of floating-point numbers,...
Matrix factorisations and the algorithms built on them.
buffer< T > hessenberg_unblocked(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
Reduces the active block low … high − 1 of the balanced row-major n × n a to upper Hessenberg form by...
Definition eigen.hpp:234
T reflector_tau(T &alpha, T *x, std::size_t count)
The Householder reflection H = I − τ v vᴴ, v = (1, v₁…), with Hᴴ (α, x) = (β, 0) and β real,...
Definition eigen.hpp:350
void reflect_columns_3(const std::array< double, 3 > &u, double tau, double *t, std::size_t ld, std::size_t count)
The same from the right, to the count × 3 columns at t.
Definition eigen.hpp:1401
buffer< T > reversed_rows(const buffer< T > &w, std::size_t n)
Row j of the rows w (n × n) its row n − 1 − j, its entries in reverse order: J applied to each of rev...
Definition eigen.hpp:3051
constexpr double back_substitution_limit
The modulus an eigenvector's components are kept under during the back-substitution: the sums stay fi...
Definition eigen.hpp:53
buffer< T > reversed_adjoint(const buffer< T > &t, std::size_t n)
S = J Tᴴ J of the upper (quasi-)triangular t (row-major n × n, J the reversal): upper (quasi-)triangu...
Definition eigen.hpp:3036
void reflect_three_rows(T *r1, T *r2, T *r3, std::size_t from, std::size_t to, const T &tau, const T &v2, const T &v3, bool adjoint)
A reflection I − τ v vᴴ, v = (1, v₂, v₃), on the entries from … to − 1 of three rows: its adjoint fro...
Definition eigen.hpp:812
void bulge_column(one_based< double > h, lapack_index count, const std::complex< double > &s1, const std::complex< double > &s2, double *v)
A multiple of the first column of (H − s₁ I)(H − s₂ I) for the leading 2 × 2 or 3 × 3 (count) of the ...
Definition eigen.hpp:1756
void multishift_schur(const schur_target< T > &target, std::complex< double > *w, bool recursive, lapack_index steps=0)
The Schur form of target's active block by the multishift QR algorithm with aggressive early deflatio...
Definition eigen.hpp:2544
void normalize_vector(std::complex< double > *v, std::size_t n, bool signed_real)
Scales v to unit Euclidean norm and turns it so that its first component of largest modulus is real: ...
Definition eigen.hpp:2868
void reflect_two_rows(T *r1, T *r2, std::size_t from, std::size_t to, const T &tau, const T &v2, bool adjoint)
reflect_three_rows for a reflection of two entries, v = (1, v₂), on two rows: its own loop,...
Definition eigen.hpp:838
buffer< T > hessenberg_blocked(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
hessenberg_unblocked by panels of hessenberg_block columns, as LAPACK's dgehrd and dlahr2: a panel's ...
Definition eigen.hpp:451
buffer< T > hessenberg(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
hessenberg_blocked from an active order of hessenberg_crossover, else hessenberg_unblocked.
Definition eigen.hpp:630
void exchange(buffer< T > &a, std::size_t n, std::size_t i, std::size_t j)
Exchanges rows i and j, then columns i and j, of the row-major n × n a: a similarity.
Definition eigen.hpp:109
std::size_t vector_work(std::size_t n) noexcept
A triangular solve's work for parallel_for over the n eigenvectors: k²/2 products for vector k,...
Definition eigen.hpp:2931
void reflect_three_columns(T *first, std::size_t rows, std::size_t ld, const T &tau, const T &v2, const T &v3)
A reflection I − τ v vᴴ, v = (1, v₂, v₃), from the right on rows rows (ld apart) of the three columns...
Definition eigen.hpp:862
constexpr std::size_t hessenberg_crossover
The active order from which hessenberg reduces by panels.
Definition eigen.hpp:328
std::complex< R > scaled(R c, const std::complex< R > &v) noexcept
c · v of a real c and a complex v: each part's product, rounded.
Definition fft.hpp:1290
carried_t< T > real_part(const T &x)
The real part of a real (or general) scalar, in carried_t.
std::function< bool(const std::complex< double > &)> eigenvalue_selection
A choice among eigenvalues, as scipy.linalg.schur's sort makes it: true where one is to lead.
Definition eigen.hpp:3407
std::size_t count_of(lapack_index count)
A count as an unsigned size (never negative where it is taken).
Definition eigen.hpp:1272
void whole_schur_form(const schur_target< double > &t, std::size_t steps)
The real Schur form of the whole of t (its eigenvalues not kept), steps its iterations' bound.
Definition eigen.hpp:3355
void reflect_two_columns(T *first, std::size_t rows, std::size_t ld, const T &tau, const T &v2)
The same for a reflection of two entries, v = (1, v₂), on two columns.
Definition eigen.hpp:882
void vigilant_deflation(one_based< T > h, lapack_index k, lapack_index ktop, lapack_index kbot, double smallest)
H(k + 1, k) set to zero where the deflation criterion of Ahues and Tisseur holds, as the sweep of dla...
Definition eigen.hpp:1866
void chase_bulges(const schur_target< T > &target, lapack_index ktop, lapack_index kbot, std::complex< double > *s, lapack_index count, bool accumulate)
One small-bulge multishift QR sweep over the active block ktop … kbot of target's Hessenberg matrix w...
Definition eigen.hpp:1924
double solve_block(const S(&m)[4], S(&r)[2], double floor)
Solves [a b; c d] x = r in place of r by Gaussian elimination with complete pivoting,...
Definition eigen.hpp:2689
constexpr std::size_t hessenberg_block
The columns of a panel of hessenberg_blocked.
Definition eigen.hpp:325
constexpr double schur_ulp
The relative spacing LAPACK's ‘dlamch('P’)` names: the roundoff a QR sweep judges a subdiagonal by.
Definition eigen.hpp:41
void pair_for_sweep(std::complex< double > *w, lapack_index ks, lapack_index kbot, double)
A real matrix's shifts brought into pairs, each a conjugate pair or two reals, as dlaqr0 does before ...
Definition eigen.hpp:2489
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
void exchange_diagonal(one_based< T > t, one_based< T > qt, lapack_index n, lapack_index k)
Exchanges the diagonal entries k and k + 1 of the upper triangular (or quasi-triangular,...
Definition eigen.hpp:1368
void reflect_from_left(T *x, std::size_t stride, const T &tau, const T &v2, const T &v3)
The adjoint I − τ̄ v vᴴ of a reflection of three entries from the left on one column (x three entries...
Definition eigen.hpp:1903
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::size_t selected_leading(const std::vector< std::complex< double > > &, const eigenvalue_selection &, std::size_t moved, std::type_identity< std::complex< double > >)
The count of a complex Schur form's sort, as zgees takes trsen's: the eigenvalues it moved.
Definition eigen.hpp:3418
real_operand operand_of(const double *v, std::size_t stride, std::size_t count)
The count entries stride apart at v as a real_operand.
Definition eigen.hpp:407
bool two_real_shifts(const std::complex< double > *w, lapack_index ks, lapack_index kbot, double)
Whether a real matrix's sweep is down to two shifts, both real: then the one nearer the corner serves...
Definition eigen.hpp:2513
void small_sylvester(const one_based< double > &tl, const one_based< double > &tr, const one_based< double > &b, lapack_index n1, lapack_index n2, double(&x)[4])
The solution X (n1 × n2, row-major in x) of TL X − X TR = B, n1 and n2 at most 2, by Gaussian elimina...
Definition eigen.hpp:1421
auto times(const A &a, const B &b)
a · b.
Definition eigen.hpp:70
lapack_index block_order(one_based< double > t, lapack_index n, lapack_index j)
The order of the diagonal block of the quasi-triangular t that starts at j: 2 where a subdiagonal ent...
Definition eigen.hpp:1632
std::size_t balanced_index(std::size_t task, std::size_t n) noexcept
The eigenvector task of n solves, the short ones and the long ones in turn (0, n − 1,...
Definition eigen.hpp:2938
bool exchange_blocks(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index j1, lapack_index n1, lapack_index n2)
Exchanges the adjacent diagonal blocks of the real quasi-triangular t at j1, of orders n1 then n2,...
Definition eigen.hpp:1512
std::ptrdiff_t lapack_index
A signed index from 1, as LAPACK's: the multishift sweep starts its bulges in phantom columns above t...
Definition eigen.hpp:1248
buffer< T > back_transformed(const buffer< T > &xt, const buffer< T > &zt, std::size_t n)
Vᵀ = Xᵀ Zᵀ, row-major n × n, through the matrix product kernel.
Definition eigen.hpp:3018
bool reorder(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index ifst, lapack_index &ilst)
Moves the diagonal block of the real quasi-triangular t at ifst to ilst by exchanges of adjacent bloc...
Definition eigen.hpp:1644
constexpr lapack_index multishift_crossover
LAPACK's nmin: the active order below which dlaqr0's iterations skip a sweep after enough deflation.
Definition eigen.hpp:1279
real_eigenvectors real_vectors(const buffer< double > &t, const buffer< double > &re, const buffer< double > &im, std::size_t n)
The eigenvectors of the real quasi-triangular t (row-major n × n, its 2 × 2 blocks standard) as the r...
Definition eigen.hpp:2979
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
bool already_reduced(double, double rest)
Whether (α, x), of tail norm rest, is already (β, 0) with β real: for a real one, its tail zero.
Definition eigen.hpp:331
deflation_count early_deflation(const schur_target< T > &target, lapack_index ktop, lapack_index kbot, lapack_index nw, std::complex< double > *w, bool recursive)
Aggressive early deflation, as LAPACK's dlaqr3 and zlaqr3: the trailing nw × nw window of the active ...
Definition eigen.hpp:2279
standard_block standardize_block(double &a, double &b, double &c, double &d)
The Schur factorisation of the real 2 × 2 block [a b; c d], as LAPACK's dlanv2: [a b; c d] ← [cs −sn;...
Definition eigen.hpp:710
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 as_scalar(const std::complex< double > &s, double)
The shift s as the matrix's scalar: a real matrix's are real where they are used one by one.
Definition eigen.hpp:1850
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
constexpr lapack_index exceptional_after
The iterations without deflation after which the shifts are exceptional (kexsh).
Definition eigen.hpp:1300
carried_t< T > rescale_tiny(buffer< T > &x)
Scales x by rescue_factor of its largest magnitude, exactly, so that a Householder vector built from ...
void plain_schur(const schur_target< double > &t, std::complex< double > *w)
The Schur form of t's active block by real_schur, its eigenvalues to w (one per row of t).
Definition eigen.hpp:2128
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
void gemm(std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
C += A·B, every element of C summed in ascending order of the depth.
Definition gemm.hpp:4583
void complex_schur(const schur_target< std::complex< double > > &t, buffer< std::complex< double > > &values, std::size_t steps)
The complex Schur form of the upper Hessenberg t's active block, as LAPACK's zlahqr: the shifted QR a...
Definition eigen.hpp:1126
lapack_index recommended_window(lapack_index nh, lapack_index ns)
The deflation window LAPACK's iparmq recommends for an active block of order nh and ns shifts.
Definition eigen.hpp:2446
std::size_t move_leading(buffer< T > &t, buffer< T > &qt, std::size_t n, const std::vector< bool > &chosen)
Moves the eigenvalues of the Schur form t whose entries of chosen are set to its leading block,...
Definition eigen.hpp:3462
double modulus_1(double x)
|x| of a real x: what modulus_1 of a complex one stands for.
Definition eigen.hpp:56
double dot_product(const double *x, const double *y, std::size_t count)
Σ x[i] · y[i] for double, as subtract_product chooses its units (in another order of summation there,...
Definition gemm.hpp:715
double largest_part(double x)
|x| of a real x.
Definition eigen.hpp:86
lapack_index undeflated(one_based< double > t, one_based< double > vt, lapack_index jw, double s, double smallest, std::complex< double > *w)
The eigenvalues of the real Schur form t (jw × jw) of a deflation window that do not deflate,...
Definition eigen.hpp:2154
T phase_of(const T &x)
The unit-modulus factor of x: x / |x| (its sign, for a real scalar), and 1 at 0. A subnormal x is sca...
void pair_shifts(std::complex< double > *s, lapack_index count, double)
Arranges a real matrix's shifts so that each pair is a conjugate pair or two reals,...
Definition eigen.hpp:1828
void real_schur(const schur_target< double > &t, buffer< double > &re, buffer< double > &im, std::size_t steps)
The real Schur form of the upper Hessenberg t's active block, as LAPACK's dlahqr: Francis's implicit ...
Definition eigen.hpp:920
void rotate_band(band_work< T > &a, std::size_t p, double c, const T &s, buffer< T > &turned)
A ← G A Gᴴ of the band a, G the rotation [c s; −s̄ c] on rows and columns p and p + 1: the two rows w...
Definition eigen.hpp:3747
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
balancing balance(buffer< T > &a, std::size_t n, bool permute=true, bool scale=true)
Balances the row-major n × n a in place, as LAPACK's ‘dgebal('B’): rows with no off-diagonal entry in...
Definition eigen.hpp:130
std::vector< std::complex< double > > schur_values(const double *t, std::size_t n)
The eigenvalues of the real quasi-triangular t (n × n, row-major), in its order: a 2 × 2 block of sta...
Definition eigen.hpp:3376
scaled_quotient< S > divided(S r, P pivot, double floor)
r / pivot, a pivot below floor taken as floor, r scaled first where the quotient would pass back_subs...
Definition eigen.hpp:2733
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
carried_t< T > scaled_norm(const T *x, std::size_t count)
The Euclidean norm of the count elements at x, by norm_at_scale for this type.
void solve_upward(const buffer< T > &t, std::size_t n, std::size_t k, std::size_t top, typename X::scalar lambda, double floor, X &x)
Solves (T − λ I) x = 0 upward from the component k, rows k − 1 … 0 of the row-major quasi-triangular ...
Definition eigen.hpp:2895
void rotate(T *x, T *y, std::size_t count, std::size_t stride, double cs, double sn)
(x, y) ← (cs x + sn y, cs y − sn x) over count pairs stride apart: a plane rotation.
Definition eigen.hpp:791
std::complex< double > complex_reflector(std::complex< double >(&v)[2])
The Householder reflection I − τ v vᴴ, v = (1, x), whose adjoint takes (α, x) to (β,...
Definition eigen.hpp:678
constexpr double balance_limit
The largest power of two a balancing scales a row or a column by, either way: the matrix enters at a ...
Definition eigen.hpp:49
buffer< std::complex< double > > complex_vectors(const buffer< std::complex< double > > &t, std::size_t n)
The eigenvectors of the complex upper triangular t (row-major n × n) as the rows of Xᵀ: row k is x wi...
Definition eigen.hpp:2948
void exceptional_shifts(one_based< double > h, std::complex< double > *w, lapack_index ks, lapack_index kbot, lapack_index ktop)
Exceptional shifts for a real matrix, as dlaqr0's after kexsh iterations without deflation: from the ...
Definition eigen.hpp:2454
constexpr lapack_index nibble
The share of the window, in percent, whose deflation makes the sweep unnecessary (nibble).
Definition eigen.hpp:1303
void schur_form(const schur_target< double > &t, buffer< double > &re, buffer< double > &im, std::size_t steps)
The real Schur form of t's active block: real_schur below multishift_from, else multishift_schur,...
Definition eigen.hpp:2654
constexpr std::size_t schur_steps_per_order
The iterations one eigenvalue (or pair) may take per unit of the active order, as dlahqr's 30.
Definition eigen.hpp:44
balancing isolate(buffer< T > &a, std::size_t n)
Isolates eigenvalues of the row-major n × n a in place by permutations alone, as LAPACK's ‘dgebal('P’...
Definition eigen.hpp:215
constexpr lapack_index multishift_from(double)
The order from which a real Schur form is taken by multishift_schur, below which real_schur is faster...
Definition eigen.hpp:1284
lapack_index recommended_shifts(lapack_index nh)
The shifts LAPACK's iparmq recommends for an active block of order nh.
Definition eigen.hpp:2421
void reflect_rows_3(const std::array< double, 3 > &u, double tau, double *t, std::size_t ld, std::size_t count)
H = I − τ u uᵀ of three entries applied from the left to the 3 × count rows at t (row stride ld).
Definition eigen.hpp:1386
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
Definition parallel.hpp:760
constexpr lapack_index window_growth
The iterations without deflation after which the window grows (kexnw).
Definition eigen.hpp:1297
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 ...
vector< std::complex< double > > eigenvalues(const matrix< T > &a)
The eigenvalues alone of the square a, as numpy.linalg.eigvals.
Definition eigen.hpp:3686
tensor< T > take(const tensor< T > &t, const tensor< std::int64_t > &indices, std::size_t axis, take_mode mode)
The elements of t at indices along axis, as numpy.take: the result's shape t's with the axis replaced...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
balanced_matrix< T > matrix_balance(const matrix< T > &a, bool permute=true, bool scale=true)
The square a balanced, as scipy.linalg.matrix_balance(a, permute, scale, separate=True) (LAPACK's dge...
Definition eigen.hpp:3082
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 > inverse(matrix< T > a)
The inverse of a square matrix.
band_tridiagonal_form< T > band_tridiagonal(const matrix< T > &lower, bool basis)
Reduces the real symmetric or complex Hermitian band matrix whose lower form is lower ((u + 1) × n,...
Definition eigen.hpp:3801
A matrix balanced, B = T⁻¹ A T with T = P D (matrix_balance).
Definition eigen.hpp:3067
matrix< T > b
The balanced matrix.
Definition eigen.hpp:3068
vector< double > scale
The diagonal of D, powers of two (1 outside the scaled block).
Definition eigen.hpp:3069
std::vector< std::size_t > permutation
P e_c = e_{permutation[c]}.
Definition eigen.hpp:3070
A symmetric or Hermitian band matrix's tridiagonal form: A = W T Wᴴ, T real symmetric tridiagonal of ...
Definition eigen.hpp:3785
vector< double > d
T's diagonal.
Definition eigen.hpp:3786
vector< double > e
T's off-diagonal, |·| of the reduced band's.
Definition eigen.hpp:3787
matrix< T > w
The basis, n × n, or empty.
Definition eigen.hpp:3788
How a matrix was balanced: swaps, in the order they were applied, then the scaling of the active bloc...
Definition eigen.hpp:100
std::vector< std::pair< std::size_t, std::size_t > > swaps
Rows and columns exchanged, in order.
Definition eigen.hpp:103
std::size_t high
One past its last.
Definition eigen.hpp:102
buffer< double > scale
The diagonal D of D⁻¹ A D (1 outside).
Definition eigen.hpp:104
std::size_t low
The active block's first row and column.
Definition eigen.hpp:101
A complex vector that rows are summed against, kept as (re, −im) and (im, re) pairs: a complex row,...
Definition eigen.hpp:394
std::complex< double > dot(const std::complex< double > *row) const
Σ row[l] v[l].
Definition eigen.hpp:399
buffer< double > real_side
(re, −im) per entry.
Definition eigen.hpp:395
buffer< double > imaginary_side
(im, re) per entry.
Definition eigen.hpp:396
What early_deflation found: the eigenvalues left as shifts, and those deflated.
Definition eigen.hpp:2265
lapack_index shifts
Undeflated: the shifts, at the bottom of the active block.
Definition eigen.hpp:2266
lapack_index deflated
Deflated below them.
Definition eigen.hpp:2267
One panel of hessenberg_blocked, Q_panel = I − V T Vᴴ.
Definition eigen.hpp:437
buffer< T > t
T, row-major width × width, upper triangular.
Definition eigen.hpp:441
std::size_t width
Its columns.
Definition eigen.hpp:439
buffer< T > v
V, row-major (high − first − 1) × width, unit lower trapezoidal.
Definition eigen.hpp:440
std::size_t first
The panel's first column; its reflectors act on rows first + 1 … high − 1.
Definition eigen.hpp:438
A complex matrix's eigenvector during its back-substitution, kept as (re, −im) and (im,...
Definition eigen.hpp:2821
void set(std::size_t j, const std::complex< double > &value)
Sets component j to value.
Definition eigen.hpp:2839
buffer< double > real_side
(re, −im) per component: a row against it gives the product's real part.
Definition eigen.hpp:2824
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
Definition eigen.hpp:2855
std::complex< double > scalar
Its components.
Definition eigen.hpp:2822
std::complex< double > dot(const std::complex< double > *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
Definition eigen.hpp:2828
std::complex< double > get(std::size_t j) const
Component j.
Definition eigen.hpp:2849
buffer< double > imaginary_side
(im, re) per component: its imaginary part.
Definition eigen.hpp:2825
A row-major matrix read through indices from 1, (1, 1) its first entry.
Definition eigen.hpp:1253
lapack_index ld
The distance between rows.
Definition eigen.hpp:1261
T & operator()(lapack_index i, lapack_index j) const
The entry of row i and column j (from 1).
Definition eigen.hpp:1264
T * data
The first entry.
Definition eigen.hpp:1260
one_based(T *first, lapack_index distance)
The matrix whose first entry is at first, its rows distance apart.
Definition eigen.hpp:1255
A plane rotation [c s; −s̄ c] and what it leaves of its first argument.
Definition eigen.hpp:1308
A real eigenvector during its back-substitution, the sums of rows against it by dot_product.
Definition eigen.hpp:2749
double scalar
Its components.
Definition eigen.hpp:2750
void set(std::size_t j, double value)
Sets component j to value.
Definition eigen.hpp:2763
double dot(const double *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
Definition eigen.hpp:2755
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
Definition eigen.hpp:2770
buffer< double > x
The components.
Definition eigen.hpp:2752
A real matrix's eigenvectors before their back-transformation: Xᵀ's real and imaginary parts.
Definition eigen.hpp:2969
buffer< double > im
Im Xᵀ, zero where every eigenvalue is real.
Definition eigen.hpp:2971
buffer< double > re
Re Xᵀ, row-major n × n.
Definition eigen.hpp:2970
A real vector that rows are summed against by dot_product.
Definition eigen.hpp:380
double dot(const double *row) const
Σ row[l] v[l].
Definition eigen.hpp:384
buffer< double > v
The vector.
Definition eigen.hpp:381
A quotient of divided and the factor its dividend was scaled by: a type of its own,...
Definition eigen.hpp:2725
double factor
The dividend's scaling, 1 where none was needed.
Definition eigen.hpp:2727
Where a QR sweep applies its reflections: the rows and columns it updates, and Z.
Definition eigen.hpp:900
std::size_t low
The active block's first row.
Definition eigen.hpp:903
std::size_t n
Its order.
Definition eigen.hpp:902
bool full
Whether the whole Schur form is wanted (else the active block alone).
Definition eigen.hpp:905
buffer< T > * h
The Hessenberg matrix, row-major.
Definition eigen.hpp:901
std::size_t high
One past its last.
Definition eigen.hpp:904
buffer< T > * zt
The Schur vectors to accumulate, transposed (row-major Zᵀ), or none.
Definition eigen.hpp:906
A real matrix's complex eigenvector during its back-substitution, its real and imaginary parts apart:...
Definition eigen.hpp:2783
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
Definition eigen.hpp:2806
buffer< double > im
The imaginary parts.
Definition eigen.hpp:2787
void set(std::size_t j, const std::complex< double > &value)
Sets component j to value.
Definition eigen.hpp:2798
std::complex< double > dot(const double *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
Definition eigen.hpp:2790
buffer< double > re
The real parts.
Definition eigen.hpp:2786
std::complex< double > scalar
Its components.
Definition eigen.hpp:2784
The rotation standardize_block found, and the eigenvalues of the block it standardised.
Definition eigen.hpp:696
double re2
The second's real part.
Definition eigen.hpp:701
double re1
The first eigenvalue's real part.
Definition eigen.hpp:699
double im1
Its imaginary part (positive for a complex pair).
Definition eigen.hpp:700
double im2
Its imaginary part (−im1).
Definition eigen.hpp:702
A decomposition and the count its sort moved first.
Definition eigen.hpp:3653
std::size_t leading
The eigenvalues moved first.
Definition eigen.hpp:3656
matrix< T > z
The Schur vectors.
Definition eigen.hpp:3655