ПРОГРАММИРОВАНИЕ, 2008, № 2, с. 32-40
— КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ БАЗИСОВ ГРЕБНЕРА
И ИНВОЛЮТИВНЫХ БАЗИСОВ*
© 2008 г. Д. А. Янович
Объединенный институт ядерных исследований Лаборатория информационных технологий 141980 г. Дубна Московской обл. E-mail: yan@jinr.ru Поступила в редакцию 07.05.2007 г.
Несколько лет назад мы представили программный комплекс для параллельного вычисления базисов Гребнера и инволютивных базисов, работающий на машинах с общей памятью. К сожалению, число процессоров, которые мы можем использовать, невелико (от 2 до 16) из-за ограничений оборудования.
В этой работе будет представлена программа для распределенного вычисления базисов, использующая те же принципы, что и вышеупомянутая, но работающая в сети разнородных машин. Будет оценена эффективность такого подхода с точки зрения использования процессорной мощности и требуемой полосы пропускания сети, а также указаны методы оптимизации использования этих ресурсов.
1. ВВЕДЕНИЕ
В течение последних лет был предпринят ряд попыток [1-4] построения эффективной параллельной версии алгоритма Бухбергера [5] для вычисления базисов Гребнера. Некоторые из этих вариантов алгоритма страдают от "случайного" поведения времени счета от запуска к запуску [3], некоторые позволяют проводить вычисления лишь с модулярными коэффициентами полиномов [4] (что не позволяет проводить расчеты для большинства реально возникающих задач).
Алгоритмы [1, 2] являются "эмуляциями" работы последовательного алгоритма вычисления базисов Гребнера, выполняемыми на нескольких процессорах. Данный подход требует проведения дополнительных расчетов, контроля выбора критических пар и т.д. Также надо заме-
* Исследования, представленные в работе, проведены при поддержке гранта 07-01-00660 РФФИ и гранта 5362.2006.2 Министерства образования и науки РФ.
тить, что подход к параллелизации, описанный в [2], "насыщается" (коэффициент ускорения не растет) уже при использовании более четырех процессоров.
В работах [6, 7] был предложен алгоритм косвенного вычисления базиса Гребнера посредством выделения его из инволютивного базиса. Таким образом, проблема параллелизации вычислений базиса Гребнера может быть сведена к проблеме параллелизации вычисления инволютивного базиса, которая имеет меньшую сложность хотя бы за счет отсутствия необходимости строго следовать стратегии выбора критических пар для редукций.
Алгоритмически, последовательное построение алгебраического инволютивного базиса или базиса Гребнера состоит из трех циклически повторяемых этапов:
• выбор критической пары/немультипликативного продолжения;
• проверка критериев нулевой редукции;
• вычисление нормальной формы по лидирующему моному (или полной нормальной формы).
Для достаточно больших задач последний этап занимает около 95% времени вычисления в случае базиса Гребнера и около 80% в случае ин-волютивного базиса.
Ранее в [8-10] мы представляли параллельную версию алгоритма вычисления базисов Гребнера и инволютивных базисов для SMP-архитектуры [11], в числе достоинств которой были устойчивость времен вычисления базисов, хорошая масштабируемость и скорость получения базисов. Дополнительным достоинством алгоритма является то, что он не требует никаких вычислений для сохранения стратегии редукций (параллельная версия программы обрабатывает полиномы в той же последовательности, что и последовательная, с точностью до лидирующего монома).
С тех пор ситуация с одновременно доступным числом процессорных ядер улучшилась (доступны машины с 16 ядрами), но для эффективного решения крупных задач необходимы сотни, а не десятки ядер. Кроме числа процессоров, при реализации любого варианта алгоритма Бухбергера или инволютивного алгоритма неизбежно сталкиваешься с проблемой ограниченности машинной памяти (до сих пор даже в самых мощных SMP-системах допустимо устанавливать не более 32Гб RAM).
Существует известная методика, позволяющая сильно увеличить доступность этих ресурсов: распределенные вычисления. К сожалению, доступность и цена кластеров, на которые ориентированы другие реализации распределенных вычислений базисов Гребнера, оставляют желать лучшего, и поэтому целью данной работы было создание первого (насколько известно автору) клиент-серверного приложения распределенного вычисления инволютивных базисов Жане и базисов Гребнера, клиентская часть которого могла бы работать в режиме "скринсейвера", потребляя свободные ресурсы компьютеров во время простоя (список подобных проектов можно увидеть, например, в [12]). В этой работе представлены параллельный алгоритм, временной анализ реализации этого ал-
горитма (пока реализация существует только для платформы Гших, ведутся работы по пор-тированию на Windows), текущие программные проблемы и методы их устранения.
2. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ
Мы будем использовать следующие обозначения:
X = {ж1,...,жга} - множество полиномиальных переменных.
Е = Q[X] - кольцо многочленов с рациональными коэффициентами.
Id(F) - идеал кольца IR, порожденный многочленами F С Ш.
М - множество мономов, т.е. произведение степеней переменных из X с целыми неотрицательными показателями.
deg^-w) - степень переменной жг- в мономе и £
£ М.
п
deg(и) = ^deg¿(и) - полная степень моно-¿=1
ма и.
>— допустимый порядок на мономах, такой, ЧТО Х\ У Х2 У ■ ■ ■ У хп.
и | V - обычное отношение делимости монома V мономом и. Если и | и и deg (и) < deg (и), т.е. если и является собственным делителем v, мы будем записывать это условие как v □ и.
Im (/) и lt(/) - старший моном и старший одночлен многочлена / £ R. \ {0} соответственно.
lm(F) - набор старших мономов полиномиального множества F С R \ {0}.
Для каждого 1 < i < п разобьем конечное множество многочленов F £ IR\0 на группы, индексированные неотрицательными целыми числами di,..., df.
[di, ...,di] =
= {/ eF\dj = degj(lm(/)), 1 <j<i}.
Переменная x\ является .J-мультипликативной (мультипликативной по Жане) [13] для многочлена / £ F, если deg1(lm(/)) = = max{deg1(lm(^)) | g £ F}. Для i > 1 жг- является J-мультипликативной для / £ [di,..., di-1], если
deg,-(lm(/)) =
= maxjdegj- (lm (g)) | g £ [dXl...,
void divisor_server(List T, Connection dConnect) {
while(l)
{
Listen (dConnect);
Monom m = Receive(dConnect);
Polynom divisor = FindDivisor(m, T);
Send(divisor, dConnect);
}
}
Listing 1. Сервер делителей.
В дальнейшем мы будем обозначать через МЛ/, С) С X и = X\MJ(/,G')
множество /-мультипликативных и /-немультипликативных переменных для / € С соответственно.
Данное разделение переменных на немультипликативные и мультипликативные переменные порождает инволютивное деление мономов [6, 14]. Это деление - деление Жане - определяется по заданному конечному набору многочленов Р и порядку на мономах >- следующим образом: если мономы и 6 V и т связа-
ны соотношением т = и ■ V и при этом моном V содержит только мультипликативные (по Жане) переменные для и, то и является делителем Жане или 3-делителем монома т. В этом случае мы будем записывать отношение инво-лютивной делимости по Жане как и \ J т.
Конечное множество Р ненулевых многочленов является 3-авторедуцированным (или авторедуцированным по Жане), если каждый моном, входящий в / 6 Р, не имеет /-делителей среди \ {1ш(/)}. 3-нормальная форма
NFJ{p, Р) многочлена р Р по отношению к /-авторедуцированному множеству Р определяется как
NFJ{p, F) = р = р - а13т13д3, п
где аг] е К, д3 £ Р, тг] £ Ь(1т(д^, 1т^)), lm(mijgj) ^ 1т(р) и р не содержит мономов, имеющих делителя Жане среди
Вычитание из многочлена р указанных в выражении для NFJ{p, Р) слагаемых под знаком суммы называется мультипликативным приведением (редукцией) р многочленами из Р. Когда 1т(/) (/ ^ Р) не имеет /-делителей сре-
ди элементов многочлен / находится в
головной .1-нормальной форме по отношению к Р. Этот факт мы будем записывать как / =
= яд^л/,
Для заданного идеала I С К и порядка на мономах >- конечное, /-авторедуцированное множество ненулевых многочленов О С К, порождающее I, является его базисом Жане, если выполнено следующее [6]:
( V/ е с ) ( е NMJ(f, с)) [ лт^*,- • /, с) = о ]
Произведение жг- • / многочлена / £ ^ и ^ £ £NMJ(f,F) называется немультипликативным продолжением /. Тем самым, для базиса Жане любое его немультипликативное продолжение приводится (редуцируется) мультипликативно к нулю.
Базис Жане является базисом Гребнера, хотя и не обязательно авторедуцированным в смысле гребнеровских редукций [6]. Подобно редуцированному базису Гребнера, минимальный базис Жане с нормированными на единицу старшими коэффициентами определяется единственным образом по идеалу и порядку на мономах [15].
3. АЛГОРИТМ
Используемые в параллельном алгоритме данные можно разделить на два независимых набора: частичный базис (используемый для поиска инволютивных делителей) и множество немультипликативных продолжений, которые необходимо рассмотреть в ходе алгоритма.
Все сетевые копии частичного базиса в ходе вычислении должны быть идентичны, поэтому
void DistributedJanetBasisServer(List Т, Ordering Р) {
List Q = Т;
Т = 0;
Start (divisor_server, Т); Sort(Q, Р);
while( Q ф 0)
{
/* редукция по лидирующему моному минимальных элементов в Q */ List D = { qi G Q | lm(pol(g¿)) - минимальны } List R = 0
/* выбран набор для редукций - надо распределить его по НФ серверам */
while ( D ф 0)
{
Polynom f = D[0]; D = D \ f;
Connection nfl = WaitForNFLServerReadyQ;
P = P U nfl_stub(f, nfl);
}
/* получили новый элемент базиса */ Polynom f = { / G P I lm(pol(/)) - минимален }
P = P \ f;
T = T U f;
/* остальные проредуцированные элементы помещаем обратно в Q */ Q = Q U Р;
Q = Q U { немультипликативные продолжения f }; /* редуцируем базис по новому элементу */ PNF(T);
}
}
Listing 2. Алгоритм работы сервера базиса.
Polynom divisor_stub(Monom m, Connection dConnect) {
// пересылаем по сети моном Send(m, dConnect); // получаем результат Polynom divisor = Receive(dConnect); return divisor;
}
Listing 3. "Стаб" (заглушка) для вызова функции по сети.
в реализации, опи
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.