3
$\begingroup$

I am facing the multidimensional permanent \begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation} of a 3-tensor $W_{j,k,l}$ of dimension $n$ ($1 \le j,k,l \le n$), and I am looking for the fastest way to evaluate it.

By applying the inclusion-exclusion principle (i.e. following the idea behind Ryser's algorithm), one can compute $\text{perm}(W)$ in around $n^2 2^{2n}$ steps, \begin{equation} \text{perm}(W) = \sum_{S, R \subseteq \{1, \dots , n\} } (-1)^{|S|+|R|} \prod_{j=1}^n \sum_{\substack{ r \in R \\ s \in S}} W_{r,s,j} , \end{equation} and I suppose that, for general $W$, there is nothing significantly faster.

In my (physically motivated) case, the tensor $W$ is structured, and it holds $$ W_{j,k,l} = M_{j,l} M^*_{k,l} {T}_{k,j} , $$ where $M_{j,k}, T_{j,k}$ are a complex $n\times n$-matrices and $T_{k,j}= T^*_{j,k}$ with $T_{j,j}=1$. Is there any way to exploit this "factorizability" to compute the permanent faster than the above adaptation of Ryser's algorithm?

I could only identify the following two special cases: If $T_{j,k}=\delta_{j,k}$, we have $\text{perm}(W)=\text{perm}(|M|^2)$, where the absolute-square is taken element-wise. On the other hand, if $\forall j,k: T_{j,k}=1$, we have $\text{perm}(W)=|\text{perm}(M)|^2$; i.e. in both cases, the problem reduces to computing a matrix-permanent instead of the tensor-permanent.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.