УДК 681.322.012
БЫСТРЫЙ РЕКУРСИВНЫЙ АЛГОРИТМ УМНОЖЕНИЯ
МАТРИЦ ПОРЯДКА
n = 3q (q > 1)
Аннотация. Предложен новый быстрый рекурсивный алгоритм умножения матриц порядка
n = 3q (q > 1),
построенный на основе гибридного алгоритма умножения матриц нечетного порядка
n = 3μ (μ = 2q − 1, q > 1),
который ис-пользуется в качестве базового алгоритма при
μ = 3q (q > 0).
По сравнению с известным блочно-рекурсивным алгоритмом
Лейдермана представленный алгоритм позволяет минимизировать на 10.4% мультипликативную слож-ность,
равную
W
M
≈ 0.896n2.854
операций умножения на глубине рекурсии
d = log3 n − 3, и сократить вектор вычислений на три рекурсивных шага.
Дана оценка мультипликативной сложности базового и рекурсивного алгоритмов.
Ключевые слова: линейная алгебра, блочно-рекурсивный алгоритм Лейдер-мана,
семейство быстрых гибридных алгоритмов умножения матриц, алго-ритм Винограда для скалярного произведения.
ПОЛНЫЙ ТЕКСТ
Елфимова Лариса Дмитриевна,
младший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
larisaelf@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- Елфимова Л.Д. Новый быстрый рекурсивный алгоритм умножения матриц. Кибернетика и системный анализ. 2019. Т.55, № 4. С. 33–38.
- Елфимова Л.Д. Капитонова Ю.В. Быстрый алгоритм для умножения матриц и его эффективная реализация на систолических массивах. Кибернетика и системный анализ. 2001. № 1. С. 135–150.
- Елфимова Л.Д. Быстрые гибридные алгоритмы умножения матриц. Кибернетика и системный анализ. 2010. Т. 46, № 4. С. 49–59.
- Елфимова Л.Д. Новые быстрые гибридные алгоритмы умножения матриц. Кибернетика и системный анализ. 2011. Т. 47, № 6. С. 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.
