Бесплатно скачать, заказать диплом, курсовую, диссертацию Алгоритмы вычисления Базисов ГрёБнера и инволютивнык Базисов

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Алгоритмы вычисления Базисов ГрёБнера и инволютивнык Базисов

Количество страниц	86

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23542.doc

Содержание	Содержание 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 Заключение 86 Введение 1 Вступление 1.1 Актуальность темы В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения. Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего времени это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Гребнера, на практике для реальных систем его производительность существенно выше. В последнее время вызывает сильный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребнера. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор воз- можных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу. Дальнейшим путем к увеличению эффективности алгоритмов является попытка обогнать прогресс в развитии вычислительной техники путем использования большого количества процессоров одновременно - распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе. Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений. В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с 4 неизвестными имеет вид /i = а 4- Ь 4- с + d /2 = ab-\- ad + bc + cd /з = абс 4- abd 4- асе/ 4- bed /4 = абес/ — 1 Базис Гребнера для этой системы имеет вид дх = с2с/6 - с2с/2 - с/4 4-1 о2 = с3с/2 4- c2d3 -с- d Для системы уравнений cyclic от пяти неизвестных базис Гребнера состоит из 11 уравнений ?1 = е15 4- 122е10 - 122е5 - 1 д2- = 55d2e5 - 55d2 - 2de11 - 23Ые6 4- 233ae - 8е12 - 979е7 4- 987е2 д3 = Ы14- 57d6e6 - 39d6e + 25d5e7 - 19d5e2 - 5d4e8 + 5d4e3 - 8d3e9 + 4- 8d3e4 - 2d2e10 + Ш2е5 - 18c/2 - 18cie6 - бе7 04 = 360150ce5- 360150c 4- 71540dV - 110722ci8e3 - 1744327dV- - 3078595d6e5 + 233730c/6 4- 219158d5e6 - 1058999d5e + 2366210ci4e7 - - 2437750d4e2 4- 1281458d3e8 - 1170736ci3e3 4- 200573c/2e9 4- 1543754d2e4 4- 2844865cie5 4-839841e6 gb = 360150cci - 360150ce6 - 71540Л2 4- 110722ci9e3 4- 1744327d8e4 + 4- 3064189ci7e5 - 233730c/7 + 313864ci6e6 4- 1058999c/6e - 795956ci5e7 4- 4- 243775Od5e2 - 1403909d4e8 + 1293187ci4e3 - 1360256d3e9 - 744221ci3e4 - 41057Ы2е10 - 2059738cZ2e5 - 1372863c/e6 - 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 12-th 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 • Митюнин В.А., Панкратьев Е.В "Параллельные алгоритмы построения базисов Гребнера", Международная алгебраическая конференция, посвященная 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, а степени, соответствующие переменной под номером i как o;t, Д, 71-Основными операциями над мономами в процессе вычисления базисов Грёбнера являются: • Вычисление степени deg(a) := Y^=i аг (возможно, взвешенной степени по отношению к весовому вектору w. deg(o;) := • Проверка делимости а \ (3 <& Vi ? {1... тг} : аг < /Зг. • Сложение двух мономов 7 '== ol + /3, Vi ? {1... п} : 7г = си.г + /Зг. • Сравнение двух мономов в соответствии с данным отношением порядка. Допустимым отношение порядка на множестве мономов Мп будем называть полное отношение порядка на Мп, совместное с полугрупповой операцией, т.е. си > (3 => j + а > 7 + P,Vj а > /3 О Ла >iex Ар для некоторой матрицы A G GL{n) R). Представление отношения порядка с помощью матриц является очень общим методов, однако редко используется на практике в силу достаточно низкой вычислительной эффективности. Вместо этого как правило используется описание отношения порядка на мономах с помощью двух определяющих условий: степени (возможно, взвешенной) и лексикографического сравнения (нормального или обратного). Условимся называть отношения порядка, которые могут быть описаны подобным образом, простыми отношениями порядка. Для мономов а, /3 ? Мп определим следующие функции: 1, если Зг: «1 = /?i,..., аг-\ = /?г_ь аг > (Зг Lex(a,fl) — ^ 0, если а. — (3 —1, иначе 1, если Зг : ап = (Зп,..., аг-г = Д-i, аг < (Зг О, если а = (3 —1, иначе если deg(a) > deg(/3) Deg(a, (3) = { 0, если deg(a) = deg(/5) — 1, иначе Тогда наиболее важные с практической точки зрения отношения порядка можно определить следующим образом: • лексикографическое Lex{a,(3) — 1; • (взвешенное) по полной степени, затем обратное лексикографическое Deg(a,(3) = 1, или Deg{a,(3) = 0и RevLex(a,(3) = 1; • (взвешенное) по полной степени, затем лексикографическое Deg(a, f3) 1, или Deg(a,(3) — О и Lex(a,/3) = 1. В силу особенностей алгоритма построения базиса Грёбнера элементарные операции над мономами являются наиболее частыми примитивными операциями. Например, сравнения мономов осуществляются более часто, а сложения по крайней мере не реже чем арифметические операции в области коэффициентов. Количество проверок делимости достаточно сильно зависит от конкретной системы уравнений, но, как правило, достаточно велико. Тем не менее, суммарный вклад элементарных операций над мономами в полное время работы алгоритма существенно зависит от области коэффициентов. Для вычислений стандартных базисов над конечными полями их доля достаточно велика, в то время как для систем с целочисленными коэффициентами этими временами, как правило, можно пренебречь. Для увеличения эффективности элементарных операций над мономами можно воспользоваться их векторизацией. Предполагая, что размер машинного слова является кратным размера степени, операции будут производится над машинными словами, а не непосредственно со степенями по отдельным переменным. Таким образом вектор степеней будет обработан одной машинной инструкцией, уменьшая тем самым длину внутренних циклов. Лемма 1. Пусть se,m G N и а = («о,... am_i),/3 = (Д>, .../?m_i) € Мт, причем аг,Рг < 28е~1. Далее, пусть sw = sem и а, Ь, а, 6,7,... 7т-ь и выполнено а ='ао Ъ = /50 а = am_i + am_22Se + . • • + aO2(m-1)Se b = (Зт-i + A»-22S* + ... + A)2(m-1)s* b + a( mod 2s-) = 7o+ 7i2Se 4-...+7m-i2^-1)Se b-a( mod 2s-) = 50 + 5i2Se + .. • + ^m-i2(m~1)Se Тогда справедливо следующее: Ъ-а( mod 2s-) < 2s-"1 4Ф Lex(a,(3) = 1 (1) b-a{ mod 2s-) < 2s-"1 & RevLex(a,(3) = -1 (2) (7o,...,7m-i) = <* + /? (3) VO < i < m : St < 2Se-1 a \| P (4) Лемма 1 показывает, что операции над мономами в правых частях могут быть векторизованы таким образом, что на машине с размером слова sw проверки левых частей могут быть осуществлены самое большое с использованием трех машинных инструкций. Тем не менее при переходе к непосредственной реализации остается ряд технических сложностей. Во-первых, необходимо удостовериться в строгих ограничениях на степень полиномов. Во вторых, условие sw — sem предполагает, что полная длина вектора степеней является кратным размера машинного слова, что может потребовать хранение (—n)( mod m) избыточных степеней, значение которых всегда будет равно нулю. В третьих, в зависимости от архитектуры компьютера и выбранного отношения порядка порядок следования степеней в векторе может быть инвертирован. Сложение мономов может быть реализовано как неявный инициализатор, в силу того что это наиболее ожидаемый источник появления новых мономов. Альтернативным способом представления мономов является представление, основанное на ранге. Первоначально оно было разработано и использовано в системе компьютерной алгебры Macaulay. Основная идея данного представления основывается на следующем свойстве отношения порядка совместном со степенью: Vra G Мп : tJ{W eMn:l Таким образом, существует возможность биективного отображения мономов на целые числа, которые мы будем называть рангами мономов. Точный вид изоморфизма зависит от выбранного отношения порядка. Для упорядочивания по полной степени, затем обратного лексикографического он задается следующей леммой. Лемма 2. Пусть а € Мп и r^v : Мп —> N задано формулой (6) 12 Тогда справедливо следующее утверждение: , (3 ? Мп : rdp(a) > rdp(/3) a >dp (3 Va, PeMn: rdp(a) = rdp((3) а = Подобные биективные отображения могут быть построены и для других отношений порядка. Благодаря использованию представления, основанного на ранге, сравнения мономов могут быть реализованы как сравнения их рангов. Кроме того, представление полиномов с использованием рангов является достаточно компактным, требуя минимальных затрат памяти. Тем не менее, это представление имеет ряд недостатков. • сложение и проверка делимости не могут быть реализованы эффективно, поскольку биекция не является аддитивной и не сохраняет делимости; • реализация данного метода для произвольных степеней требует использования арифметики произвольной точности, что в свою очередь повлечет значительные накладные расходы; ограничиваясь 32 битами машинного слова возникают следующие ограничения на степени полиномов, возникающих в процессе вычислений количество переменных 3 4 5 7 10 15 20 25 максимальная степень 2340 471 186 66 31 17 12 9 • отношения порядка, несовместные с полной степенью, например Lex не допускают построение подобных биекций. Эти проблемы накладывают достаточно серьезные ограничения на системы уравнений и используемые отношения порядка, в силу чего метод, основанный на векторизации элементарных операций над мономами, является более предпочтительным, что подтверждено экспериментально. Идеи из работы [51] были использованы в данной реализации и позволили добиться существенного улучшения производительности при вычислении в кольцах полиномов с коэффициентами из конечного поля. Вторым упомянутым методом увеличения эффективности алгоритмов построения стандартных базисов является улучшение применяемых стратегий для выбора и отбрасывания s-элементов. В качестве одной из наиболее интересных работ в данном направлении следует упомянуть работу [18], основные идеи которой состоят в следующем. Определим фиктивную гомогенизацию полиномов посредством введения фиктивной степени Sf полиномов следующим образом. • Для полиномов /г исходной системы Sft = deg(ft) (не степень старшего монома, а полная степень полинома). • Пусть дан полином / и терм t, тогда положим Stf = deg(t) + Sf. • В случае если / = д-\- h, Sf = m&x(Sg, 5д). Таким образом, с каждым полиномом может быть ассоциирован однородный полином степени, равной соответствующей фиктивной степени, при условии гомогенизирования с помощью дополнительной переменной. Стратегия выбора критических пар при использовании фиктивной однородной степени заключается в следующем. Первоначальный отбор происходит путем сравнения фиктивных степеней, а в случае их равенства для нескольких полиномов используется нормальная стратегия выбора на основании лидирующих термов. Возможно также использование модифицированных версий данной стратегии. Например, в процессе редукции имеется определенная свобода выбора элемента, по которому осуществляется редукция. Некоторые аспекты не вызывают сомнения: в случае если старший терм полинома может быть редуцирован, необходимо произвести его редукцию, так как любые другие действия, очевидно, приведут только к потере времени. Как правило, также более выгодно использовать для редукции полином, который был добавлен к промежуточному базису раньше других. Предлагаемая стратегия заключается в следующем: помимо перечисленных критериев, анализируется фиктивная однородная степень полинома, и редукция осуществляется только в том случае, если она не приводит к повышению фиктивной однородной степени. Впервые стратегия вычисления фиктивной однородной степени полиномов была реализована в системе компьютерной алгебры СоСоА, и зарекомендовала себя как достаточно эффективная. Первоначальная система критериев, используемых в алгоритме построения минимального инволютивного базиса, была построена профессором Гердтом как обобщение критериев Бухбергера на инволютивный случай. В последнее время были получены интересные результаты, касающиеся улучшения критериев, применяемых в процессе вычисления минимального инволютивного базиса, см. [1]. На данный момент существует гипотеза, что все критерии, применяемые при построении минимального инволютивного базиса, можно обобщить с использованием базиса сизигий, аналогично идеям из работы [28], но это факт еще не доказан. Критерии, которые используются большинством эффективных реализаций алгоритма Бухбергера на данный момент, основаны на идеях из работы [17]. Рассмотрим третий метод увеличения эффективности алгоритма вычисления базисов Грёбнера - распараллеливание. Основная трудность, с которой приходится столкнуться в процессе распараллеливания алгоритма построения стандартных базисов, это тот факт, что на ход работы очень сильно влияет выбор стратегии, что существенно затрудняет перенесение найденных в процессе исследования последовательного алгоритма эвристик на параллельную версию. Надо отметить также, что алгоритм Бухбергера и практически все его известные интерпретации являются существенно последовательными (точное определение этого термина и демонстрация этого факта будут приведены далее в работе). Важность сохранения стратегии, выбранной в процессе работы с последовательным алгоритмом, подчеркнута в работе [20]. Очень интересные работы, посвященные распараллеливанию алгоритма построения базисов Грёбнера, принадлежат Ж.К.Фожеру (J.C.Faiigere). В последнее время он работает над серией алгоритмов F, допускающих эффективное распараллеливание. Существует теория, что алгоритм F не может быть смоделирован последовательным алгоритмом построения базисов Грёбнера ни для какого выбора стратегии вычислений. К сожалению, работы в этом направлении не являются доступными. На идеях этого алгоритма хотелось бы остановиться немного подробнее. Введем некоторые обозначения, необходимые в дальнейшем. Условимся обозначать кольцо полиномов с целочисленными коэффициентами от переменных х\,...хп как R, а как Т - множество всех термов в этих переменных. Пусть / - полином. Тогда обозначим за HT(f),HM(f) и HC(f) его старший терм, моном и коэффициент соответственно. Определение 1. Пусть М матрица размерности s x т, и Тд/ = [ti,...tm] - упорядоченное множество термов. Пусть (et)I=(iv..m) ка- ионический базис пространства Rm. Рассмотрим, линейное отображе- ние (ртц —¦ Rm, где Vtm - подмодуль R, порожденный Тм, такое, что ФТмО'г) ~ ег- Обратную функцию обозначим за фтм- Применение тртм позволяет трактовать векторы из Rn как полиномы. Обозначим как (Л/,Тд/) матрицу, интерпретируемую таким образом. Определение 2. Пусть (М,Тм) матрица размерности Sxm, тогда построим множество полипомов следующим образом: Rows(M,TM) := {фТм(гот{М,1)) \ i = 1,... ,} \ {0} где row(M,i) является г-тым рядом матрицы М (элементом Rm). В свою очередь, если I - список полиномов uTi - упорядоченное множество термов, можно построить матрицу А размерности sxm (где s = size(l),m = size(Tf)), такую, что: Alt3 — Обозначим через A^l'Tl^ матрицу (AtiJ). Определение 3. Пусть М матрица размерности sxm uY_= [У1}..., Yr новые переменные. Тогда F = Rows(M,Y_) является новой системой уравнений. Таким образом можно перейти к вычислению редуцирован- ного базиса Грёбнера F системы F в лексикографическом отношении порядка таком, что Y\ > ... > Ym. Используя построенный базис, можно построить матрицу М = AF'—. Условимся называть М ступенчатой по строкам формой матрицы М, а базис F - ступенчатым по строкам базисом системы F. Определение 4. Пусть F - конечное подмножество R и < - допустимое отношение порядка. Обозначим kukT^F) систему Sort({T(f)\feF},<) А .= J[{F,T<(F)) и как А - ступенчатую по строкам форму А. Будем тогда говорить, что F = m является ступенчатой по строкам формой F по отношению к <. Теорема 1. Пусть М матрица размерности s x т, и Y_ = [Fi,..., Ym] новый набор переменных, F — Rows(M:Y_), M ступенчатая по стро-^ кам форма М, F = Rows(M,Y). Обозначим как: F\ HT(g) f HT(F)} F~ = F\F+ 16 Для любого подмножества F_ множества F такого, что size(F-) = size(HT(F)) и HT{FJ) = HT{F), множество G = F+ U F~ является треугольным базисом R-модуля Vm, порожденного системой F. Иначе говоря, для всех / € Vm найдутся мноо/сество (\k)k элементов R и множество (gk)k элементов G такие, что / = Ylk ^k9k, HT{g{) = HT{f) uHT(gk)>HT(gk+1). Следствие 1. Пусть F - конечное подмножество Е, < - допустимое отношение порядка и F - ступенчатая по строкам форма F относительно <. Положим {geF\ HT(g) i HT(F)} Для всех подмножеств F_ множества F таких, что size(FJ) = size{HT(FJ) = HT{F), пусть G — F+ U F_ - треугольный базис R-модуля Vm, порожденного F. Тогда для всех f ? Vm найдутся множество {\k)k элементов R и множество {gk)k элементов G такие, что f = Y2k^k9k,HT(gi) = HT(f) uHT(gk)>HT(gk+1). Хорошо известно, что в процессе работы последовательного алгоритма Бухбергера имеется свобода выбора таких элементов, как: • критическая пара для редуцирования; • элемент, по которому будет производиться редукция. Доказано, что этот выбор не влияет на корректность алгоритма, в то же время от него существенно зависит время вычислений. Более того, в большинстве современных интерпретаций при выборе анализируется только старший терм полиномов. Очевидно, что при таком подходе в случае наличия набора полиномов с одинаковым старшим термом задача выбора не может быть эффективно решена. Простая и в то же время интересная идея алгоритма F состроит в том, что этот выбор не производится вообще. Более точно, вместо выбора одной критической пары на шаге алгоритма, выбирается подмножество множества критических пар. Таким образом, необходимость выбора откладывается на этом этапе алгоритма до следующей его части, которая основана на методах линейной алгебры.

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23542.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.