5.4. Эмпирическое сравнение двух методов субрезультантных PRS

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

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

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

номера строк. Как мы уже отмечали, каждой строке соответствует полином, степень которого на единицу меньше числа элементов, заключенных между старшими и/или конечными нулями. Символ «#», предшествующий номеру строки, указывает, что для этой строки осуществлялся выбор ведущего элемента. Для определения членов PRS мы просматриваем сверху вниз самый правый столбец (степени) и из данного множества строк «степени d выбираем полином, соответствующий первой из них, в качестве следующего члена PRS. Знак «>» после номера строки (в самом левом столбце) означает, что эта строка может быть членом PRS при условии, что не осуществляется выбор ведущего элемента. Бели выполняются преобразования, связанные с выбором ведущего элемента, то соответствующая строка запоминается и распечатывается под матрицей , а также отмечается знаком «>» после номера строки. В этом случае мы сравниваем коэффициенты запомненной строки с коэффициентами первой строки в , имеющей ту же степень, и выбираем ту, коэффициенты которой меньше, в качестве нового члена PRS. (См. также доказательство теоремы 5.3.6 и историческое замечание 4.)

Пример 1. Это классический пример неполной PRS, используемый в литературе Кнутом (Knuth, 1981) и Брауном (Brown, 1971).

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

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

    (6)

Наибольшее целое число, порождаемое алгоритмом, равно 786410803602112500 (18 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 21308697620 (11 цифр).

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

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 2431362808 (10 цифр). При преобразовании 2, выбирая ведущий элемент, изменяем строку 2. Запоминаем строку

    (6)

При преобразовании 6, выбирая ведущий элемент, изменяем строку 6. Запоминаем строку

    (4)

При преобразовании 10, выбирая ведущий элемент, изменяем строку 10. Запоминаем строку

    (2)

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

Пример 2. Это — небольшой пример неполной

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

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

    (1)

Наибольшее целое число, порождаемое алгоритмом, равно 37044 (5 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (0)

Наибольшее целое число, порождаемое алгоритмом, равно 37044 (5 цифр).

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

    (4)

Наибольшее целое число, порождаемое алгоритмом, равно 2305401 (7 цифр). При преобразовании 4, выбирая ведущий элемент, изменяем строку 4. Запоминаем строку

    (1)

Пример 3. Пример полной PRS, где заметим, что свободный член полинома равен нулю.

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

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

    (6)

Наибольшее целое число, порождаемое алгоритмом, равно 3913180032193072 (16 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (6)

Наибольшее целое число, порождаемое алгоритмом, равно 3913180032193072 (16 цифр).

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

    (6)

Наибольшее целое число, порождаемое алгоритмом, равно 571513399644 (12 цифр). Заметим, что полином не появляется в

Пример 4. Пример полной PRS, использованный Ван Влеком.

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

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

    (0)

Наибольшее целое число, порождаемое алгоритмом, равно 68687289792 (11 цифр).

b. Алгоритм Габихта субрезультантных

    (6)

Наибольшее целое число, порождаемое алгоритмом, равно 68687289792 (11 цифр).

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

    (6)

    (3)

Наибольшее целое число, порождаемое алгоритмом, равно 1159985772 (10 цифр).

Пример 5. В этом примере неполной PRS имеется уменьшение степени ее членов на 3 (с 7 до 4), и это единственный представленный пример, требующий выбора ведущего элемента методом пузырька в методе матричной триангуляризации, т.е. в выборе ведущего элемента участвуют строки, не являющиеся соседними.

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

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

    (9)

Наибольшее целое число, порождаемое алгоритмом, равно 1026442541730304580597746128 (28 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (0)

Наибольшее целое число, порождаемое алгоритмом, равно 8724617648516388414672 (22 цифры).

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

    (9)

Наибольшее целое число, порождаемое алгоритмом, равно 27843817119202448 (17 цифр). При преобразовании 6, выбирая ведущий элемент, изменяем строку 6. Запоминаем строку

    (4)

При преобразовании 7, выбирая ведущий элемент, изменяем строку 7. Запоминаем строку

    (4)

Заметим, что, поскольку степень запоминаемой строки 7 совпадает со степенью запоминаемой строки 6, последняя не является членом

Пример 6. Это — пример PRS, в которой отличаются более, чем на 1.

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

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

    (5)

Наибольшее целое число, порождаемое алгоритмом, равно 41671931313194660832971041260 (29 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 41671931313194660832971041260 (29 цифр).

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

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 121237518861722851398 (21 цифра). При преобразовании 2, выбирая ведущий элемент, изменяем строку 2. Запоминаем строку

    (5)

При преобразовании 3, выбирая ведущий элемент, изменяем строку 3. Запоминаем строку

    (5)

Пример 7. Еще один пример небольшой неполной PRS.

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

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

    (0)

Наибольшее целое число, порождаемое алгоритмом, равно 212268 (6 цифр).

b. Алгоритм Габихта субрезультантных PRS

    (0)

Наибольшее целое число, порождаемое алгоритмом, равно 212268 (6 цифр).

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

    (5)

Наибольшее целое число, порождаемое алгоритмом, равно 260680 (6 цифр).

При преобразовании 4, выбирая ведущий элемент, изменяем строку 4. Запоминаем строку

    (2)

Пример 8. В этом примере неполной PRS нуль появляется в качестве свободного члена полинома

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

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

    (1)

Наибольшее целое число, порождаемое алгоритмом, равно 16 (2 цифры).

b. Алгоритм Габихта субрезультантных PRS

    (1)

Наибольшее целое число, порождаемое алгоритмом, равно 16 (2 цифры).

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

    (4)

Наибольшее целое число, порождаемое алгоритмом, равно 32 (2 цифры).

При преобразовании 4, выбирая ведущий элемент, изменяем строку 4. Запоминаем строку

    (1)

При преобразовании 7, выбирая ведущий элемент, изменяем строку 7. Запоминаем строку

    (0)

Пример 9. Здесь полиномы не являются взаимно простыми.

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

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

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 2925396948683036033024 (22 цифры).

b. Алгоритм Габихта субрезультантных PRS

    (8)

Наибольшее целое число, порождаемое алгоритмом, равно 2925396948683036033024 (22 цифры).

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

    (7)

Наибольшее целое число, порождаемое алгоритмом, равно 571896124988719104 (18 цифр).

Пример 10. Пример поменьше, где полиномы снова не взаимно просты.

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

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

    (3)

Наибольшее целое число, порождаемое алгоритмом, равно 123303313408 (12 цифр).

b. Алгоритм Габихта субрезультантных PRS

Наибольшее целое число, порождаемое алгоритмом, равно 123303313408 (12 цифр).

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

    (4)

Наибольшее целое число, порождаемое алгоритмом, равно 983685120 (9 цифр).

Мы дадим сейчас табл. 5.4.1, суммирующую информацию о наибольших целых числах, участвующих в операциях деления, в каждом из рассмотренных примеров при обоих методах. Заметим, что метод матричной триангуляризации порождает наименьшие «наибольшие целые».

Таблица 5.4.1. Число цифр в наибольшем из участвующих в делении чисел