Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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:

MATLAB visualization

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).


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 (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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.