solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看116次
Physics-inspired derivations of some algorithms for computing the permanent. (arXiv:1706.06757v1 [math-ph])
来源于:arXiv
We provide physics-inspired derivations of a number of algorithms for
computing the permanent of a matrix. In particular we formulate the computation
of the permanent as a Grassmann integral that may be viewed as an interacting
many-fermion problem. Applying a discrete Hubbard-Stratonovich decoupling then
gives approximation schemes that are equivalent to the familiar determinant
Monte Carlo algorithm. This leads to elementary derivations of the well-known
estimators of Godsil-Gutman and Karmarkar et al. Another straightfoward
manipulation of the Grassmann integral, making use of gauge invariance, gives
the efficient exact formula of Glynn. In addition to these known results we
also give some additional estimators and formulas that are natural in our
formulation. 查看全文>>