Introduction
In high-performance computing (HPC), solving massive systems of linear equations ($Ax = b$) is a foundational task. As datasets scale to billions of entries, traditional sequential bottlenecks become increasingly problematic. One such bottleneck is the process of choosing stable pivots for sparse direct solvers. This paper presents a novel distributed-memory approximation algorithm designed to find heavy-weight perfect matchings in bipartite graphs, effectively shattering the serial limitations of industry-standard tools.
The Bottleneck of Static Pivoting
For numerical stability in sparse matrix factorization, solvers like SuperLU_DIST employ "static pivoting." This involves permuting the matrix so that the diagonal contains the largest possible values, minimizing rounding errors during division. Mathematically, this is modeled as finding a Maximum Weight Perfect Matching (MWPM) in a bipartite graph, where rows and columns are vertices and non-zero entries represent weighted edges.
For decades, the sequential MC64 algorithm has been the gold standard for MWPM. However, in distributed-memory environments, MC64 forces thousands of processors to idle while a single node computes the matching. Because MWPM algorithms involve global data dependencies, they are notoriously difficult to parallelize. The authors address this by relaxing the requirement for an exact maximum weight, focusing instead on a "heavy" matching that is computationally efficient to find in parallel.
The HWPM Algorithm
The proposed Heavy-Weight Perfect Matching (HWPM) algorithm is a primal method that maintains a feasible perfect matching and iteratively improves it. The pipeline transitions from a raw matrix to a high-quality matching through distinct phases of cardinality maximization and weight refinement.
Phase 1: Initial Matching with Tie-Breaking
The algorithm begins by finding a Maximum Cardinality Matching (MCM) using a distributed-memory approach. A key innovation here is the introduction of a weight-aware tie-breaking heuristic. When the algorithm identifies multiple potential augmenting paths to increase the matching size, it prioritizes those containing edges with higher weights. This ensures that the initial perfect matching is already "heavy" before any refinement begins.
Phase 2: Weight-Increasing Alternating Cycles (WIAC)
Once a perfect matching is established, the algorithm enters an iterative refinement phase. It searches for alternating cycles of length four—the shortest possible alternating cycles—that can be "flipped" to increase the total weight. By restricting the search to length-4 cycles, the algorithm maintains linear time complexity and requires only a constant number of communication rounds. The matrix is distributed across a 2D process grid, allowing each process to identify potential cycles locally and resolve collisions with neighbors in parallel.
Experimental Evaluation
The algorithm was implemented as part of the Combinatorial BLAS library and evaluated using over 100 sparse matrices from the SuiteSparse Matrix Collection. These ranged from small-scale benchmarks to massive matrices with over 200 million non-zeros, such as NaluR3 and nlpkkt240.
Scalability and Speed
Testing on the Cray XC40 "Cori" supercomputer demonstrated exceptional scalability. The HWPM algorithm scaled up to 256 nodes (17,408 cores), achieving speedups of up to 2500x over the sequential MC64. Even when compared to parallel implementations on a single node, the distributed approach provided a 114x performance boost.
Solution Quality
Despite being an approximation, the HWPM algorithm consistently found matchings with weights within 99% of the optimal values calculated by MC64. When integrated into the SuperLU_DIST solver, the algorithm reduced the pre-pivoting phase from a multi-second bottleneck to a negligible task taking only milliseconds.
Conclusion
The HWPM algorithm represents a significant step forward for distributed sparse solvers. By prioritizing locality and employing clever heuristics, the authors have created a tool that maintains high numerical stability while scaling to the limits of modern supercomputers. Future work aims to establish theoretical approximation bounds and develop methods for generating distributed dual variables to further enhance solver performance.
Summary updated