Jelfimova L.D.
A fast recursive algorithm for multiplying matrices of order n=3q (q>1)

A new fast recursive algorithm is proposed for multiplying matrices of order n = 3q (q > 1). This algorithm is based on the hybrid algorithm for multiplying matrices of odd order n = 3μ (μ = 2q – 1, q > 1), which is used as a 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 toWm = 0 896n2.854 multiplication operations at recursion level d = log3 n – 3 and reduces the computation vector by three recursion steps. The multiplicative complexity of the basic and recursive algorithms are estimated. © 2021, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: family of fast hybrid matrix multiplication algorithms, Laderman’s block-recursive matrix multiplication algorithm, linear algebra, Winograd’s algorithm for inner product, Cybernetics, Fast recursive algorithms, Hybrid algorithms, Multiplication operations, Multiplicative complexity, Recursions, Recursive algorithms, S-algorithms, Computer science

Cite:
Jelfimova L.D. (2021). A fast recursive algorithm for multiplying matrices of order n=3q (q>1). Cybernetics and Systems Analysis, 57 (2), 41–51. doi: https://doi.org/10.1007/s10559-021-00345-x http://jnas.nbuv.gov.ua/article/UJRN-0001221020 [In Russian].