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
2) memory and the storage of
Y
requires O(n
2) memory. Ignoring for the moment the existence
of Strassen's matrix multiplication algorithm and more theoretical alternatives,
the multiplication XA
requires O(m
2n
) operations, and
the multiplication AY
requires O(m
n
2) 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>
-> 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>
-> 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>
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>)
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>)
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]
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]
impl<T> Mul<Vector<T>> for PermutationMatrix<T>
[src]
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>
The method for the *
operator
impl<'a, T> Mul<Vector<T>> for &'a PermutationMatrix<T> where T: Clone + Zero
[src]
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>
The method for the *
operator
impl<'a, 'b, T> Mul<&'a Vector<T>> for &'b PermutationMatrix<T> where T: Clone + Zero
[src]
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>
The method for the *
operator
impl<'a, T> Mul<&'a Vector<T>> for PermutationMatrix<T> where T: Clone + Zero
[src]
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>
The method for the *
operator
impl<T> Mul<Matrix<T>> for PermutationMatrix<T>
[src]
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>
The method for the *
operator
impl<'b, T> Mul<Matrix<T>> for &'b PermutationMatrix<T> where T: Clone
[src]
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>
The method for the *
operator
impl<'a, 'm, T> Mul<&'a Matrix<T>> for PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'b, 'm, T> Mul<&'a Matrix<T>> for &'b PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'm, T> Mul<&'a MatrixSlice<'m, T>> for PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'b, 'm, T> Mul<&'a MatrixSlice<'m, T>> for &'b PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'm, T> Mul<&'a MatrixSliceMut<'m, T>> for PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'b, 'm, T> Mul<&'a MatrixSliceMut<'m, T>> for &'b PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'm, T> Mul<MatrixSlice<'m, T>> for PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'b, 'm, T> Mul<MatrixSlice<'m, T>> for &'b PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'm, T> Mul<MatrixSliceMut<'m, T>> for PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<'a, 'b, 'm, T> Mul<MatrixSliceMut<'m, T>> for &'b PermutationMatrix<T> where T: Zero + Clone
[src]
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>
The method for the *
operator
impl<T: Clone> Mul<PermutationMatrix<T>> for PermutationMatrix<T>
[src]
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>
The method for the *
operator
impl<'a, T: Clone> Mul<&'a PermutationMatrix<T>> for PermutationMatrix<T>
[src]
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>
The method for the *
operator
impl<'a, T: Clone> Mul<PermutationMatrix<T>> for &'a PermutationMatrix<T>
[src]
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>
The method for the *
operator
impl<'a, 'b, T: Clone> Mul<&'a PermutationMatrix<T>> for &'b PermutationMatrix<T>
[src]
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>
The method for the *
operator