An Empirical Study of Algebraic Algorithms in Perfect Matching

Algebraic algorithms in perfect matching can be conceptually simple and theoretically capable of outperforming combinatorial approaches in dense graphs, yet combinatorial algorithms remain the standard in practice.To investigate the practical viability of algebraic methods, we implement the algorithms of Lovász, Rabin and Vazirani, Harvey, and evaluate their correctness and run-times across a wide variety of graph instances.We benchmark these against Kolmogorov's Blossom V, the combinatorial perfect matching software widely considered to be the fastest of its kind.Our results show that our algebraic implementations are 5-250× slower than Blossom V in perfect matching detection, and 328-21000× slower for solving perfect matchings.In all cases, the dominant computational bottleneck was the O(n 3 ) matrix multiplication routines performed by standard linear algebra computer libraries.Additionally, we find finite-field arithmetic to be essential for our purposes, since fixed-precision numerical arithmetic could not guarantee accurate computations in practice.