A New Fast Computation of a Permanent
Xuewei Niu, Shenghui Su, Jianghua Zheng · IOP Conference Series Materials Science and Engineering · 2020
Abstract Store-zechin is a general algorithm for computing the permanent of a square matrix, and the core ideas of this algorithm are multiplexing, recursion and storage. It means we just calculate once for every sub-items and for the second time, the previous result is substituted into the calculation. The advantage of Store-zechin algorithm is that it can make full use of computer memories and accelerate the calculations. In fact, it needs 2 n-1 (n- 2) + 1 additions and (2 n-1 - 1)n multiplications for computing the permanent of an n ± n matrix by Store-zechin algorithm. In the same situation, Ryser algorithm requires (2 n - n)(n + 1) – 2 additions and (2 n - 1) (n – 1) multiplications, R-NW algorithm requires 2 n-1 (n + 1) + n 2 - n -1 additions and 2 n-1 n + n + 2 multiplications. So Store-zechin has n2 n-1 +2 n+1 -n 2-n-3 additions, n2 n-1 -2 n +1 multiplications less than the Ryser algorithm, and 2 n-1 +2 n +n 2-n-2 additions, 2n+2 multiplications less than the R-NW algorithm. It can be confirmed that the Store-zechin can indeed calculate a permanent in fewer steps.