Struct M4riTable 

pub(crate) struct M4riTable {
    rows: Vec<usize>,
    columns: Vec<LimbBitIndexPair>,
    data: Vec<u64>,
    min_limb: usize,
}

M4RI works as follows — first row reduce k rows using the naive algorithm. We then construct a table of all 2^k linear combinations of these rows. This can be done in O(2^k) time. We then use this table to reduce the remaining rows, so that each row takes O(num_columns) time, which reduces the time taken by a factor of k x density.

Since we are likely to run into empty rows when doing row reduction, what we do in practice is that we keep reducing rows until we collect k of them. Whenever we find a row, we record it with M4riTable::add. We only record the row number and pivot column, as the values of these rows will change as we go on due to the desire to land in a RREF.

Once we have recorded enough rows, we generate the table using M4riTable::generate, and then reduce limbs using M4riTable::reduce. When we are done we clear it using M4riTable::clear and proceed to the next k rows.

Fields

rows: Vec<usize>

The indices of new rows in the table

columns: Vec<LimbBitIndexPair>

The list of pivot columns of the rows

data: Vec<u64>

The 2^k linear combinations of the k rows, apart from the first one which is identically zero.

min_limb: usize

The smallest non-zero limb in this table. We use this when row reducing to save a few operations.

Implementations

impl M4riTable

pub fn new(k: usize, cols: usize) -> Self

Create a table with space for k vectors, each with cols columns.

pub fn len(&self) -> usize

Number of rows in the M4riTable

pub fn is_empty(&self) -> bool

Whether the table has no rows

pub fn rows(&self) -> &[usize]

Get the list of pivot rows

pub fn add(&mut self, column: usize, row: usize)

Add a row to the table.

Arguments

• column: pivot column of the row
• row: index of the row

pub fn clear(&mut self)

Clear the contents of the table

pub fn generate(&mut self, matrix: &Matrix)

Generates the table from the known data num is the number of the vector being added.

pub fn reduce_naive(&self, matrix: &mut Matrix, target: usize)

pub fn reduce(&self, v: &mut [u64])

Trait Implementations

impl Debug for M4riTable

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

Formats the value using the given formatter.

impl Default for M4riTable

fn default() -> M4riTable

Returns the “default value” for a type.