Module rulinalg::matrix::decomposition

Decompositions for matrices.

This module houses the decomposition API of rulinalg. A decomposition - or factorization - of a matrix is an ordered set of factors such that when multiplied reconstructs the original matrix. The Decomposition trait encodes this property.

The decomposition API

Decompositions in rulinalg are in general modeled after the following:

1. Given an appropriate matrix, an opaque decomposition object may be computed which internally stores the factors in an efficient and appropriate format.
2. In general, the factors may not be immediately available as distinct matrices after decomposition. If the user desires the explicit matrix factors involved in the decomposition, the user must unpack the decomposition.
3. Before unpacking the decomposition, the decomposition data structure in question may offer an API that provides efficient implementations for some of the most common applications of the decomposition. The user is encouraged to use the decomposition-specific API rather than unpacking the decompositions whenever possible.

For a motivating example that explains the rationale behind this design, let us consider the typical LU decomposition with partial pivoting. In this case, given a square invertible matrix A, one may find matrices P, L and U such that PA = LU. Here P is a permutation matrix, L is a lower triangular matrix and U is an upper triangular matrix.

Once the decomposition has been obtained, one of its applications is the efficient solution of multiple similar linear systems. Consider that while computing the LU decomposition requires O(n³) floating point operations, the solution to the system Ax = b can be computed in O(n²) floating point operations if the LU decomposition has already been obtained. Since the right-hand side b has no bearing on the LU decomposition, it follows that one can efficiently solve this system for any b.

It turns out that the matrices L and U can be stored compactly in the space of a single matrix. Indeed, this is how PartialPivLu stores the LU decomposition internally. This allows rulinalg to provide the user with efficient implementations of common applications for the LU decomposition. However, the full matrix factors are easily available to the user by unpacking the decomposition.

Available decompositions

The decompositions API is a work in progress.

Currently, only a portion of the available decompositions in rulinalg are available through the decomposition API. Please see the Matrix API for the old decomposition implementations that have yet not been implemented within this framework.

Decomposition	Matrix requirements	Supported features
PartialPivLu	Square, invertible	Linear system solving Matrix inverse Determinant computation
FullPivLu	Square matrices	Linear system solving Matrix inverse Determinant computation Rank computation
Cholesky	Square, symmetric positive definite	Linear system solving Matrix inverse Determinant computation
HouseholderQr	Any matrix

Structs

Cholesky

Cholesky decomposition.

FullPivLu

LU decomposition with complete pivoting.

HouseholderComposition

An efficient representation for a composition of Householder transformations.

HouseholderQr

QR decomposition based on Householder reflections.

LUP

Result of unpacking an instance of PartialPivLu.

LUPQ

Result of unpacking an instance of FullPivLu.

PartialPivLu

LU decomposition with partial pivoting.

QR

The result of unpacking a QR decomposition.

ThinQR

The result of computing a thin (or reduced) QR decomposition.

Traits

Decomposition

Base trait for decompositions.