Швидке обчислення циклічної згортки багаторозрядних чиселна основі ШПФ у послідовній моделі обчислень

• Опубліковано в: : Компьютерная математика
• Дата: 2016
• Автори: Терещенко, А.М., Задірака, В.К.
• Формат: Стаття
• Мова: Українська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
• Теми: Оптимизация вычислений
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/168424
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Швидке обчислення циклічної згортки багаторозрядних чиселна основі ШПФ у послідовній моделі обчислень / А.М. Терещенко, В.К. Задірака // Компьютерная математика. — 2016. — № 2. — С. 110-119. — Бібліогр.: 5 назв. — укр.

Аналізується складність за кількістю однослівних операцій при реалізації операції циклічної згортки. Розглянуто методи обчислення циклічної згортки, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення циклічної згортки такого виду на основі ШПФ невеликої довжини Анализируется сложность по числу однословных операций при реализации операции циклической свертки. Рассмотрены методы вычисления циклической свертки, когда каждая точка свертки является многоразрядным числом. Предложено быстрый метод вычисления циклических сверток такого вида на основе БПФ небольшой длины. A complexity of number of single precision operations is analyzed in multi-digit convolution computation. Calculation methods of cyclic convolution elements are considered when every element is a high precision value. An effective method based on FFT of small length for calculation of cyclic convolution of multi-digit values is proposed.