GF2::LUDecompose — Construction

Construct an`LUDecompose` object which performs the LU decomposition of an input square bit-matrix.

Class constructor

LUDecompose(const GF2::Matrix &A);

Factory function

LUDecompose lu_decompose(const GF2::Matrix &A );

These construct an LUDecompose object for the square bit-matrix \(A\).

On construction the object finds a unit lower triangular bit-matrix \(L\), an upper triangular bit-matrix \(U\), and a permutation matrix \(P\) such that

\[P \cdot A = L \cdot U.\]

In practice, the \(L\) and \(U\) matrices are compactly packed into a single bit-matrix that is the same size as \(A\). The permutation matrix \(P\) is also stored in a very compact form — see row_swaps.

The decomposition always works even if \(A\) is singular but of course some of the other LUDecompose methods will not in that case.

There are generalizations of the LU decomposition that handle rectangular matrices but we have not implemented those as yet.

If \(A\) is \(n \times n\) then construction is an \(\mathcal{O}(n^3)\) operation (though due to the nature of \(\mathbb{F}_2\) things are done in blocks at a time). There are potentially sub-cubic ways of doing this work using various block-iterative methods that are not implemented here yet.

Example

#include <GF2/GF2.h>
int main()
{
    std::size_t m = 12;

    auto A = GF2::Matrix<>::random(m);
    auto lu = GF2::lu_decompose(A);
    auto L = lu.L();
    auto U = lu.U();
    std::cout << "Matrix A, L, and U:\n";
    GF2::print(A, L, U);
    std::cout << "A is singular? " << (lu.singular() ? "YES" : "NO") << "\n";

    // Check that P.A = L.U
    auto PA = A;
    lu.permute(PA);
    auto LU = GF2::dot(L,U);
    std::cout << "P.A and L.U:\n";
    GF2::print(PA, LU);
    std::cout << "P.A == L.U? " << (PA == LU ? "YES" : "NO") << "\n";
}

Output (depends on the values of the random inputs)

Matrix A, L, and U:
001111101100    100000000000    111001010000
111001010000    110000000000    011001100000
111000011010    001000000000    001111101100
000111100101    000100000000    000111100101
100000110000    101010000000    000010111010
110110101110    100001000000    000001001010
110100000110    101000100000    000000010010
011100110101    011100010000    000000010100
101101101111    111010001000    000000001001
010101110011    011011001100    000000000110
010001111101    010110001010    000000000011
001001000011    001101000001    000000000000
A is singular? YES
P.A and L.U:
111001010000    111001010000
100000110000    100000110000
001111101100    001111101100
000111100101    000111100101
110100000110    110100000110
111000011010    111000011010
110110101110    110110101110
010001111101    010001111101
101101101111    101101101111
010101110011    010101110011
011100110101    011100110101
001001000011    001001000011
P.A == L.U? YES