Matching in Scientific
Computing
Given a
graph G, a matching M is a set of edges such that no two edges in M are
incident on the same vertex. Matching is a fundamental combinatorial problem
that has applications in many contexts: high-performance computing,
bioinformatics, network switch design, web technologies, etc. Examples in the
first context include sparse linear systems, where matchings are used to place
large matrix elements on or close to the diagonal, block triangular
decomposition, computing a sparse basis for the null space or column space of
under-determined matrices, and multi-level graph partitioning algorithms where
matchings are used in the coarsening phase. Click here
for a compendium of applications of the matching problem, and here for a collection of reference material.
Based on the objective function, matching problems can be classified into:
1. Maximum (Cardinality) Matching: Maximize the number of
edges in the matching.
2. Maximum (Edge) Weighted Matching: Maximize the sum of the
weights of the matched edges.
3. Maximum (Vertex) Weighted Matching: Maximize the sum of
the weights of the matched vertices.
Matchings in a bipartite graph are easier to compute than in general (or
nonbipartite) graphs. Similarly, the unweighted versions are easier than the
weighted versions of the matching problem. The weighted versions may also have
additional restrictions on the cardinality of the matching, e.g., a maximum
weight matching among all matchings of maximum cardinality.
Matching algorithms compute optimal solutions in polynomial time with the help
of techniques like augmentation, blossoms and primal-dual formulations.
However, these polynomial time algorithms can still be slow for many scientific
computing applications. Approximation algorithms become important when matching
needs to be computed a large number of times for a given application (for
example, multi-level algorithms), for massive graphs, or in applications with
resource limitations (for example, high-speed network switches that implement
matching algorithms in hardware with severe restrictions on available memory
and high performance requirements).
The need
for parallel algorithms arise when matching needs to be computed on massive
graphs, such as the ones arising from web applications, or when the graph is predistributed on the
processors of a parallel computer.
CSCAPES is
currently developing parallel matching algorithms based on approximation
techniques. Work on serial and exact algorithms has also been undertaken in the
past. Our work has resulted in a 2/3-approximation to the maximum vertex-weight
matching problem for bipartite graphs. Efficient implementations of the
algorithms in C++ are available. Optimal and approximate solutions for all
three kinds of matching problems, discussed above, are available in MatchBox
(except weighted matching in nonbipartite graphs), and parallel implementations
are available in MatchBoxP.
Software:
MatchBox (Serial Code: Requires C++ Compiler)
MatchBoxP (Parallel Code: Requires C++ Compiler and MPI toolkit; predistributed
with Metis)
This
software has not been released yet, but beta users could email the authors for
a trial copy.
Members:
Alex Pothen (apothen at purdue dot
edu)
Florin Dobrian (dobrain at cs dot odu
dot edu)
Mahantesh Halappanavar (mhalappa at odu
dot edu)
Presentations and Papers:
Alex Pothen:
-
-
Parallel Matching algorithms
(CSCAPES Workshop,
Mahantesh Halappanavar:
-
Thesis Proposal (Mahantesh Halappanavar, Thesis proposal,
December 2007)
-
A parallel approximation
matching algorithm (CSCAPES Seminar, September 2008)
Papers are
currently being written.
Compendium of applications of the graph matching
problem: Here
Collection of reference material on graph matching :
Here