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

The symmetric indefinite factorisation A = L D Lᵀ (or L D Lᴴ) of a symmetric or Hermitian matrix with Bunch and Kaufman's diagonal pivoting, D block diagonal with blocks of order 1 and 2, as LAPACK's sytrf and hetrf (by panels, lasyf and lahef, from order 384; sytf2 and hetf2 below) and as scipy.linalg.ldl returns it. More...

#include <cmath>
#include <complex>
#include <concepts>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>
#include "factorizations.hpp"
Include dependency graph for ldl.hpp:

Go to the source code of this file.

Classes

class  numerical::ldl_decomposition< T >
 The symmetric indefinite factorisation of a symmetric or Hermitian matrix, as scipy.linalg.ldl: A = L D Lᴴ (Hermitian) or A = L D Lᵀ (symmetric), Bunch and Kaufman's diagonal pivoting (LAPACK's sytrf, hetrf: by panels of 64 columns from order 384, their trailing update one matrix product; the unblocked sytf2, hetf2 below it and for the last columns) on the lower triangle, or on the upper one (lower = false, L then upper triangular); D block diagonal with blocks of order 1 and 2; L with a unit diagonal once its rows are permuted (permutation), as SciPy returns them. More...
 

Namespaces

namespace  numerical
 The NumericAL public API.
 
namespace  numerical::detail
 

Functions

double numerical::detail::pivot_size (double x)
 LAPACK's measure of a real entry, |x|.
 
double numerical::detail::pivot_size (const std::complex< double > &z)
 LAPACK's measure of a complex entry, CABS1: |Re z| + |Im z|.
 
double numerical::detail::diagonal_size (double x, bool)
 A real diagonal entry's measure, |x|, whatever hermitian.
 
double numerical::detail::diagonal_size (const std::complex< double > &z, bool hermitian)
 A complex diagonal entry's measure: |Re z| for a Hermitian matrix (hetf2), CABS1 for a symmetric one (sytf2).
 
double numerical::detail::conjugated_if (double x, bool)
 A real x as it is.
 
std::complex< double > numerical::detail::conjugated_if (const std::complex< double > &z, bool hermitian)
 z's conjugate for a Hermitian matrix, z for a symmetric one.
 
double numerical::detail::diagonal_kept (double x, bool)
 A real x as it is.
 
std::complex< double > numerical::detail::diagonal_kept (const std::complex< double > &z, bool hermitian)
 A Hermitian matrix's diagonal entry z taken as real (hetf2 ignores its imaginary part), a symmetric one's as it is.
 
template<typename T >
void numerical::detail::symmetric_rank_one (buffer< T > &a, std::size_t n, std::size_t k, buffer< T > &w)
 The trailing matrix's update by a pivot of order 1 at k, as sytf2 (syr, then L's column scaled): A ← A − x xᵀ / d on and below the diagonal, x / d into column k; the arithmetic of T. Row by row (a is row-major), each entry's one operation as syr's column by column: the factors −x_j / d first, in w (n entries).
 
void numerical::detail::hermitian_rank_one (buffer< std::complex< double > > &a, std::size_t n, std::size_t k, buffer< std::complex< double > > &w)
 As symmetric_rank_one for a Hermitian matrix, as hetf2 (her): d real, A ← A − x xᴴ / d, the diagonal kept real.
 
template<typename T >
void numerical::detail::symmetric_rank_two (buffer< T > &a, std::size_t n, std::size_t k, buffer< T > &w)
 The trailing matrix's update by a pivot of order 2 at rows k and k + 1, as sytf2: D21 scaled out, W = [x y] D⁻¹ from D11 / D21, D22 / D21 and t = 1 / (D11 D22 / D21² − 1), A ← A − [x y] Wᵀ, W into the two columns; the arithmetic of T. Row by row, W first, in w (2n entries), each row's x and y read before its two entries of W replace them.
 
void numerical::detail::hermitian_rank_two (buffer< std::complex< double > > &a, std::size_t n, std::size_t k, buffer< std::complex< double > > &w)
 As symmetric_rank_two for a Hermitian matrix, as hetf2: |D21| scaled out in real arithmetic, the conjugates where Aᴴ has them, the diagonal kept real.
 
void numerical::detail::eliminate_pivot (buffer< double > &a, std::size_t n, std::size_t k, std::size_t step, bool, buffer< double > &w)
 A real matrix's update by a pivot of order 1 or 2 (step), sytf2's whatever hermitian.
 
void numerical::detail::eliminate_pivot (buffer< std::complex< double > > &a, std::size_t n, std::size_t k, std::size_t step, bool hermitian, buffer< std::complex< double > > &w)
 A complex matrix's update by a pivot of order 1 or 2 (step): hetf2's if hermitian, else sytf2's.
 
template<typename T >
std::vector< std::ptrdiff_t > numerical::detail::bunch_kaufman_lower (buffer< T > &a, std::size_t n, bool hermitian, bool last_on_ties, std::size_t from=0)
 Bunch and Kaufman's factorisation of the lower triangle of a (n × n, row-major; entries (i, j) with i ≥ j read and written), as LAPACK's sytf2 and hetf2 on the lower triangle: at each step a pivot of order 1 or 2 chosen with α = (1 + √17) / 8, the rows and columns exchanged, the trailing matrix updated by the pivot's rank-1 or rank-2 correction, L's columns left below the pivot and D on and next to the diagonal. The largest entry of a column is its first (idamax) or, where last_on_ties, its last of equal size: the order of the upper triangle's search when a holds it reversed. From column from, the columns before it factorised already (bunch_kaufman_blocked_lower's last columns, as sytrf leaves them to sytf2).
 
template<typename T >
std::size_t numerical::detail::factor_ldl_panel (buffer< T > &a, std::size_t n, std::size_t k0, bool hermitian, bool last_on_ties, buffer< T > &w, std::vector< std::ptrdiff_t > &pivots)
 One panel of bunch_kaufman_blocked_lower from column k0, as LAPACK's lasyf and lahef on the lower triangle: each column brought up to date by the panel's earlier ones (A − L Wᴴ, W = L D in w, n × ldl_block row-major, conjugated for a Hermitian matrix) before its pivot is chosen as bunch_kaufman_lower chooses it, the trailing block left as it was but for the exchanges of its rows and columns, its update deferred. ldl_block − 1 columns, or ldl_block where the last is a block of order 2; more than ldl_block columns remain.
 
template<typename T >
std::vector< std::ptrdiff_t > numerical::detail::bunch_kaufman_blocked_lower (buffer< T > &a, std::size_t n, bool hermitian, bool last_on_ties)
 bunch_kaufman_lower by panels, as LAPACK's sytrf and hetrf on the lower triangle: each panel of ldl_block columns factorised with its updates deferred (factor_ldl_panel), then the trailing block's lower triangle less L₂₁ W₂₁ᴴ in one product, a real one of the kernel's size on the triangle's tiles alone, otherwise by bands of rows each to the diagonal; the last ldl_block columns or fewer by bunch_kaufman_lower's steps.
 

Variables

constexpr std::size_t numerical::detail::ldl_block {64}
 The columns of one panel of the blocked factorisation (bunch_kaufman_blocked_lower), LAPACK's nb for sytrf.
 
constexpr std::size_t numerical::detail::ldl_blocked_least {384}
 The order from which bunch_kaufman_lower runs by panels (bunch_kaufman_blocked_lower): below it the panels' columns, each brought up to date one dot product at a time, cost about what the unblocked steps' updates do (arm64, real: order 256 1.08× their time under Clang and 1.25× under GCC, 384 0.74× and 0.78×; complex 0.55× and 0.76× at 256).
 

Detailed Description

The symmetric indefinite factorisation A = L D Lᵀ (or L D Lᴴ) of a symmetric or Hermitian matrix with Bunch and Kaufman's diagonal pivoting, D block diagonal with blocks of order 1 and 2, as LAPACK's sytrf and hetrf (by panels, lasyf and lahef, from order 384; sytf2 and hetf2 below) and as scipy.linalg.ldl returns it.

Definition in file ldl.hpp.