Классификационные свойства инволютивных делений

• Автор: Семенов, Александр Сергеевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 87 с. : ил.

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

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

1.2 Цель работы

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

1.4 Основные методы исследования

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

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

1.7 Публикации

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

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

2 Теория инволютивных делений
2.1 Основные понятия теории базисов Гребнера
2.2 Несимметричный подход и существенные умножения
2.3 Линейно-алгебраический подход Фожера
2.4 Инволютивные деления и инволютивные базисы
2.5 Статические инволютивные разбиения
2.6 Слоистые инволютивные разбиения
2.7 Инволютивные деления, свойства парности и фильтрации
2.8 Методы сравнения инволютивных делений
2.9 Базисные множества и парные деления без вложенности
2.10 Непрерывность
2.11 Построение инволютивных (х,сг)-делений
2.12 Деление Жане и его свойства
2.13 Инволютивный алгоритм и его сравнение с алгоритмом Бухбергера и линейно-алгебраическим подходом Фожера
2.14 Конструктивность
2.15 Монотонность
3 Вычислительные эксперименты
3.1 Алгоритм построения минимального инволютивного базиса
3.2 Зависимость результата от нумерации переменных
4 Заключение

1 Введение
1.1 Актуальность темы
За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной из приоритетных задач которой является развитие методов решения систем нелинейных ал!ебраических уравнений от нескольких переменных, а также методов изучения ашеб-раических идеалов, порожденных нелинейными полиномиальными системами. Настоящим прорывом в данной области «-ало появление базисов Гребнера и алгоритма их вычисления, предложенного Бухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному виду.
Тем не менее, теоретическая сложность алгоритма вычисления базиса Гребнера оказалась слишком высокой для непосредственного применения алгоритма на практике. Одной из основных проблем алгоритмов вычисления стандартных базисов является взрывной рост целочисленных коэффициентов. Это приводит к большим затратам по процессорному времени и памяти при работе с реальными системами. И поэтому сразу же после появления алгоритма встал вопрос об оптимизации его работы и дальнейших усовершенствованиях. За сорок лет в данной области был достигнут значительный успех, причем существенную роль сыграло более детальное изучение алгоритмов, и разработка принципиально новых подходов, например, инволютивного [10,16,17, 3] и линейноалгебраического [21,12[. Прогресс в увеличении скорости был обусловлен и появлением быстрых алгоритмов умножения целых чисел.
В основе инволютивного подхода лежит понятие инволютивного базиса, представляющего собой базис Гребнера, вообще говоря, нередуцированный. Основное отличие инволютивного алгоритма от алгоритма Бухбергера состоит в особом способе вычисления нормальной формы, который ограничивает набор возможных редукций. Этот алгоритм был получен значительно ранее, но в рамках дифференциальной алгебры.
Вопрос о том, какой из двух алгоритмов — алгоритм Бухбергера или инволютивный, является более эффективным, остается открытым. Есть гипотеза, согласно которой инволютивный алгоритм справляется с проблемой роста коэффициентов, в среднем, лучше чем алгоритм Вухбер-гера.
Отправной концепцией инволютивного подхода является теория ин-

волютивных делений, представляющих собой мультипликативные ограничения при умножении мономов. Быстрота и удобство алгоритма вычисления инволютивного базиса существенно зависит от выбора инво-лютивного деления, относительно которого строится базис. Основные результаты, полученные в рамках инволютивного подхода, в том числе достаточно многочисленные примеры, когда инволютивный алгоритм заканчивает' работу быстрее, чем алгоритм Бухбергера, основывались на инволютивном делении Жане — частном примере инволютивных делений. В результате немногочисленных экспериментов по изучению работы алгоритма построения инволютивного базиса для других делений была сформулирована гипотеза о том, что инволютивное деление Жане является наилучшим среди всех делений для большинства встречающихся на практике систем полиномиальных уравнений.
Для доказательства корректности и оптимальности инволютивного алгоритма от деления требуется выполнение ряда специальных свойств: непрерывности [16, 17], допустимости [10], конструктивности [16, 17], монотонности [18]. Деление Жане удовлетворяет всем этим свойствам. Встает вопрос о том. какие другие инволютивные деления также обладают ими.
Таким образом, на сегодняшний день результаты о мономиальных инволютивных делениях нуждаются в систематизации и углублении. Кроме того, актуальной является и задача построения достаточно общей теории инволютивных делений и инструментов для их сравнения между собой.
1.2 Цель работы
Целью настоящей работы является сравнение различных методов построения базисов Гребнера (алгоритм Бухбергера. инволютивный подход, линейно-алгебраический подход), описание нового метода построения непрерывных инволютивных делений при помощи свойства парности, изучение классификационных свойств инволютивных делений — непрерывности, конструктивности, монотонности, а также вычислительные эксперименты с перестановкой переменных в инволютивном делении Жане.
1.3 Научная новизна
Научная новизна данной работы состоит в следующем:

функции CNM:
CNM(V,m) = {х,},г = тт{Д deg_,(gcd(V) < degm)}.
Второе условие означает, что фиксируется нумерация переменных на время выполнения алгоритма для исходного U (при рекурсиях нумерация переменных на подмножествах Y является ограничением нумерации на X). и из возможных кандидатов в немультипликативные переменные берется минимальная возможная переменная. В работе [20] показано, что для подобных разбиений реализуется алгоритм быстрого поиска делителя на базе дерева, аналогичный алгоритму работы [2].
Тем не менее, свобода в выборе функции CF() и нумерации переменных для каждого исходного U остается.
Деление Жане имеет естественное описание во введенных выше терминах. Пусть а — нумерация переменных, соответствующая перестановке множества {1
1. CF(U) = maxiex. U,
2. V = U {CF(t/)},
3. i = min{j|dega0)(gcd(l/)) < dega{])(CF(U))},
4. CNM(V,CF(U))=xa{i}.
Аналогами деления Жане являются слоистые (>-, <т) — разбиения, где
> допустимый порядок, и а —произвольная перестановка переменных.
Тогда функции CF и CNM определяется следующим образом:
1. CF(U) = max>_ U,
2. V = U {CF(U)},
3. г = min{j]deg<7(j)(gcd(y)) < deg<7,j)(CF(L7))},
4. CN M{V,CF{U)) = хащ.
2.7 Инволютивные деления, свойства парности и фильтрации
Очевидно, что для каждого конкретного множества мономов U суще-ствуег конечное число различных статических инволютивных разбиений.