Permanents.jl Documentation
Permanents.fast_glynn_perm — MethodCompute the permanent of a matrix $A$ of dimension $n$ using Glynn formula
\[perm(A) = (2^{n-1})^{-1} ∑_δ (∏_{k=1}^n δ_k) ∏_{j=1}^n ∑_{j=1}^n δ_i A_{i,j}\]
where $δ ∈ (-1,+1)^n$ with time complexity $O(n2^n)$.
Permanents.naive — MethodComputes the permanent of the matrix $U$ of dimension $n$ using the definition
\[perm(U) = ∑_{σ∈S_n}∏_{i=1}^n U_{i,σ(i)}\]
as a naive implementation in $n!$ arithmetic operations.
Permanents.naive_tensor — MethodCompute the permanent the permanent of a $n^3$-dimensional 3-tensor of the form
\[W_{k,l,j} = M_{k,j} M_{l,j}^* S_{l,k}\]
following Ryser's algorithm in approximatively $2^{2n-1}$ iterations following Sampling of partially distinguishable bosons and the relation to the multidimensional permanent.
The current implementation does not use Gray code.
Permanents.ryser — MethodCompute the permanent of a matrix $A$ of dimension $n$ using Ryser algorithm with Gray ordering
\[perm(A) = (-1)^n ∑_{S ⊆ 1 … n} (-1)^{|S|} ∏_{i=1}^n ∑_{j ∈ S} A_{i,j}\]
and time complexity $O(2^{n-1}n)$.
Permanents.ryser_tensor — MethodCompute the permanent the permanent of a $n^3$-dimensional 3-tensor of the form
\[W_{k,l,j} = M_{k,j} M_{l,j}^* S_{l,k}\]
following Ryser's algorithm in approximatively $2^{2n-1}$ iterations following Sampling of partially distinguishable bosons and the relation to the multidimensional permanent.
The current implementation uses Gray code.