# Standard Algorithms for Permuting CCS or CRS Sparse Matrices

I need to permute the degrees of freedom of a system and apply this permutation to a few sparse matrices in CCS (or CRS) format. I could construct a permutation matrix and perform sparse matrix-matrix multiplies, but that seems like overkill. Are there standard algorithms for permuting sparse matrices? How do users of packages like METIS permute sparse matrices?

• In the internal representation you can just permute the elements or the compressed rows/columns, which should be straightforward. Apr 12 '15 at 6:32
• @Kirill that will only work for a left-permutation in the case of CCS or a right-permutation in the case of CRS. When permuting both the rows and columns one has to rebuild the array of offsets, which necessitates allocating extra memory. Apr 13 '15 at 20:46
• @DanielShapero Yes, but I don't see a big problem with having to allocate extra memory (isn't it necessary anyway?), see, e.g., the linked code in the accepted answer. In principle, the amount of extra memory can be reduced from $O(n)$ (e.g., cstheory.stackexchange.com/q/6711), but I'm not sure if it'd be worth the effort: presumably permuting the matrix is not the most time-consuming part of the code. What I meant was that it's just a matter of permuting some elements in an array, no special "algorithm" required. Apr 14 '15 at 2:34

## 1 Answer

A function written in C to permute a CCS matrix is shown here:

http://www.cise.ufl.edu/research/sparse/CSparse/CSparse/Source/cs_permute.c

The algorithm is fairly simple but there aren't many comments. If you want more details, take a look at Davis' book where the routine is presented.

http://www.cise.ufl.edu/research/sparse/CSparse/