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
    0 references
    0 references
    0 references
    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

    Identifiers