3.3.2. Гнездовые алгоритмы и алгоритмы простых множителей

Метод полиномиального преобразования, рассмотренный в предыдущем разделе, позволяет вычислять большие двумерные -точечные ДПФ при условии, что имеются алгоритмы больших редуцированных ДПФ. Для эти алгоритмы редуцированных ДПФ строятся достаточно просто с помощью метода Рейдера—Бреннера. Когда -составное и не является степенью 2, алгоритмы больших редуцированных ДПФ можно построить путем вложения алгоритмов коротких редуцированных ДПФ. Однако при составном часто гораздо удобнее конструировать большие преобразования, используя небольшой набор коротких преобразований в гнездовых алгоритмах [3.1] или алгоритме простых множителей [3.20, 3.21]. Эти методы особенно удобны, когда ДПФ имеет в обеих размерностях взаимно-простые множители. В последующем ограничимся рассмотрением -точечных преобразований Фурье, где — взаимно-простые, поскольку при более чем двух взаимно-простых множителях большие ДПФ можно вычислять рекурсивно, следуя алгоритму для двух множителей.

В гнездовых алгоритмах двумерное -точечное ДПФ сначала превращается в четырехмерное -точечное путем простой индексации, на основе китайской теоремы об остатках, что аналогично методу, описанному в подразд. 3.2.5 для двумерных сверток. Четырехмерное ДПФ, в свою очередь, вычисляется по методу вложения Винограда [3.1] с помощью полиномиальных преобразований для -точечного ДПФ, в котором каждый скаляр заменяется массивом и каждое умножение заменяется -точечным ДПФ. Таким образом, если — соответственно

число комплексных умножении и сложений, требуемых для оценк и -точечных ДПФ, то

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

Поскольку то метод вложения всегда требует больше сложений, чем алгоритм простых множителей. Однако, если и не намного больше что характерно для случая относительно коротких ДПФ, метод вложения требует меньше умножений, чем алгоритм простых множителей. При этом число сложений возрастает незначительно. Таким образом, гнездовой алгоритм больше пригоден для ДПФ массивов средних размеров, в то время как метод простых множителей — для ДПФ больших массивов.

Вычислительную эффективность этих алгоритмов можно улучшить, применяя метод вложения [3.17]. При этом, если воспользоваться способом, аналогичным описанному в подразд. 3.2.5 для сверток, понижается число сложении. Для алгоритма простых множителей использование метода вложения уменьшает число умножений. Для упрощения обозначений опишем этот последний алгоритм для -точечной ДПФ, результаты которого легко обобщить на -точечное ДПФ посредством замены скаляров векторами, состоящими из и , элементов соответственно. В последующем будем предполагать, что — простые. -точечное задано следующим образом:

Используя алгоритм Рейдера [3.19], это ДПФ можно найти как одно -точечное ДПФ, одну -точечную и одну -точечную корреляцию

где примитивные корни по модулю и

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