UDC 681.322.012
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 larisaelf@gmail.com
|
|
A FAST RECURSIVE ALGORITHM FOR MULTIPLYING MATRICES OF ORDER
n = 3q (q > 1)
Abstract. A new fast recursive algorithm is proposed for multiplying matrices of order
n = 3q (q > 1).
This algorithm is based on hybrid algorithm for multiplying matrices of odd order
n = 3μ (μ = 2q − 1, q > 1),
which is used as basic algorithm for
μ = 3q (q > 0).
As compared with the well-known block-recursive Laderman’s algorithm, the new algorithm minimizes
by 10.4% the multiplicative complexity equal to
W
M
≈ 0.896n2.854 multiplication operations at recursive level
d = log3 n − 3 and reduces the computation vector by three recursive steps.
The multiplicative complexity of the basic and recursive algorithms are estimated.
Keywords: linear algebra, Laderman’s block-recursive matrix multiplication algorithm, family of fast hybrid matrix multiplication algorithms, Winograd’s algorithm for inner product.
FULL TEXT
REFERENCES
- Elfimova L.D. New fast recursive matrix multiplication algorithm. Kibernetika i sistemnyj analiz. 2019. Vol. 55, N 4. P. 33–38.
- Elfimova L.D., Kapitonova Yu.V. Fast algorithm for matrix multiplication and its efficient implementation on systolic arrays. Kibernetika i sistemnyj analiz. 2001. N 1. P. 135–150.
- Elfimova L.D. Fast hybrid matrix multiplication algorithms. Kibernetika i sistemnyj analiz. 2010. Vol. 46, N 4. P. 49–59.
- Elfimova L.D. New fast hybrid matrix multiplication algorithms. Kibernetika i sistemnyj analiz. 2011. Vol. 47, N 6. P. 59–67.
- Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969. Vol. 13. P. 354–356.
- Winograd S. On multiplication of 22 matrices. Linear Algebra and Its Application. 1971. Vol. 4. P. 381–388.
- Laderman J.D. A noncommutative algorithm for multiplying 3x3 matrices using 23 multiplications. Bulletin of the American Mathematical Society. 1976. Vol. 82, N 1. P. 126–128.
- Winograd S.A. A new algorithm for inner product. IEEE Transactions on Computers. 1968. Vol. С-18. P. 693–694.
