Алгоритмы вычисления базисов Грёбнера и инволютивных базисов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Митюнин, Владимир Александрович

• Митюнин, Владимир Александрович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Митюнин, Владимир Александрович

1 Вступление

1.1 Актуальность темы.

1.2 Практическая ценность.

1.3 Апробация работы.

1.4 Публикации.

1.5 Обзор.

1.6 Структура и объем диссертации.

2 Последовательные алгоритмы вычисления базисов Грё-бнера

2.1 Классический алгоритм Бухбергера.

2.2 Вероятностный алгоритм вычисления базисов Гребнера

2.3 Версия, использованная при распараллеливании.

3 Параллельные алгоритмы вычисления базисов Грёбнера

3.1 Обзор параллельных алгоритмов.

3.2 Алгоритм Pipeline.

3.3 Алгоритм Conveyer.

3.4 Алгоритм с использованием графа редукций.

4 Оценка качества распараллеливания алгоритмов вычисления базисов Грёбнера

4.1 Оценка качества распараллеливания путем моделирования работы параллельного алгоритма.

5 Вычисление инволютивных базисов в дифференциальном модуле

5.1 Реализация алгоритма.

5.2 Анализ производительности алгоритма.

6 Пример применения системы для вычислений в дифференциальном модуле

6.1 Вычисление размерностного многочлена при заменах образующих в системе уравнений Дирака.

Введение диссертации (часть автореферата) на тему «Алгоритмы вычисления базисов Грёбнера и инволютивных базисов»

1.1 Актуальность темы

В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.

Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего вре*ме-ни это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Грёбнера, на практике для реальных систем его производительность существенно выше.

В последнее время вызывает сильный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребнера. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор воз

Ч' можных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу.

Дальнейшим путем к увеличению эффективности алгоритмов является попытка обогнать прогресс в развитии вычислительной техники путем использования большого количества процессоров одновременно - распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе.

Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.

В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с 4 неизвестными имеет вид fi = a + b + с + d /2 = аЪ + ad + be + cd /3 = abc + abd + aed 4- bed /4 = abed — 1 Базис Гребнера для этой системы имеет вид

91 = c2dQ - c2d2 - d" + 1

92 = c3d2 + c2d3 — c — d gz = bé-h + db-d gA = be - bd5 + c2dA + cd - d6 - d2 g5 = b2 + 2bd + d2 g6 = a + 6 + c + d

Для системы уравнений cyclic от пяти неизвестных базис Гребнера состоит из 11 уравнений дг = е15 + 122е10 — 122е5 — 1 д2- = ЪЫ2еъ - 55d2 - 2de11 - 23lde6 + 2Ше - 8е12 - 979е7 + 987е2 дг = 6d7 + 57dQeQ - 39d6e + 25d5e7 - 19d5e2 - 5d4e8 + 5d4e3 - 8d3e9 +

8f/3e4 - 2d2e10 + Ш2е5 - 18c/2 - 18de6 - 6e7 = 360150ce5 - 360150c + 71540d9e2 - 110722d8e3 - 1744327dV

- 3078595d6e5 + 233730d6 + 219158d5e6 - 1058999d5e + 23662Ш4е7

- 2437750d4e2 + 1281458d3e8 - 1170736d3e3 + 200573d2e9 + 1543754d2e4 + + 2844865de5 + 839841e6 gb = 360150cd — 360150ce6 — 71540d10e2 + 110722d9e3 + 1744327c?8 e4 +

3064189d7e5 - 233730d7 + 313864d6e6 + 1058999d6e - 795956dse7 +

2437750d5e2 - 1403909d4e8 + 1293187d4e3 - 1360256d3e9 - 744221d3e4

- 410571d2e10 - 2059738d2e5 - 1372863de6 - 1570254e7 и т.д. Для системы уравнений cyclic от шести неизвестных базис Гребнера состоит из 17 уравнений, длина коэффициентов которых превышает 100 десятичных цифр m

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Митюнин, Владимир Александрович

7 Заключение

В работе был проведен глубокий анализ всех наиболее эффективных из известных на данный момент алгоритмов вычисления базисов Грёбнера. Реализованы алгоритмы построения инволютивных базисов и базисов Грёбнерадля систем нелинейных алгебраических уравнений с целочисленными коэффициентами и коэффициентами из конечного поля. Предложены параллельные интерпретации наиболее эффективных последовательных алгоритмов и для них проведена оценка качества распараллеливания. Реализована система построения инволютивных базисов и базисов Грёбнера в дифференциальном модуле и продемонстрировано ее применение к задаче вычисления примитивного элемента в системе уравнений Дирака.

На основании полученных результатов можно заключить, что распараллеливание алгоритмов построения базисов Грёбнера и инволютивных базисов не позволяет линейно наращивать эффективность с ростом количества используемых процессоров, и максимальное число эффективно используемых процессоров индивидуально для каждой полиномиальной системы. В то же время метод позволяет существенно (до 10 раз и более в проведенных экспериментах) увеличить на практике производительность алгоритмов вычисления базисов Грёбнера. Достаточно интересным направлением для изучения является также серия алгоритмов

Список литературы диссертационного исследования кандидат физико-математических наук Митюнин, Владимир Александрович, 2004 год

1. Gerdt V.P. Completion of Linear Differential System to Involution // Computer Algebra in Scientific Computing, V.G.Ganzha, E.W.Mayr and E.V. Vorozhtsov (Eds.), Springer-Verlag, Berlin, 1999, pp. 115-137.

2. Gerdt V.P. On the Relation Between Pommaret and Janet Bases // Computer Algebra in Scientific Computing / CASC 2000, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2000, pp.164-171.

3. Gerdt V.P. Invoiutive Division Technique: Some Generalizations and Optimizations // Journal of Mathematical Sciences 108(6), 2002, 10341051. URL: http://arXiv.org/abs/math.SC/9912030.

4. Gerdt V.P. Groebner bases and invoiutive methods for algebraic and differential equations // Mathematics and Computers in Modelling, 25, No. 8/9, 1997, 75-90.

5. Gerdt V.P., Blinkov Yu. A. Minimal Invoiutive Bases // Mathematics and Computers in Simulation, 1998, 45.

6. Gerdt V.P., Blinkov Yu.A., Yanovich D.A., Computation of Janet Bases. I.Monomial Bases. // Computer Algebra in Scientific Computing / CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp. 233-247.

7. Gerdt V.P., Blinkov Yu.A. Yanovich D.A., Computation of Janet Bases. ILPolynomial Bases. // Computer Algebra in Scientific Computing /

8. CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp. 249-263.

9. Gerdt V.P., Blinkov Yu.A. Involutive Polynomial Bases // Publication IT-271, Laboratoire d'Informatique Fondamentale de Lille, Lille, 1995

10. Gerdt V.P., Blinkov Yu.A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation 45, 1998, 519-542.

11. Gerdt V.P., Blinkov Yu.A. Minimal Involutive Bases // Mathematics and Computers in Simulation 45, 1998, 543-560

12. Yanovich D.A. On Parallelization of Involutive Janet Bases Construction Algorithm // Programming and Computer Software, 2001

13. Yanovich D.A. Parallelization of an Algorithm for Computation of Involutive Janet Bases //Programming and Computer Software vol.28, No. 2, 2002

14. Siegl K. A Parallel Factorization Tree Gröbner Basis Algorithm // Proceedings of PASCO 1994, World Scientific Publ. Comp.

15. Reeves A.A. A Parallel Implementation of Buchberger's Algorithm over Zp for p < 31991 // J.Symbolic Computation, 1998, 229-244.

16. Gebauer R., Möller H.M. On an Installation of Buchberger's Algorithm // J. Symbolic Computation, 1988, 6, 275-286.

17. Giovanni A., Mora T., Niesi G., Robbiano L., Traverso C. One sugar cube, please or Selection Strategies in Buchberger Algorithm // Proceedings of ISSAC 1991, ACM, 1991, 49-54

18. Faugere J.C. Parallelization of Gröbner Basis // Proceedings of PASCO 1994, World Scientific Publ. Comp.

19. Attardi G., Traverso C. A strategy-accurate parallel Buchberger algorithm // Proceedings of PASCO 1994, World Scientific Publ. Comp.

20. Collart S., Kalkbrener M., Mall D. The Gröbner walk // Dept. of Math, Swiss Federal Inst, of Tech, 8092 Z urich, Switzerland

21. Amrhein B., Gloor O. The fractal walk // Groebner bases and applications, Cambridge University Press, 1998

22. Голубицкий О.Д. Инволютивный маршрут Гребнера // Фундаментальная и прикладная математика, том 7, 4, 993-1001, 2001.

23. Buchberger В. A Theoretical basis for the reduction of polynomials to canonical form // ACM SIGSAM Bulletin Vol. 10, No. 3, 19 29, 1976.

24. Buchberger B. Grobner Bases : An Algorithmic Method in Polynomial Ideal Theory // In N. K. Bose, editor, Multidimensional Systems Theory, pages 184-232. U. Reidel Publishing Company, 1985.

25. Moller H.M., Mora Т., Traverso C. Grobner bases computation using syzygies. // Proc. of ISSAC 1992.

26. Mora Т., Pfister G., Traverso C. An introduction to the tangent cone algorithm // Advances in Computing research, Issues in Robotics and nonlinear geometry, 1992, 6, 199-570.

27. Кондратьева M.B., Митюнин В.А. "Вычисление дифференциального размерностного многочлена при заменах образующих в системе уравнений Дирака"// "Программирование", 2001, 1, р. 37-40

28. Mityunin V.A. "Implementation of the differential involutive algorithms in the CAS Maple VR5",

29. Proceedings of IMACS АСА 2000, pp. 38-39.

30. 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 FPSAC'00, pp. 2324.

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

32. Mityunin V.A., Zobnin A.I., Ovchinnikov A.I., Semenov A.S. Involutive and Classical Grobner Bases Construction from The Computational Viewpoint // Proceedings of СААР 2001, , p.221-230.

33. Mityunin VA., Semenov A.S. "An Estimation of the Parallelization Quality of the Involuive Basis Computation Algorithm"// Proceedings of CASC 2002

34. Митюнин В.А., Панкратьев E.B "Параллельные алгоритмы построения базисов Гребнера"// Международная алгебраическая конференция, посвященная 250-летию Московского Государственного Университета, тезисы докладов, Москва, мех-мат МГУ, 2004, стр. 97-99

35. Boulier F., Lazard D., Ollivier F., Petitot M. Representation for the radical of a finitely generated differential ideal // Proceedings of the 1995 international symposium on Symbolic and algebraic computation, 1995, p.158-166

36. Эйнштейн А., Собрание научных трудов. T.2. Работы по теории относительности. 1921-1955 // М.: Наука 1966, с. 777-786.

37. Астрелин А.В., Голубицкий О.Д., Панкратьев Е.В., Инволютивные базисы идеалов в кольце многочленов // Программирование, 26 (1): с. 46-52, 2000

38. Kondratieva M.V., Levin А.В., Mikhalev A.V., Pankratiev E.V., Differential and Difference Dimension Polynomial // Kluwer Academic Publishers, Dordrecht Hardbound, November 1998.

39. Михалев А.В., Панкратьев E.B. Вычисления в дифференциальной и разностной алгебре // МГУ, 1989

40. Михалев А.В., Панкратьев Е.В. Компьютерная Алгебра. Факторизация многочленов. Изд-во МГУ, 1991.

41. Кондратьева М.В., Панкратьев Е.В., Серов Р.Е. Вычисления в дифференциальных и разностных модулях. // Аналитические вычисления на ЭВМ и их применение в теоретической физике. Дубна: ОИ-ЯИ, ДП-85-791, 1985, с. 208-213.

42. Кондратьева М.В. Описание множества минимальных дифференциальных размерностных многочленов. // Вестник МГУ, сер. 7, Математика, механика, 1988, N 1, с. 35-39.

43. Кондратьева М.В. Минимальный размерностный полином расширения поля, заданного системой линейных дифференциальных уравнений. // Математические заметки, т. 45, N 3, 1989, с. 80-86.

44. Quoc-Nam Tran Parallel computation and Groebner bases: an application for converting bases with the groebner walk // Groebner bases and applications, Cambridge University Press, 1998

45. Капланский И. Введение в дифференциальную алгебру // Издательство иностранной литературы, Москва, 1959

46. Kolchin E.R. Differential algebra and algebraic groups // New York, Academic Press, 1973

47. High Performance Libraries // http://www.hipilib.de/

48. Verification of Riemann's Hypothesis, ZetaGrid // http://www.zetagrid.net/

49. Bachmann 0., Schonemann H. Monomial Representations for Grobner Bases Computations / / Centre for Computer Algebra Department of Mathematics University of Kaiserslautern, 1998, http://www.mathematik.uni-kl.de/ zca/Reportsonca/18/paperhtml/paper.html

50. Bachmann O., Grabe H. The SymbolicData Project // Reports On Computer Algebra, Univ. Kaiserslautern, 27/2000 http://dol.uni-leipzig.de/pub/2000-5

51. Bini D.A., Mourrain В., Polynomial test suite // http://www-sop.inria.fr/saga/POL/

52. Robbiano, L. Term Orderings on the Polynomial Ring //In Proceedings of EUROCAL 85, Lecture Notes in Computer Science 204 (1985), pp. 513-517.