Permutations

Permutation vectors

In order to represent arbitrary permutations, Elemental recently switched from LAPACK-style pivot sequence representations to general permutation vectors, where entry i of the permutation vector p contains the column index of the nonzero entry in row i of the corresponding permutation matrix.

PermuteCols

void PermuteCols(Matrix<T> &A, const Matrix<int> &perm)
void PermuteCols(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm)
void PermuteCols(Matrix<T> &A, const Matrix<int> &perm, const Matrix<int> &invPerm)
void PermuteCols(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm, const DistMatrix<int, UPerm, STAR> &invPerm)

Provide the inverse permutations so that they do not need to be internally computed and discarded.

PermuteRows

void PermuteRows(Matrix<T> &A, const Matrix<int> &perm)
void PermuteRows(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm)
void PermuteRows(Matrix<T> &A, const Matrix<int> &perm, const Matrix<int> &invPerm)
void PermuteRows(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm, const DistMatrix<int, UPerm, STAR> &invPerm)

Provide the inverse permutations so that they do not need to be internally computed and discarded.

InversePermuteCols

void InversePermuteCols(Matrix<T> &A, const Matrix<int> &perm)
void InversePermuteCols(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm)

InversePermuteRows

void InversePermuteRows(Matrix<T> &A, const Matrix<int> &perm)
void InversePermuteRows(DistMatrix<T, U, V> &A, const DistMatrix<int, UPerm, STAR> &perm)

InvertPermutation

void InvertPermutation(const Matrix<int> &perm, Matrix<int> &invPerm)
void InvertPermutation(const DistMatrix<int, UPerm, STAR> &perm, DistMatrix<int, UPerm, STAR> &invPerm)

Compute the inverse permutation matrix in compressed (vector) form.

ExplicitPermutation

void ExplicitPermutation(const Matrix<int> &perm, Matrix<int> &P)
void ExplicitPermutation(const DistMatrix<int, UPerm, STAR> &perm, DistMatrix<int, U, V> &P)

Return the full permutation matrix, P, represented by the permutation vector perm.

PermutationParity

bool PermutationParity(const Matrix<int> &perm)
bool PermutationParity(const DistMatrix<int, UPerm, STAR> &perm)

Return true if the given permutation is odd. The parity is determined in linear time by finding the decomposition of the inverse of the permutation as a product of transpositions.

PermutationMeta

type PermutationMeta
int align
mpi::Comm comm
std::vector<int> sendCounts
std::vector<int> sendDispls
std::vector<int> sendIdx
std::vector<int> sendRanks
std::vector<int> recvCounts
std::vector<int> recvDispls
std::vector<int> recvIdx
std::vector<int> recvRanks
int TotalSend() const
int TotalRecv() const
void ScaleUp(int length)
void ScaleDown(int length)
PermutationMeta(const DistMatrix<int, U, STAR> &perm, const DistMatrix<int, U, STAR> &invPerm)

Pivot sequences

These routines make use of LAPACK-style pivot sequence vectors, where the pivot sequence vector p implies the sequence of swaps \((0,p_0)\), \((1,p_1)\), ..., \((n-1,p_{n-1})\). Elemental used to follow this convention when returning permutations from factorizations, but clearly this representation is somewhat restrictive, as routines which perform multiple swaps for each pivot (e.g., some variants of Bunch-Kaufman) cannot be handled.

ApplyColPivots

void ApplyColPivots(Matrix<T> &A, const Matrix<int> &pivots)
void ApplyColPivots(DistMatrix<T, U1, V1> &A, const DistMatrix<int, U2, V2> &pivots)

ApplyInverseColPivots

void ApplyInverseColPivots(Matrix<T> &A, const Matrix<int> &pivots)
void ApplyInverseColPivots(DistMatrix<T, U1, V1> &A, const DistMatrix<int, U2, V2> &pivots)

ApplyRowPivots

void ApplyRowPivots(Matrix<T> &A, const Matrix<int> &pivots)
void ApplyRowPivots(DistMatrix<T, U1, V1> &A, const DistMatrix<int, U2, V2> &pivots)

ApplyInverseRowPivots

void ApplyInverseRowPivots(Matrix<T> &A, const Matrix<int> &pivots)
void ApplyInverseRowPivots(DistMatrix<T, U1, V1> &A, const DistMatrix<int, U2, V2> &pivots)

ApplySymmetricPivots

void ApplySymmetricPivots(UpperOrLower uplo, Matrix<T> &A, const Matrix<int> &pivots, bool conjugate = false)
void ApplySymmetricPivots(UpperOrLower uplo, DistMatrix<T> &A, const DistMatrix<int, UPerm, STAR> &pivots, bool conjugate = false)

ApplyInverseSymmetricPivots

void ApplyInverseSymmetricPivots(UpperOrLower uplo, Matrix<T> &A, const Matrix<int> &pivots, bool conjugate = false)
void ApplyInverseSymmetricPivots(UpperOrLower uplo, DistMatrix<T> &A, const DistMatrix<int, UPerm, STAR> &pivots, bool conjugate = false)

PivotParity

bool PivotParity(const Matrix<int> &pivots)
bool PivotParity(const DistMatrix<int, UPerm, STAR> &pivots)

Return true if the permutation implied by the pivot sequence is odd. This is determined by determining if an odd number of non-trivial transpositions are performed.

Converting pivot sequences to permutations

PivotsToPermutation

void PivotsToPermutation(const Matrix<int> &pivots, Matrix<int> &perm, int offset = 0)
void PivotsToPermutation(const DistMatrix<int, U, STAR> &pivots, DistMatrix<int, UPerm, STAR> &perm, int offset = 0)

PivotsToInversePermutation

void PivotsToInversePermutation(const Matrix<int> &pivots, Matrix<int> &invPerm, int offset = 0)
void PivotsToInversePermutation(const DistMatrix<int, U, STAR> &pivots, DistMatrix<int, UPerm, STAR> &invPerm, int offset = 0)

PivotsToPartialPermutation

void PivotsToPartialPermutation(const Matrix<int> &pivots, Matrix<int> &perm, Matrix<int> &invPerm, int offset = 0)
void PivotsToPartialPermutation(const DistMatrix<int, U, STAR> &pivots, DistMatrix<int, UPerm, STAR> &perm, DistMatrix<int, UPerm, STAR> &invPerm, int offset = 0)