Struct rulinalg::matrix::PermutationMatrix [−] [src]

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

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(mn²) 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.

Methods

`impl<T> PermutationMatrix<T>`
[src]

`fn identity(n: usize) -> Self`

The identity permutation.

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

Swaps rows i and j in the permutation matrix.

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

The inverse of the permutation matrix.

`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.

`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.

`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.

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

`fn parity(self) -> Parity`

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

`impl<T: Num> PermutationMatrix<T>`
[src]

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

The permutation matrix in an equivalent full matrix representation.

`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>`
[src]

`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.

`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.

`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>`
[src]

`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.

`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.

`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.

`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: Debug> Debug for PermutationMatrix<T>`
[src]

`fn fmt(&self, __arg_0: &mut Formatter) -> Result`

Formats the value using the given formatter.

`impl<T: PartialEq> PartialEq for PermutationMatrix<T>`
[src]

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

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

`fn ne(&self, __arg_0: &PermutationMatrix<T>) -> bool`

This method tests for !=.

`impl<T: Eq> Eq for PermutationMatrix<T>`
[src]

`impl<T: Clone> Clone for PermutationMatrix<T>`
[src]

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

Returns a copy of the value. Read more

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

Performs copy-assignment from source. Read more

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

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

Performs the conversion.