Маршруты Грёбнера

• Автор: Голубицкий, Олег Дмитриевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 57 с.

Содержание
1 Введение

1.1 Актуальность темы

1.2 Цель работы

1.3 Научная новизна

1.4 Практическая и теоретическая ценность

1.5 Апробация работы

1.6 Публикации

1.7 Структура и объем диссертации

1.8 Благодарности

2 Базисы Гребнера и инволютивные базисы
2.1 Основные понятия коммутативной алгебры
2.2 Схемы симплификации и стандартные множества
2.3 Стандартные базисы
2.4 Инволютивные деления
2.5 Инволютивные базисы
2.6 Сравнение алгоритмов Бухбергера и инволютивного алгоритма
3 Инволютивный маршрут Гребнера
3.1 Допустимые отношения порядка и весовые вектора
3.2 Шаг инволютивого маршрута Гребнера
3.3 Конусы Гребнера и инволютивный маршрут Гребнера
4 Дифференциальный маршрут Гребнера
4.1 Основные понятия дифференциальной алгебры
4.2 Ранжиры
4.3 Характеристические множества
4.4 Лидеры характеристических множеств
4.5 Дифференциальное разбиение Гребнера
4.6 Преобразование характеристических множеств
4.7 Дифференциальный маршрут Гребнера
4.8 Конечность дифференциального маршрута Гребнера
4.9 Нерешенные проблемы
А Приложение

1 Введение
1.1 Актуальность темы
Системы полиномиальных уравнений изучаются на протяжении нескольких столетий и имеют множество приложений. На алгебраическом языке системы полиномиальных уравнений описываются идеалами в кольцах многочленов. Особо важна задача канонического представления идеала, вопрос о принадлежности многочлена идеалу и решение систем полиномиальных уравнений. Теория базисов Грёбнера дает алгоритмическое решение этих задач.
Первый алгоритм построения базиса Грёбнера был разработан и реа- ■ лизован Вухбергером в 1965 г. Его основная идея заключается в преобразовании исходной системы многочленов в эквивалентную каноническую систему. Решение системы линейных уравнений методом Гаусса и нахождение наибольшего общего делителя многочленов от одной переменной с помощью алгоритма Евклида являются частными случаями алгоритма Бухбергера. В общем случае алгоритм Бухбергера имеет высокую сложность, для которой не известно хорошей теоретической оценки — наоборот, известны примеры систем, для которых базис Гребнера имеет 1 экспоненциальный размер. Поэтому становится важной разработка раз-
личных методов, позволяющих усовершенствовать алгоритм Бухбергера на практике.
Идея преобразования системы в эквивалентную каноническую присутствует и в работах Жане, Томаса и Поммаре [33, 46, 41] по системам линейных уравнений в частных производных. В этих работах приведение системы к каноническому виду называется приведением в инволюцию. В работах Гердта, Жаркова и Блинкова (например [22]) разработана теория инволютивных делений и инволютивных базисов для систем многочленов. Инволютивные базисы являются нередуцированными базисами Грёбнера [49, 50] и вместе с тем имеют дополнительные полезные свойства [48]. Вид и сложность построения инволютивных базисов зависит от инволютивного деления, грамотный выбор которого позволяет ускорить алгоритм этого построения [23]. Эксперименты показывают, что во многих случаях инволютивный алгоритм работает быстрее, чем алгоритм Бухбергера.
Существует совершенно иной метод усовершенствования алгоритма

Бухбергера для построения базисов Грёбнера относительно лексикографического порядка, известный под названием маршрута Грёбнера (Grob-ner Walk). Этот метод основан на известном наблюдении, что время работы алгоритма Бухбергера существенно зависит от выбора отношения порядка на мономах. Например, построение базиса Грёбнера относительно порядка общей степени, как правило, гораздо более эффективно, чем построение базиса для лексикографического порядка. Метод маршрута Грёбнера, впервые предложенный Коллартом, Калкбренером и Маллом в работе [19], позволяет эффективно преобразовывать базис Грёбнера относительно одного порядка на мономах в базис относительно любого другого порядка. Эксперименты показывают [6], что такое косвенное построение может оказаться гораздо эффективнее прямого построения лексикографического базиса Грёбнера.
Для систем нелинейных уравнений в частных производных также существует подход, связанный с приведением системы к каноническому виду и основанный на понятиях из дифференциальной алгебры. Основы дифференциальной алгебры, включая понятие кольца дифференциальных многочленов, дифференциального идеала и характеристического множества, были заложены Риттом [43] и Колчином [34]. Дальнейшее развитие дифференциальная алгебра получила в работах ряда авторов второй половины XX века. В частности, была разработана теория дифференциальных и разностных размерностных многочленов, с которой можно ознакомиться по монографии Кондратьевой, Левина, Михалева и Панкратьева [35]. Характеристические множества дифференциальных идеалов играют роль, сходную с ролью базисов Грёбнера для полиномиальных идеалов. Однако, некоторые важные свойства базисов Грёбнера не переносятся на дифференциальный случай [35]. Например, характеристическое множество дифференциального идеала, вообще говоря, может не порождать этот идеал.
Задача построения характеристических множеств гораздо сложнее ее полиномиального аналога. В случае простых дифференциальных идеалов эта задача может быть решена с помощью алгоритма Розенфельда-Грёбнера [16] или специализированного алгоритма Розенфельда-Грёбне-ра [15]. Однако, в обоих случаях искомое характеристическое множество строится путем прямого вычисления. Такой подход может оказаться неэффективным, особенно в случае исключающего ранжира. Для ре-

всех нетривиальных производных ви лидера и = Ы< А. Если Е частично редуцирован относительно А, и с^цЕ < с^и А, то Р называется редуцированным относительно А. Непустое подмножество А С /С{£/} называется авторедуцированным, если любой элемент А редуцирован относительно любого другого элемента А. Любое авторедуцированное множество конечно [35]. Если А = {Ах,...,Аг} — авторедуцированное множество, то любые два лидера Ы< Д-, Ы< АФ ] < г различны; в дальнейшем мы будем считать, что элементы любого авторедуциро-ванного множества записаны в порядке возрастания рангов их лидеров Ы< А < 1с1< А2 < • • * < 1с1< Аг.
Пусть А — авторедуцированное подмножество в 1С{11} относительно <. Для любого Р £ /С{17}, существуют дифференциальный многочлен Е0, называемый остатком Е и обозначаемый гет<(Е, А), и числа глАл € N (Л € А), такие что Ео редуцирован относительно А, ранг Е0 не выше ранга Е, и ^ тос^ И] теоРема 5.3.7].
Для подмножества В С /С{£7}, обозначим через гет<(Д А) множество остатков дифференциальных многочленов из В относительно А.
Если множество А не является авторедуцированным за конечное число следующих шагов редукции: выберем Р £ А, редуцируемый относительно А {Е} и заменим его на гет<(Е, А {Е}) (если таких многочленов Е несколько, то предположим, что есть некоторый алгоритм, который выбирает один из них). В результате получим некоторое авторедуцированное множество А!. Семейство всех таких множеств обозначим через Аи1огес1<(А). Если Е редуцируем относительно А и ранжира <, то он также редуцируем относительно любого множества А! £ Аи1огес1<(Д) и <.
Пусть А = {Ах,..., АГ},В = {Бх,...,Д} — авторедуцированные множества. Говорят, что ранг А ниже ранга В, и пишут А < В, если существует к £ М, такое что гк< А,- = гк< Д (1 < ъ < к) и Ак < Вк, или г > я и гк< Ах = гк< Д (1 < г < й). Если г = в и гк< Аг- = гк< Д (1 < г < я), то ранги А и В считаются равными (гк< А — гк< В). Любое. непустое семейство авторедуцированных множеств содержит авторедуцированное множество минимального ранга [35, предл. 5.3.10]. Для подмножества I С К{и}, авторедуцированное подмножество I минимального ранга называется характеристическим множеством I. Авторедуцированное множество А является характеристическим для I тогда