next up previous
Next: Large Scale Nonlinear Up: Mathematical Software for Previous: Truncating the Singular

Approximating the Permanent

Isabel Beichl, ACMD
Francis Sullivan, Center for Computing Sciences

The permanent of an nxn matrix with entries is defined by

where the sum is over all permutations of . Informally, it similar to the determinant but without the alternating signs. However, in contrast with the determinant, no efficient procedure for computing this function is known. The permanent is important because it is equivalent to counting perfect matchings of a bipartite graph and arises naturally in a number of fields including discrete optimization, statistical physics and scheduling. Computing the permanent is typical of the kind of combinatorial problems that arise in data communications, a class of issues that NIST will need to face in coming years. Based on our experience in Monte Carlo simulation and in linear algebra we have developed an approximation algorithm that extends the best approximation algorithm for computing the permanent (Jerrum & Sinclair, SIAM J. Comput. v. 18) to a wider class of matrices. We use importance sampling as a method for reducing the variance of the samples generated and thus hasten convergence. We are developing a particularly efficient implementation based on some little known methods of linear algebra and plan to work on the application of this method to real problems in physics.

Generated by on Mon Aug 19 10:08:42 EDT 1996