12.7. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА

В примере 12.9 мы показали, что вычисление значения полинома степени в одной точке требует умножений. Однако мы исходили из предположения, что полином представлен своими

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

Определение. Степенью полинома от нескольких переменных называют наибольшую степень переменных этого полинома. Например, степень полинома равна 3.

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

Лемма 12.2. Пусть полиномы. Если то существует полином не все коэффициенты которого равны нулю, но для которого как функция от равна тождественно нулю.

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

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

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

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

Лемма 12.3. Пусть взаимно однозначное отображение n-мерного векторного пространства коэффициентов на -мерное векторное пространство параметров. Если таково, что каждая компонента вектора в является полиномиальной функцией компонент соответствующего вектора в то

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

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

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

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

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

Следовательно, можно представить новым множеством из параметров, а именно множеством функций Более того, коэффициенты полинома полиномиальные функции параметров По лемме 12.3 . Таким образом,

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

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

Теорема 12.2 и общая формулировка задачи, изучаемой в этом разделе, принадлежат Винограду [1970а]. Теоремы 12.1 и 12.3 взяты из работы Фидуччиа [19711. Тот факт, что без использования делений для вычисления значения полинома степени требуется умножений, приписывается (Кнутом [1969]) Гарсиа 1). Пан [1966] распространил этот результат на мультипликативные операции. Моцкин [1955] показал, что для вычисления значения полинома с предварительной обработкой коэффициентов необходимо умножений. Одной из первых в этом направлении была работа Островского [1954]. Белага [1961] усилил результат Моцкина, а также получил оценку для числа сложений — вычитаний. Виноград [19706] показал, что для умножения комплексных чисел необходимы три умножения.

Упр. 12.7 обсуждается Виноградом [1973]. Материал о нижних оценках для умножения матриц (упр. 12.9-12.16) основан на работе Хопкрофта, Керра [1971]. Результаты упр. 12.17 независимо получены несколькими авторами. Часть (в) Виноград (частное сообщение) приписывает Унгару. Упр. 12.18 и. 12.19 заимствованы у Хопкрофта, Мусинского [1973]. Упр. 12.20-12.22, 12.37 и 12.38 основаны на беседах с Флойдом. Упр. 12.24 и 12.25 взяты у Моргенштерна [1973], упр. 12.28 и 12.29 — у Нечипорука [1966], 12.30(a) - у Харпера, Сэвиджэ [1972], упр. 12.32 —у Штрассена [1974], упр. 12.33 — у Керра [1970], упр. 12.34 — у Пратта [1974], упр. 12.35 — у Ива [1964] и упр. 12.36 — у Рабина, Винограда [1971].

Еще некоторые попытки получения нижних оценок для числа арифметических операций были сделаны Бородиным, Куком [1974], Кедемом [1974] и Киркпатриком [1972, 1974].

СПИСОК ЛИТЕРАТУРЫ

(см. скан)

(см. скан)

(см. скан)

(см. скан)