# Sparse Data Structures for Weighted Bipartite Matching

60 %
40 %
Information about Sparse Data Structures for Weighted Bipartite Matching
Technology

Published on November 1, 2008

Author: jasonriedy

Source: slideshare.net

## Description

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

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

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.)

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### Sparse Data Structures for Weighted Bipartite Matching

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

### Sparse Data Structures for Weighted Bipartite Matching ...

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

### Sparse Data Structures for Weighted Bipartite Matching

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

### LNCS 3503 - Fast Algorithms for Weighted Bipartite Matching

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

### Matching (graph theory) - Wikipedia, the free encyclopedia

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

### Weighted Bipartite Matching in Matrix Multiplication Time ...

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

### Parallel ½-approx Weighted Matching Algorithm

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