Reference implementations

Module name: thewalrus.reference

This submodule provides access to 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\).

Code details

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.
rspm(s)	Generates the restricted set of single-pair matchings.
rpmp(s)	Generates the restricted set of perfect matchings matching permutations.
T(n)	Returns the \(n\) th telephone number.

Code details

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

bitstrings(n)

Returns the bistrings from 0 to n/2

Parameters:

n (int) – Twice the highest bitstring value.

Returns:

An iterable of all bistrings.

Return type:

(iterator)

mapper(x, objects)

Helper function to turn a permutation and bistring into an element of rpmp.

Parameters:

• x (tuple) – tuple containing a permutation and a bistring

• objects (list) – list objects to permute

Returns:

permuted objects

Return type:

tuple

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

mtl(A, loop=False)

Returns the Montrealer of an NxN matrix and an N-length vector.

Parameters:

• A (array) – an NxN array of even dimensions. Can be symbolic.

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

Returns:

the Montrealer of matrix A.

Return type:

np.float64, np.complex128 or sympy.core.add.Add

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

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

rpmp(s)

Generates the restricted set of perfect matchings matching permutations.

Parameters:

s (tuple) – tuple of labels to be used

Returns:

the set of restricted perfect matching permutations of the tuple s

Return type:

generator

rspm(s)

Generates the restricted set of single-pair matchings.

Parameters:

s (tuple) – tuple of labels to be used

Returns:

the set of restricted perfect matching permutations of the tuple s

Return type:

generator

splitter(elem)

Takes an element from the restricted perfect matching permutations (rpmp) and returns all the associated elements in the restricted single pair matchings (rspm)

Parameters:

elem (tuple) – tuple representing an element of rpmp

Returns:

all the associated elements in rspm

Return type:

(iterator)

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

code/reference

 

Download Python script

 

Download Notebook

 

View on GitHub