Velocity Reviews > Dulmage-Mendelsohn decomposition

# Dulmage-Mendelsohn decomposition

Jon Klingensmith
Guest
Posts: n/a

 10-17-2003
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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Tristan Miller
Guest
Posts: n/a

 10-17-2003
Greetings.

In article <(E-Mail Removed) >, 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

Arthur J. O'Dwyer
Guest
Posts: n/a

 10-17-2003

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.

Use MCC to link your C files with mlfDmperm(); but then
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...ssignment2.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