Optimizing and benchmarking the computation of the permanent of general matrices

• URL: http://arxiv.org/abs/2510.03421v1
• Date: Fri, 03 Oct 2025 18:32:04 GMT
• Title: Optimizing and benchmarking the computation of the permanent of general matrices
• Authors: Cassandra Masschelein, Michelle Richer, Paul W. Ayers,
• Abstract summary: evaluating the permanent of a matrix is a fundamental computation that emerges in many domains.<n>There is no publicly available software that automatically uses the most efficient algorithm for computing the permanent.<n>In this work we designed, developed, and investigated the performance of our software package which evaluates the permanent of an arbitrary rectangular matrix.
• Score: 11.873893621488527
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, 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 (unless $\textsc{P} = \textsc{NP}$). To the best of our knowledge there is no publicly available software that automatically uses the most efficient algorithm for computing the permanent. In this work we designed, developed, and investigated the performance of our software package which evaluates the permanent of an arbitrary rectangular matrix, supporting three algorithms generally regarded as the fastest while giving the exact solution (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 input matrix. To do this, we developed an extension of the Glynn algorithm to rectangular matrices. Our free and open-source software package is distributed via Github, at https://github.com/theochem/matrix-permanent.

Related papers

• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems.<n>We show that under standard cryptographic assumptions, we can design algorithms that are determinantally faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• Quantum algorithms for optimizers [0.24475591916185502]
  This is a set of lecture notes for a graduate-level course on quantum algorithms.<n>It is developed for applied mathematicians and engineers, and requires no previous background in quantum mechanics.<n>The main topics of this course, in addition to a rigorous introduction to the computational model, are: input/output models, quantum search, the quantum gradient algorithm, matrix manipulation algorithms, the mirror descent framework for semidefinite optimization.
  arXiv  Detail & Related papers  (2024-08-08T16:43:49Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra [6.338178373376447]
  We propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. Our method can improve the runtime of solving quantum linear systems of dimension $N$ to $O(kappa operatornamepolylog(fracNvarepsilon))$.
  arXiv  Detail & Related papers  (2022-01-27T05:24:02Z)
• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer [0.0]
  Harrow-Hassidim-Lloyd algorithm is intended for solving the system of linear equations on quantum devices. We present a numerical study of the performance of the algorithm when these caveats are not perfectly matched.
  arXiv  Detail & Related papers  (2021-09-17T15:22:06Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.