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