ПРОГРАММИРОВАНИЕ, 2013, No 2, с. 3-10
КОМПЬЮТЕРНАЯ АЛГЕБРА
У V 004.421.6
СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2011^2012 гг.
© 2013 г. С. А. Абрамов*, А. А. Боголюбская**, В. А. Ростовцев**
* Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 **Объединенный институт ядерных исследований 141980 Дубна Московской области E-mail: sergeyabramov@mail.ru, abogol@jinr.ru, rost@jinr.ru Поступила в редакцию 10.07.2012
Годовой отчет о работе научно-исследовательского семинара по компьютерной алгебре.
1. О СЕМИНАРЕ
В семинаре рассматриваются новые результаты в области компьютерной алгебры — символьные алгоритмы и их реализация, соответствующие вопросы системного программирования.
В 2011-2012 учебном году семинар собирался раз в месяц по третьим средам на факультете вычислительной математики и кибернетики МГУ, а в мае 2012 г. в Дубне, в Объединенном институте ядерных исследований (ОИЯИ) состоялось традиционное заседание, организованное совместно с Лабораторией информационных технологий ОИЯИ.
Web-страница семинара
http : //www.ccas.ru/sabramov/seminar/doku.php
содержит информацию о планируемых и состоявшихся ранее докладах.
2. РЕГУЛЯРНЫЕ СОБРАНИЯ СЕМИНАРА
С сентября по апрель были прочитаны следующие доклады1.
В.П. Гердт (ОИЯИ, Дубна; gerdt@jinr.ru). Анализ аппроксимируемости систем уравнений в частных производных конечным,и разностями.
1 Перечень докладов, прочитанных в 1995-2011 гг., опубликован в [1]—[17].
Рассматриваются конечно-разностные аппроксимации полиномиально-нелинейных систем дифференциальных уравнений в частных производных, коэффициенты которых являются рациональными функциями от независимых переменных. Общепринятое понятие (слабой) аппроксимации исходных уравнений сопоставляется с понятием сильной аппроксимации, введенным ранее автором для линейных дифференциальных систем и обобщенным недавно на нелинейные системы. Для ортогональных и равномерных сеток предлагается алгоритмическая процедура проверки сильной аппроксимируемости методами компьютерной алгебры, основанная на приведении в инволюцию исходной дифференциальной системы и построении разностного стандартного базиса для рассматриваемой аппроксимации. В качестве примеров изучаются конечно-разностные аппроксимации некоторых переопределенных линейных дифференциальных систем и две аппроксимации для двумерных нелинейных уравнений Навье-Стокса. Предложенная процедура устанавливает, что одна из этих двух аппроксимаций является сильной, а другая нет.
В.В. Корняк (ОИЯИ, Дубна; kornyak@jinr.ru). Вычислительная теория групп и квантовая физика.
Вычислительная теория групп изучает конечные (или конечно-представленные) группы конструктивными алгоритмическими методами.
Предлагается новая - "конечная" формулировка квантовой механики, основанная на конечных группах и их представлениях над конструктивными числовыми системами. Обсуждаются алгоритмы, необходимые для построения "конечной" квантовой механики.
A.A. Михалев (Мех-мат МГУ, Москва; aamikhalev@mail.ru). Примитивные элементы свободных алгебр.
Многообразие линейных алгебр над полем называется шрайеровым, если любая подалгебра свободной алгебры этого многообразия является свободной. Многообразия всех алгебр, коммутативных алгебр, антикоммутативных алгебр, алгебр Ли, супералгебр Ли, p—алгебр Ли и p—супералгебр Ли являются основными типами шрайеровых многообразий алгебр.
Пусть A(X) - свободная алгебра шрайерово-го многообразия алгебр с множеством X свободных образующих. Система элементов ul,... ,un алгебры A(X) называется примитивной, если существует множество Y свободных образующих алгебры A(X), содержащее элементы ul,..., un.
Для свободных алгебр основных типов шрайеровых многообразий алгебр построены и реализованы алгоритмы распознавания примитивных систем элементов, а также алгоритмы дополнения примитивных систем элементов до свободных порождающих множеств.
Доклад основан на совместных работах автора с К. Шампаньер, A.A. Чеповским, A.B. Михалевым, И.П. Шестаковым, У.У. Умирбаевым, Дж. Ю, A.A. Золотых.
A.B. Смирнов (НИИВЦ МГУ, Москва; asmirnov@gmail.com). Алгоритмы, вычисления фейнмановских инт,егра,лов.
Фейнмановские интегралы являются фундаментальными величинами при построении квантово-полевых амплитуд в рамках теории возмущений, в частности, они возникают при вычислениях в рамках Стандартной Модели физики элементарных частиц. На современном уровне исследований в конкретной задаче может требоваться вычисление миллионов интегралов Фейнмана, что, естественно, невозможно без современных компьютеров. Согласно классическому подходу, задача вычисления фейнмановских интегралов сводится, во-первых, к
их редукции к относительно небольшому числу мастер-интегралов и, во-вторых, к вычислению последних. Предлагаются новые алгоритмы редукции и вычисления фейнмановских интегралов.
С.П. Царев (Сибирский Федеральный Университет, Красноярск; sptsarev@mail.ru). О структуре решетки правых делит,елей линейного обыкновенного дифференциального оператора.
В 1996 г. автором был предложен алгоритм полного перечисления всех возможных факто-ризаций заданного линейного обыкновенного дифференциального оператора (ЛОДО) на неприводимые множители над полем рациональных функций. Полное описание всех возможных структур, выдаваемых данным алгоритмом, до сих пор неизвестно. Приводятся новые результаты исследования структуры всех возможных факторизаций заданного ЛОДО над произвольным дифференциальным полем коэффициентов. Удобным алгебраическим инструментом для этого описания является теория модулярных решеток.
A.B. Батхин (1111\! им. М.В. Келдыша, Москва; batkhin@gmail.com). Точные решения шестого уравнения Пенлеве.
Предлагается метод построения точных решений шестого уравнения Пенлеве (PVI) в виде конечных сумм степенных функций с рациональными показателями степени. Метод существенно использует алгоритмы степенной геометрии для построения степенных разложений решений обыкновенного дифференциального уравнения и алгоритмы компьютерной алгебры.
Д.С. Кулябов, A.B. Королькова, М.Н. Геворкян, Л.А. Севастьянов (ФМиЕН РУДН, Москва; vamadharma@gmail .com, avkorolkova@gmail .com, mngevorkvan@sci.pfu.edu.ru, sevast@sci.pfu.edu.ru) Применение симплектических интеграторов для задачи распространения электромагнитных волн.
Для численного решения дифференциальных уравнений предлагается использовать методы, сохраняющие структуру решений, а именно, методы геометрических интеграторов. Рассматривается метод симплектического интегратора в
применении к задачам распространения электромагнитных волн в волноводе. Подробно рассматриваются вспомогательные задачи: запись уравнений Максвелла в криволинейных голо-номных координатах; получение гамильтониана для уравнений Максвелла.
С.А. Абрамов (ВЦ РАН, ВМК МГУ, Москва; sergeyabramov@mail.ru), Д.Е. Хмельнов (ВЦ РАН, Москва; dennis_khmelnov@mail.ru). О валюацях мероморфных решений линейных разностных систем произвольного порядка с полиномиальными коэффициентами.
Рассматривается несколько алгоритмов получения нижних оценок валюаций (например, порядков полюсов) компонент мероморфных решений разностных линейных систем произвольного порядка с полиномиальными коэффициентами. Наряду с алгоритмами, основанными на идеях, в каком-то виде уже применявшихся в компьютерной алгебре при работе с нормальными разностными системами первого порядка, предлагается новый алгоритм, использующий «тропические» вычисления. Показывается, что последний алгоритм, обеспечивая хорошую точность оценок, является при этом и достаточно быстрым.
A.M. Денисов (ВМК МГУ, Москва; den@cs.msu.ru). Неединственность решения бесконечной системы дифференциальных уравнений в частных производных в пространстве Шварца.
Рассматривается задача, возникающая в двумерной доплеровской томографии. Требуется определить две функции u(x,y) и v(x,y) из пространства Шварца в ограниченной области, являющиеся решением бесконечной системы уравнений в частных производных. Система обладает некоторыми свойствами симметрии. Решение сформулированной задачи не единственно. Предлагается для обсуждения вопрос о выделении некоторых специальных классов единственности решения сформулированной задачи.
М.В. Зинин (ООО "Андер Девелопмент", Москва; mzinin@gmail.com). Символьные алгоритмы и программы вычисления булевых базисов Грёбнера.
Кратко описываются наиболее распространен-
ные алгоритмы вычисления базисов Грёбнера и обсуждаются аспекты применений этих алгоритмов в задаче построения булевых базисов Грёбнера. Предлагается вариант инволютивного алгоритма для эффективного решения этой задачи. Представлена реализация алгоритма в виде пакетов для открытых систем компьютерной алгебры REDUCE и Macaulav2.
3. ДВУХДНЕВНАЯ КОНФЕРЕНЦИЯ В ОБЪЕДИНЕННОМ ИНСТИТУТЕ ЯДЕРНЫХ ИССЛЕДОВАНИЙ(ДУБНА)
По установившейся традиции в мае 2012 г. в Дубне прошло совместное заседание семинаров "Компьютерная алгебра" факультета ВМК МГУ и ВЦ РАН и семинара Лаборатории информационных технологий ОИЯИ. По существу, это была двухдневная конференция по компьютерной алгебре и ее приложениям2.
Вниманию участников были предложены следующие выступления.
B.П. Иванников (ПСИ РАН, Москва; ivan@ispras.ru). О верификации программ.
Рассматриваются вопросы верификации больших программных комплексов, таких, например, как операционные системы.
C.А. Абрамов (ВЦ РАН, ВМК МГУ, Москва; sergevabramov@mail.ru), М. Петковшек (Университет Любляны, Словения;
Maxko.Petkovsek@fmf.uni-lj.si). О полиномиальных решениях линейных уравнений с частными производным,и и разностями.
Вопрос о том, имеет ли данное линейное уравнение с частными производными или разностями с полиномиальными коэффициентами ненулевое полиномиальное решение, в общем случае неразрешим алгоритмически. Но дифференциальное или разностное уравнение L(y) = 0, y = y(xi,...,xm), m > 1, с постоянными коэффициентами имеет ненулевое полиномиальное
решение если и только если коэффициент урав-y
2Примечание С.А. Абрамова и A.A. Боголюбской. Эта конференция была посвящена восьмидесятилетию В.А. Ростовцева, см. поздравительную статью в N° 3 за 2012 г.
случае ур
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.