bit::lu — Constructors

Construct a lu object either directly or using a factory function.
The object performs the LU decomposition of an input square bit-matrix.

lu(const 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, we pack the \(L\) and \(U\) matrices into a single bit-matrix of the same size as \(A\). The permutation matrix \(P\) is also stored compactly — see lu::permute.

The decomposition always works even if \(A\) is singular, but other lu methods will not.

There are generalizations of the LU decomposition that handle rectangular matrices, but we have not implemented those 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 sub-cubic ways of doing this work using various block-iterative methods, but those methods have not been implemented here yet.

Example

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

    auto A = bit::matrix<>::random(m);
    auto lu = bit::lu(A);
    auto L = lu.L();
    auto U = lu.U();
    std::cout << "bit::matrix A, L, and U:\n";
    bit::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 = bit::dot(L,U);
    std::cout << "P.A and L.U:\n";
    bit::print(PA, LU);
    std::cout << "P.A == L.U? " << (PA == LU ? "YES" : "NO") << "\n";
}

Output (depends on the values of the random inputs)

bit::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
Back to top