Reference implementations

This submodule provides access to pure-Python reference implementations of the hafnian and loop hafnian by summing over the set of perfect matching permutations or the set of single pair matchings.

For more details on these definitions see:

• Andreas Björklund, Brajesh Gupt, and Nicolás Quesada. “A faster hafnian formula for complex matrices and its benchmarking on the Titan supercomputer” arxiv:1805.12498 (2018)

Reference functions

hafnian(M[, loop])

Returns the (loop) hafnian of the matrix \(M\).

Details

hafnian(M, loop=False)

Returns the (loop) hafnian of the matrix \(M\).

\(M\) can be any two-dimensional object of square shape \(m\) for which the elements (i, j) can be accessed via Python indexing M[i, j], and for which said elements have well defined multiplication __mul__ and addition __add__ special methods.

For example, this includes nested lists and NumPy arrays.

In particular, one can use this function to calculate symbolic hafnians implemented as SymPy matrices.

Parameters

• M (array) – a square matrix

• loop (boolean) – if set to True, the loop hafnian is returned

Returns

The (loop) hafnian of M

Return type

scalar

Auxiliary functions

memoized(f[, maxsize])	Decorator used to memoize a generator.
partitions(s[, singles, pairs])	Returns the partitions of a tuple in terms of pairs and singles.
spm(s)	Generator for the set of single pair matchings.
pmp(s)	Generator for the set of perfect matching permutations.
T(n)	Returns the \(n\) th telephone number.

Details

memoized(f, maxsize=1000)

Decorator used to memoize a generator.

The standard approach of using functools.lru_cache cannot be used, as it only memoizes the generator object, not the results of the generator.

See https://stackoverflow.com/a/10726355/10958457 for the original implementation.

Parameters

• f (function or generator) – function or generator to memoize

• maxsize (int) – positive integer that defines the maximum size of the cache

Returns

the memoized function or generator

Return type

function or generator

partitions(s, singles=True, pairs=True)

Returns the partitions of a tuple in terms of pairs and singles.

Parameters

• s (tuple) – a tuple representing the (multi-)set that will be partitioned. Note that it must hold that len(s) >= 3.

• single (boolean) – allow singles in the partitions

• pairs (boolean) – allow pairs in the partitions

Returns

a generators that goes through all the single-double partitions of the tuple

Return type

generator

spm(s)

Generator for the set of single pair matchings.

Parameters

s (tuple) – an input tuple

Returns

the set of single pair matching of the tuple s

Return type

generator

pmp(s)

Generator for the set of perfect matching permutations.

Parameters

s (tuple) – an input tuple

Returns

the set of perfect matching permutations of the tuple s

Return type

generator

T(n)

Returns the \(n\) th telephone number.

They satisfy the recursion relation \(T(n) = T(n-1)+(n-1)T(n-2)\) and \(T(0)=T(1)=1\).

See https://oeis.org/A000085 for more details.

Parameters

n (integer) – index

Returns

the nth telephone number

Return type

int

code/reference

 

Download Python script

 

Download Notebook

 

View on GitHub