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

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), и выявление среди них конструктивных н монотонных. Для подобных делений возможно их дальнейшее изучение на предмет сравнении с делением Жане по эффективности в рамках алгоритма Минимальный Инволготивный Базис.

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

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).