Random path method with pivoting for computing permanents of matrices (Q870138): Difference between revisions

The authors propose a simple and practical random path (RP) method with column pivoting for approximating the permanent of a matrix. Several methods, including Monte Carlo-type methods, are reviewed from the viewpoint of practical applications. The method of \textit{L. E. Rasmussen} [Random Struct. Algorithms 5, No. 2, 349--361 (1994; Zbl 0795.05089)] is singled out since RP=RAS+column pivoting. An analysis of the RP method and numerical computations support its efficiency. It is worth noticing that RP does not require the non-negativity of the entries of a matrix \(A\). Thus RP can be easily extended to estimate permanents of arbitrary matrices whose entries are arbitrary integers or even real numbers.