Information about Sparse Data Structures for Weighted Bipartite Matching

A stab at optimizing the inner loop for auctiion-based, sparse bipartite matching.

Use Sparse Matrix Optimizations... Take a ﬁxed, simple algorithm: Auction alg. for matchings Repeated iterations over a sparse graph. What’s expensive, and is there anything we can do about it? Take an idea from optimizing sparse matrix-vector products. A little speed-up in some cases, but there are more ideas available...

Where’s the Time Going? Auction algorithm: Iterative, greedy algorithm bipartite matching: 1. An unmatched row i ﬁnds a “most proﬁtable” column j π(i) = maxj b(i, j) − p(i) 2. Row i places a bid for column j. Bid price raised until j is no longer the best choice. (Min. increment µ) 3. Highest bid gets the matching (i, j).

Time linear in entries examined... Number of entries examined is problem-dependent. 4.5 4 3.5 3 time (s) 2.5 2 1.5 1 0.5 0 0 5e+06 1e+07 1.5e+07 2e+07 2.5e+07 3e+07 number of entries examined

Expensive Inner Loop! 1.3 GHz Itanium 2 10 8 6 4 2 0 100 150 200 250 300 350 400 450 cycles per entry

Verifying... Using kcachegrind (N.Nethercote and J.Weidendorfer) and valgrind (J. Seward).

And Locating... No obvious culprits in the instructions...

And Locating... But considering cache eﬀects!

Auction’s Inner Loop Price Index Entry value = entry - price save largest...

Auction’s Inner Loop Same accesses as sparse matrix-vector multiplication! Price Index Entry y += a(i,j) * x(j)

Performance Through Blocking? (Images swiped from Berkeley’s BeBOP group.)

Performance Through Blocking? (Images swiped from Berkeley’s BeBOP group.)

Performance Through Blocking? More entries, but 1.5× performance on Pentium 3! (Images swiped from Berkeley’s BeBOP group.)

Blocking Speeds Some Matches Finite element matrix from Vavasis (in UF collection):

Blocking Speeds Some Matches

Blocking Speeds Some Matches

Observations A blocked graph data structure may provide additional performance if: you iterate over whole rows, the graph / matrix has runs of columns, and you’re willing to use an automated tuning system. Maximizing the runs: linear arrangement. Hard, but there may be cheap heuristics. Only worth-while if you’re performing many iterations. (For mat-vec, often > 50 computations of Ax.)

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy∗ Dr. James Demmel UC Berkeley October 31, 2003 1 Introduction Inspired by the ...

Read more

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy∗ Dr. James Demmel UC Berkeley October 31, 2003 1 Introduction Inspired by the ...

Read more

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy Dr. James Demmel (... and thanks to the BeBOP group) SIAM Workshop on Combinatorial ...

Read more

Fast Algorithms for Weighted Bipartite Matching ... ings between the two structures, one has to solve a weighted ... This was improved for sparse ...

Read more

Finding a maximum bipartite matching ... for sparse graphs, ~ ... A maximum weighted bipartite matching ...

Read more

In this paper we consider the problem of finding maximum weighted matchings in bipartite ... Weighted Bipartite Matching in Matrix ... Data Structures, ...

Read more

A Parallel ½-approx Weighted Matching Algorithm ... –Nonbipartite / Bipartite –Weighted / Unweighted w S T 3. ... •Vertex-oriented data structures ...

Read more

VERTEX-WEIGHTED MATCHING IN GRAPHS ... 2 Power of data structures. ... A bipartite graph G, (b) a matching M

Read more

Vertex-Weighted Matching in Two-Directional ... rithm for left-weighted convex bipartite matching ... topic of augmented BST data structures, ...

Read more

## Add a comment