| dc.description.abstract | Recently, there has been a significant desire both within the scientific community and industry to write graph algorithms using linear algebraic operations. This leads to algorithms that can leverage many important algebraic properties of matrix operations, as well as the vast body of research conducted in high performance and parallel linear algebra computations. In addition, such formulations usually lead to densely expressive and short code. To this end, SuiteSparse:GraphBLAS is a framework developed to easily write graph algorithms in the language of linear algebra. LAGraph is a test harness and collection of algorithms written with SuiteSparse; this work will detail the contribution of new algorithms to this collection, which perform maximal matching and coarsening of undirected graphs. A matching is a subset of the edges of a graph such that no two edges in the set share a common vertex. A maximal matching is one that is not a proper subset of any other matching. Finding any maximal matching is a simple process, but it is hard to find ones with optimal characteristics (i.e. maximum sum of edge weights, maximum size of matching, etc). Coarsening refers to reducing the size of a graph in a manner that preserves connectivity information. One way to achieve this is by collapsing edges in a maximal matching. It is known from prior work that matching-based coarsening produces small graphs that can be easily bisected (a process known as multilevel bisection). By projecting the coarsened graph back to its original size, and applying refinements at each stage, multilevel bisection can be recursively used to approximate good k-way partitions, which is known to be an NP-complete problem. We begin with a discussion of the mathematical background behind linear algebraic graph algorithms and the GraphBLAS standard. We then discuss graph partitioning and multilevel techniques further in depth. Finally, we present our algorithms, their performance results, and discuss avenues for future work. | |
