3.2.6. Сравнение с традиционными вычислительными методами

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

Для сверток вещественных последовательностей метод полиномиального преобразования требует только вещественных арифметических операций и не

Таблица 3.7. Число операций для двумерных сверток, вычисляемых методом вложения Агарвала — Кули

использует тригонометрических функций. Таким образом, представляется логичным сравнивать его с методом вложения Агарвала — Кули, который также обладает этими свойствами и относительно эффективен для одномерных сверток, Б табл. 3.7 приведено число арифметических операций для двумерных сверток, вычисленных по этому методу, как описано в подразд. 3.2.5, но без полиномиальных преобразований. Из сравнения табл. 3.7 и 3.6 можно видеть, что число операций всегда больше, чем в методе полиномиального преобразования, для которого относительная эффективность повышается с увеличением размерности векторов в операции свертки. Например, для -точечной свертки методов полиномиального преобразования требует примерно в 5 раз меньше умножении и в 2,5 раза меньше сложений, чем метод Агарвала — Кули.

Сравнение с вычислением при помощи БПФ является до некоторой степени более сложным, поскольку в этом случае вещественные свертки требуют комплексной арифметики и включают операции с тригонометрическими функциями. В табл. 3.8 приведено число вещественных операций для вещественных двумерных сверток, вычисляемых с помощью БПФ-алгоритма Рейдера — Бреннера [3.15]. Предполагается, что две вещественные свертки вычисляются отдельно, а тригонометрические функции вычисляются и запоминаются заранее При этих условиях, довольно благоприятных для алгоритма БПФ, число сложений для него немного больше, а число умножений примерно в два раза больше по сравнению с методом полиномиального преобразования. Применение обычного алгоритма БПФ по основанию 4 или алгоритма Винограда преобразования Фурье [3.1] приведет к сравнимым результатам.

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

Таблица 3.8. Число вещественных операций для вещественных сверток при вычислении с помощью БПФ. (Алгоритм Рейдера — Бреннера, 2 вещественные свертки на ДПФ)

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

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

Необходимо также заметить, что, когда алгоритмы реализуются путем микропрограммирования, может оказаться выгодным вычислять короткие полиномиальные произведения с помощью распределенной арифметики [3.16]. Для этого метода, который предполагает битовые операции над отдельными разрядами чисел, число операций в алгоритмах полиномиального произведения резко уменьшается, что существенно повышает, таким образом, эффективность метода полиномиальною преобразования за счет увеличения сложности программирования.