How fast can one compute the permanent of circulant matrices?
type: Item
instance of: scholarly article
title: How fast can one compute the permanent of circulant matrices?
zbMATH Open document ID: 0933.65045
DOI: 10.1016/S0024-3795(99)00012-9
author: Bruno Codenotti
author: A. Bernasconi
author: Valentino Crespi
author: Giovanni Resta
published in: Linear Algebra and its Applications
publication date: 1999-11-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 1371382
zbMATH Keywords: sparse matrices
zbMATH Keywords: permanents
zbMATH Keywords: circulant matrices
zbMATH Keywords: \((0,1)\)-circulants
zbMATH Keywords: algorithm
MaRDI profile type: Publication
Wikidata QID: Q128153645
Recommended article: Computing the permanent of (some) complex matrices
Recommended article: How Fast are Nonsymmetric Matrix Iterations?
Recommended article: Q2704232
Recommended article: Efficient computation of the permanent of a sparse matrix
Recommended article: A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
Recommended article: Q4463127
Recommended article: Computation of sparse circulant permanents via determinants
Recommended article: Q3591202
Recommended article: A fast computer algorithm for finding the permanent of adjacency matrices
Recommended article: A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
description: scientific article; zbMATH DE number 1371382