Struct rulinalg::matrix::decomposition::HouseholderQr

pub struct HouseholderQr<T> { /* private fields */ }

QR decomposition based on Householder reflections.

For any m x n matrix A, there exist an m x m orthogonal matrix Q and an m x n upper trapezoidal (triangular) matrix R such that

A = QR.

HouseholderQr holds the result of a QR decomposition procedure based on Householder reflections. The full factors Q and R can be acquired by calling unpack(). However, it turns out that the orthogonal factor Q can be represented much more efficiently than as a full m x m matrix. For this purpose, the q() method provides access to an instance of HouseholderComposition which allows the efficient application of the (implicit) Q matrix.

For some applications, it is sufficient to compute a thin (or reduced) QR decomposition. The thin QR decomposition can be obtained by calling unpack_thin() on the decomposition object.

Examples

use rulinalg::matrix::Matrix;
use rulinalg::matrix::decomposition::{
    Decomposition, HouseholderQr, QR
};

let a = matrix![ 3.0,  2.0;
                -5.0,  1.0;
                 4.0, -2.0 ];
let identity = Matrix::identity(3);

let qr = HouseholderQr::decompose(a.clone());
let QR { q, r } = qr.unpack();

// Check that `Q` is orthogonal
assert_matrix_eq!(&q * q.transpose(), identity, comp = float);
assert_matrix_eq!(q.transpose() * &q, identity, comp = float);

// Check that `A = QR`
assert_matrix_eq!(q * r, a, comp = float);

Internal storage format

Upon decomposition, the HouseholderQr struct takes ownership of the matrix and repurposes its storage to compactly store the factors Q and R. In addition, a vector tau of size min(m, n) holds auxiliary information about the Householder reflectors which together constitute the Q matrix.

Specifically, given an input matrix A, the upper triangular factor R is stored in A_ij for j >= i. The orthogonal factor Q is implicitly stored as the composition of p := min(m, n) Householder reflectors Q_i, such that

Q = Q_1 * Q_2 * ... * Q_p.

Each such Householder reflection Q_i corresponds to a transformation of the form (using MATLAB-like colon notation)

Q_i [1:(i-1), 1:(i-1)] = I
Q_i [i:m, i:m] = I - τ_i * v_i * transpose(v_i)

where I denotes the identity matrix of appropriate size, v_i is the Householder vector normalized in such a way that its first element is implicitly 1 (and thus does not need to be stored) and τ_i is an appropriate scale factor. Each vector v_i has length m - i + 1, and since the first element does not need to be stored, each v_i can be stored in column i of the matrix A.

The scale factors τ_i are stored in a separate vector.

This storage scheme should be compatible with LAPACK, although this has yet to be put to the test. For the same reason, the internal storage is not exposed in the public API at this point.

Implementations

impl<T> HouseholderQr<T>where
    T: Float,

pub fn decompose(matrix: Matrix<T>) -> HouseholderQr<T>

Decomposes the given matrix into implicitly stored factors Q and R as described in the struct documentation.

pub fn q(&self) -> HouseholderComposition<'_, T>

Returns the orthogonal factor Q as an instance of a HouseholderComposition operator.

pub fn unpack_thin(self) -> ThinQR<T>

Computes the thin (or reduced) QR decomposition.

If m <= n, the thin QR decomposition coincides with the usual QR decomposition. See ThinQR for details.

Examples

use rulinalg::matrix::decomposition::{HouseholderQr, ThinQR};
let x = matrix![3.0, 2.0;
                1.0, 2.0;
                4.0, 5.0];
let ThinQR { q1, r1 } = HouseholderQr::decompose(x).unpack_thin();

Trait Implementations

impl<T: Clone> Clone for HouseholderQr<T>

fn clone(&self) -> HouseholderQr<T>

Returns a copy of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for HouseholderQr<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Float> Decomposition for HouseholderQr<T>

type Factors = QR<T>

The type representing the ordered set of factors that when multiplied yields the decomposed matrix.

fn unpack(self) -> QR<T>

Extract the individual factors from this decomposition.