Классификационные свойства инволютивных делений тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Семенов, Александр Сергеевич

• Семенов, Александр Сергеевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Семенов, Александр Сергеевич

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 Зависимость результата от нумерации переменных

Введение диссертации (часть автореферата) на тему «Классификационные свойства инволютивных делений»

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

За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной нз приоритетных задач которой является развитие методов решении систем нелинейных алгебраических уравнений от нескольких переменных, а также методов изучения а.'П'еб-ранческих идеалов. порожденных нелинейными пол кномнальными системами, Настоящим прорывом и дайной области стало появление базисов Греби ера и алгоритма их вычисления, предложенного Бухбергором еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному внду.

Тем не менее, теоретическая сложность алгоритма вычисления базиса Грсбиера оказалась слишком высокой для непосредственного применения алгоритма на практике- Одной нэ основных проблем алгоритмов вычислении стандартных базисов является нарывной рост целочисленных коэффициентов. Это приводит к большим затратам по процессорному времени и памяти прн работе с реальными системами, И поэтому' сразу же после появлении алгоритма нетал вопрос об оптимизации его работы н дальнейших усовершенствованиях. Зв сорок лот и данной области был достигнут значительный успех, причем существенную роль сыграло более детальное изучение алгоритмов, н разработка принципиально (юных подходов, например, ннйолютивного (10,1С, 17,3| н линейно-алгебраического (21,12}. Прогресс в увеличении скорости был обусловлен н появлением быарых алгоритмов умножении целых чисел.

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

Вопрос о гом, какой из двух алгоритмов — алгоритм Бухбер1ера или ишюлютнвный, является более -эффективным, остается открытым. Есть гипотеза, согласно которой ниволюгквНЫЙ алгоритм справляется с проблемой роста коэффициентов, в среднем, лучше чем алгоритм Бухбер-гера

Огнракной концепцией инволютшшого подхода является теория нн-3 вапютивных делений, представляющих собой мультипликативные ограничения при умножении мономов. Быстрот и удобство алгоритма вычисления инволютн иного базиса существенно зависит от выбора инво-люгнвного деления. относительно которого строится базис. Основные результаты, полученные в рамках ниволютнвного подкода, в том числе достаточно многочисленные примерыг когда инволют ивныЛ алгоритм оканчивает работу бькгтрее. чем ялгоритм Бухбергера, основывались на инволютивном делении Жане — частном примере нмволютнаных делений- В результате немногочисленных экспериментов но изучению работы алгоритма построения инволют и иного базиса для других делений была сформулирована гипотеза о том, что инвилютивное деление Жане является наилучшим среди всех делений для большинства встречающихся на практике систем полиномиальных уравнений.

Для доказательства корректности и оптимальности ниволютнвного алгоритма от деления требуется выполнение ряда специальных свойств; непрерывности [16, 17], допустимости [10|, конструктивности [16, 17], монотонности (18|. Деление Жане удовлетворяет всем атим свойствам. Встает вопрос о том, какие другие инволютивные деления также обладают имя.

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

1.2 Цель работы

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

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

Научная новизна данной работы состоит в следующем:

1. Отмечена связь между алгоритмом вычисления нормальной формы, являющимся частью ал [«ритма Бухбергера, иньолютииными ДСЛС-нкныя и стратегией выбора главного цемента в методе Гаусса.

2- Предложен новый метол построения, классификации и изучения нн-волютнвных делений с исиольэоааннем свойства парности — парное замыкание, н с (.то помощью Получены результаты отноентвпьно классификационных свойств иквОЛЮтивных делений: непрерывности, коиструктивпости и монотонности, м приведены новые примеры конструктивных и неконструктивных янволютнвных делений.

3. Проведен ряд чщщцых экспсрнмешов, характеризующих работу алгоритма вычисления инвалютной о to базиса Жане в зависимости от перестановки переменных.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Семенов, Александр Сергеевич

4 Заключение

Данная работа продолжает исследование ннволютнвных базисов полиномиальных идеалов и ннволютнвных делений, начатое в [3, 16, 17, 18]. Проведено сравнение различных методов построении базисов Гребнера (алгоритм бухбергера, ннволютнвиый подход, лннеЙно-алгсбранческнД подход), а также предложен новый истод построения непрерывных ннволютнвных делений — парное замыкание. Изложение алгоритма Бухбергера и алгоритма построения ннволютивного базиса а рамках единого подхода е использованием существенного умножения, обобщающего ннволютнвные делении без вложенности, также является новым результатом.

Важным примером использования разработанных методов стало выделение класса (>■,сг)-нннолютнвныхделений (>- — мономнальное упорядочение. о — нумерация переменных), являющихся аналогами деления Жане, н нахождение в нем конструктивных и неконструктивных ннволютнвных делений, не описанных ранее.

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

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

Во-первых, отмеченная связь между алгоритмом Бухбергера и линейным методом Гаусса может стать основой разработки более эффективных алгоритмов, в том числе параллел нэуемых Вероятно, для различных типов полиномиальных систем будут использоваться различные тины алгоритмом, иодсбпо тому, как обстоит дело н линейной алп-бре.

Во-вторых, встает вопрос о полной классификации ннволютнвных делений типа (>-tf), и выявление среди них конструктивных н монотонных. Для подобных делений возможно их дальнейшее изучение на предмет сравнении с делением Жане по эффективности в рамках алгоритма Минимальный Инволготивный Базис.

В-третьих, как показали вычислительные эксперименты, порядок переменных дли инволютивного подхода играет ключевую роль Тем самым, актуальное) задачей является л разрабогка алгоритмов, способных по изначальной системе вычислить оптимальный порядок переменных.

Список литературы диссертационного исследования кандидат физико-математических наук Семенов, Александр Сергеевич, 2006 год

1. Gebauer R-, MoQer H.M. Buchberger's Algorithm and Staggered Linear Bases. Proceedings of the 5-th ACM symposium on Symbolic and algebraic computations, Waterloo, Ontario, Canada (1986),218-221

2. Gebauer R., Moller H-M. On an Installation of Buchberger's Algorithm. J Symbolic Сотр., {1988} 6, 275-286.

3. Gerdt V.P., Bltnkov Yu. A. Involutive Bases of Polynomial Ideal», Mathematics and Computers m Stmufiaffan, (1998) 45, 519-542.17j Gerdt V.P., Bltnkov Yu. A. Minimal Involutive Baas, Mathematics and Computers tn Sunulation, (1998) 45, 543-560.

4. Hemmecke R. Involutive Bases for Polynomial Ideals, PUD Thesis, Johannes Kepler Universitat Linz, (2003).

5. Kharkov A. Yu. Blmkov Yu.A. Involutions Вмеа of Zero-Dimensional Ideals. Preprint No- E5-94-X18, Joint Institute for Nuclear Research, Dubna, (1994).