КиСА | Содержание

Том 55 >>> № 4 ИЮЛЬ — АВГУСТ 2019

УДК 681.322.012

Л.Д. Елфимова

НОВЫЙ БЫСТРЫЙ РЕКУРСИВНЫЙ АЛГОРИТМ УМНОЖЕНИЯ МАТРИЦ

Аннотация. Предложен новый рекурсивный алгоритм умножения матриц порядка n=2^q (q >1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2^q–1 (q >0) . По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда–Штрассена данный алгоритм позволяет минимизировать на 7% мультипликативную сложность, равную W _M ≈0.932n ^2.807 операций умножения на глубине рекурсии d=log₂n–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.