Struct Matrix 

pub struct Matrix {
    fp: Fp<ValidPrime>,
    rows: usize,
    physical_rows: usize,
    columns: usize,
    data: AVec<u64>,
    stride: usize,
    pub(crate) pivots: Vec<isize>,
}

A matrix! In particular, a matrix with values in F_p.

The way we store matrices means it is easier to perform row operations than column operations, and the way we use matrices means we want our matrices to act on the right. Hence we think of vectors as row vectors.

Fields

fp: Fp<ValidPrime>

rows: usize

physical_rows: usize

columns: usize

data: AVec<u64>

stride: usize

pivots: Vec<isize>

The pivot columns of the matrix. pivots[n] is k if column n is the kth pivot column, and a negative number otherwise. Said negative number is often -1 but this is not guaranteed.

Implementations

impl Matrix

pub fn arbitrary_rref_with(args: MatrixArbParams) -> impl Strategy<Value = Self>

Generate an arbitrary row-reduced matrix.

This is more interesting than just generating an arbitrary matrix and row-reducing. If we pick a matrix uniformly at random in the space of all $n \times m$ matrices, it has a very high probability of having full rank with all its pivots in the first $n$ columns. This implies that, after projecting to the space of row-reduced matrices, the output is very likely to be an identity matrix augmented by a random matrix. If $m$ is significantly larger than $n$, this is only a tiny subspace of the space of all row-reduced matrices.

While a search through all $n \times m$ matrices will also cover all row-reduced matrices, in practice this space is so large that we only test a vanishingly small fraction of it. Therefore, if a method that is sensitive to the pivot structure of the input matrix is proptested using arbitrary_with, it is unlikely that the tests will cover many matrices with interesting pivots, while those are the most likely to cause bugs. This function attempts to generate a matrix that is chosen uniformly at random directly in the space of all row-reduced matrices.

In practice, this is not quite right. There is no randomness in the code; instead we generate a Strategy that samples from only the space of row-reduced matrices. Also, depending on the parameters, the strategy may output matrices that are not all of the same size or even over the same ground field, so using the word “space” is slightly improper, mathematically speaking.

pub fn arbitrary_rref() -> impl Strategy<Value = Self>

impl Matrix

pub fn new(p: ValidPrime, rows: usize, columns: usize) -> Self

Produces a new matrix over F_p with the specified number of rows and columns, initialized to the 0 matrix.

pub fn new_with_capacity( p: ValidPrime, rows: usize, columns: usize, rows_capacity: usize, columns_capacity: usize, ) -> Self

pub fn from_data( p: ValidPrime, rows: usize, columns: usize, data: Vec<u64>, ) -> Self

pub fn identity(p: ValidPrime, dim: usize) -> Self

pub fn from_bytes( p: ValidPrime, rows: usize, columns: usize, buffer: &mut impl Read, ) -> Result<Self>

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

pub(crate) fn write_pivot(v: &[isize], buffer: &mut impl Write) -> Result<()>

Read a vector of isize

pub(crate) fn read_pivot(dim: usize, data: &mut impl Read) -> Result<Vec<isize>>

Read a vector of isize of length dim.

impl Matrix

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 from_rows(p: ValidPrime, input: Vec<FpVector>, columns: usize) -> Self

Produces a Matrix from a vector of FpVectors. We pass in the number of columns because all 0 x n matrices will have an empty Vec, and we have to distinguish between them.

pub fn from_row(p: ValidPrime, row: FpVector, columns: usize) -> Self

Produces a 1 x n matrix from a single FpVector. This is a convenience function.

pub fn from_vec(p: ValidPrime, input: &[Vec<u32>]) -> Self

Produces a Matrix from an &[Vec<u32>] object. If the number of rows is 0, the number of columns is also assumed to be zero.

Example

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

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

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 augmented_from_vec(p: ValidPrime, input: &[Vec<u32>]) -> (usize, Self)

Produces a padded augmented matrix from an &[Vec<u32>] object (produces [A|0|I] from A). Returns the matrix and the first column index of I.

Example

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

let (n, m) = Matrix::augmented_from_vec(p, &input);
assert!(n >= input[0].len());

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<'_>

impl Matrix

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<'_>>

impl Matrix

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));

impl Matrix

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.

impl Matrix

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

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

impl Matrix

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 AddAssign<&Matrix> for Matrix

fn add_assign(&mut self, rhs: &Self)

Performs the += operation.

impl Arbitrary for Matrix

type Parameters = MatrixArbParams

The type of parameters that arbitrary_with accepts for configuration of the generated Strategy. Parameters must implement Default.

type Strategy = BoxedStrategy<Matrix>

The type of Strategy used to generate values of type Self.

fn arbitrary_with(args: Self::Parameters) -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self). The strategy is passed the arguments given in args.

fn arbitrary() -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self).

impl Clone for Matrix

fn clone(&self) -> Matrix

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Matrix

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for Matrix

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Matrix

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

Example

let m = Matrix::from_vec(ValidPrime::new(2), &[vec![0, 1, 0], vec![1, 1, 0]]);
assert_eq!(&format!("{m}"), "[\n    [0, 1, 0],\n    [1, 1, 0]\n]");
assert_eq!(&format!("{m:#}"), "010\n110");

impl Mul for &Matrix

type Output = Matrix

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Matrix

Performs the * operation.

impl MulAssign<u32> for Matrix

fn mul_assign(&mut self, rhs: u32)

Performs the *= operation.

impl PartialEq for Matrix

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for Matrix

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for Matrix