A New Fast Computation of a Permanent. Issue 1 (March 2020)

• Record Type: Journal Article
• Authors: Niu, Xuewei; Su, Shenghui; Zheng, Jianghua
• Is Part Of: IOP conference series. Volume 790:Issue 1(2020)
• Publication Date: 2020-03
• Subjects: Materials science -- Periodicals; 620.1105
• DOI: 10.1088/1757-899X/790/1/012057
• Languages: English
• ISSNs: 1757-8981

Abstract

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 n 2 n-1 +2 n+1 - n 2 - n -3 additions, n 2 n-1 -2 n +1 multiplications less than the Ryser algorithm, and 2 n-1 +2 n + n 2 - n -2 additions, 2 n +2 multiplications less than the R-NW algorithm. It can be confirmed that the Store-zechin can indeed calculate a permanent in fewer steps.