3.1.2. Алгоритмы свертки и произведений полиномов в алгебре полиномов

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

Теорема 3.1. (Алгоритм Кука — Тоома [3.2].) Апериодическая свертка (3.4) может быть вычислена за общих умножений.

Конструктивное доказательство теоремы можно получить, если заметить, что имеет степень Следовательно, не изменится, если оно определено по модулю любого полинома степени, равной

Предположим, что выбран так, что

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

В алгоритме Кука — Тоома результирующий полином степени восстановлен из числовых значений полученных заменой Z на Таким образом, алгоритм Кука — Тоома может рассматриваться как реализация интерполяционного метода Лагранжа [3.2]. Выбор различных а, - и поля коэффициентов произволен. Если различные а; выбраны в качестве последовательных степеней числа и если поле таково, все различны, алгоритм Кука—Тоома приводит к вычислению апериодической свертки с помощью преобразований, имеющих структуру ДПФ. Например, если и есть кольцо чисел по модулю числа Мерсенна ( — простое) или числа Ферма то такие преобразования будут преобразованиями Мерсенна или Ферма [3.8, 3.9].

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

а апериодическая свертка -точечной последовательности и -точечной вычисляется как циклическая свертка двух расширенных последовательностей

из точек, полученных добавлением нулей к последовательности нулей к последовательности Таким образом, традиционный метод вычисления апериодических сверток с помощью ДПФ и метод секционирования с суммированием близко связаны с алгоритмом Кука — Тоома.

Из теоремы 3.1 видно, что апериодическая (-точечная свертка может быть вычислена с помощью умножений посредством полиномиального умножения по модулю полинома степени причем этот полином выбирается как произведение полиномов первой степени в поле коэффициентов Полученные результаты иа случай полиномиальных произведений по модулю любого полинома обобщает следующая важная теорема, принадлежащая Винограду [3.11].

Теорема 3.2. Минимальное число общих умножений, необходимых для вычисления произведения полиномов равно где — степень и — число неприводимых множителей полинома поля (включая 1).

Конструктивное доказательство этой теоремы строится с помощью китайской теоремы об остатках. Поскольку является произведением неприводимых полиномов можно найти приведением по модулю вычислением полиномиальных произведений соответствующих приведенным полиномам и восстановлением из с помощью китайской теоремы об остатках. Как и в теореме 3.1, умножения на скаляры, используемые при приведении и восстановлении по китайской теореме об остатках, не учитываются, и единственными общими умножениями являются те, которые входят в произведение Пусть — степень Поскольку имеет степень имеют степень то их произведение можно вычислить за умножений по теореме 3.1:

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

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

Если — поле рациональных чисел, разлагается на произведения полиномов с рациональными коэффициентами. Такие полиномы называются циклотомическими [3.7]. Циклотомические полиномы являются неприводимыми в поле рациональных чисел. Их корни комплексны и образуют подмножество множества где

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

Теорема 3.3. Минимальное число общих умножений, необходимое для вычисления циклической -точечной свертки, равно , где — число делителей включая

Вычисление циклической свертки по теореме 3.2 значительно упрощается вследствие того, что коэффициенты циклотомических полиномов являются просто целыми числами. Более того, эти целые числа могут принимать значения только или за исключением случая очень больших цнклотомическнх полиномов [3.2]. При этом приведение и восстановление по китайской теореме об остатках могут быть выполнены с малым числом сложений, что можно проиллюстрировать на простом примере -точечной циклической свертки. В этом случае имеются только два делителя числа 5: 1 и 5. Таким образом, разлагается на два циклотомических полинома: Приведение входных полиномов по модулю равносильно простой замене Z на 1 в и поэтому выполняется за 4 сложения. Приведения по модулю также выполняются за 4 сложения путем вычитания члена четвертой степени из всех остальных членов входных полиномов, так как Умножение по модулю есть просто скалярное умножение, а умножение по модулю выполняется за 7 умножений при использовании теоремы 3.1. Восстановление по китайской теореме об остатках может рассматриваться как обращение приведений и выполняется за 8 сложений. Таким образом, -точечная циклическая свертка с учетом приведений и восстановления по китайской теореме об остатках вычисляется только за 8 умножений и ограниченное число сложений.