# COLAMD matrix reordering algorithm

## Background

I'm dealing with some variable size square sparse matrices resulting from a FEM analysis, and my next step is optimizing the system solving in terms of speed. This is a visualization of some aspects of a typical matrix using MATLAB's spy:

Please note I'm not using MATLAB (or this question would be useless), I just used it for generating the above graph.

The top left graph show my matrix as-is (non zero elements are blue), and bottom left shows the LU decomposition of said matrix. On the top right I have applied the COLAMD algorithm (through MATLAB function colamd()) to generate a permutation to my matrix that would result in sparser LU factorized matrix, which indeed happens as the bottom right graph suggests (less than a third of the non zero elements I had before).

## Problem

Now my problem is understanding how to implement the COLAMD function by hand in the language I'm using. I've been browsing through the COLAMD project page, read the paper on it, and tried to decypher the C source code to no avail.

What I'm looking for is an explanation of the algorithm in the likes of the ones provided by rosettacode.org (example of an algorithm), or some pseudo-code, basically anything that clearly shows what steps must be implemented.

Thank you.

Edit: I'm not sure if this belongs in Stack Overflow or here, please advise if it's in the wrong place. Thanks.

-