7.3 Алгоритм Винограда

Дальнейшей экономии вычислений в случае разложения N на взаимно простые множители можно достичь, если ступенчатый характер объединения частичных мало точечных преобразований заменить вложенным. В этом и заключается идея алгоритма Винограда. Идею вложения мало точечных алгоритмов легче всего понять на примере.

Пример 5. Рассмотрим случай 6-точечного ДПФ, т. е. N=6. Пусть N₁=2, N₂=3. Приведем сначала алгоритмы мало точечных (2- и 3-точечных) ДПФ, синтезированные оптимальным образом по методу Винограда.

Алгоритм 2-точечного ДПФ

имеет вид

(7.8)

где s_i-сложения, m_i-умножения; А_i и a_i - выходные и входные числа.

Алгоритм 3-точечного ДПФ

Имеет вид

, ,

, , (7.9)

, ,

Преобразуем исходную 6-точечную последовательность в двумерную точечную в соответствии с (7.5) и (7.6). Тогда матрицу 6-точечного ДПФ можно представить в виде прямого произведения 2- и 3-точечных ДПФ и преобразование можно записать в виде:

, (7.10)

, , , ,

Где

Применим к матричному преобразованию (7.10) алгоритм 2-точечного БПФ (7.8). В результате найдем векторыи :

Для вычисления векторов и используем алгоритм 3-точечного БПФ (7.9).

Таким образом, мы как бы «вложили» алгоритм 3-точечного БПФ в структуру 2-точечного, который оперирует 3-точечными векторами. Характерной особенностью «вложенных» алгоритмов является то, что требуемое число умножений для N-точечного алгоритма равно произведению числа умножений, требуемых для каждого из частичных алгоритмов. Этот факт легко проверяется на приведенном выше алгоритме.

В заключение отметим, что принцип «вложения» малоточечных алгоритмов применяется также для вычисления N-точечных циклических сверток, когда N разлагается на взаимно простые множители, если имеются достаточно эффективные алгоритмы малоточечных сверток. Вложенные алгоритмы циклических сверток получили название по имени авторов алгоритмов Агарвала-Кули [3]. По сравнению с традиционными алгоритмами вычисления свертки с использованием БПФ алгоритмы Агарвала-Кули позволяют сэкономить число умножений почти на порядок.

Другими классами еще более экономных алгоритмов ДПФ и свертки являются алгоритмы, основанные на теоретико-числовых и полиномиальных преобразованиях, с которыми можно познакомиться в [3].