Содержание
1 Введение 3
1.1 Актуальность темы...................................... 3
1.2 Цель работы ........................................... 4
1.3 Научная новизна........................................ 4
1.4 Основные методы исследования .......................... 5
1.5 Практическая ценность.................................. 5
1.6 Апробация работы....................................... 5
1.7 Публикации............................................. 6
1.8 Структура и объем диссертации.......................... 6
1.9 Благодарности.......................................... 6
2 Теория инволютивных делений 8
2.1 Основные понятия теории базисов Гребнера............... 8
2.2 Несимметричный подход и существенные умножения ... 12
2.3 Линейно-алгебраический подход Фожера.................. 19
2.4 Инволютивные деления и инволютивные базисы............ 27
2.5 Статические инволютивные разбиения.................... 28
2.6 Слоистые инволютивные разбиения....................... 33
2.7 Инволютивные деления, свойства парности и фильтрации 35
2.8 Методы сравнения инволютивных делений................. 38
2.9 Базисные множества и парные деления без вложенности . 40
2.10 Непрерывность........................................ 43
2.11 Построение инволютивных (>-,<т)-делений.............. 46
2.12 Деление Жане и его свойства.......................... 48
2.13 Инволютивный алгоритм и его сравнение с алгоритмом Бухбергера и линейно-алгебраическим подходом Фожера . 50
2.14 Конструктивность....................................... 58
2.15 Монотонность........................................... 74
3 Вычислительные эксперименты 75
3.1 Алгоритм построения минимального инволютивного базиса 75
3.2 Зависимость результата от нумерации переменных 77
4 Заключение 84
2
1 Введение
1.1 Актуальность темы
За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также методов изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами. Настоящим црорывом в данной области стало появление базисов Гребнера и алгоритма их вычисления, предложенного Бухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному виду.
Тем не менее, тео[>етическая сложность алгоритма вычисления базиса Гребнера оказалась слишком высокой для непосредственного применения алгоритма на практике. Одной из основных проблем алгоритмов вычисления стандартных базисов яаляется взрывной рост целочисленных коэффициентов. Это приводит к большим затратам по процессорному времени и памяти при работе с реальными системами. И поэтому сразу же после появления алгоритма встал вопрос об оптимизации его работы и дальнейших усовершенствованиях. За сорок лет в данной области был достигнут значительный успех, причем существенную роль сыграло более детальное изучение алгоритмов, и разработка принципиально новых подходов, например, инволютивного [10,16,17,3{ и линейноалгебраического [21,12[. Прогресс в увеличении скорости был обусловлен и появлением быстрых алгоритмов умножения целых чисел.
В основе инволютивного подхода лежит понятие инволютивного базиса, представляющего собой базис Гребнера, вообще говоря, нередуцированный. Основное отличие инволютивного алгоритма от алгоритма Бухбергера состоит в особом способе вычисления нормальной формы, который ограничивает набор возможных редукций. Этот алгоритм был получен значительно ранее, но в рамках дифференциальной алгебры.
Вопрос о том, какой из двух алгоритмов — алгоритм Бухбергора или инволютивный, является более эффективным, остается открытым. Есть гипотеза, согласно которой инволютивный алгоритм справляется с проблемой роста коэффициентов, в среднем, лучше чем алгоритм Бухбер-гора.
Отправной концепцией инволютивного подхода является теория ин-
3
волюгивных делений, представляющих собой мультипликативные ограничения при умножении мономов. Быстрота и удобство алгоритма вычисления инволютивнош базиса существенно зависит от выбора инво-лютивного деления, относительно которого строится базис. Основные результаты, полученные в рамках инволютивного подхода, в том числе достаточно многочисленные примеры, когда имволютивный алгоритм заканчивает работу быстрее, чем алгоритм Бухбергера, основывались на инволютивном делении Жане — частном примере инволютивных делений. В результате немногочисленных экспериментов но изучению работы алгоритма построения инволютивного базиса для других делений была сформулирована гипотеза о том, что инволютивное деление Жане является наилучшим среди всех делений для большинства встречающихся на практике систем полиномиальных уравнений.
Для доказательства корректности и оптимальности инволютивного алгоритма от деления требуется выполнение ряда специальных свойств: непрерывности [16, 17], допустимости [10], конструктивности [16, 17], монотонности [18]. Деление Жане удовлетворяет всем этим свойствам. Встает вопрос о том. какие другие инволютивные деления также обладают ими.
Таким образом, на сегодняшний день результаты о мономиальных инволютивных делениях нуждаются в систематизации и углублении. Кроме того, актуальной является и задача построения достаточно общей теории инволютивных делений и инструментов для их сравнения между собой.
1.2 Цель работы
Целью настоящей работы является сравнение различных методов построения базисов Гребнера (алгоритм Бухбергера, инволютивный подход, линейно-алгебраический подход), описание нового метода построения непрерывных инволютивных делений при помощи свойства парности, изучение классификационных свойств инволютивных делений — непрерывности, конструктивности, монотонности, а также вычислительные эксперименты с перестановкой переменных в инволютивном делении Жане.
1.3 Научная новизна
Научная новизна данной работы состоит в следующем:
4
1. Отмечена связь между алгоритмом вычисления нормальной формы, являющимся частью алгоритма Вухбергера, инволютивиыми делениями и стратегией выбора главного элемента в методе Гаусса.
2. Предложен новый метод построения, классификации и изучения ин-вол юти иных делений с использованием свойства парности — парное замыкание, и с его помощью получены результаты относительно классификационных свойств инволютивных делений: непрерывности, конструктивности и монотонности, н приведены новые примеры конструктивных и неконструктивных инволютивных делений.
3. Проведен ряд численных экспериментов, характеризующих работу алгоритма вычисления инволютивного базиса Жане в зависимости от перестановки переменных.
1.4 Основные методы исследования
В работе используются методы и результаты теории базисов Гребнера, коммутативной алгебры, теории инволютивных базисов, компьютерных вычислений.
1.5 Практическая ценность
Метод парного замыкания, предложенный в работе, позволяет строить новые инволютивные деления, не уступающие делению Жане с позиции приведенных в работе критериев. Такие деления могут оказаться более эффективными, чем деление Жане для некоторых полиномиальных систем, что требует дальнейшего изучения.
Сравнение трех различных подходов к задаче вычисления стандартного базиса, предпринятое в работе, может лечь в основу процесса нахождения более эффективных стратегий, в том числе с более высокой степенью параллелизуемости, чем существующие на сегодняшний день алгоритмы.
1.6 Апробация работы
Основные результаты диссертации докладывались на Лобачевских чтениях в КазГУ в 2001 году, на конференции "Компьютерная алгебра и ее приложения в физике" (СААР) в 2001 году в Дубне, на Международной алгебраической конференции, посвященной 250-летию МГУ и 75-летию
5
кафедры высшей алгебры в МГУ в 2004 году, на Симпозиуме (Workshop) по недо- и переопределенным системам алгебраических и дифференциальных уравнений в Карлсруэ в 2002 году, на конференции "Алгоритмическая алгебра и логика"в честь 60-летия Ф. Вайспфеннинга в Пассау в 2005 году.
1.7 Публикации
Результаты диссертации опубликованы в следующих работах:
1. Семенов A.C. Парный анализ инволютивных делений, Фундаментальная и прикладная математика, 2003, т. 9, вып. 3, стр. 199-212. http://mech.math.rasu.su/ fpm/rus/k03/k033/k03314h.htm
2. Семенов A.C. Инволютивные деления: слойность и парность, Программирование,, т. 31, №. 2, стр. 43-50.
3. Семенов. A.C. Статические свойства инволютивных делений, Лобачевские чтения 2001,113, - Казань, 2002.
4. Semenov A.S. Static Properties of Involutive Divisions, Proceedings of the Workshop on Under- and Over-Determined Systems of Algebraic or Differential Equations, 151, - Karlsruhe (Germany), 2002.
5. Semenov A.S. Characteristics of Involutive Divisions. Proceedings of the A3L 2005, Passau, Germany, 2005, p. 229-235.
1.8 Структура и объем диссертации
Диссертационная работа состоит из введения, 2 глав, заключения и библиографии. Общий объем диссертации составляет 87 страниц. Структура работы отражена в оглавлении.
1.9 Благодарности
Автор благодарит своего научного руководителя, ведущего научного сотрудника Лаборатории вычислительных методов МГУ, к. ф.-м. н. Евгения Васильевича Панкратьева за помощь в выборе темы исследования, внимательное руководство в процессе исследовательской деятельности и множество полезных идей. Невозможно оценить его вклад в общее образование и становление автора.
6
- Київ+380960830922