Article

Article title ON THE PARALLEL FORM OF DISCRETE FOURIER TRANSFORM
Authors Y.E. Romm, V.V. Zabeglov
Section SECTION II. ALGORITHMIC AND SOFTWARE
Month, Year 05, 2010 @en
Index UDC 519.6: 681.3
DOI
Abstract The article outlines the scheme of parallel performance of Discrete Fourier Transform (DFT). The scheme includes calculation of DFP base founded on piecewise polynomial approximation of functions by means of Newton interpolated polynomial. In case of a priori arbitrarily set bound of error, time complexity of the calculation constitutes O(1). Parallel performance of DFT, including base calculation, is estimated as having time complexity O(log2N).

Download PDF

Keywords Discrete Fourier Transform.
References 1. Аксайская Л. Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций / Автореферат диссертации на соискание ученой степени кандидата технических наук. – Таганрог: ТТИ ЮФУ. – 2008. – 18 с.
2. Ахмед Н., Рао К.Р. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. Т.Э. Кренкеля / Под ред. И.Б. Фоменко. – М.: Связь, 1980. – 248 с.
3. Миклошко Й. Связь между алгоритмами, программами и структурой параллельных ЭВМ. – В кн.: Алгоритмы математического обеспечения и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. – М.: Наука, 1982. – С. 6-36.
4. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Дис… д-ра техн. наук. – Таганрог: ТРТУ, 1998. – 546 с.; ВНТИ Центр. – № 05.990.001006.
5. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. – 2007. – № 2. – C.161-174.
6. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // Теория сложности вычислений. 1: Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – Т. 118. – С. 159-187.

Comments are closed.