Разработка алгоритмов и создание программ в секторе

Актуальность работ

Математический аппарат современной теоретической и математической физики включает такие сложные и на практике часто очень громоздкие математические объекты, как системы нелинейных алгебраических и дифференциальных уравнений, алгебры и супералгебры Ли, грассмановы алгебры и супермногообразия, расслоения со связностями Римана-Картана и калибровочными связностями, структуры некоммутативной геометрии, квантовые алгебры и группы и т.д. Операции над многими из этих объектов являются неассоциативными и некоммутативными. Стандартные системы компьютерной алгебры, такие как Maple, Mathematica, Reduce, Macsyma, MuPAD, Axiom и др. обычно или не имеют достаточно развитых встроенных средств работы с упомянутыми объектами и структурами, либо недостаточно эффективны для получения действительно новых результатов, обычно имеющих, в силу своей природы, высокую вычислительную сложность. В связи с этим разработка специальных алгоритмических подходов и их эффективная реализация приобретают важное значение.

Анализ алгебраических и дифференциальных систем

Для решения систем нелинейных алгебраических уравнений многих переменных, а также для исследования и решения линейных систем дифференциальных уравнений в частных производных эти системы необходимо приводить к некоторому каноническому виду. Одной из таких канонических форм является так называемый базис Гребнера, алгоритмы приведения к которому для алгебраических систем, ввиду их практической важности и многочисленных приложений встроены в виде специальных модулей во все современные программные системы компьютерной алгебры универсального назначения, такие как Maple, Mathematica, Reduce, Axiom, MuPAD и др. Другой канонической формой алгебраических и дифференциальных систем являются инволютивные базисы, введенные в рассмотрение в секторе алгебраических и квантовых вычислений ЛИТ [1] и представляющие собой базисы Гребнера специальной структуры. Приведение алгебраических и дифференциальных систем уравнений к канонической форме (базисам Гребнера или инволютивным базисам) требует выполнения огромного объема сложных аналитических преобразований.

Среди инволютивных базисов наибольшее внимание в последние годы привлекли базисы Жане. Для эффективного вычисления этих базисов был разработан и реализован на языках Reduce, Си и Си++ новый класс инволютивных алгоритмов [2,3]. Эти алгоритмы используют специально введенные для них структуры данных, названные деревьями Жане. Использование этих типов данных позволяет значительно ускорить приведение в инволюцию нелинейных систем уравнений. Созданные пакеты программ были сравнены по эффективности вычислений, с написаннными на языке Си системами компьютерной алгебры специального назначения Singular и Magma, которые разработаны для задач коммутативной алгебры и алгебраической геометрии и вычислительной теории групп, соответственно, и являются наиболее быстродействующими программами для вычисления базисов Гребнера, реализующими классический алгоритм Бухбергера. На большинстве задач, взятых из широко известной базы данных нелинейных систем, созданной для тестирования программных продуктов, программы работы [3] работают быстрее, чем Singular и Magma. Результаты сравнения, так же как и другие компьютерные эксперименты с указанными программами приведены на сайте http://invo.jinr.ru/

Более того, новые алгоритмы, в отличие от классического алгоритма Бухбергера для построения базисов Гребнера, встроенного в систему Singular и во все универсальные системы, такие как Maple, Mathematica, Reduce и др., допускают эффективное распараллеливание, что было явно показано в [4] на двухпроцессорном компьютере 2 х PIII-700 Мгц. Моделирование многопроцессорных вычислений на этом компьютере выявило хорошую масштабируемость времени счета по отношению к числу процессоров. В качестве одного из применений базисов Гребнера в задачах теоретической физике, приведем результаты работы [5], выполненной совместно с ЛТФ ОИЯИ. В этой работе изучена механика калибровочной теории Янга-Миллса на световом конусе. Эта механика, как и любая другая в современных моделях квантовой теории поля и физики элементарных частиц, является вырожденной, содержащей "скрытые" связи, которые обусловлены наличием нефизических, в том числе, калибровочных степеней свободы. Чтобы отделить эти степени свободы и, тем самым, выделить физические наблюдаемые свободы для целей квантования теории, необходимо, следуя классической процедуре Дира, вычислить все связи и разделить их на связи первого и второго рода. Для этой, достаточно сложной с вычислительной точки зрения задачи, в применении к вырожденным динамическим системам ранее был разработан специальный алгоритм [6,7], основанный на технике базисов Гребнера и инволютивных базисов. Этот алгоритм был реализован на языке Maple. Мы использовали для данной задачи реализацию на Maple, а не гораздо более эффективные по скорости вычислений Си/Cи++ программы [3] потому, что, во-первых, быстродействия Maple оказалось достаточно а, во-вторых, помимо вычисления базисов Гребнера, для разделения связей необходим также ряд операций линейной алгебры, которые встроены в Maple. В случае же, когда производительности Maple окажется недостаточно для вычислений базисов Гребнера предполагается использование программ [3].

Вычисление когомологий алгебр и супералгебр Ли

Когомологии алгебр, так же как и супералгебр Ли, имеют много важных приложений в математике (характеристические классы слоений; инвариантные дифференциальные операторы; комбинаторные тождества и т. д.), в теоретической и математической физике (построение центральных расширений и деформаций (супер)алгебр Ли, построение уравнений супергравитации для N - расширенных суперпространств Минковского и поиск возможных моделей для таких суперпространств, новые методы исследования интегрируемости динамических систем, построение алгебр Ли высшего порядка, используемых при формулировке механики Намбу, обобщающей обычную гамильтонову механику; построение возможных инвариантных эффективных действий типа Весса--Зумино--Виттена и изучение аномалий, механике (изучение устойчивости неголономных систем, таких, как подшипники, гироскопы, электромеханические устройства и т. д., описание аналога тензора кривизны при наличии нелинейных неголономных связей). Основные вычислительные трудности при вычислении когомологий возникают из-за очень высоких размерностей пространств коцепей входящих в коцепные комплексы. Для эффективного вычисления когомологий предложен новый алгоритм [8], основная идея которого состоит в извлечении наименьших возможных подкомплексов полного коцепного комплекса. Производительность этого алгоритма, реализованного в виде программы на языке Си, весьма высока в сравнении с конкурирующими программами.

Литература

[1] V.P.Gerdt, Yu.A.Blinkov. Involutive Bases of Polynomial Ideals. Mathematics and Computers in Simulation 45 (1998) 519-542; Minimal Involutive Bases. Ibid, 543-560.

[2] V.P.Gerdt, Yu.A.Blinkov, D.A.Yanovich. Construction of Janet Bases. I. Monomial Bases. In: "Computer Algebra in Scientific Computing \ CASC 2001 ", V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag , Berlin , 2001, pp.233-247.

[3] V.P.Gerdt, Yu.A.Blinkov, D.A.Yanovich. Construction of Janet Bases. II. Polynomial Bases. In: "Computer Algebra in Scientific Computing \ CASC 2001", V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag , Berlin , 2001, pp.249-263.

[4] V.P.Gerdt, D.A.Yanovich. Parallelism in Computing Janet Bases. In: "Computer Algebra and its Application to Physics / CAAP-2001", V.P.Gerdt (Ed.), JINR E5,11-2001-279, Dubna, 2002, pp. 93-103.

[5] V.P.Gerdt, A.M.Khvedelidze, D.M.Mladenov. Analysis of Constraints in Light-Cone Version of SU(2) Yang-Mills Mechanics. In: "Computer Algebra and its Application to Physics / CAAP-2001", V.P.Gerdt (Ed.), JINR E5,11-2001-279, Dubna, 2002, pp. 93-103.

[6] V.P.Gerdt, S.A.Goglilidze. Constrained Hamiltonian Systems and Groebner Bases. In: "Computer Algebra in Scientific Computing \ CASC'99", V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 1999, pp. 138-146.

[7] V.P.Gerdt. Computer Algebra and Constrained Dynamics. In: "Problems of Modern Physics", A.N.Sisakian and D.I.Trubetskov (Eds.), JINR D2-99-263, 2000, pp. 164-171.

[8] V.V.Kornyak. A New Algorithm for Computing Cohomologies of Lie Superalgebras. In: "Computer Algebra in Scientific Computing \ CASC 2001", V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2001, pp.391-398.

 

 


Copyright © 2007 compalg.jinr.ru. All rights reserved.