Новый быстрый рекурсивный алгоритм умножения матриц
Предложен новый рекурсивный алгоритм умножения матриц порядка n=2ʳ (r > 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2ʳ⁻¹ (r > 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда Штрассена данный алгоритм по...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2019 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/181008 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862741814277046272 |
|---|---|
| author | Елфимова, Л.Д. |
| author_facet | Елфимова, Л.Д. |
| citation_txt | Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-07T20:21:53Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-181008 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T20:21:53Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | Новый быстрый рекурсивный алгоритм умножения матриц Елфимова, Л.Д. Кібернетика |
| title | Новый быстрый рекурсивный алгоритм умножения матриц |
| title_alt | Новий швидкий рекурсивний алгоритм множення матриць A new fast recursive matrix multiplication algorithm |
| title_full | Новый быстрый рекурсивный алгоритм умножения матриц |
| title_fullStr | Новый быстрый рекурсивный алгоритм умножения матриц |
| title_full_unstemmed | Новый быстрый рекурсивный алгоритм умножения матриц |
| title_short | Новый быстрый рекурсивный алгоритм умножения матриц |
| title_sort | новый быстрый рекурсивный алгоритм умножения матриц |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181008 |
| work_keys_str_mv | AT elfimovald novyibystryirekursivnyialgoritmumnoženiâmatric AT elfimovald noviišvidkiirekursivniialgoritmmnožennâmatricʹ AT elfimovald anewfastrecursivematrixmultiplicationalgorithm |