В эквивалентном виде это можно записать так: У" = ((N mod п") у mod п"), / = ((N" mod п) у mod п). Тогда выходной индекс j можно вычислить следующим образом:

У = п"у + пу" (mod п). Чтобы проверить это, запишем

У = п" (N"j + Qyti) + п (Nj + Qn") (mod пп") = у (n"N" + nN) (mod n)

При такой переиндексации формула Vj = IlZlaVi принимает вид

t"=0 t=0

Выполним умножение в показателе степени. Так как порядок элемента а равен пп", то члены, содержащие пп", можно отбросить. Используя выписанные соответствия для индексов, будем рассматривать входной и выходной векторы как двумерные таблицы. Тогда

i=0 t"=0 n-l n"-l

= I L P""T""f,.r,

i=0 t"=0

где p = a"(«")-элемент порядка n, a у = a<."У--элемент порядка n". Полученная формула представляет собой двумерное (п X п")-точечное преобразование Фурье, для вычисления которого требуется примерно п (п + п") умножений и примерно столько же сложений. Если длина преобразования по столбцам или по строкам является составным числом, то можно провести дальнейшее упрощение, снова применяя быстрое преобразование Фурье. Поступая таким образом, можно преобразование длины п, распадающейся на взаимно простые множители щ, привести к форме, для вычисления которой требуется порядка « умножений и сложений.

Для выполнения преобразования Фурье можно выбрать как алгоритм Кули-Тьюки, так и алгоритм Гуда-Томаса. Иногда возможно даже использование обоих алгоритмов одновременно. Например, используя БПФ-алгоритм Гуда-Томаса, можно раз-

бить 63-точечное преобразование на 7-точечное и 9-точечное, а затем, используя БПФ-алгоритм Кули-Тьюки, свести 9-точечное преобразование к двум 3-точечным. Организованное так вычисление будет аналогично (3 X 3 X 7)-точечному трехмерному преобразованию Фурье.

11.4. АЛГОРИТМЫ АГАРВАЛА-КУЛИ ВЫЧИСЛЕНИЯ СВЕРТОК

Ту же схему индексации, которая была использована в алгоритме Гуда-Томаса для превращения одномерного преобразования Фурье в многомерное преобразование Фурье, можно использовать для превращения одномерной свертки в многомерную. Этот метод разбиения свертки известен под названием алгоритма Агарвала -Кули вычисления свертки. Он не дает такого же уменьшения числа умножений, как алгоритм Винограда вычисления свертки, но зато и не имеет такой, как у алгоритма Винограда, тенденции роста числа сложений для больших п. Далее этот метод более структурирован и, следовательно, для больших п более обозрим, так как допускает разбиения на подалгебры. Используя алгоритм Агарвала-Кули разбиения длинной свертки на короткие и алгоритм Винограда вычисления коротких сверток, можно получить хорошие алгоритмы для вычисления свертки.

В отличие от алгоритма Винограда для свертки, использующего китайскую теорему об остатках для многочленов, алгоритм Агарвала-Кули основан на китайской теореме об остатках для целых чисел и может быть использован только в тех случаях, когда длина п имеет взаимно простые делители. Для заданных векторов с компонентами gi и di при г = О, п - I требуется вычислить циклическую свертку

Cl = 11 gw~k))dk, i = О.....n-1,

где двойные скобки у индексов обозначают вычисления по модулю п.

Превратим эту одномерную свертку в двумерную. В предыдущем параграфе мы уже видели, как с помощью китайской теоремы об остатках отобразить одномерные входные данные в двумерную таблицу и как двумерную таблицу выходных данных отобразить обратно в одномерный вектор. Заменим индексы ink парами индексов (Г, i") и (k, k") так, что

При рассмотрении алгоритма Гуда-Томаса мы уже видели, как определить новые индексы, чтобы они выполняли свое предназначение:

Г = N"i (mod п), i" = Ni (mod n").

W = N"k (mod n), k" = Nk (mod n").

где N и N" представляют собой целые числа, удовлетворяюш,ие условию

Nn + N"n" = 1. Тогда свертка записывается равенством

П-\ п"-1

Cn"i+nl" = 1 1 dnk-+nk"gn" (i-lf) 4-п- (i"-k")-k-=0 k"=0

Двойное суммирование по паре (k, k") эквивалентно суммированию по k, так.как перебираются те же самые члены суммы. Определим теперь двумерные переменные g, d и с:

так что свертка задается выражением

п-\ п"~1

Ci,i" = 2j 2j (k,k"gC-k, i"-~k", k-=0 fe"=0

где первые и вторые индексы берутся соответственно по модулю п и п". Мы получили настояш,ую двумерную циклическую свертку.

Для того чтобы описанный алгоритм был полезен, надо располагать эффективным способом вычисления двумерной циклической свертки. Применим вдоль каждого из двух измерений алгоритм Винограда вычисления свертки. Этот метод легче проследить, представив двумерную таблицу в виде одномерной таблицы многочленов. Определим множество п" многочленов равенствами

dk(x) = Ц 4./г"Х, Г = О, ..., п" - 1.