A New Fast Recursive Matrix Multiplication Algorithm
- PDF / 100,118 Bytes
- 5 Pages / 594 x 792 pts Page_size
- 90 Downloads / 240 Views
A NEW FAST RECURSIVE MATRIX MULTIPLICATION ALGORITHM
L. D. Jelfimova
UDC 681.322.012
Abstract. A new recursive algorithm is proposed for multiplying matrices of order n = 2 q ( q > 1) . This algorithm is based on a fast hybrid algorithm for multiplying matrices of order n = 4m with m = 2 q -1 ( q > 0) . As compared with the well-known recursive Strassen’s and Winograd–Strassen’s algorithms, the new algorithm minimizes the multiplicative complexity equal to Wm » 0.932 n 2 . 807 multiplication operations at recursive level d = log 2 n - 3 by 7% and reduces the computation vector by three recursion steps. The multiplicative complexity of the algorithm is estimated. Keywords: linear algebra, block-recursive Strassen’s algorithm, block-recursive Winograd’s–Strassen’s algorithm, family of fast hybrid matrix multiplication algorithms. At present, with increasing requirements on the speed of solving modern problems that require large volumes of computations with dense matrices, the problem of obtaining fast efficient matrix algorithms in which multiplicative complexity is dominant is topical. Among well-known fast matrix multiplication algorithms, the regular Winograd algorithm [1] and block-recursive algorithms of Strassen [2], Winograd–Strassen [3], and Laderman [4] are efficient in practice and are used in many object domains, especially in processing digital signals and images and for high-speed computations in real time. The first fast regular algorithm for multiplying ( n ´ n) matrices was developed by Winograd [1]; its multiplicative complexity amounted to O (0 .5n 3 + n 2 ) multiplication operations, and the additive and total complexities were accordingly equal to O (1. 5n 3 + 2n 2 - 2n) addition operations and O (2n 3 + 3n 2 - 2n) multiplication/addition operations. In 1969, V. Strassen proposed a fast block-recursive algorithm for multiplying matrices of order n = 2 q ( q > 0) [2] whose multiplicative complexity equals O ( n log 2 7 ) ~ O ( n 2 . 807 ) multiplication operations. As the basic algorithm, V. Strassen used an algorithm for multiplying (2 ´ 2) matrices that requires seven multiplication operations and 18 addition operations. This recursive algorithm is executed in log 2 n recursion steps and is efficient when the order of matrices is large ( n ³ 64) . In 1971, S. Winograd proposed a modified version [3] of Strassen’s algorithm that allowed to minimize the additive complexity of the algorithm from [2] with the constant multiplicative complexity O ( n 2 . 807 ) multiplication operations. In 1976, J. D. Laderman developed a block-recursive algorithm for multiplying matrices of order n = 3 q ( q > 0) [4] with multiplicative complexity equal to O ( n log 3 23 ) ~ O ( n 2 . 854 ) multiplication operations. As the basic algorithm, J. D. Laderman used an algorithm for multiplying (3 ´ 3) matrices that requires 23 multiplication operations and 98 addition operations. This recursive algorithm is executed in log 3 n recursion steps and is used for matrices of odd order. Moreover, at present, a family of new
Data Loading...
