Содержание к диссертации
Введение
1 Вступление 3
1.1 Актуальность темы 3
1.2 Практическая ценность 5
1.3 Апробация работы 6
1.4 Публикации 7
1.5 Обзор 8
1.6 Структура и объем диссертации 21
2 Последовательные алгоритмы вычисления базисов Грёбнера 22
2.1 Классический алгоритм Бухбергера 22
2.2 Вероятностный алгоритм вычисления базисов Грёбнера . 42
2.3 Версия, использованная при распараллеливании 45
3 Параллельные алгоритмы вычисления базисов Грёбнера 47
3.1 Обзор параллельных алгоритмов 47
3.2 Алгоритм Pipeline 48
3.3 Алгоритм Conveyer 52
3.4 Алгоритм с использованием графа редукций 55
4 Оценка качества распараллеливания алгоритмов вычисления базисов Грёбнера 59
4.1 Оценка качества распараллеливания путем моделирования работы параллельного алгоритма 59
5 Вычисление инволютивных базисов в дифференциальном модуле 67
5.1 Реализация алгоритма 70
5.2 Анализ производительности алгоритма 73
6 Пример применения системы для вычислений в дифференциальном модуле 79
6.1 Вычисление размерностного многочлена при заменах образующих в системе уравнений Дирака 79
7 Заключение
- Практическая ценность
- Вероятностный алгоритм вычисления базисов Грёбнера
- Алгоритм Conveyer
- Анализ производительности алгоритма
Введение к работе
В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.
Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего вре ме-ни это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Гребнера, на практике для реальных систем его производительность существенно выше.
В последнее время вызывает сильный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребнера. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор воз можных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу.
Дальнейшим путем к увеличению эффективности алгоритмов является попытка обогнать прогресс в развитии вычислительной техники путем использования большого количества процессоров одновременно - распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе.
Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.
В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с неизвестными имеет вид
/i = a + b + c + d
/2 = ab -f ad + be + cd
/3 = abc + abd + acd + bed
/4 == abed — 1
Базис Гребнера для этой системы имеет вид
дг = C2dQ-C2d2-dA + l
92 = c3d2 + c2d3 - с - d
gz = bdA-b + db-d
g4 = bc-bd5 + c2d4 + cd- d6 - d2
g5 = b2 + 2bd + d2
g& = a + b + c + d
Для системы уравнений cyclic от пяти неизвестных базис Гребнера состоит из 11 уравнений
91 = е15 4-122е10 - 122е5 - 1
д2- = 55d2e5 - 55d2 - 2deu - 231de6 + 233de - 8е12 - 979е7 + 987е2
дг = 6d7 + 57d6e6 - 39d6e + 25d5e7 - Ш5е2 - 5d4e8 + 5d4e3 - 8d3e9 +
+ 8d3e4 - 2dV° + 14d2e5 - 18d2 - 18de6 - 6e7
g4 = 360150ce5- 360150c + 71540d9e2 - 110722d8e3 - 1744327d7e4 - 3078595d6e5 + 233730d6 + 219158d5e6 - 1058999d5e + 2366210d4e7 - 2437750d4e2 + 1281458d3e8 - 1170736d3e3 + 200573d2e9 + 1543754d2e4 + + 2844865de5 + 839841e6
g5 = 360150cd-360150ce6-71540d10e2 + 110722d9e3 + 1744327d8e4 +
+ 3064189dV - 233730d7 + 313864d6e6 + 1058999d6e - 795956d5e7 +
+ 2437750d5e2 - 1403909d4e8 + 1293187d4e3 - 1360256d3e9 - 744221d3e4 - 410571d2e10 - 2059738dV - 1372863de6 - 1570254e7
и т.д. Для системы уравнений cyclic от шести неизвестных базис Гребнера состоит из 17 уравнений, длина коэффициентов которых превышает 100 десятичных цифр
1.2 Практическая ценность
Результатом работы является программный комплекс, предназначенный для построения базисов Гребнера и инволютивных базисов в кольце мно гочленов с целочисленными коэффициентами и коэффициентами из конечного поля. В качестве языка реализации был выбран язык C++, позволяющий добиться высокой производительности и качества программного кода. Распараллеливание осуществлялось на кластере типа "сеть рабочих станций" под управлением операционной системы Linux и было осуществлено в терминах библиотеки MPI.
В качестве примеров применения базисов Гребнера можно привести такие задачи, как исследование систем нелинейных алгебраических уравнений на совместность, нахождение количества решений систем нелинейных алгебраических уравнений, составная часть большого количества алгоритмов в конструктивной теории полиномиальных колец или предварительный этап для численного решения систем нелинейных алгебраических уравнений.
1.3 Апробация работы
По результатам, полученным в данной работе, были сделаны доклады и публикации на российских и международных конференциях, список которых приведен ниже.
• International Association for Mathematics and Computers in Simulation Conference on Applications of Computer Algebra (IMACS АСА) 2000, Петербург, Россия
• Formal Power Series and Algebraic Combinatorics (FPSAC) 2000, Москва, Россия
• International Workshop on Computer Algebra and its Application to Physics (СААР) 2001, Дубна, Россия
• International Workshop on Involutive Systems and Symmetries of Differential Equations, 2001, Новосибирск, Россия
• Workshop on Under- and Over-Determined Systems of Algebraic or Differential Equations, 2002, Карлсруэ, Германия
• Computer Algebra in Scientific Computing (CASC) 2002, Ялта, Украина
• International Association for Mathematics and Computers in Simulation Conference on Applications of Computer Algebra (IMACS АСА) 2003, Соединенные Штаты Америки
С помощью созданного пакета программ были вычислены базисы Гребнера для большого набора тестовых систем из набора POSSO. В частности, были вычислены базисы Гребнера для систем попадающих в категории "очень сложные" и недоступные для пакета компьютерной алгебры Singular.
1.4 Публикации
•
М.В. Кондратьева, В.А. Митюнин "Вычисление дифференциального размерностного многочлена при заменах образующих в системе уравнений Дирака", "Программирование", 2001, 1, р. 37-40
Mityunin V.A. "Implementation of the differential involutive algorithms in the CAS Maple VR5", Proceedings of IMACS АСА 2000, pp. 38-39.
•
Kondratieva M., Makarevich N., Mityunin V. "Computation of primitive element in differential module", Proceedings of IMACS АСА 2000, p. 28-29. Add. Thesises 12h International Conference FP-SAC 00, pp. 23-24.
• V.A.Mityunin, A.I.Zobnin, A.I.Ovchinnikov, A.S.Semenov "Involutive and Classical Groebner Bases Construction from the Computational Viewpoint" Proceedings of СААР 2001, p.221-230
• Mityunin V.A., Semenov A.S. "Parallel Implementations of Honey Strategy Buchberger Algorithm", Proceedings of "Workshop on Under-and Over-Determined Systems of Algebraic or Differential Equations" (Karlsruhe, Germany, 2002), p.221-225
• Mityunin V.A., Semenov A.S. "An Estimation of the Parallelization Quality of the Involuive Basis Computation Algorithm", Proceedings of CASC 2002
• Mityunin V.A, Pankratev E.V., "Comparison of the parallellization quality of algorithms for computing Groebner and involutive bases using the Faugere method", Proceedings of IMACS АСА 2003, United States Of America
•
Митюнин B.A., Панкратьев E.B "Параллельные алгоритмы построения базисов Гребнера", Международная алгебраическая конференция, посвященная 250-летию Московского Государственного Университета, тезисы докладов, Москва, мех-мат МГУ, 2004, стр. 97-99
1.5 Обзор
В силу важности задачи эффективного построения стандартных базисов с практической точки зрения, ее решению уделялось достаточно много внимания. В последние годы также существенно возрос интерес к алгоритмам построения инволютивных базисов, которые могут рассматриваться как частный случай нередуцированных базисов Грёбнера и для построения которых могут быть использованы как специальные алгоритмы, так и модифицированные алгоритмы построения базиса Грёбнера.
Работы по увеличению эффективности алгоритма вычисления стандартного базиса можно разделить на несколько классов. К первому из них следует отнести методы, имеющие достаточно низкий теоретический интерес (по крайней мере с точки зрения теории стандартных базисов) и направленные на оптимизацию элементарных операций, таких как арифметика коэффициентов или сравнение мономов. Вторым подходом является улучшение применяемых стратегий для выбора и отбрасывания 5-элементов. Третьим способом увеличения эффективности алгоритмов вычисления базисов Грёбнера является их распараллеливание.
Рассмотрим работы в этих трех направлениях более детально. Что касается оптимизации элементарных операций - арифметики коэффициентов и сравнения мономов - ни первый, ни второй метод очевидно не позволяют улучшить асимптотическую сложность алгоритма, тем не менее могут увеличить скорость работы в несколько раз. Роль оптимизаций первого типа, очевидно, более заметна при вычислении стандартных базисов в кольцах полиномов с коэффициентами из конечного поля, в то время как оптимизации второго типа оказывают большее влияние на вычислениях в кольцах полиномов с целочисленными коэффициентами.
Как правило, в свободно распространяемых реализациях алгоритмов построения стандартных базисов (в виде отдельных модулей или встроенных процедур систем компьютерной алгебры) используется библиотека целочисленной арифметики произвольной точности GMP (Gnu Multiple Precision). Основными преимуществами данной библиотеки являются ее доступность на большинстве систем и достаточно высокая эффективность. Тем не менее, для некоторых специфических задач, таких как вычисление стандартных базисов (где наряду с арифметическими операциями очень важно эффективное вычисление наибольшего общего делителя, активно используемое при вычислениях содержания многочленов), возможна модификация данной библиотеки с целью повышения скорости вычислений без изменения алгоритмической части. Известна система компьютерной алгебры Magma, в которой была проведена оптимизация процедур этой библиотеки.
В данной работе наряду с библиотекой GMP была проведена апробация библиотеки Piologie [49], реализованной на языке C++. На данный момент это, по-видимому, вторая после GMP по эффективности свободно доступная библиотека целочисленной арифметики произвольной точности. В качестве ее преимуществ можно привести язык реализации, что облегчает ее поддержку и использование, однако это безусловно несколько сказывается на эффективности библиотеки. Кроме того, в библиотеке Piologie недостаточно эффективно реализован алгоритм вычисления наибольшего общего делителя, что существенно понижает ее эффективность в случае вычисления базисов Грёбнера. В результате обсуждений с авторами библиотеки данный алгоритм вычисления GCD был существенно улучшен, хотя все еще уступает GMP.
На данный момент эта библиотека используется в проекте, посвященном проверке гипотезы Римана [50]. Вычисления организованы достаточно интересным образом - любой желающий может загрузить на свой компьютер необходимое программное обеспечение по сети интернет и таким образом подключить свой компьютер к системе. Процесс будет запущен на компьютере в низком приоритете и исполняться в то время, когда микропроцессор не загружен какой-либо другой задачей. На данный момент в проекте участвуют более 8000 компьютеров но всему миру, а производительность полученного кластера превышает 700 GFlops, при пиковой производительности свыше 4000 GFlops. Каждый день вычисляется более 1 миллиарда нулей дзета-функции Римана.
В результате вычислений на данный момент были проверены первые 100 миллиардов нулей дзета функции Римана. Гипотеза Римана, таким образом, справедлива для \t\ 29,538,618,432.236.
Наиболее интересной работой, направленной на оптимизацию сравнения мономов, является, на мой взгляд, интернет-публикация одного из создателей системы компьютерной алгебры Singular Олафа Бах.мана (Olaf Bachmann) [51].
Условимся обозначать мономы буквами греческого алфавита а, /3,7, а степени, соответствующие переменной под номером і как аг, Д, 71-Основными операциями над мономами в процессе вычисления базисов Грёбнера являются:
• Вычисление степени deg(a) := Y =i аг (возможно, взвешенной степени по отношению к весовому вектору w. deg(a) := Х Г=і aiwi) • Проверка делимости а \ (3 -& Vi Є {1... п} : аг Рг.
• Сложение двух мономов j := а + (3,Уг Є {1.. .п} : % = аг + рг.
• Сравнение двух мономов в соответствии с данным отношением порядка.
Допустимым отношение порядка на множестве мономов Мп будем называть полное отношение порядка на Мп, совместное с полугрупповой операцией, т.е. а /? 7 + а 7 +А 7 Мп. Роббиано а работе [54] доказал, что любое отношение порядка на мономах может быть представлено в виде
а р & Аа іех Ар
для некоторой матрицы А Є (7L(n, R). Представление отношения порядка с помощью матриц является очень общим методов, однако редко используется на практике в силу достаточно низкой вычислительной эффективности.
Вместо этого как правило используется описание отношения порядка на мономах с помощью двух определяющих условий: степени (возможно, взвешенной) и лексикографического сравнения (нормального или обратного). Условимся называть отношения порядка, которые могут быть описаны подобным образом, простыми отношениями порядка.
Для мономов а,Р Є Мп определим следующие функции:
( 1, если Зг : е і = /?і,..., аг-\ = рг-\, аг рг
Lex(a,P) = 0, если а = Р [ — 1, иначе
{
1, если Зі : ап = рп,..., аг-\ = Д_і, аг рг О, если а — Р —1, иначе {1, если deg(a) deg(/3) О, если deg(a) = deg(/?) — 1, иначе Тогда наиболее важные с практической точки зрения отношения порядка можно определить следующим образом:
• лексикографическое Lex{a,p) — 1;
• (взвешенное) по полной степени, затем обратное лексикографическое Deg(a,P) = 1, или Deg(a,P) = 0 и RevLex(a,p) = 1;
• (взвешенное) по полной степени, затем лексикографическое Deg(a, (3) — 1, или Deg{a,(3) — 0 и Lex{a f3) = 1.
В силу особенностей алгоритма построения базиса Грёбнера элементарные операции над мономами являются наиболее частыми примитивными операциями. Например, сравнения мономов осуществляются более часто, а сложения по крайней мере не реже чем арифметические операции в области коэффициентов. Количество проверок делимости достаточно сильно зависит от конкретной системы уравнений, но, как правило, достаточно велико.
Тем не менее, суммарный вклад элементарных операций над мономами в полное время работы алгоритма существенно зависит от области коэффициентов. Для вычислений стандартных базисов над конечными полями их доля достаточно велика, в то время как для систем с целочисленными коэффициентами этими временами, как правило, можно пренебречь.
Для увеличения эффективности элементарных операций над мономами можно воспользоваться их векторизацией. Предполагая, что размер машинного слова является кратным размера степени, операции будут производится над машинными словами, а не непосредственно со степенями по отдельным переменным. Таким образом вектор степеней будет обработан одной машинной инструкцией, уменьшая тем самым длину внутренних циклов.
Лемма 1. Пусть se,m Є N и а = (ао,...ат-і),р = (Д ,.. • An-і) Є Мт, причем аг,(Зг 2Se_1. Далее, пусть sw = sem и
а, 6, а, Ь, 7,... 7т-ь о • • • т-і Є N 7.Л 2в«
и выполнено
a = b =
a =
b b + a( mod 2Sw) b-a( mod 2Sw) + + ... + 0 2 -1 /% + A2S + ...+ (Зт-гІЇ™-1 ат_х + am_22s + ... + a02(m-1)Se An-i + A»-22s + ... + A)2(m-1)Se 7o + 7i2Se + ...+7m-i2(m-1)Se 50 + 5i2Se + ... + -12 -1 Тогда справедливо следующее:
b-a{ mod 2s-) 2s-"1 4Ф Lex(a, (5) = 1 (1)
b-a{ mod 2s-) 2s-"1 S RevLex(a, (3) = -1 (2)
(7o,...,7m-i) = a + P (3)
VO і m : St 2Se_1 & a\(3 (4)
Лемма 1 показывает, что операции над мономами в правых частях могут быть векторизованы таким образом, что на машине с размером слова sw проверки левых частей могут быть осуществлены самое большое с использованием трех машинных инструкций.
Тем не менее при переходе к непосредственной реализации остается ряд технических сложностей. Во-первых, необходимо удостовериться в строгих ограничениях на степень полиномов. Во вторых, условие sw — sem предполагает, что полная длина вектора степеней является кратным размера машинного слова, что может потребовать хранение (—n)( mod га) избыточных степеней, значение которых всегда будет равно нулю. В третьих, в зависимости от архитектуры компьютера и выбранного отношения порядка порядок следования степеней в векторе может быть инвертирован.
Сложение мономов может быть реализовано как неявный инициализатор, в силу того что это наиболее ожидаемый источник появления новых мономов.
Альтернативным способом представления мономов является представление, основанное на ранге. Первоначально оно было разработано и использовано в системе компьютерной алгебры Macaulay. Основная идея данного представления основывается на следующем свойстве отношения порядка совместном со степенью:
Vra Є Мп : Й{т Є Мп : 1 т т} со (5)
Таким образом, существует возможность биективного отображения мономов на целые числа, которые мы будем называть рангами мономов. Точный вид изоморфизма зависит от выбранного отношения порядка. Для упорядочивания по полной степени, затем обратного лексикографического он задается следующей леммой.
Лемма 2. Пусть а Є Мп и Г ІР : Мп — N задано формулой
г (а) :=(!-« у "1) (6)
Тогда справедливо следующее утверждение:
Va, /? Є Мп : Гф(а) rdp(P) & a dp (3
Va, j3eMn: rdp(a) = rdp(J3) = a =/3
Подобные биективные отображения могут быть построены и для других отношений порядка.
Благодаря использованию представления, основанного на ранге, сравнения мономов могут быть реализованы как сравнения их рангов. Кроме того, представление полиномов с использованием рангов является достаточно компактным, требуя минимальных затрат памяти. Тем не менее, это представление имеет ряд недостатков.
• сложение и проверка делимости не могут быть реализованы эффективно, поскольку биекция не является аддитивной и не сохраняет
делимости;
• реализация данного метода для произвольных степеней требует использования арифметики произвольной точности, что в свою очередь повлечет значительные накладные расходы; ограничиваясь 32 битами машинного слова возникают следующие ограничения на степени полиномов, возникающих в процессе вычислений
количество переменных 3 4 5 7 10 15 20 25
максимальная степень 2340 471 186 66 31 17 12 9
• отношения порядка, несовместные с полной степенью, например Lex не допускают построение подобных биекций.
Эти проблемы накладывают достаточно серьезные ограничения на системы уравнений и используемые отношения порядка, в силу чего метод, основанный на векторизации элементарных операций над мономами, является более предпочтительным, что подтверждено экспериментально.
Идеи из работы [51] были использованы в данной реализации и позволили добиться существенного улучшения производительности при вычислении в кольцах полиномов с коэффициентами из конечного поля.
Вторым упомянутым методом увеличения эффективности алгоритмов построения стандартных базисов является улучшение применяемых стратегий для выбора и отбрасывания s-элементов.
В качестве одной из наиболее интересных работ в данном направлении следует упомянуть работу [18], основные идеи которой состоят в следующем. Определим фиктивную гомогенизацию полиномов посредством введения фиктивной степени Sf полиномов следующим образом. • Для полиномов /г исходной системы 5/t = deg(/j) (не степень старшего монома, а полная степень полинома).
• Пусть дан полином / и терм t, тогда положим Stf = deg() + S/.
• В случае если f = д + h, Sf = max(Sg, Sh).
Таким образом, с каждым полиномом может быть ассоциирован однородный полином степени, равной соответствующей фиктивной степени, при условии гомогенизирования с помощью дополнительной переменной. Стратегия выбора критических пар при использовании фиктивной однородной степени заключается в следующем. Первоначальный отбор происходит путем сравнения фиктивных степеней, а в случае их равенства для нескольких полиномов используется нормальная стратегия выбора на основании лидирующих термов.
Возможно также использование модифицированных версий данной стратегии. Например, в процессе редукции имеется определенная свобода выбора элемента, по которому осуществляется редукция. Некоторые аспекты не вызывают сомнения: в случае если старший терм полинома может быть редуцирован, необходимо произвести его редукцию, так как любые другие действия, очевидно, приведут только к потере времени. Как правило, также более выгодно использовать для редукции полином, который был добавлен к промежуточному базису раньше других. Предлагаемая стратегия заключается в следующем: помимо перечисленных критериев, анализируется фиктивная однородная степень полинома, и редукция осуществляется только в том случае, если она не приводит к повышению фиктивной однородной степени.
Впервые стратегия вычисления фиктивной однородной степени полиномов была реализована в системе компьютерной алгебры СоСоА, и зарекомендовала себя как достаточно эффективная.
Первоначальная система критериев, используемых в алгоритме построения минимального инволютивного базиса, была построена профессором Гердтом как обобщение критериев Бухбергера на инволютивный случай. В последнее время были получены интересные результаты, касающиеся улучшения критериев, применяемых в процессе вычисления минимального инволютивного базиса, см. [1]. На данный момент существует
гипотеза, что все критерии, применяемые при построении минимального инволютивного базиса, можно обобщить с использованием базиса сизигий, аналогично идеям из работы [28], но это факт еще не доказан. Критерии, которые используются большинством эффективных реализаций алгоритма Бухбергера на данный момент, основаны на идеях из работы [17].
Рассмотрим третий метод увеличения эффективности алгоритма вычисления базисов Грёбнера - распараллеливание. Основная трудность, с которой приходится столкнуться в процессе распараллеливания алгоритма построения стандартных базисов, это тот факт, что на ход работы очень сильно влияет выбор стратегии, что существенно затрудняет перенесение найденных в процессе исследования последовательного алгоритма эвристик на параллельную версию. Надо отметить также, что алгоритм Бухбергера и практически все его известные интерпретации являются существенно последовательными (точное определение этого термина и демонстрация этого факта будут приведены далее в работе).
Важность сохранения стратегии, выбранной в процессе работы с последовательным алгоритмом, подчеркнута в работе [20].
Очень интересные работы, посвященные распараллеливанию алгоритма построения базисов Грёбнера, принадлежат Ж.К.Фожеру (J.C.Faugere) В последнее время он работает над серией алгоритмов F, допускающих эффективное распараллеливание. Существует теория, что алгоритм F не может быть смоделирован последовательным алгоритмом построения базисов Грёбнера ни для какого выбора стратегии вычислений. К сожалению, работы в этом направлении не являются доступными. На идеях этого алгоритма хотелось бы остановиться немного подробнее.
Введем некоторые обозначения, необходимые в дальнейшем. Условимся обозначать кольцо полиномов с целочисленными коэффициентами от переменных xi,...xn как Я, а как Т - множество всех термов в этих переменных. Пусть / - полином. Тогда обозначим за HT(f),HM(f) и HC(f) его старший терм, моном и коэффициент соответственно.
Определение 1. Пусть М матрица размерности s х т, и Тд/ = [i,...m] - упорядоченное множество термов. Пусть (єг)г=(іі...гп) канонический базис пространства Rm. Рассмотрим, линейное отображение іртЛ{ — Rm, где VTM - подмодуль R, порожденный Тд/, такое, что PTM{ti) ег- Обратную функцию обозначим за "фтм- Применение іртм позволяет трактовать векторы из Rn как полиномы. Обозначим как (Л/, Тд/) матрицу, интерпретируемую таким образом.
Определение 2. Пусть (М,Тм) матрица размерности S х т, тогда построим множество полиномов следующим образом:
Rows(M,TM) := {фТм{гои){М,ї)) \ г = 15..., s] \ {0}
где row(M,i) является г-тым рядом матрицы М (элементом Rm). В свою очередь, если I - список полиномов и Ті - упорядоченное множество термов, можно построить матрицу А размерности s х т (где s = size(l),m = size{Ti)), такую, что:
Кз :=соеЯ№],7/И),г = 1,---,5,j = 1,..., m
Обозначим через A l,Tl матрицу (A,j).
Определение 3. Пусть М матрица размерности sxm uY_= [УЇ,..., Yr новые переменные. Тогда F = Rows(M,Y_) является новой системой уравнений. Таким образом можно перейти к вычислению редуцированного базиса Грёбнера F системы F в лексикографическом отношении порядка таком, что Y\ ... Ym. Используя построенный базис, можно построить матрицу М = AF —. Условимся называть М ступенчатой по строкам формой матрицы М, а базис F - ступенчатым по строкам базисом системы F.
Определение 4. Пусть F - конечное подмножество R и - допустимое отношение порядка. Обозначим как TK(F) систему
Sort({T(f)\feF}, ) А .- Д(Р,Т (П)
и как А - ступенчатую по строкам форму А. Будем тогда говорить, что
F = Rows{A,T {F))
является ступенчатой по строкам формой F по отношению к .
Теорема 1. Пусть М матрица размерности sxm, и Y_ = [УЇ,..., Ym] гювый набор переменных, F — Rows(M,Y_), М ступенчатая по строкам форма М, F = Rows(M,Y_). Обозначим как:
F+ = {geF\ HT(g) HT(F)}
F = F\F+ Для любого подмножества F_ множества F такого, что size(F-) = size(HT(F)) и HT(FJ) = HT(F), множество G = F+ U F является треугольным базисом R-модуля Ум, порожденного системой F. Иначе говоря, для всех f Є Ум найдутся множество (\k)k элементов R и множество (gk)k элементов G такие, что f = Y2k k9k, HT(g{) = HT(f)uHT(gk) HT(gk+1).
Следствие 1. Пусть F - конечное подмножество Е, - допустимое отношение порядка и F - ступенчатая по строкам форма F относительно . Положим
F+ = {geF\ HT(g) ЯГ(F)} Для всех подмножеств F- множества F таких, что
size(F-) = size(HT(FJ) = HT{F),
пусть G — F+ U F- - треугольный базис R-модуля Ум, порожденного F.
Тогда для всех f Є Ум найдутся множество (Xk)k элементов R и множество (gk)k элементов G такие, что f = Ylk kgk, HT{g{) = HT(f) и HT{gk) HT(gk+1).
Хорошо известно, что в процессе работы последовательного алгоритма Бухбергера имеется свобода выбора таких элементов, как:
• критическая пара для редуцирования;
• элемент, по которому будет производиться редукция.
Доказано, что этот выбор не влияет на корректность алгоритма, в то же время от него существенно зависит время вычислений. Более того, в большинстве современных интерпретаций при выборе анализируется только старший терм полиномов. Очевидно, что при таком подходе в случае наличия набора полиномов с одинаковым старшим термом задача выбора не может быть эффективно решена. Простая и в то же время интересная идея алгоритма F состроит в том, что этот выбор не производится вообще. Более точно, вместо выбора одной критической пары на шаге алгоритма, выбирается подмножество множества критических пар. Таким образом, необходимость выбора откладывается на этом этапе алгоритма до следующей его части, которая основана на методах линейной алгебры.
Algorithm F
Input: G - конечное множество полиномов из R;
Sel - функция List(Pairs) — List(Pairs) такая,
что Sel(l) ф 0 если І ф 0. Output: GB - базис Грёбнера идеала [G] begin
F+ — G
d — 0
P — {Pairing) \f,gQG,/ ф g}
while P ф 0 do d — d+1 Pd — SeJ(P)
Ld — Le/t(Pd) U Right{Pd) Fd — Reduction(Ld, G) for h Є F/ do P — P U {Pair{h, g)\geG} GB — G5U {fr} end for end while return(GP) end
#
Расширим понятие редукции полинома f Є R по подмножеству R до понятия редукции подмножества полиномов R по подмножеству Л.
Algorithm Reduction
Input: L - конечное подмножество Т х R;
G - конечное подмножество полиномов из R. Output: F+ - конечное (возможно пустое) подмножество R begin
F — SymbolicPreprocessing(L, G)
F — Reduction to Row Echelon Form of F
F+ -{feF\ HT(f) І HT(F)} returnF+ end
Изложим теперь главную функцию алгоритма, цель работы которой построение "матрицы" F.
Algorithm Symbolic Preprocessing
Input: L - конечное множество полиномов из Т х R;
G - конечное подмножество полиномов из R. Output: F - конечное подмножество R begin
F — {t f\(tj) Є L} Done І— HT(F) while T(F) ф Done do m — выберем элемент из T(F) \ Done Done — Done U {m} if m может быть редуцировано no G do
m — m HT(f) для некоторых / Є F и m! Є T F — FU{m /} end if end while returnF end
Лемма 3. Пусть G - конечное подмножество R, L - образ конечного подмножества Т х G при отображении mult и F+ = Reduction(L, G). Тогда HT(h) Id(HT(G)) для всех h Є F+.
Лемма 4. Пусть G конечное подмножество R, L образ конечного подмножества Т х G при отображении mult и F+ — Reduction(L, G). Тогда F+ является подмножеством Id(HT(G)). Более того, для всех f из R-модуля порожденного L, f редуцируется к нулю по множеству GUF+.
Используя приведенные выше леммы, можно доказать следующую теорему:
Теорема 2. Алгоритм F вычисляет базис Грёбнера G в R такой, что FcG uId{G) = Id{F).
Замечание 1. В случае если size(Sel(l)) = 1 для всех I 0, алгоритм F является алгоритмом Бухбергера. В этом случае Sel реализует стратегию выбора последовательного алгоритма вычисления базиса Грёбнера.
Замечание 2. Алгоритми Symbolic Preprocessing является очень эффективным в силу того факта, что врелія его работы линейно в случае, если size(G) меньше чем итоговый размер T{F), что, как правило, является справедливым.
Таким образом задача построения базиса Грёбнера для полиномиальной системы сводится к задаче решения (сильно) разреженных систем линейных уравнений, которая может быть эффективно решена с использованием большого числа процессоров. Для достаточно больших задач возникает необходимость в сжатии матриц, что может быть осуществлено рядом известных алгоритмов, вплоть до использования стандартных утилит архивирования, таких как gzip.
Немаловажной задачей является подборка тестовых примеров для проверки эффективности работы реализации алгоритма построения базисов Грёбнера. Эта проблема достаточно остро заявила о себе в последнее время, в результате чего было предпринято несколько попыток предложить ее комплексное решение. Несколько проектов было направленно на создание общедоступного глобального банка таких полиномиальных систем, например [52], [53]. Набор тестовых полиномиальных систем для проверки эффективности реализации в данной работе был сформирован из систем, аналогичных использованным в работах В.П. Гердта, и включает все стандартные примеры, используемые для оценки эффективности реализаций алгоритмов вычисления базисов Грёбнера в системах компьютерной алгебры.
Методы, представленные в данной работе для распараллеливания алгоритмов вычисления базисов Грёбнера и оценки качества распараллеливания, могут быть применены к произвольным интерпретациям алгоритма Бухбергера и различным стратегиям. Для апробации в работе были зафиксированы стратегии, показавшие свою высокую эффективность в экспериментах. Предложенные вероятностные алгоритмы могут быть достаточно легко (ценой небольшого количества относительно недорогих дополнительных полиномиальных операций) преобразованы в детерминированные с помощью изложенной хметодики. Параллельные алгоритмы могут быть реализованы на кластерах типа сеть рабочих станций, без существенной потери эффективности по сравнению с использованием архитектуры с разделяемой памятью. Все результаты также могут быть обобщены на алгоритмы построения инволютивных базисов. 1.6 Структура и объем диссертации
Диссертационная работа состоит из введения, 5 глав, заключения, и содержит библиографию, включающую 49 наименований. Общий объем диссертации составляет 88 страниц.
Структура работы отражена в оглавлении.
Практическая ценность
Одним из наиболее важных методов, используемых для решения систем алгебраических уравнений, является построение базиса Грёбнера, также известного как стандартный базис. В случае идеала размерности ноль, когда система имеет конечное число решений, в качестве метода решения алгебраической системы уравнений можно предложить следующий алгоритм, состоящий из четырех шагов. В первую очередь, необходимо построить базис Грёбнера для отношения порядка DegRevLex (степень обратная лексикографика). Затем проводится вычисление базиса в отношении порядка Lex (чистая лексикографика) путем пересчета найденного базиса с помощью, например, алгоритма FGLM или GrobnerWalk, и полученная треугольная система уравнений решается с помощью численных методов. Наиболее сложным с алгоритмической точки зрения является первый шаг данной цепочки в силу того, что очень непросто предсказать время, необходимое для построения стандартного базиса и размер коэффициентов как результата, так и полиномов, возникающих в процессе вычислений. Как правило, на практике существует огромное различие между вычислениями в кольцах полиномов с коэффициентами из конечного поля и целочисленными коэффициентами. Основной проблемой является рост коэффициентов в процессе вычислений. Далее в данной работе будет рассматриваться задача построения базиса Грёбнера для систем полиномов с целочисленными коэффициентами.
Обозначим Р кольцо полиномов от п переменных {Хі,...Хп} над полем к, азаГ- свободную коммутативную полугруппу порожденную {Х\,... Хп} с полу групповым отношением порядка . Каждый полином / Є Р \ {0} может быть единственным образом записан в виде / = J2I=L. t c m t Є k \ (} тг Є T,mi m2 ... mt.
Положим T(f) = mi, M(f) = сіті, lc(f) = ci - максимальные терм, моном и коэффициент в данном представлении. В случае необходимости подчеркнуть отношение порядка в определении выше, будем писать Т , А/ или ауТа, Ма.
В случае F С Р положим M{F} = {A/(/) : / Є F \ {0}}, а за M(F) обозначим идеал, порожденный M{F}. Тем самым, в случае если / - идеал, то М{1) является мономиальным идеалом, порожденным максимальными элементами І. В дальнейшем будем предполагать, что - допустимое отношение порядка.
Пусть / - идеал в Р. В частности, / будет также являться подпространством А;-векторного пространства Р (бесконечной размерности в случае I ф {0}). Пусть В = {t Є Г : t М(1)} и к[В] - /с-векторное пространство с базисом В. Лемма 1. 1. 1Г\к[В] = {0}; 2. V/i Р найдется f Є I,g Є к[В] :h = g + f.
Доказательство. 1. Пусть / Є Р\ {0}. Тогда / = Ylt=i tcim%- ci Є k \ {0},тг Є Г,ті ... mt. Если f Є І, то ггц = М(/) Є М(7), в то время как если f Є k[B] то ті Є В.
2. Определим рекурсивно последовательность элементов Р, (hn : п Є N),(fn : п Є N),(gn : n Є iV) таким образом: /г0 := /г, /о := 0, := 0; если hn = 0, то положим hn+i := 0, fn := fn-i,9n := Pn-i; если Ігпф 0 и M(hn) ф М(1), то положим /in+i := h n — M(hn), fn = fn-h 9n := gn-i + M(hn); иначе / ф 0 и M(hn) Є М{1). Тем самым найдется / Є / такой, что M(hn) — M(f), положим в этом случае /гп+і := hn — f, fn = fn-\ + /, gn — 9n-\ Очевидно, что для любого п справедливо h = hn + /„ + gn; если /in 7 0 то T(/in+i) T(hn).
В силу того что допустимое отношение порядка, не существует бесконечной убывающей цепочки термов T(ho) ... T(hn) T(hn+i) — Тем самым найдется такое п что hn = 0, следовательно
Следствие 1. Для любого h Є Р существует единственный g Є &[?] такой, что h — g Є I. Полином g который условимся называть канонической формой h по отношению к I и обозначать g = Can(h, I). Более того, Can(h,I) = 0 тогда и только тогда, когда h Є /; Can(ho,I) = Can{h\,I) тогда и только тогда, когда ho — hi Є І.
Доказательство леммы 1 может быть легко преобразовано в алгоритм построения канонической формы полинома относительно идеала (и тем самым решена проблема вхождения). Другими словами: для монома т возможно определить, принадлежит ли он М(7), и в случае положительного ответа найти / Є / такой, что M(f) = т. Если / задан посредством базиса F такого, что M(F) = М(7), то т Є М{1) тогда и только тогда, когда найдутся д Є F, с Є к\ {0}, t Є Т такие, что га = ctM(g). В данном случае можно выбрать / = ctg. Более того, в этом случае мы получим представление h — Can(h: І) в терминах F, обладающее интересными свойствами: h - Can{hml) = J gtft, дгєР\[0}, /,6F,rb,)r(/,) T(/)Vi
Определение 1. Мнооюество f С I \ {0} назовем базисом Грёбнера идеала I, если M{F} порождает идеал М(1). Определение 2. Пусть дан f G Р\ {0},F сР\ {0}. Тогда элемент h Р назовем нормальной формой f по отношению к F, если f — h = ТІЯгїг, 9і Є -P\{0}; ft Є. F, и либо h = 0 либо M(h) ф. M(F). Обозначим за NF(f, F) мнооюество {h Є Р : h нормальная форма f по отношению к F}
Отметим, что в отличие от канонической формы, которая единственна и зависит только от отношения порядка , нормальная форма не является однозначно определенной даже если F является базисом Грёбнера : если h - нормальная форма / по отношению к F и дг/г такова, что T(gt)T(ft) T(h), то h + Y 9%fi еЩе одна нормальная форма / по отношению к F. Некоторые слабые свойства единственности нормальной формы (в случае если F является базисом Грёбнера) доказываются в следующем предложении, где также показано, что нормальная форма может использоваться вместо канонической для разрешения проблемы вхождения.
Вероятностный алгоритм вычисления базисов Грёбнера
В процессе работы с программной реализацией изложенных выше алгоритмов были сделаны следующие наблюдения. Во-первых, очень велик рост коэффициентов при вычислении базисов Гребнера в кольце полиномов с целочисленными коэффициентами. Далее, свыше 90% времени тратится на редукции, не дающие вклада в базис; вычисления базисов Гребнера в кольце полиномов с коэффициентами из конечного поля проходит значительно эффективнее; "след" вычислений целочислленого и модулярного базисов практически идентичен для подавляющего большинства примеров.
В связи с изложенными фактами возникает идея: попробовать использовать модулярные вычисления для оценки результатов целочисленных редукций. На основании этого соображения изложенные выше алгоритмы могут быть модифицированы следующим образом. Пусть нам необходимо вычислить базис Гребнера для полиномиальной системы с целочисленными коэффициентами. Как показывает практика, большая часть вычислительного времени тратится на процесс редукции s-полиномов, не дающих вклада в базис (имеющих нулевую нормальную форму). Вместо обычной целочисленной редукции может быть осуществлен ее аналог в кольце полиномов с коэффициентами из конечного ноля, и на ее основании сделано заключение об избыточности данной s-пары. Далее, имея протокол редукций в кольце полиномов с коэффициентами из конечного ноля, шаг за шагом могут быть осуществлены соответствующие редукции в кольце полиномов с целочисленными коэффициентами. Естественно, результат работы данного алгоритма может отличаться от корректного базиса Гребнера, однако результат его работы будет базисом Гребнера для системы уравнений с целочисленными коэффициентами с достаточно высокой вероятностью. После завершения работы данной части алгоритма необходимо проверить, является ли результат базисом Гребнера идеала, порожденного исходной системой полиномов. В случае ошибки может быть осуществлен запуск медленного целочисленного алгоритма, или в качестве альтернативы снова запущен вероятностный алгоритм с другим конечным полем.
На практике оказывается, что для достаточно большого количества систем результатом работы вероятностного алгоритма будет являться корректный базис Гребнера для исходной системы полиномов. Надо также отметить, что проверка свойства "быть базисом Гребнера" является достаточно быстрой операцией по сравнению с его построением, а также у нее есть очень важное свойство: редукция s-полиномов может быть осуществлена фактически независимо друг от друга (процесс проверки состоит в редукции конечного множества полиномов по конечному множеству полиномов), что будет использовано далее при построении параллельных алгоритмов.
Процедура getModularPolynomial() осуществляет отображение полиномов с целочисленными коэффициентами в кольцо полиномов с коэффициентами из конечного поля Zp (в предположении, что простое число р выбрано и зафиксировано до начала работы алгоритма). В данной работе обычно использовалось число р, равное 31013 (аналогично выбранному для вычислений минимальных инволютивных базисов для систем полиномов с коэффициентами из конечного поля в работах Гердта).
Следует отметить, что названия процедур в изложенном далее алгоритме совпадают для различных областей коэффициентов - например, используется одно и то же обозначение sugarnormalfO как для процедур вычисления нормальных форм полиномов с целочисленными коэффициентами, так и для вычисления нормальных форм полиномов с коэффициентами из конечного поля относительно подходящих множеств полиномов соответственно. Важным является также то, что в данной версии алгоритма множество критических пар В содержит пары из множества полиномов с коэффициентами из конечного ПОЛЯ.
В случае, если предположение было несправедливо и нормальная форма s-нолинома с целочисленными коэффициентами оказалась нулевой, в то время как нормальная форма s-полинома с коэффициентами из конечного ноля была отлична от нуля, вычисления необходимо остановить и далее запустить детерминированный алгоритм вычисления базиса Гребнера (или повторить работу вероятностного алгоритма для другого р).
Процедура CheckQ осуществляет проверку свойства "быть базисом Гребнера" и возвращает значение true в случае его выполнения и false иначе.
С использованием данной версии алгоритма было проведено вычисление базисов Гребнера для достаточно больших систем уравнений. Время работы алгоритма как правило достаточно невелико (по сравнению с детерминированный алгоритмом) и сравнимо (или превосходит) с результатами практически всех широко известных реализаций алгоритмов вычисления базиса Гребнера.
В качестве примера можно привести систему cyclic для семи переменных, вычисления которых данной версией алгоритма занимает около 2380 секунд на процессоре Pentium-HI 900 Mhz, и фаза проверки корректности занимает всего 47 секунд. К сожалению, время, необходимое для проверки результата вычислений, не настолько хорошо по отношению ко времени работы первой части алгоритма для всех систем. Например, для примера katsura9 вычисления базиса Гребнера занимает 312, а его проверка 2078 секунд, но это скорее исключение из правила.
Алгоритм Conveyer
При моделировании параллельного алгоритма были приняты следующие допущения: мы располагаем неограниченным числом процессоров, (на практике необходимое их число не так уж велико, так что это требование сделано исключительно для простоты); пренебрегаем временами на пересылку сообщений; предполагаем, что все элементарные операции над полиномами, такие, как шаг редукции (не полная редукция!) и вычисление s-полинома выполняются за постоянное время.
Условимся называть полином /г независимым в случае если полином не был использован в процессе вычисления /г. Условимся называть полином /г почти независимым, если "почти весь" полином /г может быть вычислен без непосредственного вычисления fi-i. Поясним значение фразы "почти весь". Определим величину р для полинома /г следующим образом
где Si является списком индексов полиномов использованных в процессе редукции полинома /г в порядке возникновения, и первые два элемента списка St являются индексами образующих s-полинома, если полином /г является s-полиномом. Выберем величину 0.66 как граничное значение для р, и условимся называть полиномы с р 0.66 почти независимыми. Далее, обозначим как Nau полное число полиномов, вычисленных в процессе вычисления базиса Грёбнера; обозначим как Nmd число независимых полиномов и как Naimost число почти независимых полиномов. Пусть
Это - в точности число элементарных полиномиальных операций в процессе работы алгоритма. В параллельной версии алгоритма список St является стеком полиномов, которые необходимо вычислить для того, чтобы вычисление полинома ft стало возможным. Допуская, что каждый полином базиса будет вычисляться на выделенном процессоре (для этого потребуется Nau процессоров) можно найти число элементарных полиномиальных операций в процессе работы параллельного алгоритма. Данное число обозначим за Траг. Обозначим за Ртах максимальное количество процессоров, используемых одновременно в процессе работы алгоритма и за Taierage среднее количество используемых процессоров.
Приведенные ниже таблицы показывают, что в процессе вычисления базиса Гребнера эффективно может быть использовано только достаточно небольшое количество процессоров. Как правило, увеличение эффективности невозможно при использовании более чем 5 процессоров. Тем не менее, максимальное число процессоров, использованных в процессе вычисления, достаточно велико - до 194 в задаче iliasl2. Увеличение скорости работы алгоритма в среднем не очень велико, тем не менее значительно. С использованием данного подхода в некоторых задачах вычисления могут быть ускорены на порядок. Интересно сравнить приведенную ниже таблицу с результатами, полученными для алгоритма Conveyer. Результаты достаточно хорошо согласуются, откуда можно заключить, что данный алгоритм является очень эффективным и в то же время достаточно простым в реализации.
Данный подход может быть использован в процессе вычисления инво-лютивных базисов. След модулярных вычислений может быть использован в процессе вычисления над целыми числами, при условии проверки базиса после завершения вычислений. В качестве примера можно использовать интерпретацию алгоритма вычисления минимального инволютив-ного базиса, представленную в работе В.П. Гердта [9], и модифицировать ее с использованием изложенного метода.
Оценка качества распараллеливания для алгоритма с использованием графа редукций приведена в таблице 1, для алгоритма Pipeline - в таблице 2, и для алгоритма Conveyer - в таблице 3 соответственно.
В качестве иллюстрации, что алгоритм Бухбергера является "очень последовательным" (что является основным объяснением низкого качества распараллеливания в работе [19]) можно продемонстрировать граф зависимостей (см. рис. 3). Этот граф был получен при вычислении базиса с коэффициентами из конечного поля, и может быть использован далее в вычислениях в кольце полиномов с целочисленными коэффициентами. Чем больше в графе ребер относительно количества вершин, тем ниже потенциальное качество распараллеливания. Естественно, система представленная на графе, очень мала. Для реальных примеров число вершин и ребер в подобных графах очень велико.
Анализ производительности алгоритма
В 1952 г. А. Эйнштейн в работе [38] ввел понятие "жесткости" системы уравнений поля следующим образом "... систему уравнений поля следует выбирать так, чтобы полевые величины определялись системой как можно более жестким образом. Чтобы применять этот принцип, нам нужен метод, который позволял бы дать меру жесткости системы уравнений. Поступим следующим образом: разложим переменные поля вблизи точки Р в ряд Тейлора (предполагается аналитический характер поля). Коэффициенты разложения, которые представляют собой не что иное, как производные элементов ноля в точке Р, распадаются на группы соответственно порядку дифференцирования. В каждом порядке дифференцирования мы на первых норах получаем набор коэффициентов, которые можно было бы выбрать произвольно, если бы иоле не должно было удовлетворять системе уравнений. Благодаря наличию системы дифференциальных уравнений (и уравнений, получаемых из них путем дифференцирования по координатам) число независимых коэффициентов уменьшается, так что в каждой группе уже меньшее число коэффициентов может быть выбрано произвольно. Количество "свободных" коэффициентов в каждой группе непосредственно дает меру "слабости" системы уравнений и, таким образом, определяет и "жесткость" системы".
Соответствующие математические определения были сформулированы в рамках дифференциальной алгебры Э. Колчиным в 1964 г. [48]. Центральным понятием в построенной теории является понятие дифференциального размерностного многочлена - математический объект, соответствующий "жесткости" системы по Эйнштейну. В данной работе изучаются преобразования системы дифференциальных уравнений, приводящие к уменьшению дифференциального размерностного многочлена, что соответствует увеличению "жесткости" системы по Эйнштейну.
Пусть F - дифференциальное поле с множеством попарно коммутирующих дифференцирований A = {di,..., dm}, G = F {ipi ..., cpk) - его конечно порожденное А-расширение. По традиции, приставка А- будет означать дифференциальный, например, А-ноле — это дифференциальное поле и т.д. Тогда (см. [48, 40]) существует дифференциальный раз-мерностный полином (Колчина) ipu.,,ipk{s), т.е. такой целозначный мно гочлен, что для всех достаточно больших натуральных s выполняется условие: Ч 1, ,у кМ = trdegF{Q(s)ipu ..., 0(s)ipk)/F (здесь 0(s) - множество всех дифференциальных операторов dj1... d3 степени не выше 5, trdeg - степень трансцендентности расширения поля). Иными словами, мы присоединяем к исходному полю F все производные элементов pi,..., (fk степени 1,..., 5 и ищем мощность максимального алгебраически независимого над F множества элементов полученного поля. Для достаточно больших s эта зависимость будет полиномиальной, а точнее говоря, дифференциальный размерностный многочлен является полиномом Гильберта фильтрованного модуля дифференциалов расширения G над F. Этот многочлен содержит некоторые Д-инварианты поля G над F (в частности, степень и старший коэффициент), но сам многочлен может изменяться при выборе другой системы образующих G = F (трі,... ,фі). Если степень ш9и. , pk(s) меньше m, а поле F содержит C(xi,... ,хт) (поле рациональных функций от неизвестных х\,..., жгп), то (см. [48]) в G есть примитивный элемент (т.е. такой, что G = F ()). Более того, можно выбрать в виде комбинации = X 7=i \Фэ- \j Є F,j = 1,... ,к. При такой замене дифференциальный размерностный многочлен не увеличивается, т.е. oo (s) w pu.,., ?k(s) для всех достаточно больших s и поэтому проблема нахождения минимального дифференциального размерностного Л-многочлена связана с поиском примитивного элемента поля (хотя и не решает ее, см. [44, 45]). И задача вычисления многочлена w pi,...,(pk(s), и поиск "в принципе" решаются использованием алгоритма Розенфельда-Грёбнера, входящем в пакет diffag системы компьютерной алгебры Maple-V (см.[37]) или пакета для вычисления дифференциальных инволютивных базисов Invo, написанным в нашей лаборатории и находящегося в данный момент в стадии тестирования. Однако при реальных вычислениях прямое применение этих алгоритмов не всегда возможно из-за внутренних ограничений системы, влекущих прерывание работы после сообщения "Object too large". Для устранения этой ошибки изготовители системы предложили проводить вычисления на 64-битной платформе. С другой стороны, иногда возможно применение теоретических методов, которые мы продемонстрируем на примере уравнений Дирака.
В работе был проведен глубокий анализ всех наиболее эффективных из известных на данный момент алгоритмов вычисления базисов Грёбнера. Реализованы алгоритмы построения инволютивных базисов и базисов Грёбнерадля систем нелинейных алгебраических уравнений с целочисленными коэффициентами и коэффициентами из конечного поля. Предложены параллельные интерпретации наиболее эффективных последовательных алгоритмов и для них проведена оценка качества распараллеливания. Реализована система построения инволютивных базисов и базисов Грёбнера в дифференциальном модуле и продемонстрировано ее применение к задаче вычисления примитивного элемента в системе уравнений Дирака.
На основании полученных результатов можно заключить, что распараллеливание алгоритмов построения базисов Грёбнера и инволютивных базисов не позволяет линейно наращивать эффективность с ростом количества используемых процессоров, и максимальное число эффективно используемых процессоров индивидуально для каждой полиномиальной системы. В то же время метод позволяет существенно (до 10 раз и более в проведенных экспериментах) увеличить на практике производительность алгоритмов вычисления базисов Грёбнера
