gf2::BitLU< Word >

The BitLU class provides the LU decomposition for bit-matrices. More...

#include <BitLU.h>

Public Member Functions
	BitLU (const BitMat< Word > &A)
	Constructs the LU decomposition object for a square matrix A.
constexpr usize	rank () const
	Returns the rank of the matrix.
constexpr bool	is_singular () const
	Returns true if the underlying matrix is singular (i.e. rank deficient).
constexpr bool	determinant () const
	Returns the value of the determinant of the underlying matrix as true or false for 1 or 0.
constexpr const BitMat< Word > &	LU () const
	Read-only access to the LU form of the bit-matrix where A -> [L\U].
constexpr BitMat< Word >	L () const
	Returns the unit lower triangular matrix L in the LU decomposition.
constexpr BitMat< Word >	U () const
	Returns the upper triangular matrix U in the LU decomposition.
constexpr const std::vector< usize > &	swaps () const
	Returns a reference to the row swap instructions in LAPACK form.
std::vector< usize >	permutation_vector () const
	Returns the permutation matrix as a vector of showing the index positions of the non-zero entries.
constexpr void	permute (BitMat< Word > &B) const
	Permutes the rows of the input matrix B in-place using our row-swap instruction vector.
constexpr void	permute (BitVec< Word > &b) const
	Permute the rows of the input vector b in-place using our row-swap instruction vector.
std::optional< BitVec< Word > >	operator() (const BitVec< Word > &b) const
	Solves the linear system A.x_for = b for any b where A is the matrix used to construct the BitLU object.
std::optional< BitMat< Word > >	operator() (const BitMat< Word > &B) const
	Solves the linear system A.X_for = B for any B where A is the matrix used to construct the BitLU object.
std::optional< BitMat< Word > >	inverse () const
	Returns the inverse of the matrix A as a full independent bit-matrix or std::nullopt if the matrix is singular.

Detailed Description

template<unsigned_word Word>
class gf2::BitLU< Word >

The BitLU class provides the LU decomposition for bit-matrices.

The class also has methods for solving systems of linear equations over GF(2) and for inverting square bit-matrices.

Formally, LU decomposition of A is \(P \cdot A = L \cdot U\) where \(P\) is a permutation matrix, \(L\) is a unit lower triangular matrix and \(U\) is an upper triangular matrix.

The L and U triangles can be efficiently packed into a single bit-matrix of the same size as A

P is a permutation of the identity matrix with one non-zero entry per row. In practice, we just need to store the locations of those entries as some form of vector.

Note

There are generalisations of the LU decomposition for non-square matrices but those are not considered yet.

See also

Finite field arithmetic

Constructor & Destructor Documentation

BitLU()

template<unsigned_word Word>

gf2::BitLU< Word >::BitLU ( const BitMat< Word > & A )

inline

Constructs the LU decomposition object for a square matrix A.

On construction, this method computes a unit lower triangular matrix L, an upper triangular matrix U, and a permutation matrix P such that P.A = L.U. The L and U triangles are efficiently packed into a single matrix and P is stored as a vector of row swap instructions.

The construction works even if A is singular, though the solver methods will not.

If A is n x n, then the construction takes O(n^3) operations. There are block iterative methods that can reduce that to a sub-cubic count but they are not implemented here. Of course, the method works on whole words or bit elements at a time so is very efficient even without those enhancements.

Note

Panics if the A matrix is not square. There are generalisations of the LU decomposition for non-square matrices but those are not considered yet.

Example (checks that LU = PA for a random matrix A)

auto A = BitMat<u8>::random(100, 100);
auto lu = A.LU();
auto LU = lu.L() * lu.U();
auto PA = A;
lu.permute(PA);
assert_eq(PA, LU);

Member Function Documentation

inverse()

template<unsigned_word Word>

std::optional< BitMat< Word > > gf2::BitLU< Word >::inverse ( ) const

inline

Returns the inverse of the matrix A as a full independent bit-matrix or std::nullopt if the matrix is singular.

Example

auto A = BitMat<>::left_rotation(100, 1);
BitLU lu{A};
auto A_inv = lu.inverse().value();
assert_eq(A_inv, BitMat<>::right_rotation(100, 1));

operator()() [1/2]

template<unsigned_word Word>

std::optional< BitMat< Word > > gf2::BitLU< Word >::operator() ( const BitMat< Word > & B ) const

inline

Solves the linear system A.X_for = B for any B where A is the matrix used to construct the BitLU object.

This methods returns std::nullopt if the matrix is singular.

Each column of X is a solution to the linear system A.x_for = b where b is the corresponding column of B.

Note

This method panics if the bit-matrix B has a different number of rows than the number of row swap instructions.

Example

auto A = BitMat<>::left_rotation(100, 5);
auto B = BitMat<>::random(100, 12);
auto lu = A.LU();
auto X = lu(B).value();
assert_eq(A * X, B);

operator()() [2/2]

template<unsigned_word Word>

std::optional< BitVec< Word > > gf2::BitLU< Word >::operator() ( const BitVec< Word > & b ) const

inline

Solves the linear system A.x_for = b for any b where A is the matrix used to construct the BitLU object.

This methods returns std::nullopt if the matrix is singular.

Note

This method panics if the bit-matrix b has a different number of rows than the number of row swap instructions.

Example

auto n = 100uz;
auto A = BitMat<>::left_rotation(n, 1);
auto lu = A.LU();
auto b = BitVec<>::random(n);
auto x = lu(b).value();
assert_eq(A * x, b);

permutation_vector()

template<unsigned_word Word>

std::vector< usize > gf2::BitLU< Word >::permutation_vector ( ) const

inline

Returns the permutation matrix as a vector of showing the index positions of the non-zero entries.

A permutation matrix is just some row permutation of the identity matrix, so it has a single non-zero, 1, entry in each row or column. You don't need to store the entire matrix but instead store the locations of those 1's.

In the literature, the permutation vector is often given as a permutation of the index vector. For example, the permutation vector [0,2,1,4,3] tells you that elements/rows 1 and 2 are swapped, as are elements/rows 3 and 4. This form is easy to interpret at a glance and is returned by the P_vector method.

See the swaps method for an alternative form of the permutation matrix that is more convenient for executing the permutations in place.

permute() [1/2]

template<unsigned_word Word>

void gf2::BitLU< Word >::permute ( BitMat< Word > & B ) const

inlineconstexpr

Permutes the rows of the input matrix B in-place using our row-swap instruction vector.

Note

This method panics if the dimensions of B and the row-swap instruction vector do not match.

permute() [2/2]

template<unsigned_word Word>

void gf2::BitLU< Word >::permute ( BitVec< Word > & b ) const

inlineconstexpr

Permute the rows of the input vector b in-place using our row-swap instruction vector.

Note

This method panics if the dimensions of b and the row-swap instruction vector do not match.

rank()

template<unsigned_word Word>

usize gf2::BitLU< Word >::rank ( ) const

inlineconstexpr

Returns the rank of the matrix.

Example

auto A = BitMat<>::left_rotation(100, 1);
auto lu = A.LU();
assert_eq(lu.rank(), 100);

swaps()

template<unsigned_word Word>

const std::vector< usize > & gf2::BitLU< Word >::swaps ( ) const

inlineconstexpr

Returns a reference to the row swap instructions in LAPACK form.

A permutation matrix is just some row permutation of the identity matrix, so it has a single non-zero, 1, entry in each row or column. You don't need to store the entire matrix but instead store the locations of those 1's.

In the literature, the permutation vector is often given as a permutation of the index vector. For example, the permutation vector [0,2,1,4,3] tells you that elements/rows 1 and 2 are swapped, as are elements/rows 3 and 4. This form is easy to interpret at a glance. However, it is tedious to use as a guide to actually executing the permutations in place.

The LAPACK style swaps vector is an alternate, equally compact, form of the permutation matrix. Our previous example becomes [0,2,2,4,4]. This is interpreted as follows:

• No swap for row 0.
• Swap row 1 with row 2.
• No swap for row 2.
• Swap row 3 with row 4.
• No swap for row 4.