@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}
}
@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}
}
@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}
}
@article {24590,
title = {Codesign Lessons Learned from Implementing Graph Matching on Multithreaded Architectures},
journal = {IEEE Computer},
volume = {48},
year = {2015},
month = {08/2015},
pages = {46{\textendash}55},
publisher = {ACM IEEE},
doi = {10.1109/MC.2015.215},
url = {http://doi.ieeecomputersociety.org/10.1109/MC.2015.215},
author = {Halappanavar, Mahantesh and Pothen, Alex and Azad, Ariful and Manne, Fredrik and Langguth, Johannes and Arif M. {Khan}}
}
@article {JohaSimula.simula.2866,
title = {On Parallel Push-Relabel Based Algorithms for Bipartite Maximum Matching},
journal = {Parallel Computing},
volume = {40},
number = {7},
year = {2014},
month = {July},
pages = {289-308},
publisher = {Elsevier},
abstract = {We study multithreaded push-relabel based algorithms for computing maximum cardinality matching in bipartite graphs. Matching is a fundamental combinatorial problem with applications in a wide variety of problems in science and engineering. We are motivated by its use in the context of sparse linear solvers for computing the maximum transversal of a matrix. Other applications can be found in many fields such as bioinformatics (Azad et al., 2010) [4], scheduling (Timmer and Jess, 1995) [27], and chemical structure analysis (John, 1995) [14]. We implement and test our algorithms on several multi-socket multicore systems and compare their performance to state-of-the-art augmenting path-based serial and parallel algorithms using a test set comprised of a wide range of real-world instances. Building on several heuristics for enhancing performance, we demonstrate good scaling for the parallel push-relabel algorithm. We show that it is comparable to the best augmenting path-based algorithms for bipartite matching. To the best of our knowledge, this is the first extensive study of multithreaded push-relabel based algorithms. In addition to a direct impact on the applications using matching, the proposed algorithmic techniques can be extended to preflow-push based algorithms for computing maximum flow in graphs.},
doi = {10.1016/j.parco.2014.03.004},
author = {Langguth, Johannes and Azad, Ariful and Halappanavar, Mahantesh and Manne, Fredrik}
}