Efficient Evaluation of Rectangular Matrix Permanents

Abstract

Evaluating the permanent of a matrix is a fundamental computation that emerges in many domains, including traditional fields like computational complexity theory, graph theory, and many-body quantum theory and emerging disciplines like machine learning and quantum computing. While conceptually simple, evaluating the permanent is extremely challenging: no polynomial-time algorithm is available. This thesis presents a software package that we designed to evaluate the permanent of an arbitrary rectangular matrix, supporting three algorithms (the straightforward combinatoric algorithm, the Ryser algorithm, and the Glynn algorithm) and, optionally, automatically switching to the optimal algorithm based on the type and dimensionality of the matrix of interest. To do this, we developed an extension of the Glynn algorithm to rectangular matrices. Except for very small matrices (where the naive combinatoric algorithm is best) and very rectangular matrices (where the Ryser algorithm is the best), the Glynn algorithm is fastest. In addition to our computational tests, we applied the method by incorporating it into PyCI, allowing the antisymmetric product of interacting geminals wavefunction to be evaluated with unprecedented speed. We believe that the methods we developed, together with their efficient implementation, will be broadly useful to mathematicians, physicists, and chemists and, accordingly, our software package is distributed as free and open-source software on Github, at https://github.com/theochem/matrix-permanent.