Istituto di Informatica e Telematica     
Bernasconi A., Codenotti B., Crespi V., Resta G. How fast can one compute the permanent of circulant matrices?. Technical report, 1997.
In this paper we address the problem of computing the permanent of (0,1)-circulant matrices. We investigate structural properties of circulant matrices, showing that (i) if they are dense enough, then they contain large arbitrary submatrices, and, (ii) if they are very sparse, then they are not too ``far'' from convertible matrices. Building upon (ii), we then develop an efficient algorithm, which allows us to compute permanents of very sparse circulants of size up to 200.
Subject Circulant matrices

Icona documento 1) Download Document PS

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional