NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
Classes | Namespaces | Typedefs | Functions | Variables
dqds.hpp File Reference

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"
Include dependency graph for dqds.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).
 

Detailed Description

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.