|
NumericAL
A header-only C++20 lexer built on REAL
|
The singular values of a real bidiagonal by the dqds algorithm (Fernando and Parlett's differential quotient-difference with shifts, as LAPACK's dlasq1–dlasq6): the eigenvalues of BᵀB from the qd array of the squares of B's entries, every transform's numbers non-negative, so that each value is found to high relative accuracy. The routines keep LAPACK's one-based indices into the array Z of 4n entries, so that each line reads against its original.
More...
#include <algorithm>#include <cmath>#include <cstddef>#include <functional>#include <limits>#include "buffer.hpp"Go to the source code of this file.
Classes | |
| class | numerical::detail::qd_array |
The qd array Z of 4n entries, read one-based: Z(i) is z[i − 1]. More... | |
| struct | numerical::detail::dqds_state |
What one dqds step hands the next: the least ds of the last transform and the shift's memory. More... | |
Namespaces | |
| namespace | numerical |
| The NumericAL public API. | |
| namespace | numerical::detail |
Typedefs | |
| using | numerical::detail::qd_index = std::ptrdiff_t |
| An index into the qd array, one-based and signed as LAPACK's. | |
Functions | |
| void | numerical::detail::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₁, c = q₂: the larger into a, the smaller into c, each to high relative accuracy. No change where b is negligible against c, nor where half the sum (a − c) + b underflows to zero. | |
| void | numerical::detail::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 eigenvalue from the last transform's least ds, by the case state's ttype records. Some cases return with the shift as it was, where a ratio of the array exceeds one. | |
| void | numerical::detail::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 the array into the other (LAPACK's dlasq5, its IEEE form): a zero shift where it is under half of ε (σ + τ), the ds it takes below that bound set to zero. dmin is NaN where the last d is not finite: a d + e of zero, or past overflow, makes every d after it NaN, which a least of them alone does not show. | |
| void | numerical::detail::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 array into the other, each quotient guarded against underflow and overflow (LAPACK's dlasq6): the transform a shifted one falls back to when its numbers are not finite. | |
| void | numerical::detail::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). | |
| void | numerical::detail::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(4k − 3), sigma added back), flips the block where its far end is the smaller, then one transform with the shift of dqds_shift. A shift that makes a d negative is lowered and the transform retried; one whose numbers are not finite is dropped, the transform then unshifted, guarded as dqd_transform. | |
| bool | numerical::detail::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₁ e₁ q₂ e₂ … qₙ, non-negative, in its first 2n − 1 entries, n at least two. | |
| bool | numerical::detail::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), descending into d: its entries' magnitudes scaled so that the largest is √(ε / DBL_MIN), their squares' eigenvalues found by dqds_squares, the square roots scaled back. | |
Variables | |
| constexpr double | numerical::detail::dqds_tolerance_squared |
LAPACK's bound of the off-diagonal against the diagonal under which a value deflates: (100 ε)². | |
| constexpr qd_index | numerical::detail::dqds_sweeps {100} |
| The steps of the inner iteration per value of its block before dqds gives up (LAPACK's 100). | |
The singular values of a real bidiagonal by the dqds algorithm (Fernando and Parlett's differential quotient-difference with shifts, as LAPACK's dlasq1–dlasq6): the eigenvalues of BᵀB from the qd array of the squares of B's entries, every transform's numbers non-negative, so that each value is found to high relative accuracy. The routines keep LAPACK's one-based indices into the array Z of 4n entries, so that each line reads against its original.
Definition in file dqds.hpp.