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¶
|
Returns the (loop) hafnian of the matrix \(M\). |
Code details¶
Auxiliary functions¶
|
Decorator used to memoize a generator. |
|
Returns the partitions of a tuple in terms of pairs and singles. |
|
Generator for the set of single pair matchings. |
|
Generator for the set of perfect matching permutations. |
|
Generates the restricted set of single-pair matchings. |
|
Generates the restricted set of perfect matchings matching permutations. |
|
Returns the \(n\) th telephone number. |
Code details¶
- T(n)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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)[source]¶
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