Struct AugmentedMatrix 

pub struct AugmentedMatrix<const N: usize> {
    pub end: [usize; N],
    pub start: [usize; N],
    pub inner: Matrix,
}

This models an augmented matrix.

In an ideal world, this will have no public fields. The inner matrix can be accessed via deref, and there are functions that expose end and start. However, in the real world, the borrow checker exists, and there are cases where directly accessing these fields is what it takes to let you pass the borrow checker.

In particular, if m is an augmented matrix and f is a function that takes in &mut Matrix, trying to run m.f(m.start[0]) produces an error because it is not clear if we first do the deref_mut then retrieve start[0]. (since deref_mut takes in a mutable borrow, it could in theory modify m non-trivially)

Fields

end: [usize; N]

start: [usize; N]

inner: Matrix

Implementations

impl<const N: usize> AugmentedMatrix<N>

pub fn new(p: ValidPrime, rows: usize, columns: [usize; N]) -> Self

pub fn new_with_capacity( p: ValidPrime, rows: usize, columns: &[usize], row_capacity: usize, extra_column_capacity: usize, ) -> Self

pub fn segment(&mut self, start: usize, end: usize) -> MatrixSliceMut<'_>

pub fn row_segment_mut( &mut self, i: usize, start: usize, end: usize, ) -> FpSliceMut<'_>

pub fn row_segment(&self, i: usize, start: usize, end: usize) -> FpSlice<'_>

pub fn into_matrix(self) -> Matrix

pub fn into_tail_segment( self, row_start: usize, row_end: usize, segment_start: usize, ) -> Matrix

pub fn compute_kernel(&self) -> Subspace

pub fn extend_column_dimension(&mut self, columns: usize)

impl AugmentedMatrix<2>

pub fn compute_image(&self) -> Subspace

pub fn compute_quasi_inverse(&self) -> QuasiInverse

impl AugmentedMatrix<3>

pub fn drop_first(self) -> AugmentedMatrix<2>

pub fn compute_quasi_inverses(self) -> (QuasiInverse, QuasiInverse)

This function computes quasi-inverses for matrices A, B given a reduced row echelon form of [A|0|B|0|I] such that A is surjective. Moreover, if Q is the quasi-inverse of A, it is guaranteed that the image of QB and B|_{ker A} are disjoint.

This takes ownership of the matrix since it heavily modifies the matrix. This is not strictly necessary but is fine in most applications.

Methods from Deref<Target = Matrix>

pub fn to_bytes(&self, data: &mut impl Write) -> Result<()>

pub fn prime(&self) -> ValidPrime

pub fn rows(&self) -> usize

Gets the number of rows in the matrix.

pub(crate) fn physical_rows(&self) -> usize

Gets the physical number of rows allocated (for BLAS operations).

pub fn columns(&self) -> usize

Gets the number of columns in the matrix.

pub(crate) fn stride(&self) -> usize

pub(crate) fn data(&self) -> &[u64]

pub(crate) fn data_mut(&mut self) -> &mut [u64]

pub fn initialize_pivots(&mut self)

Set the pivots to -1 in every entry. This is called by Matrix::row_reduce.

pub fn pivots(&self) -> &[isize]

pub fn pivots_mut(&mut self) -> &mut [isize]

pub fn to_vec(&self) -> Vec<Vec<u32>>

let matrix_vec = vec![vec![1, 0], vec![0, 1]];

assert_eq!(Matrix::from_vec(TWO, &matrix_vec).to_vec(), matrix_vec);

pub fn is_zero(&self) -> bool

pub fn set_to_zero(&mut self)

pub fn assign(&mut self, other: &Self)

pub fn as_slice_mut(&mut self) -> MatrixSliceMut<'_>

pub fn slice_mut( &mut self, row_start: usize, row_end: usize, col_start: usize, col_end: usize, ) -> MatrixSliceMut<'_>

pub fn row(&self, row: usize) -> FpSlice<'_>

pub fn row_mut(&mut self, row: usize) -> FpSliceMut<'_>

pub fn iter(&self) -> impl Iterator<Item = FpSlice<'_>>

pub fn iter_mut(&mut self) -> impl Iterator<Item = FpSliceMut<'_>>

pub fn maybe_par_iter_mut( &mut self, ) -> impl MaybeIndexedParallelIterator<Item = FpSliceMut<'_>>

pub fn safe_row_op(&mut self, target: usize, source: usize, c: u32)

A no-nonsense, safe, row operation. Adds c * self[source] to self[target].

pub unsafe fn row_op( &mut self, target: usize, source: usize, pivot_column: usize, prime: ValidPrime, )

Performs a row operation using pivot_column as the pivot column. This assumes that the source row is zero in all columns before the pivot column.

Safety

target and source must be distinct and less that vectors.len()

pub unsafe fn row_op_naive( &mut self, target: usize, source: usize, pivot_column: usize, prime: ValidPrime, )

A version of Matrix::row_op without the zero assumption.

Safety

target and source must be distinct and less that vectors.len()

pub(crate) unsafe fn split_borrow( &mut self, i: usize, j: usize, ) -> (FpSliceMut<'_>, FpSliceMut<'_>)

Mutably borrows x[i] and x[j].

Safety

i and j must be distinct and not out of bounds.

pub fn swap_rows(&mut self, i: usize, j: usize)

pub fn find_pivots_permutation<T: Iterator<Item = usize>>( &mut self, permutation: T, ) -> Vec<usize>

This is very similar to row_reduce, except we only need to get to row echelon form, not reduced row echelon form. It also returns the list of pivots instead.

pub fn row_reduce(&mut self) -> usize

Perform row reduction to reduce it to reduced row echelon form. This modifies the matrix in place and records the pivots in column_to_pivot_row. The way the pivots are recorded is that column_to_pivot_row[i] is the row of the pivot if the ith row contains a pivot, and -1 otherwise.

Returns

The number of non-empty rows in the matrix

Arguments

• column_to_pivot_row - A vector for the function to write the pivots into. The length should be at least as long as the number of columns (and the extra entries are ignored).

Example

let p = ValidPrime::new(7);

let input = [vec![1, 3, 6], vec![0, 3, 4]];

let result = [vec![1, 0, 2], vec![0, 1, 6]];

let mut m = Matrix::from_vec(p, &input);
m.row_reduce();

assert_eq!(m, Matrix::from_vec(p, &result));

pub fn find_first_row_in_block(&self, first_column: usize) -> usize

Given a row reduced matrix, find the first row whose pivot column is after (or at) first_column.

pub fn compute_quasi_inverse( &self, last_target_col: usize, first_source_col: usize, ) -> QuasiInverse

Computes the quasi-inverse of a matrix given a rref of [A|0|I], where 0 is the zero padding as usual.

Arguments

• last_target_col - the last column of A
• first_source_col - the first column of I

Example

let p = ValidPrime::new(3);
let input = [
    vec![1, 2, 1, 1, 0],
    vec![1, 0, 2, 1, 1],
    vec![2, 2, 0, 2, 1],
];

let (padded_cols, mut m) = Matrix::augmented_from_vec(p, &input);
m.row_reduce();
let qi = m.compute_quasi_inverse(input[0].len(), padded_cols);

let preimage = [vec![0, 1, 0], vec![0, 2, 2]];
assert_eq!(qi.preimage(), &Matrix::from_vec(p, &preimage));

pub fn compute_image( &self, last_target_col: usize, first_source_col: usize, ) -> Subspace

Computes the quasi-inverse of a matrix given a rref of [A|0|I], where 0 is the zero padding as usual.

Arguments

• last_target_col - the last column of A
• first_source_col - the first column of I

Example

let p = ValidPrime::new(3);
let input = [
    vec![1, 2, 1, 1, 0],
    vec![1, 0, 2, 1, 1],
    vec![2, 2, 0, 2, 1],
];

let (padded_cols, mut m) = Matrix::augmented_from_vec(p, &input);
m.row_reduce();

let computed_image = m.compute_image(input[0].len(), padded_cols);

let image = [vec![1, 0, 2, 1, 1], vec![0, 1, 1, 0, 1]];
assert_eq!(*computed_image, Matrix::from_vec(p, &image));
assert_eq!(computed_image.pivots(), &vec![0, 1, -1, -1, -1]);

pub fn compute_kernel(&self, first_source_column: usize) -> Subspace

Computes the kernel from an augmented matrix in rref. To compute the kernel of a matrix A, produce an augmented matrix of the form

[A | I]

An important thing to note is that the number of columns of A should be a multiple of the number of entries per limb in an FpVector, and this is often achieved by padding columns with 0. The padded length can be obtained from FpVector::padded_dimension.

After this matrix is set up, perform row reduction with Matrix::row_reduce, and then apply compute_kernel.

Arguments

• column_to_pivot_row - This is the list of pivots row_reduce gave you.
• first_source_column - The column where the I part of the augmented matrix starts.

Example

let p = ValidPrime::new(3);
let input = [
    vec![1, 2, 1, 1, 0],
    vec![1, 0, 2, 1, 1],
    vec![2, 2, 0, 2, 1],
];

let (padded_cols, mut m) = Matrix::augmented_from_vec(p, &input);
m.row_reduce();
let ker = m.compute_kernel(padded_cols);

let mut target = vec![0; 3];
assert_eq!(ker.row(0).iter().collect::<Vec<u32>>(), vec![1, 1, 2]);

pub fn extend_column_dimension(&mut self, columns: usize)

pub fn extend_column_capacity(&mut self, columns: usize)

pub fn add_row(&mut self) -> FpSliceMut<'_>

Add a row to the matrix and return a mutable reference to it.

pub fn extend_to_surjection( &mut self, start_column: usize, end_column: usize, extra_column_capacity: usize, ) -> Vec<usize>

Given a matrix M in rref, add rows to make the matrix surjective when restricted to the columns between start_column and end_column. That is, if M = [|B|] where B is between columns start_column and end_column, we want the new B to be surjective. This doesn’t change the size of the matrix. Rather, it adds the new row to the next empty row in the matrix. This will panic if there are not enough empty rows.

The rows added are all zero except in a single column, where it is 1. The function returns the list of such columns.

Arguments

• first_empty_row - The first row in the matrix that is empty. This is where we will add our new rows. This is a mutable borrow and by the end of the function, first_empty_row will be updated to the new first empty row.
• current_pivots - The current pivots of the matrix.

Panics

The function panics if there are not enough empty rows.

pub fn extend_image( &mut self, start_column: usize, end_column: usize, desired_image: &Subspace, extra_column_capacity: usize, ) -> Vec<usize>

Given a matrix in rref, say [A|B|C], where B lies between columns start_column and end_columns, and a superspace of the image of B, add rows to the matrix such that the image of B becomes this superspace.

The rows added are basis vectors of the desired image as specified in the Subspace object. The function returns the list of new pivot columns.

Panics

It may panic if the current image is not contained in desired_image, but is not guaranteed to do so.

pub fn apply(&self, result: FpSliceMut<'_>, coeff: u32, input: FpSlice<'_>)

Applies a matrix to a vector.

Example

let p = ValidPrime::new(7);
let input = [vec![1, 3, 6], vec![0, 3, 4]];

let m = Matrix::from_vec(p, &input);
let v = FpVector::from_slice(p, &vec![3, 1]);
let mut result = FpVector::new(p, 3);
let desired_result = FpVector::from_slice(p, &vec![3, 5, 1]);
m.apply(result.as_slice_mut(), 1, v.as_slice());
assert_eq!(result, desired_result);

pub fn trim(&mut self, row_start: usize, row_end: usize, col_start: usize)

pub fn rotate_down(&mut self, range: Range<usize>, shift: usize)

Rotate the rows downwards in the range range.

pub fn as_tile(&self) -> MatrixTileSlice<'_>

pub fn as_tile_mut(&mut self) -> MatrixTileSliceMut<'_>

pub fn naive_mul(&self, rhs: &Self) -> Self

pub fn fast_mul_sequential(&self, other: &Self) -> Self

pub fn fast_mul_sequential_order<L: LoopOrder>(&self, other: &Self) -> Self

pub fn fast_mul_concurrent(&self, other: &Self) -> Self

pub fn fast_mul_concurrent_blocksize<const M: usize, const N: usize>( &self, other: &Self, ) -> Self

pub fn fast_mul_concurrent_blocksize_order<const M: usize, const N: usize, L: LoopOrder>( &self, other: &Self, ) -> Self

Trait Implementations

impl<const N: usize> Clone for AugmentedMatrix<N>

fn clone(&self) -> AugmentedMatrix<N>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const N: usize> Deref for AugmentedMatrix<N>

type Target = Matrix

The resulting type after dereferencing.

fn deref(&self) -> &Matrix

Dereferences the value.

impl<const N: usize> DerefMut for AugmentedMatrix<N>

fn deref_mut(&mut self) -> &mut Matrix

Mutably dereferences the value.