Новый быстрый рекурсивный алгоритм умножения матриц / Елфимова Л. Д. (2019)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0001003091
  Кибернетика и системный анализ      А - 2019  /     Випуск (2019, Т. 55, № 4)

Елфимова Л. Д.
Новый быстрый рекурсивный алгоритм умножения матриц

Предложен новый рекурсивный алгоритм умножения матриц порядка <$E n~=~2 sup q> (q >> 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка <$E 4 mu> при <$E mu~=~2 sup q-1> (q >> 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда - Штрассена данный алгоритм позволяет минимизировать на 7 % мультипликативную сложность, равную Wм <$E symbol Ы~0,932n sup 2,807> операций умножения на глубине рекурсии d = log2 n - 3, и сократить вектор вычислений на 3 рекурсивных шага. Дана оценка мультипликативной сложности представленного алгоритма.

 https://doi.org/10.1007/s10559-019-00163-2
 Scopus

Бібліографічний опис:
Елфимова Л. Д.  Новый быстрый рекурсивный алгоритм умножения матриц. Кибернетика и системный анализ. 2019. Т. 55, № 4. С. 33-38. doi: https://doi.org/10.1007/s10559-019-00163-2 URL: http://jnas.nbuv.gov.ua/article/UJRN-0001003091

English  Cybernetics and Systems Analysis   /     Issue (2019, 55 (4))

Jelfimova L.D.
A new fast recursive matrix multiplication algorithm

A new recursive algorithm is proposed for multiplying matrices of order n = 2q (q > 1). This algorithm is based on a fast hybrid algorithm for multiplying matrices of order n = 4μ with μ = 2q−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.932n2.807 multiplication operations at recursive level d = log2n−3 by 7% and reduces the computation vector by three recursion steps. The multiplicative complexity of the algorithm is estimated. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: block-recursive Strassen’s algorithm, block-recursive Winograd’s–Strassen’s algorithm, family of fast hybrid matrix multiplication algorithms, linear algebra, Linear algebra, Matrix algebra, Hybrid algorithms, Hybrid matrix multiplication algorithms, Multiplication operations, Multiplicative complexity, Recursions, Recursive algorithms, Recursive matrix, S-algorithms, Computational complexity

Cite:
Jelfimova L.D. (2019). A new fast recursive matrix multiplication algorithm. Cybernetics and Systems Analysis, 55 (4), 33-38. doi: https://doi.org/10.1007/s10559-019-00163-2 http://jnas.nbuv.gov.ua/article/UJRN-0001003091 [In Russian].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна