Struct Subspace 

#[repr(transparent)]
pub struct Subspace {
    matrix: Matrix,
}

A subspace of a vector space.

In general, a method is defined on the Subspace if it is a meaningful property of the subspace itself. Otherwise, users can dereference the subspace to gain read-only access to the underlying matrix object.

Fields

• matrix - A matrix in reduced row echelon, whose number of columns is the dimension of the ambient space and each row is a basis vector of the subspace.

Fields

matrix: Matrix

Implementations

impl Subspace

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

pub fn from_matrix(matrix: Matrix) -> Self

Create a new subspace from a matrix. The matrix does not have to be in row echelon form.

pub fn update_then_row_reduce<T, F: FnOnce(&mut Matrix) -> T>( &mut self, f: F, ) -> T

Run a closure on the matrix and then ensure it is row-reduced.

pub fn from_bytes(p: ValidPrime, data: &mut impl Read) -> Result<Self>

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

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

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

This adds a vector to the subspace. This function assumes that the last row of the matrix is zero, i.e. the dimension of the current subspace is strictly less than the number of rows. This can be achieved by setting the number of rows to be the dimension plus one when creating the subspace.

Returns

The new dimension of the subspace

pub fn add_vectors( &mut self, rows: impl for<'a> FnMut(FpSliceMut<'a>) -> Option<()>, )

This adds some rows to the subspace

Arguments

• rows: A function that writes the row to be added to the given FpSliceMut. This returns None if it runs out of rows, Some(()) otherwise.

pub fn add_basis_elements(&mut self, rows: impl Iterator<Item = usize>)

pub fn reduce(&self, vector: FpSliceMut<'_>)

Projects a vector to a complement of the subspace. The complement is the set of vectors that have a 0 in every column where there is a pivot in matrix

pub fn contains(&self, vector: FpSlice<'_>) -> bool

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

pub fn dimension(&self) -> usize

pub fn is_empty(&self) -> bool

Whether the subspace is empty. This assumes the subspace is row reduced.

pub fn ambient_dimension(&self) -> usize

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

Returns a basis of the subspace.

pub fn set_to_zero(&mut self)

Sets the subspace to be the zero subspace.

pub fn set_to_entire(&mut self)

Sets the subspace to be the entire subspace.

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

pub fn iter_all_vectors(&self) -> impl Iterator<Item = FpVector> + '_

Iterate over all vectors in the subspace.

Example

let subspace = Subspace::from_matrix(Matrix::from_vec(
    ValidPrime::new(3),
    &[vec![1, 0, 0], vec![0, 1, 2]],
));
let mut all_vectors = subspace.iter_all_vectors().map(|v| (&v).into());

assert_eq!(all_vectors.next(), Some(vec![0, 0, 0]));
assert_eq!(all_vectors.next(), Some(vec![0, 1, 2]));
assert_eq!(all_vectors.next(), Some(vec![0, 2, 1]));
assert_eq!(all_vectors.next(), Some(vec![1, 0, 0]));
assert_eq!(all_vectors.next(), Some(vec![1, 1, 2]));
assert_eq!(all_vectors.next(), Some(vec![1, 2, 1]));
assert_eq!(all_vectors.next(), Some(vec![2, 0, 0]));
assert_eq!(all_vectors.next(), Some(vec![2, 1, 2]));
assert_eq!(all_vectors.next(), Some(vec![2, 2, 1]));
assert_eq!(all_vectors.next(), None);

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

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 fn pivots(&self) -> &[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 row(&self, row: usize) -> FpSlice<'_>

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

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 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 as_tile(&self) -> MatrixTileSlice<'_>

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 Arbitrary for Subspace

type Parameters = SubspaceArbParams

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

type Strategy = BoxedStrategy<Subspace>

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 Subspace

fn clone(&self) -> Subspace

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Subspace

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

Formats the value using the given formatter.

impl Deref for Subspace

type Target = Matrix

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<'de> Deserialize<'de> for Subspace

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Subspace

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

Example

let subspace = Subspace::entire_space(TWO, 3);

expect![[r#"
    [1, 0, 0]
    [0, 1, 0]
    [0, 0, 1]
"#]]
.assert_eq(&format!("{}", subspace));

assert_eq!(
    "[1, 0, 0], [0, 1, 0], [0, 0, 1]",
    &format!("{:#}", subspace)
);

impl From<Subspace> for AffineSubspace

fn from(subspace: Subspace) -> Self

Converts to this type from the input type.

impl PartialEq for Subspace

fn eq(&self, other: &Subspace) -> 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 Subspace

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 Subspace

impl StructuralPartialEq for Subspace