УДК 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.
