научная статья по теме СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2010-2011 ГГ Математика

Текст научной статьи на тему «СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2010-2011 ГГ»

ПРОГРАММИРОВАНИЕ, 2012, No 2, с. 3-10

КОМПЬЮТЕРНАЯ АЛГЕБРА -

УДК 004.92+004.94

СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2010-2011 гг.

© 2012 г. С. А. Абрамов*, А. А. Боголюбская**, В. А. Ростовцев**

*Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 **Объединенный институт ядерных исследований 141980 Дубна, Московская область E-mail: sergeyabramov@mail.ru, abogol@jinr.ru, rost@jinr.ru Поступила в редакцию 14.07.2011

Годовой отчет о работе научно-исследовательского семинара по компьютерной алгебре.

1. О СЕМИНАРЕ

В семинаре рассматриваются новые результаты в области компьютерной алгебры — символьные алгоритмы и их реализация, соответствующие вопросы системного программирования.

В 2010-2011 учебном году семинар проводился совместно факультетом вычислительной математики и кибернетики (ВМК) и НИИ ядерной физики МГУ. Встречи участников проходили раз в месяц по третьим средам на ВМК. В июне 2011 г. в Дубне, в Объединенном институте ядерных исследований (ОИЯИ) состоялось традиционное заседание, организованное совместно с Лабораторией информационных технологий ОИЯИ.

2. РЕГУЛЯРНЫЕ СОБРАНИЯ СЕМИНАРА

С сентября по апрель были прочитаны следующие доклады1.

Д.Е. Хмельнов (ВЦ РАН; ёепп18_кЬше1поу@ mai1.ru). Компьютерно-алгебраические методы решения систем линейных обыкновенных уравнений, основанные на индуцированных рекурренциях.

Предлагается несколько компьютерно-алгебраических (символьных) алгоритмов

1 Перечень докладов, прочитанных в 1995-2010 гг., опубликован в [1]—[16].

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

В.Г. Романовский (Университет Марибора, Словения; va1ery.romanovsky@uni-mb.si). Бифуркации предельных циклов в системах полиномиальных дифференциальных уравнений с нерадикальным идеалом Баутина.

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

алгоритмов, основанных на теории базисов Гребнера.

Д.В. Трушин (Мех-мат МГУ; trushindima@ yandex.ru). Дифференциальные идеалы.

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

И.Г. Ключников (ИПМ РАН; ilya.klyuchnikov@ gmail.com). Выявление и доказательство свойств функциональных программ методами суперкомпиляции.

Предлагается новый алгоритм суперкомпиляции для функционального языка высшего порядка, ориентированный на трансформационный анализ. Алгоритм основан на существующих алгоритмах суперкомпиляции для функциональных языков первого порядка.

Разработанный алгоритм реализован в экспериментальном суперкомпиляторе HOSC, являющимся первым суперкомпилятором для языка Haskell, для которого формально доказаны теоремы корректности и завершаемости.

А.Б. Арансон (НИИ дальней радиосвязи, Москва; aboar@yandex.ru). Программы для вычисления степенных разложений решений нелинейных систем ОДУ алгоритмами степенной геометрии.

Представлены программы вычисления степенных разложений решений нелинейных систем ОДУ алгоритмами степенной геометрии. Эти программы написаны на языке C++ и на языке системы символьных вычислений Maxima. Демонстрируется вычисление первых членов степенных разложений действительных решений в нуле и бесконечности по времени для системы ОДУ Эйлера-Пуассона, описывающей движение твердого тела около неподвижной точки. (Система Эйлера-Пуассона состоит из шести автономных ОДУ первого порядка с шестью параметрами и имеет три первых интеграла при любых допустимых значениях параметров.) При условиях на параметры системы Эйлера-Пуассона, допускающих редукцию Н. Ковалевского, с помощью разработанных программ были вычислены носители уравнений и трех первых интегралов системы, а также

пары нормальный конус - укороченная система. Число пар составило 53637 для случая, когда время стремится к нулю и 53456 для случая, когда время стремится к бесконечности. Для всех этих пар были выполнены вычисления и получено 58 вещественных степенных разложений решений в нуле.

Д.Дж. Джеффри (Университет Западного Онтарио, Канада; djeffrey@uwo.ca). Интегрирование: распрямление преобразований.

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

С.А. Гутник (МФТИ, МГИМО; в^шк@тпо. mgimo.ru), В.А. Сарычев (ИПМ РАН; вагу chev@keldysh.ru). Исследование положений равновесия спутника под действием гравитационного и постоянного моментов с использованием методов компьютерной алгебры.

Представлен анализ положений равновесия спутника на круговой орбите в гравитационном поле Земли с заданным постоянным моментом и главными центральными моментами инерции с использованием символьно-численных методов. Движение спутника относительно центра масс описывается системой дифференциальных уравнений Лагранжа. Стационарные уравнения движения представляют собой систему из шести алгебраических уравнений второго порядка с параметрами, представляющими проекции моментов на оси связанной с корпусом спутника системы координат. С использованием методов компьютерной алгебры было проведено построение базиса Гребнера для данной алгебраической системы. Показано, что при небольшом модуле вектора постоянного момента существуют 24 положения равновесия спутника. Рассмотрены точки бифуркации, в

которых происходит смена числа равновесных решений. В пространстве параметров системы численно построены области с постоянным числом равновесий спутника и исследована эволюция этих областей.

С.А. Абрамов (ВЦ РАН, МГУ; sergeyabramov@ mail.ru), Д.Е. Хмельнов (ВЦ РАН; dennis_khmel nov@mail.ru). Особые точки решений линейных дифференциальных систем с полиномиальными коэффициентами.

Рассматриваются системы линейных обыкновенных дифференциальных уравнений относительно т неизвестных функций одной переменной х. Коэффициенты систем являются полиномами над некоторым числовым полем. Каждая система состоит из т независимых уравнений. Уравнения имеют произвольные порядки. Предлагается алгоритм, который для заданной системы 5 описанного типа строит ненулевой полином й(х) такой, что если 5 обладает аналитическим решением с особенностью в точке а, то й(а) = 0.

В.Г. Романовский (Университет Марибо-ра, Словения; valery.romanovsky@uni-mb.si). Обратимость и инварианты полиномиальных систем ОДУ.

Описывается алгоритм вычисления порождающего множества инвариантов группы вращений полиномиальных двумерных систем дифференциальных уравнений (инвариантов Сибирского). С использованием методов вычислительной алгебры показана взаимосвязь обратимости, инволюции и инвариантов Сибирского. Охарактеризовано множество всех обратимых систем в заданном семействе комплексных двумерных полиномиальных дифференциальных систем и предложен эффективный алгоритм нахождения этого множества. Также обсуждается применение инвариантов к изучению периодических колебаний и бифуркаций предельных циклов в полиномиальных системax ОДУ.

А.Д. Брюно (ИПМ РАН, abruno@keldysh.ru), А.Б. Батхин (ИПМ РАН; batkhin@gmail.com). Разрешение алгебраической сингулярности алгоритмами степенной геометрии.

Статья по теме доклада публикуется в этом номере журнала.

Е.С. Шемякова (ВЦ РАН; shemyakova. katya@ gmail.com). Алгебраическая структура преобразований Дарбу операторов DxDy + a(x,y)Dx + b(x,y)Dy + c(x,y).

Статья по теме доклада публикуется в этом номере журнала.

Е.В. Зима (Университет Уилфрида Лорье, Ватерлоо, Канада). Синтетическое деление в контексте неопределенного суммирования.

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

3. ДВУХДНЕВНАЯ КОНФЕРЕНЦИЯ В ОБЪЕДИНЕННОМ ИНСТИТУТЕ ЯДЕРНЫХ ИССЛЕДОВАНИЙ (ДУБНА)

По установившейся традиции в июне 2011 г. в Дубне прошло совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ. По существу, это была двухдневная конференция по компьютерной алгебре и ее приложениям.

Вниманию участников были предложены следующие выступлен

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком