How fast can one compute the permanent of circulant matrices? (Q1124882)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | How fast can one compute the permanent of circulant matrices? |
scientific article |
Statements
How fast can one compute the permanent of circulant matrices? (English)
0 references
29 November 1999
0 references
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.
0 references
sparse matrices
0 references
permanents
0 references
circulant matrices
0 references
\((0,1)\)-circulants
0 references
algorithm
0 references