C&SA | Contents

Volume 55 >>> № 4 JULY — AUGUST 2019

UDC 681.322.012

L.D. Jelfimova¹

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

A NEW FAST RECURSIVE MATRIX MULTIPLICATION ALGORITHM

Abstract. A new recursive algorithm is proposed for multiplying matrices of order n=2^q (q >1) . This algorithm is based on fast hybrid algorithm for multiplying matrices of order 4μ for μ=2^q–1 (q >0) . As compared with the well-known recursive Strassen’s and Winograd–Strassen’s algorithms, the new algorithm minimizes by 7% the multiplicative complexity equal to W _M ≈0.932n ^2.807 multiplication operations at recursive level d=log₂n–3 and reduces the computation vector by three recursive steps. The multiplicative complexity of the algorithm is estimated .

Keywords: linear algebra, Strassen’s and Winograd–Strassen’s block-recursive matrix multiplication algorithms, family of fast hybrid matrix multiplication algorithms.

FULL TEXT

REFERENCES

Winograd S.A. A new algorithm for inner product. IEEE Transactions on Computers. 1968. Vol. С-18. P. 693–694.

Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969. Vol. 13. P. 354–356.

Winograd S. On multiplication of matrices. Linear Algebra and Its Application. 1971. Vol. 4. P. 381–388.

Laderman J.D. A noncommutative algorithm for multiplying matrices using 23 multiplications. Bulletin of the American Mathematical Society. 1976. Vol. 82, N 1. P. 126–128.

Elfimova L.D., Kapitonova Yu.V. Fast algorithm for matrix multiplication and its effective 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.