1.4.7. Использование модульной арифметики в кольце полиномов

Последовательность равная круговой свертке последовательностей является последовательностью коэффициентов полинома

где

Для вычисления (1.61) воспользуемся китайской теоремой об остатках. Если представить полином в виде произведения взаимно-простых полиномов с коэффициентами из поля рациональных чисел (использование других полей рассмотрено в [1.12])

то

где

полиномы должны удовлетворять соотношениям

Пример 1.16. Вывести алгоритм вычисления круговой свертки последовательностей длиной

Согласно (1.61):

Представим где Тогда

Согласно Согласно

Отсюда

Подставляя полученные значения в (1.63), получаем

или

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

Пример 1.17. Алгоритм -точечной круговой свертки с предварительной обработкой данных (см. пример 1.16) имеет вид:

В [1.12] показано, что минимальное число операций умножения, требуемых для вычисления (1.16), составляет где К равно числу различных неприводимых в поле С множителей полинома Для многих (особенно простых) это число достижимо ценой чрезмерного увеличения числа операций сложения. Поэтому предпочтительными являются так называемые субоптимальные алгоритмы с несколько большим числом операций умножения, но гораздо меньшим числом операций сложения. В [1.12] приведены алгоритмы с предварительной обработкой данных для нескольких значений . В табл. 1.5 приведено число требуемых арифметических операций, необходимых для их реализация.

Таблица 1.5 (см. скан)

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

Рассматриваемый метод является, по существу, методом представления одномерной -точечной свертки в виде двумерной -точечной свертки:

где

Пример 1.18. Рассмотрим алгоритм вычисления -точечной круговой свертки. Положим . Сопоставим каждому индексу пару координат , где Тогда получим следующее взаимно-однозначное отображение:

Теперь изменим порядок расположения элементов в векторе матричного выражения (1.42) таким образом, чтобы сначала размещались элементы, для которых а затем элементы, для которых Тогда искомая свертка записывается в виде

Матрица последнего выражения представляет собой циклическую матрицу размера элементами которой являются циклические матрицы размера . Вычисление (1.67) сводится к вычислению и -точечных круговых сверток. Пусть:

Тогда

Используя алгоритм -точечной свертки (см. пример 1.17), иолучаем:

Для вычисления М и применяется алгоритм -точечной свертки.

Пусть — числа требуемых умножений для и -точечных сверток соответственно Аналогично — числа требуемых операций сложения. Тогда для -точечной свертки число требуемых операций умножения и сложения а составит соответственно:

Пример 1.19. Пусть Согласно табл. . Пользуясь формулами (1.68) и (1.69), получаем:

Теперь положим: Тогда: . Аналогично находим:

Расчеты показывают, что второй вариант является более экономичным по числу требуемых операций сложения.