ПРОГРАММИРОВАНИЕ, 2009, № 2, с. 3-9
— КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2007-2008 гг.
© 2009 г. С. А. Абрамов*, А. А. Боголюбская**, В. А. Ростовцев**, В. Ф. Еднерал***
* Вычислительный центр РАН
119991 Москва, ул. Вавилова, 40
** Объединенный институт ядерных исследований
141980 г. Дубна Московской обл. ***НИИ ядерной физики МГУ им. М.В. Ломоносова
119992 Москва, Воробьевы горы
E-mail: sabramov@ccas.ru, abogol@jinr.ru, rost@jinr.ru, edneral@theory.simp.msu.ru
Поступила в редакцию 26.06.2008 г.
Годовой отчет о работе научно-исследовательского семинара по компьютерной алгебре.
1. О СЕМИНАРЕ
В семинаре рассматриваются новые результаты в области компьютерной алгебры - символьные алгоритмы и их реализация, соответствующие вопросы системного программирования.
В 2007-2008 учебном году семинар собирался, как правило, раз в месяц по третьим средам на факультете вычислительной математики и кибернетики, а в мае 2008 г. в Дубне, в Объединенном институте ядерных исследований (ОИЯИ) состоялось традиционное заседание, организованное совместно с Лабораторией информационных технологий ОИЯИ.
Web-страница семинара1
http ://theory.sinp.msu.ru/dokuwiki/docu.php/ calg:main
содержит информацию о планируемых и состоявшихся ранее докладах.
2. РЕГУЛЯРНЫЕ СОБРАНИЯ СЕМИНАРА
С сентября по апрель были прочитаны следующие доклады2.
поддержке сайта принимает участие А.П. Крюков.
2Перечень докладов, прочитанных в 1995-2007 г.г., опубликован в [1-12].
А.Д. Брюно (ИПМ РАН), В.Ф. Еднерал (НИИЯФ МГУ). Анализ локальной интегрируемости методами нормальных форм и степенной геометрии.
На примере редуцированного уравнения Янга-Миллза, представляющего собой гамиль-тонову систему из четырех уравнений, рассматривается техника исследования локальной интегрируемости методами нормальных форм и степенной геометрии. Доказано, что в окрестности одной из бесконечно удаленных неподвижных точек эта система локально неинтегрируе-ма.
М.В. Кондратьева (механико-математический факультет МГУ). Граница Якоби для систем обыкновенных дифференциальных уравнений.
Граница Якоби оценивает "число произвольных констант в общем решении системы дифференциальных уравнений". Исследование этой границы является одной из задач дифференциальной алгебры, сформулированных Е. Колчи-ным в докладе на Московском математическом конгрессе в 1966 году. Обсуждается современное состояние проблемы границы Якоби.
Ю. Герхард (Мейплсофт, Ватерлоо, Канада). Решение параметрических полиномиальных систем с помощью системы Maple.
Описывается новый Мар1е-пакет 11ос^Ртс1-11^[Рагате1;пс] для решения параметрических систем полиномиальных уравнений и неравенств. Использованный подход основан на разбиении пространства параметров К^ на две части: на дискриминантное многообразие и его дополнение Понятие дискриминант-
ного многообразия является обобщением понятия дискриминанта полинома одной переменной. Такое многообразие содержит значения параметров, приводящих к появлению вырожденных решений системы. Дополнение К<г\И/ может быть представлено как конечное объединение открытых клеток, таких, что число вещественных решений исходной системы постоянно для каждой клетки.
А.П. Немытых (ИПС РАН, Переславль-За-лесский). Специализация функциональных программ методами суперкомпиляции.
Суперкомпиляция есть набор методов специализации программ, написанных на функциональных языках программирования. Методы суперкомпиляции основаны на метаинтерпрета-ции специализируемых программ. Дается краткое введение в суперкомпиляцию и обсуждаются некоторые методы и алгоритмы суперкомпиляции, на основе которых автором реализован первый автоматический суперкомпилятор 8СР4.
С.Д. Махортов (Воронежский ГУ). Алгебраические модели продукционной логики и возможности их применения в системах символьной математики.
Вводятся основанные на решетках алгебраические системы, представляющие собой модели логики продукционного типа. Основная идея состоит в моделировании продукционных связей специальным бинарным отношением с соответствующими свойствами. Каждая модель определяется собственным набором таких свойств. При этом порождающее решетку базовое отношение частичного порядка отражает универсальные тавтологии и является фиксированным. Второе (продукционное) отношение происходит из логических связей конкретной предметной области и может подвергаться преобразованиям с целью оптимизации. Для каждой модели рассматривается стандартный круг во-
просов: замкнутость, эквивалентные преобразования, структура замыкания, логическая редукция. Обсуждаются возможности применения изложенной теории при разработке систем символьной математики.
М.В. Кондратьева (механико-математический факультет МГУ). Памяти Евгения Васильевича Панкратьева.
С.П. Царев (Красноярский ГПУ). Вычислительный вызов (challenge) в компьютерной алгебре: вычисление гипердетерминантов и их связь с интегрируемыми уравнениями в частных разностях.
А. Кэли ввел определение гипердетерминанта и вычислил простейший гипердетерминант гиперматрицы размера 2x2x2, т.е. тензора с тремя индексами в двумерном пространстве. Полученное выражение имеет всего 12 слагаемых. Гипердетерминант размера 2x2x2x2 имеет уже 2894276 слагаемых (www.arxiv.org, math.C0/0602149 v2 3 0ct2006).
Рассказывается о двух задачах, решенных недавно с помощью гипердетерминантов: об описании соотношений между главными минорами симметрических матриц (О. Хольц и Б. Штурм-фельс) и о доказательстве интегрируемости одной разностной системы, описываемой гипердетерминантом 2x2x2.
Е.В. Зима (Университет Вилфрид Лауэр, Ватерлоо, Канада). Интегральное представление и суммирование в замкнутом виде.
Рассматриваются приемы использования интегрального представления (метода коэффициентов) в различных классах задач неопределенного и определенного суммирования. В частности, алгоритмический подход к задаче рационального суммирования сопоставляется с подходом на основе интегрального представления. Показывается, как идеи метода коэффициентов могут использоваться для практического улучшения известных алгоритмов суммирования.
Результаты получены совместно с Г.П. Его-рычевым.
М.С. Зуев (Тамбовский ГУ). Блочные символьные матричные алгоритмы.
Предлагаются два новых блочных алгоритма вычисления обратной матрицы над полем
и алгоритм вычисления присоединенной матрицы и определителя над коммутативной областью. Приводятся оценки сложности этих алгоритмов по количеству мультипликативных операций. Приводятся оценки сложности операций сложения и умножения разреженных матриц над разреженными полиномами, основанные на вероятностном подходе. Рассматривается древовидный формат хранения матриц, предназначенный для организации вычислений с блочно-рекурсивными матричными алгоритмами. Обсуждаются результаты вычислительных экспериментов.
С.А. Абрамов (ВЦ РАН). Степенные ряды и линейные разностные уравнения.
Обсуждаются, в частности, некоторые достаточные условия применимости суммирующего оператора к решению данного разностного уравнения с полиномиальными коэффициентами, включая случай многомерных гипергеометрических последовательностей.
3. ТРЕХДНЕВНАЯ КОНФЕРЕНЦИЯ В ОБЪЕДИНЕННОМ ИНСТИТУТЕ ЯДЕРНЫХ ИССЛЕДОВАНИЙ (ДУБНА)
По установившейся традиции в мае 2008 г. в Дубне прошло совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ. По существу, это была трехдневная конференция по компьютерной алгебре и ее приложениям.
Вниманию участников были предложены следующие выступления.
Д. Штефанеску (Бухарестский университет, Румыния). Вычисление границ корней ортогональных полиномов.
Обсуждаются два метода вычисления границ наибольших корней ортогональных полиномов. Один из этих методов основывается на результатах, касающихся вещественных корней полиномов, другой - на том факте, что гессиан гиперболических полиномов положителен.
А.И. Овчинников (механико-математический факультет МГУ и Университет Иллинойса, Чикаго, США), О.Д. Голубицкий (Университет Западного Онтарио, Канада), М.В. Кондратьева (механико-математический факультет МГУ),
А. Санто (Университет штата Северная Каролина, Роли, США). Верхняя граница в дифференциальной теореме Гильберта о нулях.
Рассматривается задача получения оценки для порядков дифференцирований в дифференциальной теореме Гильберта о нулях как для обыкновенного случая, так и для уравнений с частными производными.
А.И. Зобнин (механико-математический факультет МГУ). Исследование алгоритма F5.
Алгоритм F5 для вычисления базиса Гребне-ра был предложен Фожером в 2002 году и позиционировался как алгоритм, в котором не возникает редукций к нулю. Однако корректная работа этого алгоритма гарантировалась только для однородных многочленов, образующих регулярную последовательность. К тому же, обоснование алгоритма оставалось крайне запутанным, aero "матричная" версия, представленная в диссертации Барде, была вовсе без доказательства. Предлагается простое обоснование этого алгоритма и рассматривается вопрос о его обобщении на случай произвольных образующих.
Л.А. Севастьянов, Д.С. Кулябов, М.Г. Кокот-чикова (РУДН, Москва). Символьно-численный алгоритм построения матриц стабилизирующего функционала в задаче восстановления поверхности.
При решении задачи восстановления поверхности возникает неустойчивость процедуры. С использованием метода регуляризации Тихонова находится стабилизирующий функционал. Восстановленная поверхность строится по коэффициентам Фурье в разложении по базису полиномов Цернике. Предлагается символьно-численный алгоритм построения матриц стабилизирующего функционала, реализованный в системе компьютерной алгебры Axiom.
А.Б. Арансон (НИИ дальней радиосвязи, Москва). Алгоритм вычисления степенных преобразований для анализа системы ОДУ в окрестности бесконечно удаленных особых точек.
Рассматривается автономная система ОДУ с полиномиальными правыми частями. Для анализа такой системы в окрестности ее непо-
движных точек используется метод нормальных форм. Чтобы исследовать этим методом окрестности особых точек, расположенных на бескон
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.