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?

  • 1
    $\begingroup$ In the internal representation you can just permute the elements or the compressed rows/columns, which should be straightforward. $\endgroup$ – Kirill Apr 12 '15 at 6:32
  • $\begingroup$ @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. $\endgroup$ – Daniel Shapero Apr 13 '15 at 20:46
  • $\begingroup$ @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. $\endgroup$ – Kirill Apr 14 '15 at 2:34

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


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.