ПРОГРАММИРОВАНИЕ, 2008, № 2, с. 61-66
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ИНВОЛЮТИВНЫЕ ДЕЛЕНИЯ И МОНОМИАЛЬНЫЕ УПОРЯДОЧЕНИЯ. ЧАСТЬ II*
© 2008 г. А. С. Семенов, П. А. Зюзиков
Механико-математический факультет МГУ им. М.В. Ломоносова 119992 Москва, Воробьевы горы E-mail: semyonovl980@mail.ru, petrzyuzikov@gmail.com Поступила в редакцию 03.06.2007 г.
Статья продолжает исследования авторов в области классификационных свойств инволютивных делений, начатые в [1]. Приводится пример, когда минимальный инволютивный базис конкретного мономиального идеала для -«¡-деления "антипод Жане" не является ни инволютивным базисом Жане, ни минимальным базисом Janet-like деления для любого из п\ упорядочений переменных. Этот пример опровергает гипотезу о том, что минимальный инволютивный базис для непрерывных и конструктивных делений всегда совпадает с базисом Жане при некотором упорядочении переменных.
1. ВВЕДЕНИЕ
В работах [2-4] развит общий алгоритмический подход к построению инволютивных базисов - базисов Гребнера специального вида. Данный подход пришел в компьютерную алгебру из теории линейных уравнений в частных производных, где метод приведения системы в инволюцию использовался уже в середине XX века (работы Жане, Рикье, Томаса, Поммаре). Процедура приведения линейной системы в инволюцию основывалась на линейных преобразованиях уравнений, входящих в систему, и последовательных однократных дифференцированиях по независимым переменным, причем только по тем из них, которые объявлялись немультипликативными, исходя из используемых правил (правило Томаса, Жане, Поммаре). Правда, для целей упрощения каждого из уравнений после такого однократного дифференцирования разрешалось дифференцировать другие уравнений сколь угодно раз по мультипликативным переменным.
* Работа была частично поддержана Российским фондом фундаментальных исследований, проект №05-01-00671.
В работах [5, 6] осуществлен перенос инволю-тивной техники на случай коммутативных алгебраических систем, где последовательным дифференцированиям ставится в соответствие однократное домножение полиномов на немультипликативные переменные, а вспомогательным дифференцированиям при упрощении - домножение многочленов на мономы, состоящие из мультиликативных переменных.
При анализе метода приведения в инволюцию в коммутативной алгебре выяснилось, что вычисление инволютивных базисов полиномиальных систем является процедурой вычисления базисов Гребнера специального вида, и интерес к инволютивному алгоритму в рамках компьютерной алгебры вызвал появление общей теории инволютивных базисов в работах В.П. Гердта и Ю.А. Блинкова [3, 4] (Россия), И. Апе-ля [2] (Германия). Теория вычисления инволютивных базисов, в свою очередь, базируется на теории инволютивных делений на множествах мономов - правил разбиения переменных на мультипликативные и немультипликативные для каждого конечного множества мономов. Базовая аксиоматика инволютивных делений схожа во всех работах, однако в работах Гердта и Блинкова [3, 4] она дополнена аксиомой филь-
трации, которая делает инволютивные деления более удобными для вычислительного процесса. Аксиоматический подход к определению ин-волютивных делений дал возможность их теоретического исследования и построения новых примеров делений.
В процессе исследования инволютивных делений выяснилось, что для эффективной работы алгоритма построения инволютивного базиса инволютивное деление должно обладать специальными свойствами: непрерывностью и конструктивностью [3, 4, 7]. Не менее важной является и скорость вычисления множества мультипликативных переменных и быстрого поиска инволютивного делителя. Этот вопрос рассмотрен в работах [7] (парность инволютивного деления), [8] (быстрый поиск делителя Жане с помощью дерева).
В работе [7] введен класс парных инволютивных делений, изучение которого продолжено в работе [9]. Установлена связь между свойством парности [7] и аксиомой фильтрации. Предложена процедура построения непрерывных инволютивных делений методом парного замыкания. Эти теоретические результаты сделали возможным описание широких классов непрерывных инволютивных делений и изучение их свойств, в первую очередь, конструктивности. Результаты этой работы отражены в статьях [1, 10, 11]. В них выявлена связь между инво-лютивными делениями и мономиальными упорядочениями, введены классы У- и ^-делений и изучен ряд их свойств, описаны широкие множества конструктивных и неконструктивных делений.
В недавних исследованиях В.П. Гердта и Ю.А. Блинкова [12] в качестве альтернативы инволютивным делениям для вычисления базисов Гребнера предложено степенное деление Жане (Janet-like деление) - особый метод разбиения мономов на мультипликативные и немультипликативные. Хотя Janet-like деление не является инволютивным, на него могут быть перенесены основные понятия теории инволютивных делений и инволютивных базисов. В ряде случаев (например, вычисление базисов Гребнера торических идеалов) Janet-like базис содержит во много раз меньше элементов, чем инво-лютивный базис Жане.
Данная работа продолжает работу [1]. В ней приводится пример конечного мономиального множества, на котором его минимальный ин-волютивный базис для ^-деления - "антипода Жане" [1] по размерности меньше, чем базис Жане и Janet-like базис для любого из га! упорядочений га переменных. Этот пример опровергает гипотезу о том, что для непрерывных и конструктивных инволютивных делений минимальные инволютивные базисы совпадают с одним их га! возможных минимальных базисов Жане.
Авторы выражают благодарность своему научному руководителю Е.В. Панкратьеву, В.П. Гердту и Ю.А. Блинкову за помощь, замечания и полезные идеи, повлиявшие на ход исследования.
2. ТЕОРИЯ ИНВОЛЮТИВНЫХ ДЕЛЕНИЙ
Обозначим символом N множество неотрицательных целых чисел. Тогда М = {xf1 ...
является множеством всевозможных мономов от га переменных.
Обозначим как deg(ii) и deg,-(ti) полную степень монома и и степень переменной жг- в и. Для наименьшего общего кратного и наибольшего общего делителя двух мономов и, v используются обозначения 1ст(и,г>) и gcd(-w,t>).
Рассмотрим произвольное конечное множество мономов U с попарно различными элементами. На U задано инволютивное деление L, если для любого и G U определен подмоноид L(u, U) в М, удовлетворяющий следующим аксиомам [3]:
• Если w G L(u, U) и v\w, то v G L(u, U).
• Если и, v G С/ и uL(u, U) П vL(v, U) ф 0, то и G vL(v, U) или v G uL(u, U).
• Если v G U и v G uL(u,U), то L(v,U) С С L{u,U).
• Если U С V, то Ми G U L(u, V) С L(u, U).
Последняя аксиома носит название аксиомы фильтрации.
Элементы L(u, U) называются мультипликативными для и. В случае, если w G uL(u, U), то и называется инволютивным делителем w, для деления используется обозначение u\lw. Моном w называется инволютивным кратным и.
ИНВОЛЮТИВНЫЕ ДЕЛЕНИЯ И МОНОМИАЛЬНЫЕ УПОРЯДОЧЕНИЯ. ЧАСТЬ II
63
Моном V = т/и является мультипликативным для и, а равенство т = иу записывается как ю = и X V. Если и является обычным делителем т, но не является инволютивным, это же равенство записывается как т = и ■ V. Моном V называется немультипликативным для и.
Для каждого и в £7 существует разбиение множества всех переменных на два непересекающихся множества: мультипликативные переменные и) С Ь(и,11)) и немультипликативные переменные II) Ь(и, II)). Напротив, если для любого элемента и в конечном II задано такое разбиение переменных, при этом соответствующие подмоноиды Ь(и, II) мономов, составленных из переменных из Мь(и,и), удовлетворяют аксиомам, то разбиение переменных задает инволютивное деление.
Подмоноиды Ь(и, II) имеют естественную геометрическую интерпретацию [13]. Рассмотрим множество иЬ(и,11) и обозначим его Сь{и,11). Легко убедиться в том, что при взаимнооднозначном отображении М в ТИ1 образом множества Сь(и, и) будет дискретный конус. Первые три аксиомы эквивалентны следующим двум геометрическим утверждениям:
• Множество Сь(и, и) является дискретным конусом.
• Сь(и,и) П Сф,и) ф 0 Сь(и,и) С С Сь(у1и)УСь(у1и) С Сь{и,и).
Кроме того, введем обозначение Сь{11) = = и иеиСь(и,и).
Пример 1 (деление Жане .1). Рассмотрим конечное множество мономов II с попарно различными элементами. Для любого 1 ^ I п множество II можно разделить на подмножества, маркируемые неотрицательными целыми ¿1, ...,
[¿г,.. .,с1г] = {и е II | ¿3 = ск^-(и), 1 ^ 2 ^ г}.
Переменная жг- мультипликативна для и 6 17, если г = 1 и с^^и) = тах {с^^и) | V £ II}, или если I > 1, и £ [б?1,..., б?г_ 1], и с^г-(и) = = тах{ск^г(г;) | V е [¿1, • • •, ^-1]}.
Далее приводится определение степенного деления Жане [12].
Определение 1 (немультипликативная степень [12]). Пусть II С М - мономиальное мно-
жество, и его элементы разделены на подмножества, как в примере 1. Для каждого и G U и 1 ^ i ^ п рассмотрим функцию hi(u,U) G заданную как
hi(u, U) :=
:= max{deg8(i;) | и, v G [d0,..., 1]} - deg8(-w). Если hi{u, U) > 0, то степень х^', где
кг := min{deg8(i;) - deg8(-w) | v, и G [d0,..., 1],
deg,-(t;) > deg,-(ti)},
будет называться немультипликативной степенью для и.
Обозначим за NMP(u, U) множество всех немультипликативных степеней для и G U.
Пример 2 (степенное деление Жане JL (Janet-like) [12]). Рассмотрим конечное множество мономов U. Для любого 1 < i < п множество U можно разделить на подмножества, маркируемые неотрицательными целыми d\,...,
[di, ...,di] = {и е U\d3 = degj (и), 1 < j < i}.
Моном хявляется минимальным немультипликативным для и £ U, если i = 1, к = = min{deg1(t;) — deg1(«)|t; £ U, deg^ii) < deg^i;)}, или если i > 1, и G [d\,..., ¿¿_i], к = = min{deg8(t;) - deg8-(ii)|i; E [db . . ., 1], deg8-(w) < < deg8(i;)}. Иными словами, x\ - немультипликативная степень для и.
Аксиома фильтрации допускает следующую переформулировку. Пусть имеются два конечных множества мономов U, V и правило разбиения L. Тогда \fu G U П V
ML(u,UUV)CML(u,U)nML(u,V). (1)
Логика построения алгоритма вычисления инволютивных базисов предполагает, что чем больше объем и размерность множеств инволютивных кратных, тем меньше локальных инволютивных продолжений нужно рассматривать. Исходя
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.