# Dulmage-Mendelsohn decomposition

Discussion in 'C Programming' started by Jon Klingensmith, Oct 17, 2003.

1. ### Jon KlingensmithGuest

Does anyone know where to find an implementation in C of the
Dulmage-Mendelsohn decomposition of a sparse matrix, like the 'dmperm'
command in MATLAB?

Thanks,
Jon

Jon Klingensmith, Oct 17, 2003

2. ### Tristan MillerGuest

Greetings.

In article <>, Jon
Klingensmith wrote:
> Does anyone know where to find an implementation in C of the
> Dulmage-Mendelsohn decomposition of a sparse matrix, like the 'dmperm'
> command in MATLAB?

Not here, but the people on comp.sources.wanted or sci.math.num-analysis
probably do.

--
_
_V.-o Tristan Miller [en,(fr,de,ia)] >< Space is limited
/ |`-' -=-=-=-=-=-=-=-=-=-=-=-=-=-=-= <> In a haiku, so it's hard
(7_\\ http://www.nothingisreal.com/ >< To finish what you

Tristan Miller, Oct 17, 2003

3. ### Arthur J. O'DwyerGuest

On Fri, 17 Oct 2003, Jon Klingensmith wrote:
>
> Does anyone know where to find an implementation in C of the
> Dulmage-Mendelsohn decomposition of a sparse matrix, like the 'dmperm'
> command in MATLAB?

This question is fairly off-topic here; a better question would
have been, "Here's some code that is supposed to find a maximal
matching in a bipartite graph; why doesn't it work right?"

Note also that you've really got two questions here: how to perform
DMD, and how to handle sparse matrices in C. Perhaps some people
here have had experience with sparse matrices, but I doubt many
have had occasion to use DMD ::brings foot to neck level in
preparation::

Several solutions present themselves immediately:

'open dmperm' in Matlab; cut and paste; translate into C.

you'll have to struggle with Matlab's defined types instead
of simple arrays and whatnot.

Read Problem 2 in this handout
http://www.cs.mcgill.ca/~fukuda/610A/handouts/assignment2.pdf
and see if you can follow the algorithm given. That's the
best thing I could find in five minutes with Google. Requires
knowledge of some acronyms.

If all else fails, hire yourself a C programmer to write the
code for you.

HTH,
-Arthur

Arthur J. O'Dwyer, Oct 17, 2003