Struct rulinalg::matrix::PermutationMatrix

pub struct PermutationMatrix<T> { /* private fields */ }

An efficient implementation of a permutation matrix.

Examples

use rulinalg::matrix::PermutationMatrix;

let ref x = matrix![1, 2, 3;
                    4, 5, 6;
                    7, 8, 9];

// Swap the two first rows of x by left-multiplying a permutation matrix
let expected = matrix![4, 5, 6;
                       1, 2, 3;
                       7, 8, 9];
let mut p = PermutationMatrix::identity(3);
p.swap_rows(0, 1);
assert_eq!(expected, p * x);

// Swap the two last columns of x by right-multiplying a permutation matrix
let expected = matrix![1, 3, 2;
                       4, 6, 5;
                       7, 9, 8];
let mut p = PermutationMatrix::identity(3);
p.swap_rows(1, 2);
assert_eq!(expected, x * p);

// One can also construct the same permutation matrix directly
// from an array representation.
let ref p = PermutationMatrix::from_array(vec![0, 2, 1]).unwrap();
assert_eq!(expected, x * p);

// One may also obtain a full matrix representation of the permutation
assert_eq!(p.as_matrix(), matrix![1, 0, 0;
                                  0, 0, 1;
                                  0, 1, 0]);

// The inverse of a permutation matrix can efficiently be obtained
let p_inv = p.inverse();

// And permutations can be composed through multiplication
assert_eq!(p * p_inv, PermutationMatrix::identity(3));

Rationale and complexity

A permutation matrix is a very special kind of matrix. It is essentially a matrix representation of the more general concept of a permutation. That is, an n x n permutation matrix corresponds to a permutation of ordered sets whose cardinality is n. In particular, given an m x n matrix A and an m x m permutation matrix P, the action of left-multiplying A by P, PA, corresponds to permuting the rows of A by the given permutation represented by P. Conversely, right-multiplication corresponds to column permutation. More precisely, given another permutation matrix Q of size n x n, then AQ is the corresponding permutation of the columns of A.

Due to their unique structure, permutation matrices can be much more efficiently represented and applied than general matrices. Recall that for general matrices X and Y of size m x m and n x n respectively, the storage of X requires O(m²) memory and the storage of Y requires O(n²) memory. Ignoring for the moment the existence of Strassen’s matrix multiplication algorithm and more theoretical alternatives, the multiplication XA requires O(m²n) operations, and the multiplication AY requires O(m``n²) operations.

By contrast, the storage of P requires only O(m) memory, and the storage of K requires O(n) memory. Moreover, the products PA and AK both require merely O(mn) operations.

Representation

A permutation of an ordered set of cardinality n is a map of the form

p: { 1, ..., n } -> { 1, ..., n }.

That is, for any index i, the permutation p sends i to some index j = p(i), and hence the map may be represented as an array of integers of length n.

By convention, an instance of PermutationMatrix represents row permutations. That is, the indices referred to above correspond to row indices, and the internal representation of a PermutationMatrix is an array describing how the permutation sends a row index i to a new row index j in the permuted matrix. Because of this internal representation, one can only efficiently swap rows of a PermutationMatrix. However, keep in mind that while this API only lets one swap individual rows of the permutation matrix itself, the right-multiplication of a general matrix with a permutation matrix will permute the columns of the general matrix, and so in practice this restriction is insignificant.

Implementations

impl<T> PermutationMatrix<T>

pub fn identity(n: usize) -> Self

The identity permutation.

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

Swaps rows i and j in the permutation matrix.

pub fn inverse(&self) -> PermutationMatrix<T>

The inverse of the permutation matrix.

pub fn size(&self) -> usize

The size of the permutation matrix.

A permutation matrix is a square matrix, so size() is equal to both the number of rows, as well as the number of columns.

pub fn from_array<A: Into<Vec<usize>>>(
    array: A
) -> Result<PermutationMatrix<T>, Error>

Constructs a PermutationMatrix from an array.

Errors

The supplied N-length array must satisfy the following:

• Each element must be in the half-open range [0, N).
• Each element must be unique.

pub unsafe fn from_array_unchecked<A: Into<Vec<usize>>>(
    array: A
) -> PermutationMatrix<T>

Constructs a PermutationMatrix from an array, without checking the validity of the supplied permutation.

Safety

The supplied N-length array must satisfy the following:

• Each element must be in the half-open range [0, N).
• Each element must be unique.

Note that while this function itself is technically safe regardless of the input array, passing an incorrect permutation matrix may cause undefined behavior in other methods of PermutationMatrix. As such, it may be difficult to debug. The user is strongly encouraged to use the safe function from_array, which for most real world applications only incurs a minor or even insignificant performance hit as a result of the extra validation.

pub fn map_row(&self, row_index: usize) -> usize

Maps the given row index into the resulting row index in the permuted matrix.

More specifically, if the permutation sends row i to j, then map_row(i) returns j.

Examples

use rulinalg::matrix::PermutationMatrix;
let mut p = PermutationMatrix::<u32>::identity(3);
p.swap_rows(1, 2);
assert_eq!(p.map_row(1), 2);

pub fn parity(self) -> Parity

Computes the parity of the permutation (even- or oddness).

impl<T: Num> PermutationMatrix<T>

pub fn as_matrix(&self) -> Matrix<T>

The permutation matrix in an equivalent full matrix representation.

pub fn det(self) -> T

Computes the determinant of the permutation matrix.

The determinant of a permutation matrix is always +1 (if the permutation is even) or -1 (if the permutation is odd).

impl<T> PermutationMatrix<T>

pub fn permute_rows_in_place<M>(self, matrix: &mut M)where
    M: BaseMatrixMut<T>,

Permutes the rows of the given matrix in-place.

Panics

• The number of rows in the matrix is not equal to the size of the permutation matrix.

pub fn permute_cols_in_place<M>(self, matrix: &mut M)where
    M: BaseMatrixMut<T>,

Permutes the columns of the given matrix in-place.

Panics

• The number of columns in the matrix is not equal to the size of the permutation matrix.

pub fn permute_vector_in_place(self, vector: &mut Vector<T>)

Permutes the elements of the given vector in-place.

Panics

• The size of the vector is not equal to the size of the permutation matrix.

impl<T: Clone> PermutationMatrix<T>

pub fn permute_rows_into_buffer<X, Y>(&self, source_matrix: &X, buffer: &mut Y)where
    X: BaseMatrix<T>,
    Y: BaseMatrixMut<T>,

Permutes the rows of the given source_matrix and stores the result in buffer.

Panics

• The number of rows in the source matrix is not equal to the size of the permutation matrix.
• The dimensions of the source matrix and the buffer are not identical.

pub fn permute_cols_into_buffer<X, Y>(
    &self,
    source_matrix: &X,
    target_matrix: &mut Y
)where
    X: BaseMatrix<T>,
    Y: BaseMatrixMut<T>,

Permutes the columns of the given source_matrix and stores the result in buffer.

Panics

• The number of columns in the source matrix is not equal to the size of the permutation matrix.
• The dimensions of the source matrix and the buffer are not identical.

pub fn permute_vector_into_buffer(
    &self,
    source_vector: &Vector<T>,
    buffer: &mut Vector<T>
)

Permutes the elements of the given source_vector and stores the result in buffer.

Panics

• The size of the source vector is not equal to the size of the permutation matrix.
• The dimensions of the source vector and the buffer are not identical.

pub fn compose_into_buffer(
    &self,
    source_perm: &PermutationMatrix<T>,
    buffer: &mut PermutationMatrix<T>
)

Computes the composition of self with the given source_perm and stores the result in buffer.

Panics

• The size of the permutation matrix (self) is not equal to the size of the source permutation matrix.

Trait Implementations

impl<T: Clone> Clone for PermutationMatrix<T>

fn clone(&self) -> PermutationMatrix<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for PermutationMatrix<T>

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

Formats the value using the given formatter.

impl<T> From<PermutationMatrix<T>> for Vec<usize>

fn from(p: PermutationMatrix<T>) -> Vec<usize>

Converts to this type from the input type.

impl<'a, T> Into<&'a [usize]> for &'a PermutationMatrix<T>

fn into(self) -> &'a [usize]

Converts this type into the (usually inferred) input type.

impl<'a, 'b, 'm, T> Mul<&'a Matrix<T>> for &'b PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a Matrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<&'a Matrix<T>> for PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a Matrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'a MatrixSlice<'m, T>> for &'b PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a MatrixSlice<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<&'a MatrixSlice<'m, T>> for PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a MatrixSlice<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'a MatrixSliceMut<'m, T>> for &'b PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a MatrixSliceMut<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<&'a MatrixSliceMut<'m, T>> for PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a MatrixSliceMut<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, T: Clone> Mul<&'a PermutationMatrix<T>> for &'b PermutationMatrix<T>

Multiply a permutation matrix by a permutation matrix.

type Output = PermutationMatrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a PermutationMatrix<T>) -> PermutationMatrix<T>

Performs the * operation.

impl<'a, T> Mul<&'a PermutationMatrix<T>> for Matrix<T>where
    T: Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, T: Clone> Mul<&'a PermutationMatrix<T>> for PermutationMatrix<T>

Multiply a permutation matrix by a permutation matrix.

type Output = PermutationMatrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &PermutationMatrix<T>) -> PermutationMatrix<T>

Performs the * operation.

impl<'a, 'b, T> Mul<&'a Vector<T>> for &'b PermutationMatrix<T>where
    T: Clone + Zero,

Left-multiply a vector by a permutation matrix.

type Output = Vector<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a Vector<T>) -> Vector<T>

Performs the * operation.

impl<'a, T> Mul<&'a Vector<T>> for PermutationMatrix<T>where
    T: Clone + Zero,

Left-multiply a vector by a permutation matrix.

type Output = Vector<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'a Vector<T>) -> Vector<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'b PermutationMatrix<T>> for &'a Matrix<T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'b PermutationMatrix<T>> for &'a MatrixSlice<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'b PermutationMatrix<T>> for &'a MatrixSliceMut<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'b PermutationMatrix<T>> for MatrixSlice<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<&'b PermutationMatrix<T>> for MatrixSliceMut<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'b, T> Mul<Matrix<T>> for &'b PermutationMatrix<T>where
    T: Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: Matrix<T>) -> Matrix<T>

Performs the * operation.

impl<T> Mul<Matrix<T>> for PermutationMatrix<T>

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: Matrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<MatrixSlice<'m, T>> for &'b PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: MatrixSlice<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<MatrixSlice<'m, T>> for PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: MatrixSlice<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'b, 'm, T> Mul<MatrixSliceMut<'m, T>> for &'b PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: MatrixSliceMut<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<MatrixSliceMut<'m, T>> for PermutationMatrix<T>where
    T: Zero + Clone,

Left-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: MatrixSliceMut<'m, T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<PermutationMatrix<T>> for &'a Matrix<T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<PermutationMatrix<T>> for &'a MatrixSlice<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<PermutationMatrix<T>> for &'a MatrixSliceMut<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, T: Clone> Mul<PermutationMatrix<T>> for &'a PermutationMatrix<T>

Multiply a permutation matrix by a permutation matrix.

type Output = PermutationMatrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> PermutationMatrix<T>

Performs the * operation.

impl<T> Mul<PermutationMatrix<T>> for Matrix<T>

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<PermutationMatrix<T>> for MatrixSlice<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<'a, 'm, T> Mul<PermutationMatrix<T>> for MatrixSliceMut<'m, T>where
    T: Zero + Clone,

Right-multiply a matrix by a permutation matrix.

type Output = Matrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> Matrix<T>

Performs the * operation.

impl<T: Clone> Mul<PermutationMatrix<T>> for PermutationMatrix<T>

Multiply a permutation matrix by a permutation matrix.

type Output = PermutationMatrix<T>

The resulting type after applying the * operator.

fn mul(self, rhs: PermutationMatrix<T>) -> PermutationMatrix<T>

Performs the * operation.

impl<'a, T> Mul<Vector<T>> for &'a PermutationMatrix<T>where
    T: Clone + Zero,

Left-multiply a vector by a permutation matrix.

type Output = Vector<T>

The resulting type after applying the * operator.

fn mul(self, rhs: Vector<T>) -> Vector<T>

Performs the * operation.

impl<T> Mul<Vector<T>> for PermutationMatrix<T>

Left-multiply a vector by a permutation matrix.

type Output = Vector<T>

The resulting type after applying the * operator.

fn mul(self, rhs: Vector<T>) -> Vector<T>

Performs the * operation.

impl<T: PartialEq> PartialEq<PermutationMatrix<T>> for PermutationMatrix<T>

fn eq(&self, other: &PermutationMatrix<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<T: Eq> Eq for PermutationMatrix<T>

impl<T> StructuralEq for PermutationMatrix<T>

impl<T> StructuralPartialEq for PermutationMatrix<T>