Computing the permanent

Computing the permanent

In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions.

The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant assigns a ±1 sign to each of these products, the permanent does not.

While the determinant can be computed in polynomial time by Gaussian elimination, Gaussian elimination cannot be used to compute the permanent. In computational complexity theory, a theorem of Valiant states that computing permanents, even of matrices in which all entries are 0 or 1, is #P-complete Valiant (1979) putting the computation of the permanent in a class of problems believed to be even more difficult to compute than NP. It is known that computing the permanent is impossible for logspace-uniform ACC0 circuits (Allender & Gore 1994).

Despite, or perhaps because of, its computational difficulty, there has been much research on exponential-time exact algorithms and polynomial time approximation algorithms for the permanent, both for the case of the 0-1 matrices arising in the graph matching problems and more generally.

Definition and naive algorithm

The permanent of an n-by-n matrix A = (ai,j) is defined as

$\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$

The sum here extends over all elements σ of the symmetric group Sn, i.e. over all permutations of the numbers 1, 2, ..., n. This formula differs from the corresponding formula for the determinant only in that, in the determinant, each product is multiplied by the sign of the permutation σ while in this formula each product is unsigned. The formula may be directly translated into an algorithm that naively expands the formula, summing over all permutations and within the sum multiplying out each matrix entry. This requires n! n arithmetic operations.

Ryser formula

The fastest known [1] general exact algorithm is due to Herbert John Ryser (Ryser (1963)). Ryser’s method is based on an inclusion–exclusion formula that can be given[2] as follows: Let Ak be obtained from A by deleting k columns, let P(Ak) be the product of the row-sums of Ak, and let Σk be the sum of the values of P(Ak) over all possible Ak. Then

$\operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k}\Sigma_k.$

It may be rewritten in terms of the matrix entries as follows[3]

$\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.$

Ryser’s formula can be evaluated using O(2nn2) arithmetic operations, or O(2nn) by processing the sets S in Gray code order.

Glynn formula

Another formula that appears to be as fast as Ryser's is closely related to the polarization identity for a symmetric tensor Glynn (2010).

It has the formula (when the characteristic of the field is not two)

$\operatorname{perm} (A) =\left[ \Sigma_{\delta} ~ (\Pi_{k=1}^m~\delta_k)~ \Pi_{j=1}^m~\Sigma_{i=1}^m ~\delta_i a_{ij}\right]/2^{m-1},$

where the outer sum is over all 2m − 1 vectors $\delta=(\delta_1=1,\delta_2,\dots,\delta_m)\in \{\pm1\}^m$.

Special cases

The number of perfect matchings in a bipartite graph is counted by the permanent of the graph's biadjacency matrix, and the permanent of any 0-1 matrix can be interpreted in this way as the number of perfect matchings in a graph. For planar graphs (regardless of bipartiteness), the FKT algorithm computes the number of perfect matchings in polynomial time by changing the signs of a carefully chosen subset of the entries in the Tutte matrix of the graph, so that the Pfaffian of the resulting skew-symmetric matrix (the square root of its determinant) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph homeomorphic to the complete bipartite graph K3,3. [4]

George Pólya had asked the question[5] of when it is possible to change the signs of some of the entries of a 01 matrix A so that the determinant of the new matrix is the permanent of A. Not all 01 matrices are "convertible" in this manner; in fact it is known (Marcus & Minc (1961)) that there is no linear map T such that $\operatorname{per}\,T(A) = \det A$ for all $n\times n$ matrices A. The characterization of "convertible" matrices was given by Little (1975) who showed that such matrices are precisely those that are the biadjacency matrix of bipartite graphs that have a Pfaffian orientation: an orientation of the edges such that for every even cycle C for which $G\setminus C$ has a perfect matching, there are an odd number of edges directed along C (and thus an odd number with the opposite orientation). It was also shown that these graphs are exactly those that do not contain a subgraph homeomorphic to K3,3, as above.

Computation modulo a number

Modulo 2, the permanent is the same as the determinant, as $(-1) \equiv 1 \pmod 2.$ It can also be computed modulo 2k in time O(n4k − 3) for $k \ge 2$. However, it is UP-hard to compute the permanent modulo any number that is not a power of 2. Valiant (1979)

There are various formulae given by Glynn (2010) for the computation modulo a prime p. Firstly there is one using symbolic calculations with partial derivatives.

Secondly for p = 3 there is the following formula using the determinants of the principal submatrices of the matrix:

$\operatorname{perm} (A) = (-1)^{m-1}\Sigma_{U\subset \{2,\dots,m\}} \det(A_U).\det(A_{\bar U}),$

where AU is the principal submatrix of A induced by the rows and columns of A indexed by U, and $\bar U$ is the complement of U in $\{1,\dots,m\}.$

Approximate computation

When the entries of A are nonnegative, the permanent can be computed approximately in probabilistic polynomial time, up to an error of εM, where M is the value of the permanent and ε > 0 is arbitrary. In other words, there exists a fully polynomial-time randomized approximation scheme (FPRAS) (Jerrum, Vigoda & Sinclair (2001)).

The main part of the computation is the construction of an algorithm to sample almost uniformly from the set of all perfect matchings in a given bipartite graph: in other words, a fully polynomial almost uniform sampler (FPAUS). This is a Markov chain Monte Carlo algorithm: it consists of running a Markov chain whose distribution is close to uniform (achieved using a Metropolis rule), and whose mixing time is polynomial.

Once there is a FPAUS, it is possible to approximately count the number of perfect matchings using the self-reducibility of the permanent, using a well-known reduction from sampling to counting due to Jerrum, Valiant & Vazirani (1986). Let M(G) be the number of perfect matchings in G. Roughly, for any particular edge e in G, by sampling many matchings in G and counting how many of them are matchings in $G \setminus e$, one can obtain an estimate of the ratio $\rho=\frac{M(G)}{M(G\setminus e)}$. The number M(G) is then $\rho M(G \setminus e)$, where $M(G \setminus e)$ is found recursively by the same method.

References

• Allender, Eric; Gore, Vivec (1994), "A uniform circuit lower bound for the permanent", SIAM J. Comput. 23 (5): 1026–1049
• David G. Glynn (2010), "The permanent of a square matrix", European Journal of Combinatorics 31 (7): 1887–1891, doi:10.1016/j.ejc.2010.01.010
• Jerrum, M.; Sinclair, A.; Vigoda, E. (2001), "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries", Proc. 33rd Symposium on Theory of Computing, pp. 712–721, doi:10.1145/380752.380877, ECCC TR00-079
• Mark Jerrum; Leslie Valiant; Vijay Vazirani (1986), "Random generation of combinatorial structures from a uniform distribution", Theoretical Computer Science 43: 169–188, doi:10.1016/0304-3975(86)90174-X
• van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), A Course in Combinatorics, ISBN 0521006015
• Little, C. H. C. (1974), "An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs", in Holton, D., Proc. 2nd Australian Conf. Combinatorial Mathematics, Lecture Notes in Mathematics, 403, Springer-Verlag, pp. 63–72
• Little, C. H. C. (1975), "A characterization of convertible (0, 1)-matrices", J. Combin. Theory Series B 18 (3): 187–208, doi:10.1016/0095-8956(75)90048-9
• Marcus, M.; Minc, H. (1961), "On the relation between the determinant and the permanent", Illinois J. Math. 5: 376–381
• Pólya, G. (1913), "Aufgabe 424", Arch. Math. Phys. 20 (3): 27
• Reich, Simeon (1971), "Another solution of an old problem of pólya", American Mathematical Monthly 78 (6): 649–650, doi:10.2307/2316574, JSTOR 2316574
• Rempała, Grzegorz A.; Wesolowski, Jacek (2008), Symmetric Functionals on Random Matrices and Random Matchings Problems, pp. 4, ISBN 0387751459
• Ryser, H. J. (1963), Combinatorial Mathematics, The Carus mathematical monographs, The Mathematical Association of America
• Vazirani, Vijay V. (1988), "NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems", Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT '88), Lecture Notes in Computer Science, 318, Springer-Verlag, pp. 233–242, doi:10.1007/3-540-19487-8_27
• Leslie G. Valiant (1979), "The Complexity of Computing the Permanent", Theoretical Computer Science (Elsevier) 8 (2): 189–201, doi:10.1016/0304-3975(79)90044-6
• "Permanent", CRC Concise Encyclopedia of Mathematics, Chapman & Hall/CRC, 2002

Wikimedia Foundation. 2010.

Поможем написать реферат

Look at other dictionaries:

• Permanent is sharp-P-complete — The correct title of this article is Permanent is #P complete. The substitution or omission of the # sign is because of technical restrictions. In a 1979 paper Leslie Valiant proved[1] that the problem of computing the permanent of a matrix is #P …   Wikipedia

• Permanent — In linear algebra, the permanent of a matrix is a function of a matrix related to the determinant. The permanent as well as the determinant are polynomials of the entries of the matrix. Definition The permanent of an n by n matrix A = ( a i,j )… …   Wikipedia

• The Singularity Is Near — The Singularity Is Near: When Humans Transcend Biology   …   Wikipedia

• The Culture — is a fictional interstellar anarchist, socialist, and utopian[1][2] society created by the Scottish writer Iain M. Banks which features in a number of science fiction novels and works of short fiction by him, collectively called the Culture… …   Wikipedia

• The Showcase (The Price Is Right) — The Showcase is the major prize round on the game show The Price Is Right .The two winners of the Showcase Showdowns in each episode compete against each other in the Showcase; in the show s original half hour format, the two on stage contestants …   Wikipedia

• The Age of Spiritual Machines — Infobox Book name = The Age of Spiritual Machines: When Computers Exceed Human Intelligence title orig = translator = image caption = author = Ray Kurzweil illustrator = cover artist = country = language = series = subject = genre = publisher =… …   Wikipedia

• The O2 — Infobox building|right building name= building type=Entertainment District former names= Millennium Dome architectural style=Dome structural system=Steel tensioned fabric location=The O2 Drawdock Road / Millennium Way Greenwich Peninsula North… …   Wikipedia

• Proposed directive on the patentability of computer-implemented inventions — The Proposal for a Directive of the European Parliament and of the Council on the patentability of computer implemented inventions (Commission proposal COM(2002) 92),[1] procedure number 2002/0047 (COD)[2] was a proposal for a European Union (EU) …   Wikipedia

• The O2 (London) — This article is about the entertainment district incorporating the former Millennium Dome. For the indoor arena within it, see The O2 Arena (London). For its counterpart in Ireland, see The O2 (Dublin). For other uses, see O2. Coordinates:… …   Wikipedia

• The Bill Robertson Library — About The Bill Robertson Library provides library and information services to the staff and students of the Dunedin College of Education and Otago Polytechnic, New Zealand. There are four branches of the library: *Union Street East *Tennyson… …   Wikipedia