8.12. РАЗРЕЖЕННЫЕ ПОЛИНОМЫ

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

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

Наиболее разумная из известных стратегий умножения разреженных полиномов состоит в том, что полиномзадается списком пар где все различны и расположены в порядке убывания, т. е. для 1 Чтобы умножить два полинома, представленных таким образом, находим произведения пар и располагаем их по величине показателей (по вторым компонентам пар), объединяя все члены с одинаковыми показателями. Если это не делать, то придется расплачиваться ростом числа членов с одинаковыми показателями. Поэтому по мере выполнения арифметических операций сложность начнет значительно превосходить ту, которая была бы, если бы приведение подобных членов выполнялось на каждом шаге.

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

Алгоритм 8.8. Умножение упорядоченных разреженных полиномов

Вход. Полиномы представленные списками пар

и

где последовательности монотонно убывают.

Выход. Полином представленный списком пар, в котором последовательность монотонно убывает.

Метод. Не умаляя общности, предполагаем, что

1. Строим последовательности в которых член, 1 равен Таким образом, представляет произведение полинома на член полинома

2. Сливаем для приводя подобные члены. Затем попарно сливаем полученные последовательности, приводя подобные члены, и повторяем процесс, пока не получим одну упорядоченную последовательность.

Теорема 8.22. Алгоритм 8.8 занимает времени в предположении, что

Доказательство. Шаг 1, очевидно, имеет сложность Шаг 2 надо повторить раз, и ясно, что при каждом выполнении вся работа займет времени.

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

Пример 8.13. Вычислим где полином с членами в случаях, когда он плотный и когда разреженный. Если полином плотный, то легко показать, что лучше всего вычислять дважды возводя в квадрат. Иными словами, пусть где время умножения плотных полиномов. Тогда можно вычислить за шагов и результат возвести в квадрат за шагов, всего затратив шагов. Для сравнения укажем, что если вычислять то, как легко видеть, требуется шагов в предположении, что на тратится шагов, а на тратится шагов. Таким образом, для плотных полиномов получаем, как и ожидали, что надо вычислять повторным возведением в квадрат.

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

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Теорема 8.2, утверждающая, что обращение не сложнее умножения, взята у Кука [1966]. Любопытно, что существование полиномиального аналога алгоритма 8.1 не осознавали в течение нескольких лет. Моенк, Бородин [1972] описали алгоритм сложности 0б для деления, а вскоре затем алгоритм деления сложности Об независимо изложили несколько авторов, в том числе Зивекинг [1972].

Построение алгоритмов для модульной арифметики, а также для вычисления значений и интерполяции полиномов следует работе Моеика, Бородина [1972]. Хейндел, Хоровиц [1971] нашли алгоритм сложности Об восстанавливающий числа по китайской теореме об остатках и использующий предварительную обработку данных. Бородин, Муиро [1971] описали алгоритм сложности для вычисления значений полинома в нескольких точках, а Хоровиц [1972] обобщил его на интерполяцию. Куиг [1973] построил алгоритм сложности О а для вычисления значений полинома без применения быстрого (сложности алгоритма деления. Единство восстановления по вычетам, интерполяции, вычисления значений полиномов и вычисления вычетов целых чисел установил Липсон [1971].

Алгоритм сложности Об для нахождения НОД целых чисел принадлежит Шёнхаге [1971]. На полиномы и общие евклидовы области его перенес Моенк [1973].

Обзор классической техники для нахождения НОД дан Кнутом [1969]. Некоторую подборку материала о сложности арифметических операций над разреженными полиномами можно найти у Брауна [1971], Джентльмена [1972], Джентльмена, Джонсона [1973]. Дополнительные результаты о реализации арифметических операций над полиномами на вычислительных машинах приведены Холлом [1971], Брауном [1973] и Коллинзом [1973]. Алгоритм 8.8 со структурой данных в виде сортирующего дерева реализовал С. Джонсон на языке ALTRAN (см. [Браун, 1973]).

Упр. 8.19 и 8.20 принадлежат Карпу и Ульману. Упр. 8.21 о вычислении значений полинома и его производных можно найти в работах Вари [1974] и Ахо, Стейглица, Ульмана [1974]. Из последней работы взято также упр. 8.28. Упр. 8.27 приведено Блюстейном [1970] и Рабинером, Шэфером, Рейдером [1969]. Подробно арифметические операции над полиномами и целыми числами обсуждаются в книге Бородина, Муиро [1975].