Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices (Q999813)

The author presents a new algorithm for computing the permanent and the Hafnian of banded Toeplitz matrices for cases that were not covered by previously-known methods. Loosely speaking, the main idea behind the new algorithm is to construct a digraph which depends only on the bandwidth and the size of matrix. Certain paths in that digraph correspond to permutations used by the permanent and the Hafnian. Since counting paths can be done efficiently, the permanent and the Hafnian can be computed using simple matrix multiplication of the weighted adjacency matrix of the constructed digraph.