Efficient computation of the permanent of a sparse matrix

Abstract

Computation of the permanent of a general matrix is a hard problem. However, for a sparse matrix its permanent can be obtained. In this note an efficient method is described for computing the permanent of (0,l)-matrix. The method is based on the numerical structure of a matrix defined in Cushkov [4]. We outline a method with reduced computation efforts and show that, by application on five examples, the method significantly increases the computation speed.

Keywords:

• (0,1)-matrix
• Sparse matrix
• Numerical structure
• Permanent
• Determinant
• Uncompressed storage scheme

C. R. Category::

• F2.1

^∗Corresponding author

^∗Corresponding author

Notes

^∗Corresponding author