Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Permanent Computation Efficiency

• To: mathgroup at smc.vnet.net
• Subject: [mg105436] Re: Permanent Computation Efficiency
• From: "g.resta at iit.cnr.it" <g.resta at iit.cnr.it>
• Date: Wed, 2 Dec 2009 06:28:04 -0500 (EST)
• References: <200911181200.HAA04436@smc.vnet.net> <he372o$err$1@smc.vnet.net>

The best algorithm known for the computation of the permanent
in the general case is the Ryser algorithm and has a cost of
O(n 2^n) operations or O(n^2 2^n) depending on the implementation.

http://mathworld.wolfram.com/RyserFormula.html

It is quite simple to implement and it is much faster than the
recursive
algorithm you are discussing, unless the matrix is so sparse
that there are relative few submatrices whose permanent has to
be computed.

Several years ago I used it for computing the permanent
of 0-1 matrices, but I implemented it in C, where some binary tricks
can be
used.

On current hardware, the computation of the permanent
of a random NxN 0-1 matrix (with about one half of entries equal to 1)
takes less than 0.01 sec. for N=16 and about 1 second for N=24.
I do not know how efficient can be Mathematica in comparison.

giovanni resta
--
http://anagram.it : anagrams, alphametics, arithmogriphs,...

• Follow-Ups:
  • Re: Re: Permanent Computation Efficiency
    • From: Daniel Lichtblau <danl@wolfram.com>