Random path method with pivoting for computing permanents of matrices (Q870138): Difference between revisions
From MaRDI portal
Latest revision as of 15:48, 25 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random path method with pivoting for computing permanents of matrices |
scientific article |
Statements
Random path method with pivoting for computing permanents of matrices (English)
0 references
12 March 2007
0 references
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.
0 references
permanent
0 references
Monte Carlo method
0 references
Rasmussen method
0 references
unbiased estimator
0 references
random path method
0 references
numerical examples
0 references
0 references