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

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

Предложен новый рекурсивный алгоритм умножения матриц порядка n=2ʳ (r > 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2ʳ⁻¹ (r > 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда Штрассена данный алгоритм по...

Full description

Saved in:
Bibliographic Details
Published in:Кибернетика и системный анализ
Date:2019
Main Author: Елфимова, Л.Д.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Subjects:
Кібернетика
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/181008
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-181008
record_format dspace
spelling Елфимова, Л.Д.
2021-10-26T16:59:20Z
2021-10-26T16:59:20Z
2019
Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос.
1019-5262
https://nasplib.isofts.kiev.ua/handle/123456789/181008
681.322.012
Предложен новый рекурсивный алгоритм умножения матриц порядка 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.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Кібернетика
Новый быстрый рекурсивный алгоритм умножения матриц
Новий швидкий рекурсивний алгоритм множення матриць
A new fast recursive matrix multiplication algorithm
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Новый быстрый рекурсивный алгоритм умножения матриц
spellingShingle Новый быстрый рекурсивный алгоритм умножения матриц
Елфимова, Л.Д.
Кібернетика
title_short Новый быстрый рекурсивный алгоритм умножения матриц
title_full Новый быстрый рекурсивный алгоритм умножения матриц
title_fullStr Новый быстрый рекурсивный алгоритм умножения матриц
title_full_unstemmed Новый быстрый рекурсивный алгоритм умножения матриц
title_sort новый быстрый рекурсивный алгоритм умножения матриц
author Елфимова, Л.Д.
author_facet Елфимова, Л.Д.
topic Кібернетика
topic_facet Кібернетика
publishDate 2019
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Новий швидкий рекурсивний алгоритм множення матриць
A new fast recursive matrix multiplication algorithm
description Предложен новый рекурсивный алгоритм умножения матриц порядка 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.
issn 1019-5262
url https://nasplib.isofts.kiev.ua/handle/123456789/181008
citation_txt Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос.
work_keys_str_mv AT elfimovald novyibystryirekursivnyialgoritmumnoženiâmatric
AT elfimovald noviišvidkiirekursivniialgoritmmnožennâmatricʹ
AT elfimovald anewfastrecursivematrixmultiplicationalgorithm
first_indexed 2025-12-07T20:21:53Z
last_indexed 2025-12-07T20:21:53Z
_version_ 1850882301028728832

Similar Items