Новый быстрый рекурсивный алгоритм умножения матриц
Предложен новый рекурсивный алгоритм умножения матриц порядка n=2ʳ (r > 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2ʳ⁻¹ (r > 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда Штрассена данный алгоритм по...
Збережено в:
| Видавець: | Інститут кібернетики ім. В.М. Глушкова НАН України |
|---|---|
| Дата: | 2019 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/181008 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-181008 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1810082021-10-27T01:26:42Z Новый быстрый рекурсивный алгоритм умножения матриц Елфимова, Л.Д. Кібернетика Предложен новый рекурсивный алгоритм умножения матриц порядка 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. 2019 Article Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/181008 681.322.012 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кібернетика Кібернетика |
| spellingShingle |
Кібернетика Кібернетика Елфимова, Л.Д. Новый быстрый рекурсивный алгоритм умножения матриц Кибернетика и системный анализ |
| description |
Предложен новый рекурсивный алгоритм умножения матриц порядка n=2ʳ (r > 1), в котором в качестве базового применяется быстрый гибридный алгоритм умножения матриц порядка 4μ при μ=2ʳ⁻¹ (r > 0). По сравнению с известными рекурсивными алгоритмами Штрассена и Винограда Штрассена данный алгоритм позволяет минимизировать на 7% мультипликативную сложность, равную Wм≈0.932n²⋅⁸⁰⁷ операций умножения на глубине рекурсии d=log₂n-3, и сократить вектор вычислений на три рекурсивных шага. Дана оценка мультипликативной сложности представленного алгоритма. |
| format |
Article |
| author |
Елфимова, Л.Д. |
| author_facet |
Елфимова, Л.Д. |
| author_sort |
Елфимова, Л.Д. |
| title |
Новый быстрый рекурсивный алгоритм умножения матриц |
| title_short |
Новый быстрый рекурсивный алгоритм умножения матриц |
| title_full |
Новый быстрый рекурсивный алгоритм умножения матриц |
| title_fullStr |
Новый быстрый рекурсивный алгоритм умножения матриц |
| title_full_unstemmed |
Новый быстрый рекурсивный алгоритм умножения матриц |
| title_sort |
новый быстрый рекурсивный алгоритм умножения матриц |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| topic_facet |
Кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181008 |
| citation_txt |
Новый быстрый рекурсивный алгоритм умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 33-38. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT elfimovald novyjbystryjrekursivnyjalgoritmumnoženiâmatric |
| first_indexed |
2023-10-18T22:51:22Z |
| last_indexed |
2023-10-18T22:51:22Z |
| _version_ |
1796156611751837696 |