5.1.1. Общий обзор классических алгоритмов PRS

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

Псевдоделение означает предварительное умножение полинома на , а затем применение алгоритма PDF, когда известно, что все частные существуют, т.е.

где — псевдочастное и псевдоостаток соответственно.

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

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

GEA-P.

Обобщенный алгоритм Евклида для полиномов над целыми числами (Generalized Euclidean Algorithm for Polynomials over the Integers)

Вход: — ненулевые полиномы в

Выход: наибольший общий делитель полиномов

1. [Вычисление содержаний] с (Здесь мы используем известный алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел.)

2. [Вычисление примитивных частей]

3. [Построение ] Вычислить

4. [Выход] Если то вернуть с, иначе вернуть

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

где для некоторого h. [Разумеется, где определены на шаге 2 алгоритма Если дан метод выбора коэффициентов то выписанное

соотношение дает алгоритм построения PRS; разумеется, условие завершения этого семейства алгоритмов — равенство нулю псевдоостатка.

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

Евклидов алгоритм PRS.

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

Пример. Рассмотрим полиномы Очевидно, что . Мы имеем такую последовательность:

полученную при выполнении следующих псевдоделений:

Из шага 4 алгоритма GEA-P следует, что . Отметим также, что в последнем псевдоделении коэффициенты имеют 8 десятичных цифр, поскольку

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

способа сказать a priori, будет PRS полной или неполной. См. также (Barnett, 1970, 1974; Brown et al., 1971; Collins, 1966, 1971).

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

Алгоритм примитивных PRS.

В этом случае , где обозначает псевдоостаток, т.е. теперь мы удаляем содержание ( члена PRS до того, как мы используем его. [Напомним, что для данного ) удобно определять так, чтобы старший коэффициент был положительным.]

Пример. Рассмотрим те же полиномы, что и в предыдущем примере: где снова Теперь мы получаем

что достигается выполнением следующих псевдоделений:

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

детальное описание этих методов может быть найдено в разд. 5.2 и 5.3 соответственно.

Метод Сильвестра-Габихта псевдоделения субрезультантных PRS.

С этим методом связаны два алгоритма: алгоритм Сильвестра редуцированных (субрезультантных) PRS, если последовательность полна, и алгоритм Габихта субрезультантных PRS, если последовательность неполна. (См. историческое замечание 1.)

В соответствии с этим методом в случае полной PRS мы выбираем

[алгоритм Сильвестра редуцированных (субрезультантных) PRS], в то время как в случае неполных PRS мы полагаем

(алгоритм Габихта субрезультантных PRS); здесь

Выбор значений в соотношениях (S) и (Н) разъясняется в разд. 5.2.1 и 5.2.3 соответственно. В случае полных PRS метод Габихта сводится к методу Сильвестра. В общем случае соотношения (S) могут быть записаны в виде

известном также как алгоритм Сильвестра редуцированных (субрезультантных) PRS.

Заметим, что в обоих приведенных выше алгоритмах последовательности полиномиальных остатков вычислялись с помощью классического алгоритма деления полиномов PDF; более того, вместо вычисления содержания члена PRS мы просто делили его коэффициенты на зная, что это деление может быть выполнено без остатка. (Почему это так, мы увидим в разд. 5.2.1 и 5.2.3). В обоих приведенных алгоритмах мы имели

также равенство означавшее, что полином не может быть редуцирован, и читателю следует помнить об этом.

Как уже упоминалось, Габихт обобщил результат Сильвестра, и поэтому его алгоритм PRS может применяться также для полных PRS (конечно, за счет дополнительной стоимости). Однако алгоритм Сильвестра или (S)] работает не очень хорошо, если наша PRS неполна, т.е. рост может быть экспоненциальным, хотя и не таким быстрым, как в случае алгоритма Евклида PRS. (Напомним, что не существует способа a priori узнать, будет PRS полной или неполной.)

Пример. Снова рассмотрим полиномы где Имеем

Поскольку мы имеем дело с полной PRS, оба алгоритма в методе Сильвестра-Габихта псевдоделения субрезультантных PRS порождают одну и ту же последовательность, которая получается такой же, как и для евклидова алгоритма PRS. Однако отметим, что теперь а не -441, поскольку разделили на [Здесь — моном, но это несущественно.]

Метод матричной триангуляризации субрезультантных PRS.

В отличие от приведенных выше алгоритмов PRS метод матричной триангуляризации не использует явного деления полиномов. Чтобы посмотреть, как он работает, рассмотрим два полинома в для которых мы хотим вычислить последовательность полиномиальных остатков. Прежде всего построим матрицу, соответствующую результанту в форме Сильвестра (определение см. в разд. 5.2.2 и 5.3.3), являющуюся в нашем случае выписанной ниже квадратной матрицей порядка преобразуется в полином степени

добавлением нулевых коэффициентов]:

Затем эту матрицу мы приводим к верхней треугольной форме, используя преобразования, сохраняющие целочисленность матрицы, и все члены (полной или неполной) PRS получаются из строк результирующей матрицы с помощью доказанной автором теоремы (теорема 5.3.6); время вычислений метода матричной триангуляризации — то же самое, что и у метода Сильвестра-Габихта псевдоделения.

Заметим, что сильвестрова форма результанта используется впервые в настоящем столетии; она была погребена в статье Сильвестра 1853 г. и только однажды была использована Ван Влеком в 1899 г.

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

Пример. Снова рассмотрим полиномы Как мы уже видели, оба алгоритма метода Сильвестра-Габихта псевдоделения субрезультантных PRS дают полиномы а метод матричной триангуляризации дает (детали реализации обсуждаются в разд. 5.3.3). Соответствующая результирующая матрица:

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

полинома получены из третьей строки до перестановки, и мы видим, что они в три раза меньше полученных методом псевдоделения Сильвестра-Габихта. Это происходит потому, что частное от псевдоделения на равно : и не содержит свободного члена; это означает, что нам не нужно умножать на достаточно на 3. (Однако нет способа узнать об этом до выполнения деления.)

Следующим рассмотрим пример неполной

Пример. Если мы рассмотрим полиномы то верхняя треугольная форма матрицы, соответствующей форме Сильвестра результанта, равна

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