8
$\begingroup$

In MATLAB there is a nice implementation of the so called AMD (approximate minimum degree permutation) algorithm named amd (see Online MATLAB Documentation). There is an alternative algorithm called COLAMD (see Online MATLAB Documentation). This algorithm is especially interesting when one wants to model large resistor networks e.g. calculate path resistances or reduce a network of resistors (for the theory see, e.g., Efficient Methods for Large Resistor Networks). There the AMD step is a preconditioning step for a large matrix before a Cholesky decomposition (available in Mathematica through CholeskyDecomposition) is done.

The original fortran coded algorithms can be found on the webpage from the autors.

Is anybody aware of an implementation of the AMD or the COLAMD algorithm in Mathematica?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ If you do have access to MATLAB but you prefer to do your work in Mathematica because you're much more fluent in it (like me), then consider using MATLink to call these MATLAB functions directly. Disclosure: I'm one of the MATLink authors. $\endgroup$
    – Szabolcs
    Dec 11, 2013 at 21:28
  • 1
    $\begingroup$ Would it make sense to instead use MinCut to permute rows/columns? $\endgroup$
    – Daniel Lichtblau
    Dec 11, 2013 at 21:56
  • $\begingroup$ @Szabolcs: It crossed my mind to use MATLink :-) , that would be my last resort if there is no Mathematica implementation available. Since I'm planning to do a broad statistical analysis on the networks (thousands of different resistor networks topographies) I hesitate to involve MATLink if not absolutely necessary. $\endgroup$
    – Rainer
    Dec 12, 2013 at 5:30
  • 3
    $\begingroup$ There is an example in the documentation for MinCut that applies to permuting rows/columns of a matrix, for the purpose of decreasing fill-in. Which is to say, it is a precondition-by-permutation example. As such, it could be an alternative to AMD. $\endgroup$
    – Daniel Lichtblau
    Dec 12, 2013 at 15:51
  • 2
    $\begingroup$ Also I wonder if just reordering based on vertex degree would suffice as a preconditioner? For a sparse matrix that should be fairly efficient, though I don't know how effective the resulting preconditioning would be in practice. $\endgroup$
    – Daniel Lichtblau
    Dec 12, 2013 at 15:53

3 Answers 3

Reset to default
7
$\begingroup$

While the MinCut (and also the MinimumBandwidth command in the GraphUtilities package) may be useful in many situations, this is a very general problem and might also benefit from more general solutions. For example, a while ago I had some data about the relationship between 120 items in the form of a distance matrix, basically a measurement of the distance between each object. With the data labelled arbitrarily, the matrix looks like this:

enter image description here

Black means zero distance (which you see along the diagonal because each item is zero distance from itself) while white represents the maximum possible distance between the items. Obviously, the matrix is completely scrambled. Laboriously using prior knowledge of the relationships between the various items, we were able to manually reorder the distance matrix into the form

enter image description here

which nicely shows the clustering along the diagonal. Though we were quite happy with this, it nagged at me: shouldn't there be some way to automatically reorder the data and hence rearrange the matrix? I tried two commands from Matlab (symamd -- a variant of amd, and symrcm which implements the minimum bandwidth algorithm of Cuthill-McKee). I tried both MinCut and MinimumBandwidth ordering in the graph utilities in Mathematica. None came close to what we could do manually -- that is -- the reordered matrices, while more organized than the first matrix above, were still quite random looking.

At this point, someone suggested that what we really needed was a clustering algorithm because what we were trying for was to cluster the elements into small groups. Accordingly, I tried

clusters = FindClusters[scrambled -> Range[Length[scrambled]], 10, 
           DistanceFunction -> (Norm[#1 - #2, 1] &)];
ind = Flatten[clusters];
ArrayPlot[scrambled[[ind, ind]]]

enter image description here

where scrambled is the unsorted (original) distance matrix. This was by far the best automated results we were able to obtain. The beauty of it is that by changing the DistanceFunction and the number of requested clusters, we could get many different plausible clusterings.

Improve this answer
$\endgroup$
7
$\begingroup$

Finally I got a feedback from Wolfram support on the AMD algorithm. It turned out that there is (almost as usual) an undocumented implementation of the AMD algorithm within Mathematica. The algorithm is exactly identical to the MATLAB implementation, thus exactly what I was looking for. By calling

SparseArray`ApproximateMinimumDegree[m_Matrix]

one gets the order index array for the preconditioned matrix through

G=G[[order,order]]

The algorithm results in a moderate speedup of the CholeskyDecomposition for very large (rank > 10000) in the range of a few percent. It seems that the Decomposition is in general already somehow optimized. Biggest drawback of the CholeskyDecomposition routine is that it does not return SparseArrays yet. However support told me they are working on an sparse implementation.

Improve this answer
$\endgroup$
6
$\begingroup$

There is an alternative solution to implement AMD into Mathematica, by using the MinCut function from the GraphUtilities Package. This function is not just working on Graphs but is also usable for Matrices.

The algorithm is reordering the Matrix into blocks and effectively reducing the off diagonal elements. It can be involved rather easily. If one starts with a matrix G to be preconditioned the following commands are involved.

Needs["GraphUtilities`"];
order = MinCut[G, Quotient[Length[G], 2]];
G = G[[Flatten[order], Flatten[order]]];

Here Length[G]/2 block diagonals are defined resulting in an almost diagonalized matrix. This matrix is much better suited for CholeskyDecomposition.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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