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

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

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

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

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

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

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

Тогда свертка записывается равенством

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

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

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

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

Аналогично определим

и

При этом двумерная свертка превращается в одномерную свертку многочленов:

Для каждого в этой сумме производится сложение произведений многочленов. Всего имеется произведений многочленов. Каждое из произведений многочленов является сверткой и может быть вычислено с помощью подходящего алгоритма. Одним из таких алгоритмов является алгоритм Винограда вычисления свертки.

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

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

Аналогично если длнна циклической свертки является произведением трех или более взаимно простых множителей,

Рис. 11.5. Характеристики некоторых алгоритмов Агарвала-Кули вычисления циклических сверток. (Используются алгоритмы коротких сверток, приведенные на рис. 11.1.)

то алгоритм Агарвала-Кули позволяет преобразовать эту свертку в трехмерную или многомерную циклическую свертку и вычислять по каждому отдельному измерению циклическую свертку с помощью алгоритма Винограда.

Структуру многомерной циклической свертки можно описать через одномерные циклические свертки также с помощью кронекеровского произведения (кронекеровское произведение будет описано в § 11.5). На рис. 11.5 приведена таблица мультипликативной сложности некоторых алгоритмов Агарвала-Кули вычисления циклической свертки в полях характеристики 2.