@misc {26133,
title = {A distributed - memory parallel approximation of maximum weight perfect bipartite matching},
howpublished = {Sparse Days 2018, Toulouse, France},
year = {2018},
note = {Similar talk was given again at Inria Bordeaux in October 2018},
abstract = {We discuss efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximumweight. 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 beforefactorization where sequential implementations of maximum weight perfect matching algorithms, are generally used due to the lack of scalable alternatives. To overcome this limitation, we propose a parallel distributed memoryalgorithm and discuss its approximation properties.},
keywords = {Bipartite graphs, graph theory, matching, parallel approximation algorithms, transversals},
author = {Langguth, Johannes and Azad, Ariful and Buluc, Aydin and Li, Xiaoye and Wang, Xinliang}
}
@misc {26376,
title = {A distributed - memory parallel approximation of maximum weight perfect bipartite matching},
howpublished = {Pacific Northwest National Laboratory, Richland, WA, USA},
year = {2018},
abstract = {We discuss efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximumweight. 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 beforefactorization where sequential implementations of maximum weight perfect matching algorithms, are generally used due to the lack of scalable alternatives. To overcome this limitation, we propose a parallel distributed memoryalgorithm and discuss its approximation properties.},
author = {Langguth, Johannes and Azad, Ariful and Buluc, Aydin and Li, Xiaoye and Wang, Xinliang}
}
@article {25986,
title = {A Distributed-Memory Approximation Algorithm for Maximum Weight Perfect Bipartite Matching},
journal = {SIAM Journal on Scientific Computing},
year = {2018},
publisher = {SIAM},
abstract = {We design and implement an efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximum weight. 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 where sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64, are widely used due to the lack of scalable alternatives.To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then searches for weight-augmenting cycles of length four in parallel and iteratively augments the matching with a vertex disjoint set of such cycles. 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.},
keywords = {Bipartite graphs, graph theory, matching, parallel approximation algorithms, transversals},
author = {Azad, Ariful and Buluc, Aydin and Li, Xiaoye and Wang, Xinliang and Langguth, Johannes}
}
@misc {26375,
title = {ExaGraph Collaboration with STRUMPACK/SuperLU: Factorization-Based Sparse Solvers and Preconditioners for Exascale},
year = {2018},
month = {08/2018},
publisher = {Exascale Computing Project (ECP)},
address = {ECP Website},
abstract = {When researchers try to solve science and engineering problems, they often create systems of linear equations that need to be solved. Software libraries known as solvers provide mathematical tools that can be applied to similar problems. Direct solvers that use variants of Gaussian elimination are one of the most popular methods for solving such systems due to their robustness, especially for algebraic systems arising from multiphysics simulations.In many situations, the system is sparse, meaning that the majority of the matrix entries are zero and ideally need neither to be stored nor operated on. The strength of SuperLU and STRUMPACK is that they can automatically determine which matrix entries are zeros and can be ignored, allowing the computer to focus its calculations on the other entries and finish the problem much faster.Results of the effort showed that the parallel AWPM (approximate-weight perfect matching) code can run up to 2,500x faster than the sequential algorithm on 256 nodes of the Cori/KNL supercomputer.},
url = {https://www.exascaleproject.org/exagraph-with-strumpack-superlu/},
author = {Li, Xiaoye and Azad, Ariful and Buluc, Aydin and Ghysels, Pieter and Langguth, Johannes and Wang, Xinliang}
}