  We design and implement an efficient parallel algorithm for finding a perfect
matching in a weighted bipartite graph such that weights on the edges of the
matching are large. This problem differs from the maximum weight matching
problem, for which scalable approximation algorithms are known. It is primarily
motivated by finding good pivots in scalable sparse direct solvers before
factorization. Due to the lack of scalable alternatives, distributed solvers
use sequential implementations of maximum weight perfect matching algorithms,
such as those available in MC64. To overcome this limitation, we propose a
fully parallel distributed memory algorithm that first generates a perfect
matching and then iteratively improves the weight of the perfect matching by
searching for weight-increasing cycles of length four in parallel. For most
practical problems the weights of the perfect matchings generated by our
algorithm are very close to the optimum. An efficient implementation of the
algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer
and can solve instances that are too large to be handled by a single node using
the sequential algorithm.
