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

• Veröffentlicht in: Кибернетика и системный анализ
• Datum: 2019
• ISSN: 1019-5262
• 1. Verfasser: Елфимова, Л.Д.
• Format: Artikel
• Sprache: Russisch
• Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
• Schlagworte: Кібернетика
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/181008
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос.

Предложен новый рекурсивный алгоритм умножения матриц порядка n=2ʳ (r > 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2ʳ⁻¹ (r > 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда Штрассена данный алгоритм позволяет минимизировать на 7% мультипликативную сложность, равную Wм≈0.932n²⋅⁸⁰⁷ операций умножения на глубине рекурсии d=log₂n-3, и сократить вектор вычислений на три рекурсивных шага. Дана оценка мультипликативной сложности представленного алгоритма. Запропоновано новий рекурсивний алгоритм множення матриць порядку n=2ʳ (r > 1), в якому як базовий застосовується швидкий гібридний алгоритм множення матриць порядку 4μ, коли μ=2ʳ⁻¹ (r > 0). Порівняно з відомими рекурсивними алгоритмами Штрасена та Винограда Штрасена цей алгоритм дозволяє мінімізувати на 7% мультиплікативну складність, яка дорівнює Wм≈0.932n²⋅⁸⁰⁷ операцій множення на глибині рекурсії d=log₂n-3, та скоротити вектор обчислень на три рекурсивних кроки. Наведено оцінку мультиплікативної складності представленого алгоритму. A new recursive algorithm is proposed for multiplying matrices of order n=2ʳ (r > 1), This algorithm is based on fast hybrid algorithm for multiplying matrices of order 4μ for μ=2ʳ⁻¹ (r > 0). As compared with the well-known recursive Strassen’s and Winograd–Strassen’s algorithms, the new algorithm minimizes by 7% the multiplicative complexity equal toWм≈0.932n²⋅⁸⁰⁷ multiplication operations at recursive level d d=log₂n-3 and reduces the computation vector by three recursive steps. The multiplicative complexity of the algorithm is estimated.