Description
Motivation
It is well known that it is inefficient to store and multiply by dense permutation matrices. Instead permutation matrices should be stored as vectors which give information on how to organize the rows/columns of a matrix depending on whether left or right multiplication by the permutation matrix is desired.
Procedures would include:
- Inverting a permutation
- Multiplication by a permutation matrix on the right (column permutation)
- Multiplication by a permutation matrix on the left (row permutation)
- Support for "finalized and nonfinalized" permutations (see below for more details)
Prior Art
Julia has implementations for nonfinalized permutation matrix multiplication, see permutecols! and permuterows! in https://github.com/JuliaLang/julia/blob/master/base/combinatorics.jl. As far as I know, LAPACK only has an implementation for nonfinalized left permutation matrix multiplication (row permutation), see dlaswp https://www.netlib.org/lapack/explore-html/d1/d7e/group__laswp_ga5d3ea3e3cb61e32750bf062a2446aa33.html#ga5d3ea3e3cb61e32750bf062a2446aa33.
Some outputs of LAPACK routines contain finalized permutations, see the jpvt argument of dgeqp3 https://www.netlib.org/lapack/explore-html/d0/dea/group__geqp3_gae96659507d789266660af28c617ef87f.html#gae96659507d789266660af28c617ef87f.
The difference between what I have been calling a finalized and nonfinalized permutation matrix is that a finalized permutation matrix tells you exactly where each column/row should end up after multiplication, while a nonfinalized permutation matrix just tells you what columns/rows to switch and where (with the possibility of moving a single column/row multiple times).
I have my own implementations of some multiplication routines, but their performance is questionable. I can provide them if they would be of use.
Additional Information
No response