Advanced

A faster hafnian formula for complex matrices and its benchmarking on a supercomputer

Björklund, Andreas LU ; Gupt, Brajesh and Quesada, Nicolás (2019) In ACM Journal of Experimental Algorithmics 24(1).
Abstract

We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of n × n complex matrices run in O(n32n/2) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 × 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 × 100 matrix.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Gaussian boson sampling, Hafnian, Perfect matching
in
ACM Journal of Experimental Algorithmics
volume
24
issue
1
pages
17 pages
external identifiers
  • scopus:85067788588
ISSN
1084-6654
DOI
10.1145/3325111
language
English
LU publication?
yes
id
48be8e16-9833-4b7a-89a4-2be02de7014b
date added to LUP
2019-07-05 13:44:40
date last changed
2019-07-30 05:06:11
@article{48be8e16-9833-4b7a-89a4-2be02de7014b,
  abstract     = {<p>We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of n × n complex matrices run in O(n<sup>3</sup>2<sup>n/2</sup>) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 × 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 × 100 matrix.</p>},
  articleno    = {1.11},
  author       = {Björklund, Andreas and Gupt, Brajesh and Quesada, Nicolás},
  issn         = {1084-6654},
  keyword      = {Gaussian boson sampling,Hafnian,Perfect matching},
  language     = {eng},
  number       = {1},
  pages        = {17},
  series       = {ACM Journal of Experimental Algorithmics},
  title        = {A faster hafnian formula for complex matrices and its benchmarking on a supercomputer},
  url          = {http://dx.doi.org/10.1145/3325111},
  volume       = {24},
  year         = {2019},
}