NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
dqds.hpp
Go to the documentation of this file.
1
9#ifndef NUMERICAL_DQDS_HPP
10#define NUMERICAL_DQDS_HPP
11
12#include <algorithm>
13#include <cmath>
14#include <cstddef>
15#include <functional>
16#include <limits>
17
18#include "buffer.hpp"
19
20namespace numerical::detail {
21
23 using qd_index = std::ptrdiff_t;
24
27 {
28 public:
29
31 explicit qd_array(double* z) noexcept
32 : z_ {z}
33 {}
34
36 [[nodiscard]] double& operator()(qd_index i) const noexcept
37 {
38 return z_[i - 1];
39 }
40
41 private:
42
43 double* z_;
44 };
45
48 {
49 double dmin1 {0.0};
50 double dmin2 {0.0};
51 double dn {0.0};
52 double dn1 {0.0};
53 double dn2 {0.0};
54 double g {0.0};
55 double tau {0.0};
57 };
58
60 inline constexpr double dqds_tolerance_squared {(std::numeric_limits<double>::epsilon() * 100.0) *
61 (std::numeric_limits<double>::epsilon() * 100.0)};
62
64 inline constexpr qd_index dqds_sweeps {100};
65
71 inline void qd_pair(double& a,
72 double b,
73 double& c) noexcept
74 {
75 if (c > a) {
76 std::swap(a, c);
77 }
78 const double t {0.5 * ((a - c) + b)};
79 if (b > c * dqds_tolerance_squared && t != 0.0) {
80 double s {c * (b / t)};
81 if (s <= t) {
82 s = c * (b / (t * (1.0 + std::sqrt(1.0 + (s / t)))));
83 }
84 else {
85 s = c * (b / (t + (std::sqrt(t) * std::sqrt(t + s))));
86 }
87 const double larger {a + (s + b)};
88 c = c * (a / larger);
89 a = larger;
90 }
91 }
92
105 inline void dqds_shift(qd_index i0,
106 qd_index n0,
107 const qd_array& z,
108 qd_index pp,
110 double dmin,
112 {
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};
120 if (dmin <= 0.0) {
121 state.tau = -dmin;
122 state.ttype = -1;
123 return;
124 }
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};
130 const qd_index nn {(4 * n0) + pp};
131 double s {0.0};
132 double a2 {0.0};
133 double b1 {0.0};
134 double b2 {0.0};
135 double gam {0.0};
136 double gap1 {0.0};
137 double gap2 {0.0};
138 qd_index np {0};
139 if (n0in == n0) { // no value deflated
140 if (dmin == dn || dmin == dn1) {
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) { // the two least at the end: Gershgorin's discs of the trailing 2 × 2
145 gap2 = dmin2 - a2 - (dmin2 * qurtr);
146 if (gap2 > 0.0 && gap2 > b2) {
147 gap1 = a2 - dn - ((b2 / gap2) * b2);
148 }
149 else {
150 gap1 = a2 - dn - (b1 + b2);
151 }
152 if (gap1 > 0.0 && gap1 > b1) {
153 s = std::max(dn - ((b1 / gap1) * b1), half * dmin);
154 state.ttype = -2;
155 }
156 else {
157 s = 0.0;
158 if (dn > b1) {
159 s = dn - b1;
160 }
161 if (a2 > (b1 + b2)) {
162 s = std::min(s, a2 - (b1 + b2));
163 }
164 s = std::max(s, third * dmin);
165 state.ttype = -3;
166 }
167 }
168 else { // the least at one of the two ends: a Rayleigh-quotient-like estimate along the array
169 state.ttype = -4;
170 s = qurtr * dmin;
171 if (dmin == dn) {
172 gam = dn;
173 a2 = 0.0;
174 if (z(nn - 5) > z(nn - 7)) {
175 return;
176 }
177 b2 = z(nn - 5) / z(nn - 7);
178 np = nn - 9;
179 }
180 else {
181 np = nn - (2 * pp);
182 gam = dn1;
183 if (z(np - 4) > z(np - 2)) {
184 return;
185 }
186 a2 = z(np - 4) / z(np - 2);
187 if (z(nn - 9) > z(nn - 11)) {
188 return;
189 }
190 b2 = z(nn - 9) / z(nn - 11);
191 np = nn - 13;
192 }
193 a2 = a2 + b2;
194 for (qd_index i4 {np}; i4 >= (4 * i0) - 1 + pp; i4 -= 4) {
195 if (b2 == 0.0) {
196 break;
197 }
198 b1 = b2;
199 if (z(i4) > z(i4 - 2)) {
200 return;
201 }
202 b2 = b2 * (z(i4) / z(i4 - 2));
203 a2 = a2 + b2;
204 if (hundrd * std::max(b2, b1) < a2 || cnst1 < a2) {
205 break;
206 }
207 }
208 a2 = cnst3 * a2;
209 if (a2 < cnst1) {
210 s = gam * (1.0 - std::sqrt(a2)) / (1.0 + a2);
211 }
212 }
213 }
214 else if (dmin == dn2) {
215 state.ttype = -5;
216 s = qurtr * dmin;
217 np = nn - (2 * pp);
218 b1 = z(np - 2);
219 b2 = z(np - 6);
220 gam = dn2;
221 if (z(np - 8) > b2 || z(np - 4) > b1) {
222 return;
223 }
224 a2 = (z(np - 8) / b2) * (1.0 + (z(np - 4) / b1));
225 if (n0 - i0 > 2) {
226 b2 = z(nn - 13) / z(nn - 15);
227 a2 = a2 + b2;
228 for (qd_index i4 {nn - 17}; i4 >= (4 * i0) - 1 + pp; i4 -= 4) {
229 if (b2 == 0.0) {
230 break;
231 }
232 b1 = b2;
233 if (z(i4) > z(i4 - 2)) {
234 return;
235 }
236 b2 = b2 * (z(i4) / z(i4 - 2));
237 a2 = a2 + b2;
238 if (hundrd * std::max(b2, b1) < a2 || cnst1 < a2) {
239 break;
240 }
241 }
242 a2 = cnst3 * a2;
243 }
244 if (a2 < cnst1) {
245 s = gam * (1.0 - std::sqrt(a2)) / (1.0 + a2);
246 }
247 }
248 else { // the least inside the array: a fraction of it, raised after each shift of this type
249 if (state.ttype == -6) {
250 state.g = state.g + (third * (1.0 - state.g));
251 }
252 else if (state.ttype == -18) {
253 state.g = qurtr * third;
254 }
255 else {
256 state.g = qurtr;
257 }
258 s = state.g * dmin;
259 state.ttype = -6;
260 }
261 }
262 else if (n0in == n0 + 1) { // one value deflated
263 if (dmin1 == dn1 && dmin2 == dn2) {
264 state.ttype = -7;
265 s = third * dmin1;
266 if (z(nn - 5) > z(nn - 7)) {
267 return;
268 }
269 b1 = z(nn - 5) / z(nn - 7);
270 b2 = b1;
271 if (b2 != 0.0) {
272 for (qd_index i4 {(4 * n0) - 9 + pp}; i4 >= (4 * i0) - 1 + pp; i4 -= 4) {
273 a2 = b1;
274 if (z(i4) > z(i4 - 2)) {
275 return;
276 }
277 b1 = b1 * (z(i4) / z(i4 - 2));
278 b2 = b2 + b1;
279 if (hundrd * std::max(b1, a2) < b2) {
280 break;
281 }
282 }
283 }
284 b2 = std::sqrt(cnst3 * b2);
285 a2 = dmin1 / (1.0 + (b2 * b2));
286 gap2 = (half * dmin2) - a2;
287 if (gap2 > 0.0 && gap2 > b2 * a2) {
288 s = std::max(s, a2 * (1.0 - (cnst2 * a2 * (b2 / gap2) * b2)));
289 }
290 else {
291 s = std::max(s, a2 * (1.0 - (cnst2 * b2)));
292 state.ttype = -8;
293 }
294 }
295 else {
296 s = qurtr * dmin1;
297 if (dmin1 == dn1) {
298 s = half * dmin1;
299 }
300 state.ttype = -9;
301 }
302 }
303 else if (n0in == n0 + 2) { // two values deflated
304 if (dmin2 == dn2 && 2.0 * z(nn - 5) < z(nn - 7)) {
305 state.ttype = -10;
306 s = third * dmin2;
307 b1 = z(nn - 5) / z(nn - 7); // under one half: the condition above
308 b2 = b1;
309 if (b2 != 0.0) {
310 for (qd_index i4 {(4 * n0) - 9 + pp}; i4 >= (4 * i0) - 1 + pp; i4 -= 4) {
311 if (z(i4) > z(i4 - 2)) {
312 return;
313 }
314 b1 = b1 * (z(i4) / z(i4 - 2));
315 b2 = b2 + b1;
316 if (hundrd * b1 < b2) {
317 break;
318 }
319 }
320 }
321 b2 = std::sqrt(cnst3 * b2);
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;
324 if (gap2 > 0.0 && gap2 > b2 * a2) {
325 s = std::max(s, a2 * (1.0 - (cnst2 * a2 * (b2 / gap2) * b2)));
326 }
327 else {
328 s = std::max(s, a2 * (1.0 - (cnst2 * b2)));
329 }
330 }
331 else {
332 s = qurtr * dmin2;
333 state.ttype = -11;
334 }
335 }
336 else { // more than two deflated: no estimate
337 s = 0.0;
338 state.ttype = -12;
339 }
340 state.tau = s;
341 }
342
351 qd_index n0,
352 const qd_array& z,
353 qd_index pp,
354 double& tau,
355 double sigma,
356 double& dmin,
358 {
359 const double dthresh {std::numeric_limits<double>::epsilon() * (sigma + tau)};
360 if (tau < dthresh * 0.5) {
361 tau = 0.0;
362 }
363 qd_index j4 {(4 * i0) + pp - 3};
364 double emin {z(j4 + 4)};
365 double d {z(j4) - tau};
366 const bool zero_shift {tau == 0.0};
367 dmin = d;
368 if (pp == 0) {
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;
373 if (zero_shift && d < dthresh) {
374 d = 0.0;
375 }
376 dmin = std::min(dmin, d);
377 z(j4) = z(j4 - 1) * temp;
378 emin = std::min(z(j4), emin);
379 }
380 }
381 else {
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;
386 if (zero_shift && d < dthresh) {
387 d = 0.0;
388 }
389 dmin = std::min(dmin, d);
390 z(j4 - 1) = z(j4) * temp;
391 emin = std::min(z(j4 - 1), emin);
392 }
393 }
394 // The last two steps apart, their d's kept for the shift.
395 state.dn2 = d;
396 state.dmin2 = dmin;
397 j4 = (4 * (n0 - 2)) - pp;
398 qd_index j4p2 {j4 + (2 * pp) - 1};
399 z(j4 - 2) = state.dn2 + z(j4p2);
400 z(j4) = z(j4p2 + 2) * (z(j4p2) / z(j4 - 2));
401 state.dn1 = (z(j4p2 + 2) * (state.dn2 / z(j4 - 2))) - tau;
402 dmin = std::min(dmin, state.dn1);
403 state.dmin1 = dmin;
404 j4 = j4 + 4;
405 j4p2 = j4 + (2 * pp) - 1;
406 z(j4 - 2) = state.dn1 + z(j4p2);
407 z(j4) = z(j4p2 + 2) * (z(j4p2) / z(j4 - 2));
408 state.dn = (z(j4p2 + 2) * (state.dn1 / z(j4 - 2))) - tau;
409 dmin = std::min(dmin, state.dn);
410 z(j4 + 2) = state.dn;
411 z((4 * n0) - pp) = emin;
412 if (!std::isfinite(state.dn)) {
413 dmin = std::numeric_limits<double>::quiet_NaN();
414 }
415 }
416
423 qd_index n0,
424 const qd_array& z,
425 qd_index pp,
426 double& dmin,
428 {
429 const double safmin {std::numeric_limits<double>::min()};
430 qd_index j4 {(4 * i0) + pp - 3};
431 double emin {z(j4 + 4)};
432 double d {z(j4)};
433 dmin = d;
434 if (pp == 0) {
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) {
438 z(j4) = 0.0;
439 d = z(j4 + 1);
440 dmin = d;
441 emin = 0.0;
442 }
443 else if (safmin * z(j4 + 1) < z(j4 - 2) && safmin * z(j4 - 2) < z(j4 + 1)) {
444 const double temp {z(j4 + 1) / z(j4 - 2)};
445 z(j4) = z(j4 - 1) * temp;
446 d = d * temp;
447 }
448 else {
449 z(j4) = z(j4 + 1) * (z(j4 - 1) / z(j4 - 2));
450 d = z(j4 + 1) * (d / z(j4 - 2));
451 }
452 dmin = std::min(dmin, d);
453 emin = std::min(emin, z(j4));
454 }
455 }
456 else {
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) {
460 z(j4 - 1) = 0.0;
461 d = z(j4 + 2);
462 dmin = d;
463 emin = 0.0;
464 }
465 else if (safmin * z(j4 + 2) < z(j4 - 3) && safmin * z(j4 - 3) < z(j4 + 2)) {
466 const double temp {z(j4 + 2) / z(j4 - 3)};
467 z(j4 - 1) = z(j4) * temp;
468 d = d * temp;
469 }
470 else {
471 z(j4 - 1) = z(j4 + 2) * (z(j4) / z(j4 - 3));
472 d = z(j4 + 2) * (d / z(j4 - 3));
473 }
474 dmin = std::min(dmin, d);
475 emin = std::min(emin, z(j4 - 1));
476 }
477 }
478 // The last two steps apart, their d's kept for the shift.
479 state.dn2 = d;
480 state.dmin2 = dmin;
481 qd_index j4p2 {0};
482 for (int last {0}; last < 2; ++last) {
483 j4 = last == 0 ? (4 * (n0 - 2)) - pp : j4 + 4;
484 j4p2 = j4 + (2 * pp) - 1;
485 const double before {last == 0 ? state.dn2 : state.dn1};
486 double after {0.0};
487 z(j4 - 2) = before + z(j4p2);
488 if (z(j4 - 2) == 0.0) {
489 z(j4) = 0.0;
490 after = z(j4p2 + 2);
491 dmin = after;
492 emin = 0.0;
493 }
494 else if (safmin * z(j4p2 + 2) < z(j4 - 2) && safmin * z(j4 - 2) < z(j4p2 + 2)) {
495 const double temp {z(j4p2 + 2) / z(j4 - 2)};
496 z(j4) = z(j4p2) * temp;
497 after = before * temp;
498 }
499 else {
500 z(j4) = z(j4p2 + 2) * (z(j4p2) / z(j4 - 2));
501 after = z(j4p2 + 2) * (before / z(j4 - 2));
502 }
503 dmin = std::min(dmin, after);
504 if (last == 0) {
505 state.dn1 = after;
506 state.dmin1 = dmin;
507 }
508 else {
509 state.dn = after;
510 }
511 }
512 z(j4 + 2) = state.dn;
513 z((4 * n0) - pp) = emin;
514 }
515
517 inline void qd_flip(qd_index i0,
518 qd_index n0,
519 const qd_array& z) noexcept
520 {
521 const qd_index ipn4 {4 * (i0 + n0)};
522 for (qd_index i4 {4 * i0}; i4 <= 2 * (i0 + n0 - 1); i4 += 4) {
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));
526 std::swap(z(i4), z(ipn4 - i4 - 4));
527 }
528 }
529
545 inline void dqds_step(qd_index i0,
546 qd_index& n0,
547 const qd_array& z,
548 qd_index& pp,
549 double& dmin,
550 double& sigma,
551 double& desig,
552 double& qmax,
554 {
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};
559 const double tol2 {dqds_tolerance_squared};
560 const qd_index n0in {n0};
561 while (n0 >= i0) {
562 if (n0 == i0) { // one value left
563 z((4 * n0) - 3) = z((4 * n0) + pp - 3) + sigma;
564 --n0;
565 continue;
566 }
567 const qd_index nn {(4 * n0) + pp};
568 if (n0 != i0 + 1) {
569 if (z(nn - 5) <= tol2 * (sigma + z(nn - 3)) || z(nn - (2 * pp) - 4) <= tol2 * z(nn - 7)) { // the last
570 z((4 * n0) - 3) = z((4 * n0) + pp - 3) + sigma;
571 --n0;
572 continue;
573 }
574 if (z(nn - 9) > tol2 * sigma && z(nn - (2 * pp) - 8) > tol2 * z(nn - 11)) {
575 break; // nothing converged: on to the transform
576 }
577 }
578 // The last two.
579 qd_pair(z(nn - 7), z(nn - 5), z(nn - 3));
580 z((4 * n0) - 7) = z(nn - 7) + sigma;
581 z((4 * n0) - 3) = z(nn - 3) + sigma;
582 n0 -= 2;
583 }
584 if (n0 < i0) {
585 return;
586 }
587 if (pp == 2) {
588 pp = 0;
589 }
590 if (dmin <= 0.0 || n0 < n0in) { // a new start: flip if the far end is much the smaller
591 if (cbias * z((4 * i0) + pp - 3) < z((4 * n0) + pp - 3)) {
592 qd_flip(i0, n0, z);
593 if (n0 - i0 <= 4) {
594 z((4 * n0) + pp - 1) = z((4 * i0) + pp - 1);
595 z((4 * n0) - pp) = z((4 * i0) - pp);
596 }
597 state.dmin2 = std::min(state.dmin2, z((4 * n0) + pp - 1));
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)});
600 qmax = std::max({qmax, z((4 * i0) + pp - 3), z((4 * i0) + pp + 1)});
601 dmin = -0.0;
602 }
603 }
604 dqds_shift(i0, n0, z, pp, n0in, dmin, state);
605 for (;;) {
606 dqds_transform(i0, n0, z, pp, state.tau, sigma, dmin, state);
607 if (std::isnan(dmin)) { // not finite: again unshifted, then guarded
608 if (state.tau == 0.0) {
609 dqd_transform(i0, n0, z, pp, dmin, state);
610 break;
611 }
612 state.tau = 0.0;
613 continue;
614 }
615 if (dmin >= 0.0) { // the least d of a finite transform bounds the others: all non-negative
616 break;
617 }
618 if (state.dmin1 > 0.0 && z((4 * (n0 - 1)) - pp) < tol * (sigma + state.dn1) && std::abs(state.dn) < tol * sigma) {
619 // Only the last d is negative, and negligible: the last value has converged to the shift.
620 z((4 * (n0 - 1)) - pp + 2) = 0.0;
621 dmin = 0.0;
622 break;
623 }
624 // The shift was too large: lower it.
625 if (state.ttype < -22) {
626 state.tau = 0.0;
627 }
628 else if (state.dmin1 > 0.0) {
629 state.tau = (state.tau + dmin) * (1.0 - (2.0 * eps));
630 state.ttype -= 11;
631 }
632 else {
633 state.tau = qurtr * state.tau;
634 state.ttype -= 12;
635 }
636 }
637 // sigma += tau, its rounding error carried in desig.
638 double t {0.0};
639 if (state.tau < sigma) {
640 desig = desig + state.tau;
641 t = sigma + desig;
642 desig = desig - (t - sigma);
643 }
644 else {
645 t = sigma + state.tau;
646 desig = sigma - (t - state.tau) + desig;
647 }
648 sigma = t;
649 }
650
661 qd_index n,
663 {
664 const qd_array zz {z.data()};
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()};
669 const double tol2 {dqds_tolerance_squared};
670 const auto descending {[&] {
671 std::sort(z.begin(), z.begin() + n, std::greater<> {});
672 return true;
673 }};
674 if (n == 2) {
675 qd_pair(zz(1), zz(2), zz(3));
676 zz(2) = zz(3);
677 return true;
678 }
679 zz(2 * n) = 0.0;
680 double e {0.0};
681 for (qd_index k {2}; k <= 2 * (n - 1); k += 2) {
682 e = e + zz(k);
683 }
684 if (e == 0.0) { // diagonal: the q's themselves
685 for (qd_index k {2}; k <= n; ++k) {
686 zz(k) = zz((2 * k) - 1);
687 }
688 return descending();
689 }
690 // Spread q₁ e₁ … qₙ to every fourth entry, both halves.
691 for (qd_index k {2 * n}; k >= 2; k -= 2) {
692 zz(2 * k) = 0.0;
693 zz((2 * k) - 1) = zz(k);
694 zz((2 * k) - 2) = 0.0;
695 zz((2 * k) - 3) = zz(k - 1);
696 }
697 qd_index i0 {1};
698 qd_index n0 {n};
699 if (cbias * zz((4 * i0) - 3) < zz((4 * n0) - 3)) { // the far end the smaller: flip
700 const qd_index ipn4 {4 * (i0 + n0)};
701 for (qd_index i4 {4 * i0}; i4 <= 2 * (i0 + n0 - 1); i4 += 4) {
702 std::swap(zz(i4 - 3), zz(ipn4 - i4 - 3));
703 std::swap(zz(i4 - 1), zz(ipn4 - i4 - 5));
704 }
705 }
706 // Two dqd transforms, unshifted, each splitting at the negligible e's.
707 qd_index pp {0};
708 double d {0.0};
709 double qmax {0.0};
710 for (int k {1}; k <= 2; ++k) {
711 d = zz((4 * n0) + pp - 3);
712 for (qd_index i4 {(4 * (n0 - 1)) + pp}; i4 >= (4 * i0) + pp; i4 -= 4) {
713 if (zz(i4 - 1) <= tol2 * d) {
714 zz(i4 - 1) = -0.0;
715 d = zz(i4 - 3);
716 }
717 else {
718 d = zz(i4 - 3) * (d / (d + zz(i4 - 1)));
719 }
720 }
721 d = zz((4 * i0) + pp - 3);
722 for (qd_index i4 {(4 * i0) + pp}; i4 <= (4 * (n0 - 1)) + pp; i4 += 4) {
723 zz(i4 - (2 * pp) - 2) = d + zz(i4 - 1);
724 if (zz(i4 - 1) <= tol2 * d) {
725 zz(i4 - 1) = -0.0;
726 zz(i4 - (2 * pp) - 2) = d;
727 zz(i4 - (2 * pp)) = 0.0;
728 d = zz(i4 + 1);
729 }
730 else if (safmin * zz(i4 + 1) < zz(i4 - (2 * pp) - 2) && safmin * zz(i4 - (2 * pp) - 2) < zz(i4 + 1)) {
731 const double temp {zz(i4 + 1) / zz(i4 - (2 * pp) - 2)};
732 zz(i4 - (2 * pp)) = zz(i4 - 1) * temp;
733 d = d * temp;
734 }
735 else {
736 zz(i4 - (2 * pp)) = zz(i4 + 1) * (zz(i4 - 1) / zz(i4 - (2 * pp) - 2));
737 d = zz(i4 + 1) * (d / zz(i4 - (2 * pp) - 2));
738 }
739 }
740 zz((4 * n0) - pp - 2) = d;
741 pp = 1 - pp;
742 }
744 // Each pass takes the last unreduced block, n0 down to its split; n0 falls with each.
745 while (n0 >= 1) {
746 double desig {0.0};
747 double sigma {n0 == n ? 0.0 : -zz((4 * n0) - 1)}; // a split stored −σ at its end
748 double emax {0.0};
749 double qmin {zz((4 * n0) - 3)};
750 qmax = qmin;
751 qd_index i4 {4 * n0};
752 for (; i4 >= 8; i4 -= 4) {
753 if (zz(i4 - 5) <= 0.0) {
754 break;
755 }
756 if (qmin >= four * emax) {
757 qmin = std::min(qmin, zz(i4 - 3));
758 emax = std::max(emax, zz(i4 - 5));
759 }
760 qmax = std::max(qmax, zz(i4 - 7) + zz(i4 - 5));
761 }
762 i0 = i4 / 4;
763 pp = 0;
764 if (n0 - i0 > 1) { // flip if the least d of a dqd sits in the block's first third
765 double dee {zz((4 * i0) - 3)};
766 double deemin {dee};
767 qd_index kmin {i0};
768 for (qd_index j {(4 * i0) + 1}; j <= (4 * n0) - 3; j += 4) {
769 dee = zz(j) * (dee / (dee + zz(j - 2)));
770 if (dee <= deemin) {
771 deemin = dee;
772 kmin = (j + 3) / 4;
773 }
774 }
775 if ((kmin - i0) * 2 < n0 - kmin && deemin <= half * zz((4 * n0) - 3)) {
776 pp = 2;
777 qd_flip(i0, n0, zz);
778 }
779 }
780 double dmin {-std::max(0.0, qmin - (2.0 * std::sqrt(qmin) * std::sqrt(emax)))};
781 const qd_index nbig {sweeps * (n0 - i0 + 1)};
782 qd_index steps {0};
783 while (i0 <= n0) {
784 if (steps++ == nbig) {
785 return false;
786 }
787 dqds_step(i0, n0, zz, pp, dmin, sigma, desig, qmax, state);
788 pp = 1 - pp;
789 if (pp == 0 && n0 - i0 >= 3 && (zz(4 * n0) <= tol2 * qmax || zz((4 * n0) - 1) <= tol2 * sigma)) {
790 // A negligible e inside the block: split there, the part above left for a later pass.
791 qd_index splt {i0 - 1};
792 qmax = zz((4 * i0) - 3);
793 double emin {zz((4 * i0) - 1)};
794 double oldemn {zz(4 * i0)};
795 for (qd_index j {4 * i0}; j <= 4 * (n0 - 3); j += 4) {
796 if (zz(j) <= tol2 * zz(j - 3) || zz(j - 1) <= tol2 * sigma) {
797 zz(j - 1) = -sigma;
798 splt = j / 4;
799 qmax = 0.0;
800 emin = zz(j + 3);
801 oldemn = zz(j + 4);
802 }
803 else {
804 qmax = std::max(qmax, zz(j + 1));
805 emin = std::min(emin, zz(j - 1));
806 oldemn = std::min(oldemn, zz(j));
807 }
808 }
809 zz((4 * n0) - 1) = emin;
810 zz(4 * n0) = oldemn;
811 i0 = splt + 1;
812 }
813 }
814 }
815 for (qd_index k {2}; k <= n; ++k) {
816 zz(k) = zz((4 * k) - 3);
817 }
818 return descending();
819 }
820
832 const buffer<double>& e,
833 std::size_t n,
835 {
836 double sigmx {0.0};
837 for (std::size_t i {0}; i + 1 < n; ++i) {
838 sigmx = std::max(sigmx, std::abs(e[i]));
839 }
840 if (sigmx == 0.0) { // diagonal
841 for (std::size_t i {0}; i < n; ++i) {
842 d[i] = std::abs(d[i]);
843 }
844 std::sort(d.begin(), d.begin() + static_cast<std::ptrdiff_t>(n), std::greater<> {});
845 return true;
846 }
847 for (std::size_t i {0}; i < n; ++i) {
848 sigmx = std::max(sigmx, std::abs(d[i]));
849 }
850 // Each entry over the largest first: the scale's quotient by a subnormal largest would overflow.
851 const double scale {std::sqrt(std::numeric_limits<double>::epsilon() / std::numeric_limits<double>::min())};
852 buffer<double> z(4 * n, 0.0);
853 for (std::size_t i {0}; i < n; ++i) {
854 const double v {(std::abs(d[i]) / sigmx) * scale};
855 z[2 * i] = v * v;
856 }
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;
860 }
861 if (!dqds_squares(z, static_cast<qd_index>(n), sweeps)) {
862 return false;
863 }
864 for (std::size_t i {0}; i < n; ++i) {
865 d[i] = (std::sqrt(z[i]) / scale) * sigmx;
866 }
867 return true;
868 }
869} // namespace numerical::detail
870
871#endif // NUMERICAL_DQDS_HPP
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].
Definition dqds.hpp:27
qd_array(double *z) noexcept
The array over z.
Definition dqds.hpp:31
double * z_
The first entry.
Definition dqds.hpp:43
double & operator()(qd_index i) const noexcept
Z(i).
Definition dqds.hpp:36
std::ptrdiff_t qd_index
An index into the qd array, one-based and signed as LAPACK's.
Definition dqds.hpp:23
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).
Definition dqds.hpp:517
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...
Definition dqds.hpp:660
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...
Definition dqds.hpp:350
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...
Definition dqds.hpp:422
constexpr double dqds_tolerance_squared
LAPACK's bound of the off-diagonal against the diagonal under which a value deflates: (100 ε)².
Definition dqds.hpp:60
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),...
Definition dqds.hpp:831
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...
Definition dqds.hpp:545
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₁,...
Definition dqds.hpp:71
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...
Definition dqds.hpp:105
constexpr qd_index dqds_sweeps
The steps of the inner iteration per value of its block before dqds gives up (LAPACK's 100).
Definition dqds.hpp:64
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
What one dqds step hands the next: the least ds of the last transform and the shift's memory.
Definition dqds.hpp:48
double dmin1
The least d but the last.
Definition dqds.hpp:49
double g
The fraction of the least d that a shift of type −6 takes.
Definition dqds.hpp:54
double dn1
The d before it.
Definition dqds.hpp:52
double tau
The shift.
Definition dqds.hpp:55
qd_index ttype
Which estimate gave the shift.
Definition dqds.hpp:56
double dn2
The d before that.
Definition dqds.hpp:53
double dmin2
The least d but the last two.
Definition dqds.hpp:50
double dn
The last d.
Definition dqds.hpp:51