3.2.5. Гнездовые алгоритмы

Систематическое применение методов, рассмотренных в предыдущем разделе, позволяет построить большое число алгоритмов полиномиального произведения, требующих относительно малого числа сложении и умножений, и, следовательно, вычислять большие двумерные свертки с помощью составных полиномиальных преобразований. В качестве альтернативного подхода может служить конструирование больших двумерных сверток из ограниченного ряда коротких двумерных сверток методами, подобными тому, который использовался для одномерных сверток [3.2]. В этом методе двумерная (ЛАХЛЛ-точечная свертка — взаимно-простые, превращается в четырехмерную -точечную свертку путем простого изменения индексации. Пусть задано

Поскольку и — взаимно-простые числа и индексы и определены по модулю прямым следствием китайской теоремы об остатках [3.7] является то, что можно отобразить на два ряда индексов где

Следовательно, преобразуется в четырехмерную -точечную свертку

Эту четырехмерную свертку можно рассматривать как двумерную -точечную свертку, в которой все скаляры заменены двумерными -точечными полиномами. Точнее, представляя входные и выходные последовательности в виде двумерных полиномов, получим

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

Если поменять местами, число умножений останется таким же. число сложений станет равным , В случае более двух множителей этот способ вычисления можно использовать рекурсивно, при условии, что нее множители взаимно-простые. На практике и -точечные свертки вычисляются с помощью полиномиальных преобразований, а большие двумерные свертки — посредством небольшого набора алгоритмов полиномиальных преобразований. Например, -точечную свертку можно было бы вычислить с помощью и -точечных сверток. Поскольку эти свертки вычисляются соответственно за 13 умножений, 70 сложений и 55 умножений, 369 сложений (см. табл. 3.4), вложение двух алгоритмов позволяет вычислить -точечную свертку за 715 умножений и 6547 сложений. В табл. 3.5 приведено число арифметических операций для различных двумерных сверток, вычисленных с помощью полиномиальных преобразований и вложения. Можно видеть, что этот метод дает очень малое число умножений на отсчет, но число

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

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

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

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