How fast can one compute the permanent of circulant matrices? (Q1124882)

The authors continue their work [Linear Algebra 267, 65-100 (1997; Zbl 0891.65049)] and investigate structural and computational properties of permanents of circulant matrices. First, computing the permanent of circulants is compared with the general case. The permanents of dense circulants cannot be computed significantly faster than those of arbitrary matrices. Very sparse circulants are not too far from convertible matrices. Taking advantage of this property an efficient algorithm is developed for the computation of the permanent of \((0,1)\)-circulants with three nonzero entries per row. By this algorithm permanents of matrices of size up to 200 can be computed. The efficiency of the algorithm depends on the content of large convertible submatrices and on the matrix sparsity structure.