10. БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ МНОГОМЕРНОГО ДПФ

В разд. 2.2 было показано, что многомерное ДПФ (ДПФ-m) представимо в виде кронекеровского произведения матриц одномерных ДПФ Далее в гл. 5 рассмотрены два альтернативных метода факторизации кронекеровского произведения матриц — построчно-столбцовый (ПСА) и гнездовой (ГА) алгоритмы.

В литературе к настоящему времени наиболее изучен построчно-столбцовый метод вычисления ДПФ имеющий наиболее простую структуру вычислений. ПСА для имеет вид

где матрица -точечного одномерного

Таким образом может быть вычислено -точечными ДПФ-1, которые, в свою очередь, могут быть представлены быстрыми алгоритмами. Отсюда вычислительная сложность (по числу умножений) ПСА согласно (10.1) определяется оценкой

Если

В ряде работ начиная с 1977 г. были предложены гнездовые алгоритмы многомерного основанные на различных вариантах объединения построчно-столбцовых базовых операций (в литературе данные алгоритмы часто называются векторными В частности, в [2,3] были предложены быстрые алгоритмы вычисления размерности позволяющие уменьшить на 25% количество умножений по сравнению с ПСА при и до 25% при было рассмотрено обобщение такого подхода на многомерный случай В [5,6] рассматривается обобщенное представление гнездового подхода к синтезу алгоритмов через факторизацию кронекеровского произведения матриц и определяются в общем случае процедуры синтеза быстрых алгоритмов. В указанных работах было показано, что общая оценка сложности по умножениям для гнездовых алгоритмов составляет

где некоторая переменная.

В частности, для в [5] показано, что

Отсюда, при больших

В 1978г. Нуссбаумер [7] предложил не менее перспективный подход вычисления через полиномиальные преобразования (ПП) и редуцированные алгоритмы показано, что наилучшая оценка по числу умножений для

В 1984 г. Григорян А.М. предложил метод синтеза алгоритмов на основе построения соответствующего тензора третьего ранга [8]. Было показано, что тензорный способ вычисления ДПФ-2 дает оценку а, равную соответственно для простое число):

В более поздних работах [9—11] им был предложен модифицированный метод, основанный на применении спаренного тензора ДПФ-2. Данный подход приводит к алгоритму БПФ-2, похожему по конструкции БПФ-2, полученному методом ПП ([7], с. 170), с одинаковыми оценками сложности по числу умножений (10.4).

В 1985 г. Лабунец В. Г. и Кренкель Т. Э. предложили метод вычисления ДПФ-m на основе дискретного преобразования Радона, не требующего умножений, и одномерных ДПФ. В работе [12] было показано, что вычислительная сложность алгоритмов полученных данным методом для составляет

Рис. 10.1. Метод построения быстрых алгорчтмов многомерного ДПФ

Из сказанного выше, таким образом, можно выделить пять основных методом вычислений БПФ-m, приведенных на рис. 10.1, где используются следующие обозначения:

ПСА - построчно-столбцевые алгоритмы;

ГА - гнездовые алгоритмы;

ПП — полиномиальные преобразования;

ТА - тензорные алгоритмы;

ПР - преобразование Радона.

К настоящему времени алгоритмы классов и находят ограниченное применение на практике вследствие их высокой струк турной сложности. Для построения таких алгоритмов необходимо обеспечение многочисленных операций промежуточных перестановок (метод IIII) либо сложных адресных операций для построения соответствующих компонент тензора 3-го ранга (метод Построение методом аналогично по структурной сложности методу Кроме того, указанные методы имеют пока ограничения при построении быстрых алгоритмов имеющего разную размерность по координатам.

В связи с этим в данной главе наиболее подробно будут рассматриваться построчно-столбцовый, гнездовой подход к синтезу алгоритмов БПФ-т, имеющие пока наибольшие перспективы практического применения.