NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes | List of all members
numerical::cholesky_decomposition< T > Class Template Reference

A Cholesky factorisation A = L Lᴴ of a Hermitian positive-definite matrix. More...

#include <factorizations.hpp>

Public Member Functions

 cholesky_decomposition (const matrix< T > &a)
 Factorises a.
 
 cholesky_decomposition (matrix< T > &&a)
 Factorises a in its own storage, an expiring matrix's elements taken over: no copy of them.
 
matrix< T > lower () const &
 The lower-triangular factor L (with L Lᴴ == A).
 
matrix< T > lower () &&
 The lower-triangular factor L, moved out of an expiring decomposition.
 
vector< T > solve (const vector< T > &b) const
 Solves A x = b via L y = b then Lᴴ x = y.
 
matrix< T > solve (const matrix< T > &b) const
 Solves A X = B for every column of b at once: L Y = B, then Lᴴ X = Y, row by row, each row of the solution its column's terms in solve's order (so each column solve's bits), a row of terms at a time over the columns; the threads share the columns by slices of 8 and more.
 
T determinant () const
 The determinant — the product of the squared diagonal of L (real, positive), its partial products kept among the doubles (detail::scaled_product).
 
double reciprocal_condition (double one_norm) const
 The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of the factorised matrix, as LAPACK's pocon: ‖A⁻¹‖₁ estimated from L (Hager's method, a few solves of n² each), so within a small factor of the exact; the caller gives ‖A‖₁. Under the machine epsilon, a solve's answer may have no correct digit.
 

Private Member Functions

void factorize ()
 
void factor_rows_together (std::size_t i, std::size_t k0)
 The columns [k0, i) of the detail::cholesky_diagonal_rows rows from i, together: each element depends on its own row's earlier columns and on the rows above i alone, so the rows' sums are chains of their own, where row by row each term waited on the last. Each element is factor_row's, its terms in the same order. The rows' loops unrolled: rolled, GCC kept the sums in memory (order 33 on one arm64 core: 8.3 µs, against 2.8 unrolled and 4.6 row by row).
 
void factor_row (std::size_t i, std::size_t k0, std::size_t first, std::size_t last)
 Row i of L in the columns [first, last), the terms of the columns before k0 already subtracted: the unblocked step, L[i][j] = (A[i][j] − Σₖ L[i][k]·conj(L[j][k])) / L[j][j] over k ∈ [k0, j).
 
void factor_rows_below (std::size_t k0, std::size_t end, buffer< T > &minus_adjoint)
 The rows below the panel [k0, end), L₂₁ = A₂₁ L₁₁⁻ᴴ: chunks of detail::cholesky_rows rows in parallel, each in a column-major copy where column j takes L[i][j] −= L[i][k]·conj(L[j][k]) for k ascending, then the division by L[j][j], for every row of the chunk at once along the column: by sub-blocks of 16 columns, the terms of the sub-blocks before one through the matrix product's plain loop, its own column by column (detail::subtract_product), each element's terms in ascending order, each fused as the column step fuses it, so the unblocked step's arithmetic, in its order (one core of six AVX2, order 1000: 4.95 → 3.95 ms; all column by column, the solve took 37 % of the factorisation for a tenth of its work); row by row, each sum waited on its last addition. Each chunk also writes its columns of minus_adjoint (−L₂₁ᴴ, row-major), the trailing update's right operand, which a copy on one thread after it took 15 to 20 % of the factorisation on six x86-64 cores (order 1024 to 2048).
 
void update_trailing (std::size_t k0, std::size_t end, const buffer< T > &minus_adjoint, buffer< T > &packing)
 A22 += L21 (−L21ᴴ), by tiles of detail::cholesky_update_columns columns and detail::cholesky_update_rows rows on and below the diagonal blocks (the upper triangle, never read, takes what falls in a block past the diagonal), in parallel, each element's terms in the order of one product, L₂₁ read in the factor and minus_adjoint as factor_rows_below wrote it: the sign on the right, (−a) b being a (−b) exactly, so no negated copy of L₂₁ (one AVX2 core, order 100: 48 → 45 µs, 300 −4 %). L₂₁ is packed once, in packing, for the tile the products run on (detail::pack_left), and every tile reads its rows there (a tile packed its own, again for each block of columns: 8 % of the factorisation on one AVX2 core at order 1000): so a tile's rows start at a multiple of the tile's slivers, a few rows above the diagonal block.
 

Private Attributes

std::size_t n_
 The matrix order.
 
std::size_t block_ {detail::cholesky_block_for(n_)}
 The panel width.
 
buffer< T > lower_
 The lower-triangular factor L, row-major (upper triangle zero).
 

Detailed Description

template<field T>
class numerical::cholesky_decomposition< T >

A Cholesky factorisation A = L Lᴴ of a Hermitian positive-definite matrix.

Template Parameters
TThe scalar element type (a field: double, std::complex<double>, …).

L is lower-triangular with a real, positive diagonal. Only the lower triangle of a is read, so a is assumed Hermitian (symmetric, for a real scalar); the factorisation is about twice as cheap as an LU for this special case and cannot be singular. A matrix that is not positive-definite throws not_positive_definite_error.

Definition at line 2606 of file factorizations.hpp.

Constructor & Destructor Documentation

◆ cholesky_decomposition() [1/2]

template<field T>
numerical::cholesky_decomposition< T >::cholesky_decomposition ( const matrix< T > &  a)
inlineexplicit

Factorises a.

Parameters
[in]aThe Hermitian positive-definite matrix, its lower triangle alone read.
Exceptions
dimension_errorIf a is not square.
non_finite_errorIf an entry of its lower triangle is infinite or NaN.
not_positive_definite_errorIf a is not positive-definite.

Definition at line 2616 of file factorizations.hpp.

◆ cholesky_decomposition() [2/2]

template<field T>
numerical::cholesky_decomposition< T >::cholesky_decomposition ( matrix< T > &&  a)
inlineexplicit

Factorises a in its own storage, an expiring matrix's elements taken over: no copy of them.

Parameters
[in]aThe Hermitian positive-definite matrix, its lower triangle alone read.
Exceptions
dimension_errorIf a is not square.
non_finite_errorIf an entry of its lower triangle is infinite or NaN.
not_positive_definite_errorIf a is not positive-definite.

Definition at line 2627 of file factorizations.hpp.

Member Function Documentation

◆ determinant()

template<field T>
T numerical::cholesky_decomposition< T >::determinant ( ) const
inline

The determinant — the product of the squared diagonal of L (real, positive), its partial products kept among the doubles (detail::scaled_product).

Definition at line 2732 of file factorizations.hpp.

◆ factor_row()

template<field T>
void numerical::cholesky_decomposition< T >::factor_row ( std::size_t  i,
std::size_t  k0,
std::size_t  first,
std::size_t  last 
)
inlineprivate

Row i of L in the columns [first, last), the terms of the columns before k0 already subtracted: the unblocked step, L[i][j] = (A[i][j] − Σₖ L[i][k]·conj(L[j][k])) / L[j][j] over k ∈ [k0, j).

Exceptions
not_positive_definite_errorAt a diagonal that is not positive.

Definition at line 2824 of file factorizations.hpp.

◆ factor_rows_below()

template<field T>
void numerical::cholesky_decomposition< T >::factor_rows_below ( std::size_t  k0,
std::size_t  end,
buffer< T > &  minus_adjoint 
)
inlineprivate

The rows below the panel [k0, end), L₂₁ = A₂₁ L₁₁⁻ᴴ: chunks of detail::cholesky_rows rows in parallel, each in a column-major copy where column j takes L[i][j] −= L[i][k]·conj(L[j][k]) for k ascending, then the division by L[j][j], for every row of the chunk at once along the column: by sub-blocks of 16 columns, the terms of the sub-blocks before one through the matrix product's plain loop, its own column by column (detail::subtract_product), each element's terms in ascending order, each fused as the column step fuses it, so the unblocked step's arithmetic, in its order (one core of six AVX2, order 1000: 4.95 → 3.95 ms; all column by column, the solve took 37 % of the factorisation for a tenth of its work); row by row, each sum waited on its last addition. Each chunk also writes its columns of minus_adjoint (−L₂₁ᴴ, row-major), the trailing update's right operand, which a copy on one thread after it took 15 to 20 % of the factorisation on six x86-64 cores (order 1024 to 2048).

Definition at line 2859 of file factorizations.hpp.

◆ factor_rows_together()

template<field T>
void numerical::cholesky_decomposition< T >::factor_rows_together ( std::size_t  i,
std::size_t  k0 
)
inlineprivate

The columns [k0, i) of the detail::cholesky_diagonal_rows rows from i, together: each element depends on its own row's earlier columns and on the rows above i alone, so the rows' sums are chains of their own, where row by row each term waited on the last. Each element is factor_row's, its terms in the same order. The rows' loops unrolled: rolled, GCC kept the sums in memory (order 33 on one arm64 core: 8.3 µs, against 2.8 unrolled and 4.6 row by row).

Definition at line 2795 of file factorizations.hpp.

◆ factorize()

template<field T>
void numerical::cholesky_decomposition< T >::factorize ( )
inlineprivate

Definition at line 2756 of file factorizations.hpp.

◆ lower() [1/2]

template<field T>
matrix< T > numerical::cholesky_decomposition< T >::lower ( ) &&
inline

The lower-triangular factor L, moved out of an expiring decomposition.

Definition at line 2645 of file factorizations.hpp.

◆ lower() [2/2]

template<field T>
matrix< T > numerical::cholesky_decomposition< T >::lower ( ) const &
inline

The lower-triangular factor L (with L Lᴴ == A).

Definition at line 2639 of file factorizations.hpp.

◆ reciprocal_condition()

template<field T>
double numerical::cholesky_decomposition< T >::reciprocal_condition ( double  one_norm) const
inline

The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of the factorised matrix, as LAPACK's pocon: ‖A⁻¹‖₁ estimated from L (Hager's method, a few solves of n² each), so within a small factor of the exact; the caller gives ‖A‖₁. Under the machine epsilon, a solve's answer may have no correct digit.

Parameters
[in]one_norm‖A‖₁, the largest column sum of moduli of A.
Returns
The estimate: 1 for an empty matrix; 0 for a zero one_norm or an estimate that overflows.

Definition at line 2745 of file factorizations.hpp.

◆ solve() [1/2]

template<field T>
matrix< T > numerical::cholesky_decomposition< T >::solve ( const matrix< T > &  b) const
inline

Solves A X = B for every column of b at once: L Y = B, then Lᴴ X = Y, row by row, each row of the solution its column's terms in solve's order (so each column solve's bits), a row of terms at a time over the columns; the threads share the columns by slices of 8 and more.

Parameters
[in]bThe right-hand sides (n × k).
Returns
X (n × k).
Exceptions
dimension_errorIf b's row count differs from the matrix.

Definition at line 2688 of file factorizations.hpp.

◆ solve() [2/2]

template<field T>
vector< T > numerical::cholesky_decomposition< T >::solve ( const vector< T > &  b) const
inline

Solves A x = b via L y = b then Lᴴ x = y.

Parameters
[in]bThe right-hand side.
Returns
The solution x.
Exceptions
dimension_errorIf b's size differs from the matrix.

Definition at line 2656 of file factorizations.hpp.

◆ update_trailing()

template<field T>
void numerical::cholesky_decomposition< T >::update_trailing ( std::size_t  k0,
std::size_t  end,
const buffer< T > &  minus_adjoint,
buffer< T > &  packing 
)
inlineprivate

A22 += L21 (−L21ᴴ), by tiles of detail::cholesky_update_columns columns and detail::cholesky_update_rows rows on and below the diagonal blocks (the upper triangle, never read, takes what falls in a block past the diagonal), in parallel, each element's terms in the order of one product, L₂₁ read in the factor and minus_adjoint as factor_rows_below wrote it: the sign on the right, (−a) b being a (−b) exactly, so no negated copy of L₂₁ (one AVX2 core, order 100: 48 → 45 µs, 300 −4 %). L₂₁ is packed once, in packing, for the tile the products run on (detail::pack_left), and every tile reads its rows there (a tile packed its own, again for each block of columns: 8 % of the factorisation on one AVX2 core at order 1000): so a tile's rows start at a multiple of the tile's slivers, a few rows above the diagonal block.

Definition at line 2939 of file factorizations.hpp.

Member Data Documentation

◆ block_

template<field T>
std::size_t numerical::cholesky_decomposition< T >::block_ {detail::cholesky_block_for(n_)}
private

The panel width.

Definition at line 2984 of file factorizations.hpp.

◆ lower_

template<field T>
buffer<T> numerical::cholesky_decomposition< T >::lower_
private

The lower-triangular factor L, row-major (upper triangle zero).

Definition at line 2985 of file factorizations.hpp.

◆ n_

template<field T>
std::size_t numerical::cholesky_decomposition< T >::n_
private

The matrix order.

Definition at line 2983 of file factorizations.hpp.


The documentation for this class was generated from the following file: