9#ifndef NUMERICAL_DQDS_HPP
10#define NUMERICAL_DQDS_HPP
61 (std::numeric_limits<double>::epsilon() * 100.0)};
78 const double t {0.5 * ((a - c) + b)};
80 double s {c * (b / t)};
82 s = c * (b / (t * (1.0 + std::sqrt(1.0 + (s / t)))));
85 s = c * (b / (t + (std::sqrt(t) * std::sqrt(t + s))));
87 const double larger {a + (s + b)};
113 constexpr double cnst1 {0.5630};
114 constexpr double cnst2 {1.010};
115 constexpr double cnst3 {1.050};
116 constexpr double qurtr {0.25};
117 constexpr double third {0.3330};
118 constexpr double half {0.5};
119 constexpr double hundrd {100.0};
125 const double dmin1 {
state.dmin1};
126 const double dmin2 {
state.dmin2};
127 const double dn {
state.dn};
128 const double dn1 {
state.dn1};
129 const double dn2 {
state.dn2};
141 b1 = std::sqrt(z(
nn - 3)) * std::sqrt(z(
nn - 5));
142 b2 = std::sqrt(z(
nn - 7)) * std::sqrt(z(
nn - 9));
143 a2 = z(
nn - 7) + z(
nn - 5);
144 if (
dmin == dn && dmin1 == dn1) {
162 s = std::min(s,
a2 - (
b1 +
b2));
174 if (z(
nn - 5) > z(
nn - 7)) {
177 b2 = z(
nn - 5) / z(
nn - 7);
183 if (z(
np - 4) > z(
np - 2)) {
186 a2 = z(
np - 4) / z(
np - 2);
187 if (z(
nn - 9) > z(
nn - 11)) {
190 b2 = z(
nn - 9) / z(
nn - 11);
199 if (z(
i4) > z(
i4 - 2)) {
210 s =
gam * (1.0 - std::sqrt(
a2)) / (1.0 +
a2);
214 else if (
dmin == dn2) {
221 if (z(
np - 8) >
b2 || z(
np - 4) >
b1) {
224 a2 = (z(
np - 8) /
b2) * (1.0 + (z(
np - 4) /
b1));
226 b2 = z(
nn - 13) / z(
nn - 15);
233 if (z(
i4) > z(
i4 - 2)) {
245 s =
gam * (1.0 - std::sqrt(
a2)) / (1.0 +
a2);
249 if (
state.ttype == -6) {
252 else if (
state.ttype == -18) {
262 else if (
n0in ==
n0 + 1) {
263 if (dmin1 == dn1 && dmin2 == dn2) {
266 if (z(
nn - 5) > z(
nn - 7)) {
269 b1 = z(
nn - 5) / z(
nn - 7);
274 if (z(
i4) > z(
i4 - 2)) {
285 a2 = dmin1 / (1.0 + (
b2 *
b2));
286 gap2 = (half * dmin2) -
a2;
291 s = std::max(s,
a2 * (1.0 - (
cnst2 *
b2)));
303 else if (
n0in ==
n0 + 2) {
304 if (dmin2 == dn2 && 2.0 * z(
nn - 5) < z(
nn - 7)) {
307 b1 = z(
nn - 5) / z(
nn - 7);
311 if (z(
i4) > z(
i4 - 2)) {
322 a2 = dmin2 / (1.0 + (
b2 *
b2));
323 gap2 = z(
nn - 7) + z(
nn - 9) - (std::sqrt(z(
nn - 11)) * std::sqrt(z(
nn - 9))) -
a2;
328 s = std::max(s,
a2 * (1.0 - (
cnst2 *
b2)));
359 const double dthresh {std::numeric_limits<double>::epsilon() * (sigma + tau)};
365 double d {z(
j4) - tau};
369 for (
j4 = 4 *
i0;
j4 <= 4 * (
n0 - 3);
j4 += 4) {
370 z(
j4 - 2) = d + z(
j4 - 1);
371 const double temp {z(
j4 + 1) / z(
j4 - 2)};
372 d = (d *
temp) - tau;
382 for (
j4 = 4 *
i0;
j4 <= 4 * (
n0 - 3);
j4 += 4) {
383 z(
j4 - 3) = d + z(
j4);
384 const double temp {z(
j4 + 2) / z(
j4 - 3)};
385 d = (d *
temp) - tau;
412 if (!std::isfinite(
state.dn)) {
413 dmin = std::numeric_limits<double>::quiet_NaN();
429 const double safmin {std::numeric_limits<double>::min()};
435 for (
j4 = 4 *
i0;
j4 <= 4 * (
n0 - 3);
j4 += 4) {
436 z(
j4 - 2) = d + z(
j4 - 1);
437 if (z(
j4 - 2) == 0.0) {
444 const double temp {z(
j4 + 1) / z(
j4 - 2)};
449 z(
j4) = z(
j4 + 1) * (z(
j4 - 1) / z(
j4 - 2));
450 d = z(
j4 + 1) * (d / z(
j4 - 2));
457 for (
j4 = 4 *
i0;
j4 <= 4 * (
n0 - 3);
j4 += 4) {
458 z(
j4 - 3) = d + z(
j4);
459 if (z(
j4 - 3) == 0.0) {
466 const double temp {z(
j4 + 2) / z(
j4 - 3)};
471 z(
j4 - 1) = z(
j4 + 2) * (z(
j4) / z(
j4 - 3));
472 d = z(
j4 + 2) * (d / z(
j4 - 3));
488 if (z(
j4 - 2) == 0.0) {
523 std::swap(z(
i4 - 3), z(
ipn4 -
i4 - 3));
524 std::swap(z(
i4 - 2), z(
ipn4 -
i4 - 2));
525 std::swap(z(
i4 - 1), z(
ipn4 -
i4 - 5));
555 constexpr double cbias {1.50};
556 constexpr double qurtr {0.25};
557 const double eps {std::numeric_limits<double>::epsilon()};
558 const double tol {
eps * 100.0};
563 z((4 *
n0) - 3) = z((4 *
n0) +
pp - 3) + sigma;
569 if (z(
nn - 5) <=
tol2 * (sigma + z(
nn - 3)) || z(
nn - (2 *
pp) - 4) <=
tol2 * z(
nn - 7)) {
570 z((4 *
n0) - 3) = z((4 *
n0) +
pp - 3) + sigma;
580 z((4 *
n0) - 7) = z(
nn - 7) + sigma;
581 z((4 *
n0) - 3) = z(
nn - 3) + sigma;
594 z((4 *
n0) +
pp - 1) = z((4 *
i0) +
pp - 1);
595 z((4 *
n0) -
pp) = z((4 *
i0) -
pp);
598 z((4 *
n0) +
pp - 1) = std::min({z((4 *
n0) +
pp - 1), z((4 *
i0) +
pp - 1), z((4 *
i0) +
pp + 3)});
599 z((4 *
n0) -
pp) = std::min({z((4 *
n0) -
pp), z((4 *
i0) -
pp), z((4 *
i0) -
pp + 4)});
607 if (std::isnan(
dmin)) {
608 if (
state.tau == 0.0) {
620 z((4 * (
n0 - 1)) -
pp + 2) = 0.0;
625 if (
state.ttype < -22) {
628 else if (
state.dmin1 > 0.0) {
639 if (
state.tau < sigma) {
645 t = sigma +
state.tau;
665 constexpr double cbias {1.50};
666 constexpr double half {0.5};
667 constexpr double four {4.0};
668 const double safmin {std::numeric_limits<double>::min()};
671 std::sort(z.begin(), z.begin() + n, std::greater<> {});
681 for (
qd_index k {2}; k <= 2 * (n - 1); k += 2) {
686 zz(k) =
zz((2 * k) - 1);
691 for (
qd_index k {2 * n}; k >= 2; k -= 2) {
693 zz((2 * k) - 1) =
zz(k);
694 zz((2 * k) - 2) = 0.0;
695 zz((2 * k) - 3) =
zz(k - 1);
710 for (
int k {1}; k <= 2; ++k) {
711 d =
zz((4 *
n0) +
pp - 3);
718 d =
zz(
i4 - 3) * (d / (d +
zz(
i4 - 1)));
721 d =
zz((4 *
i0) +
pp - 3);
726 zz(
i4 - (2 *
pp) - 2) = d;
740 zz((4 *
n0) -
pp - 2) = d;
747 double sigma {
n0 == n ? 0.0 : -
zz((4 *
n0) - 1)};
752 for (;
i4 >= 8;
i4 -= 4) {
753 if (
zz(
i4 - 5) <= 0.0) {
768 for (
qd_index j {(4 *
i0) + 1}; j <= (4 *
n0) - 3; j += 4) {
780 double dmin {-std::max(0.0,
qmin - (2.0 * std::sqrt(
qmin) * std::sqrt(
emax)))};
784 if (steps++ ==
nbig) {
816 zz(k) =
zz((4 * k) - 3);
837 for (std::size_t i {0}; i + 1 < n; ++i) {
841 for (std::size_t i {0}; i < n; ++i) {
842 d[i] = std::abs(d[i]);
844 std::sort(d.begin(), d.begin() +
static_cast<std::ptrdiff_t
>(n), std::greater<> {});
847 for (std::size_t i {0}; i < n; ++i) {
851 const double scale {std::sqrt(std::numeric_limits<double>::epsilon() / std::numeric_limits<double>::min())};
853 for (std::size_t i {0}; i < n; ++i) {
854 const double v {(std::abs(d[i]) /
sigmx) * scale};
857 for (std::size_t i {0}; i + 1 < n; ++i) {
858 const double v {(std::abs(e[i]) /
sigmx) * scale};
859 z[(2 * i) + 1] = v * v;
864 for (std::size_t i {0}; i < n; ++i) {
865 d[i] = (std::sqrt(z[i]) / scale) *
sigmx;
numerical::buffer, the storage of the library's vectors, matrices and tensors: a std::vector whose el...
The qd array Z of 4n entries, read one-based: Z(i) is z[i − 1].
qd_array(double *z) noexcept
The array over z.
double * z_
The first entry.
double & operator()(qd_index i) const noexcept
Z(i).
std::ptrdiff_t qd_index
An index into the qd array, one-based and signed as LAPACK's.
void qd_flip(qd_index i0, qd_index n0, const qd_array &z) noexcept
Turns the block i0…n0 of the array end for end, both halves (LAPACK's flip in dlasq2 and dlasq3).
bool dqds_squares(buffer< double > &z, qd_index n, qd_index sweeps)
The eigenvalues of the positive semi-definite tridiagonal whose qd array is in z (LAPACK's dlasq2): q...
void dqds_transform(qd_index i0, qd_index n0, const qd_array &z, qd_index pp, double &tau, double sigma, double &dmin, dqds_state &state)
One dqds transform of the block i0…n0 (at least three values) with the shift tau, from the half pp of...
void dqd_transform(qd_index i0, qd_index n0, const qd_array &z, qd_index pp, double &dmin, dqds_state &state)
One dqd transform (no shift) of the block i0…n0 (at least three values), from the half pp of the arra...
constexpr double dqds_tolerance_squared
LAPACK's bound of the off-diagonal against the diagonal under which a value deflates: (100 ε)².
bool dqds_singular_values(buffer< double > &d, const buffer< double > &e, std::size_t n, qd_index sweeps=dqds_sweeps)
The singular values of the real upper bidiagonal (d, e) of order n by dqds (LAPACK's dlasq1),...
void dqds_step(qd_index i0, qd_index &n0, const qd_array &z, qd_index &pp, double &dmin, double &sigma, double &desig, double &qmax, dqds_state &state)
One step on the block i0…n0 (LAPACK's dlasq3): deflates the values its end has converged to (into Z(4...
void qd_pair(double &a, double b, double &c) noexcept
The eigenvalues of the 2 × 2 [[a, √b], [√b, c]]-like block of a qd array, a = q₁, b = e₁,...
void dqds_shift(qd_index i0, qd_index n0, const qd_array &z, qd_index pp, qd_index n0in, double dmin, dqds_state &state)
The shift of the next transform of the block i0…n0 (LAPACK's dlasq4): an estimate of the least eigenv...
constexpr qd_index dqds_sweeps
The steps of the inner iteration per value of its block before dqds gives up (LAPACK's 100).
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...
What one dqds step hands the next: the least ds of the last transform and the shift's memory.
double dmin1
The least d but the last.
double g
The fraction of the least d that a shift of type −6 takes.
double dn1
The d before it.
qd_index ttype
Which estimate gave the shift.
double dn2
The d before that.
double dmin2
The least d but the last two.