ПРОГРАММИРОВАНИЕ, 2011, No 2, с. 3-8
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.92+004.94
СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2009-2010 г.г.
© 2011 г. С.А. Абрамов*, А.А. Боголюбская**, В.Ф. Еднерал***, В.А. Ростовцев** * Вычислительный центр РАН 119991 Москва, ГСП-1, ул. Вавилова, 40 ** Объединенный институт ядерных исследований 141980 Дубна Московской области ***НИИ ядерной физики МГУ 119991 Москва, Воробьевы горы E-mail: sergeyabramov@mail.ru, abogol@jinr.ru, rost@jinr.ru, edneral@theory.sinp.msu.ru
Поступила в редакцию 12.10.2010 г.
Годовой отчет о работе научно-исследовательского семинара по компьютерной алгебре.
1. О СЕМИНАРЕ
В семинаре рассматриваются новые результаты в области компьютерной алгебры — символьные алгоритмы и их реализация, соответствующие вопросы системного программирования.
В 2009-2010 учебном году семинар собирался, как правило, раз в месяц по третьим средам на факультете вычислительной математики и кибернетики и в НИИ ядерной физики МГУ, а в мае 2010 г. в Дубне, в Объединенном институте ядерных исследований (ОИЯИ) состоялось традиционное заседание, организованное совместно с Лабораторией информационных технологий ОИЯИ. Web-страница семинара
http://theory.sinp.msu.ru/dokuwiki/calg:main содержит информацию о планируемых и состоявшихся ранее докладах.
2. РЕГУЛЯРНЫЕ СОБРАНИЯ СЕМИНАРА С сентября по апрель были прочитаны следующие доклады1.
С.П. Поляков (ВЦ РАН; s.p.polyakov@gmail. com) Символьные алгоритмы, связанные с задачами суммирования.
Исследуются два подхода к задачам суммирования рациональных функций, один
хПеречень докладов, прочитанных в 1995-2009 г.г., опубликован в [1-15]
из которых избегает полной факторизации знаменателей, а другой основан на такой факторизации. В рамках обоих подходов обсуждаются алгоритмы суммирования рациональных функций и предлагаются новые алгоритмы суммирования с дополнительной минимизацией степеней знаменателя просуммированной части и числителя остатка. Дополнительно доказывается корректность алгоритма Цейлбергера в однородном случае. Демонстрируется, что этот случай может иметь место при любом порядке оператора Цейлбергера. Предлагается алгоритм построения аннулирующего оператора минимального порядка. Все обсуждаемые алгоритмы реализованы в среде Maple.
А.И. Зобнин (Мех-мат МГУ; al_zobnin@ mail.ru) Обыкновенные дифференциальные многочлены и дифференциальные стандартные базисы.
Рассматриваются решенные и нерешенные задачи теории дифференциальных стандартных базисов (в частности, критерии их конечности при различных упорядочениях).
Ю.А. Климов (ИПМ им.М.В.Келдыша РАН; yuklimov@keldysh.ru) Специализация программ на объектно-ориентированных языках методом частичных вычислений.
На основе существующих методов частичных вычислений для функциональных и объектно-ориентированных программ предлагается новый
метод специализации программ на объектно-ориентированных языках, впервые обеспечивающий специализацию всех основных конструкций таких языков, как C# и Java, и обладающий поливариантностью. Разработанный метод реализован в экспериментальном спе-циализаторе CILPE для промежуточного объектно-ориентированного языка CIL платформы Microsoft .NET и опробован на модельных задачах, показавших возможность ускорения программ до 10 и более раз.
А.В. Климов (ИППМ РАН; arkady.klimov@ gmail.com) Алгебра деревьев выбора и ее использование при построении графа алгоритма и трансляции с фортрана в язык потоков данных.
Распараллеливающая компиляция Фортрана требует проведения анализа программы для построения ее графа потоковых зависимостей (решетчатого графа, графа алгоритма). Предлагается метод построения графа алгоритма, основанный на использовании деревьев выбора -специальной синтаксической структуры, удобной для представления как промежуточных результатов анализа (таких как эффекты операторов и описания состояний), так и самого графа. Также предлагается система операций над деревьями выбора, в терминах которых удобно выражаются алгоритмы анализа программ и построения графа зависимостей. Анализ используется в компиляторе Фортрана в язык потоковой модели вычислений PolyDFL.
А.А. Кытманов (Сибирский федеральный университет, Красноярск; kytmanov@lan.krasu.ru) Построение алгоритмов компьютерной алгебры на основе методов теории функций.
Предлагается алгоритм исключения неизвестных из систем нелинейных неалгебраических уравнений, основанный на многомерном логарифмическом вычете, и алгоритм построения класса интегральных представлений в областях многомерного комплексного пространства и класса вычетов — аналогов многомерного логарифмического вычета.
А. Геффар (Лиможский университет, Франция; f_gheffar@yahoo.fr), С.А. Абрамов (ВЦ РАН, МГУ; sergeyabramov@mail.ru) Порядки рациональных решений разностных уравнений относительно неприводимых полиномов.
Обсуждаются два алгоритма, которые для заданного линейного разностного уравнения с коэффициентами в виде рациональных функций над полем k характеристики 0 строят конечное множество M неприводимых в k[x] полиномов, такое, что если данное уравнение имеет решение F(x) € k(x) и при этом p(x)F(x) < 0 для неприводимого p(x), то p(x) € M. Затем каждый из алгоритмов вычисляет некоторую нижнюю границу для p(x)F (x). Алгоритмы применимы как к скалярным уравнениям, так и к системам линейных уравнений первого порядка и основываются на комбинациях обновленных подходов, использованных в более ранних алгоритмах нахождения универсальных знаменателей (Абрамов, Баркату) и границ знаменателей (ван Хое). Проводится сравнение сложностей представленных алгоритмов.
А.А. Гусев, С.И. Виницкий, О. Чулуунбаатар, В.А. Ростовцев (ОИЯИ и Международный университет "Дубна"; gooseff@jinr.ru, vinitsky@ thsun1.jinr.ru, chuka@jinr.ru, rost@jinr.ru)
Разработка символьно-численных алгоритмов решения низкоразмерных краевых задач квантовой механики методом Канторовича — приведением к обыкновенным дифференциальным уравнениям.
Обсуждаются символьно-численные алгоритмы решения эллиптических задач методом Канторовича для примесных состояний в моделях квантовых точек, квантовых проволок и ям. Программная реализация выполнена в среде Maple-Fortran. В перспективе возможен переход к среде типа Mathematica-Delphi.
М.Г. Кокотчикова, Д.С. Кулябов, Л.А. Севастьянов (РУДН; mgkokotchikova@gmail.com, yamadharma@gmail.com, leonid.sevast@gmail. com) Регуляризованный метод восстановления функции по зашумленным значениям ее производных в точках сетки.
Решается задача восстановления функции, заданной на круге Q по измеренным с погрешностью значениям производных в точках сетки T = ti,t2,---,tk € Q диафрагмы Гартмана. Для устойчивого восстановления применяется метод регуляризации Тихонова, на основе которого разработан символьно-численный метод построения матрицы стабилизирующего функционала, реализованный в системах символьных вычислений Axiom и Matlab.
3. ДВУХДНЕВНАЯ КОНФЕРЕНЦИЯ В ОБЪЕДИНЕННОМ ИНСТИТУТЕ ЯДЕРНЫХ ИССЛЕДОВАНИЙ (ДУБНА)
По установившейся традиции в мае 2010 г. в Дубне прошло совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ. По существу, это была двухдневная конференция по компьютерной алгебре и ее приложениям.
Вниманию участников были предложены следующие выступления.
B.П. Гердт (ОИЯИ; gerdt@jinr.ru), Д. Роберте (ТУ, Ахен, ФРГ; daniel@momo.math.rwth-aaehen.de) Алгоритмическая проверка согласованности дискретных разностных аппроксимаций для систем линейных уравнений в частных производных.
Предлагается алгоритм проверки согласованности конечно-разностных аппроксимаций на однородных и ортогональных сетках для линейных уравнений в частных производных с помощью построения и анализа соответствующих разностных базисов Гребнера или инволютивных базисов.
C.А. Абрамов (Вычислительный Центр РАН, МГУ; sergeyabramov@mail.ru) О некоторых разрешимых и неразрешимых проблемах, связанных с q-разностными уравнениями с параметрами.
Рассматриваются линейные q-разностные уравнения с полиномиальными коэффициентами, зависящими от параметров. Для случая, когда в качестве основного поля выступает Q(q), предлагается алгоритм, распознающий существование числовых значений параметров, при которых уравнение имеет полиномиальное (рациональное) решение. Доказывается, что такой алгоритм невозможен, если допустимыми значениями параметров являются полиномы или рациональные функции от q.
А.М. Рапортиренко (ОИЯИ; ram@sunet1.jinr. ru) PSL версия системы Reduce для 64-битовых ОС Windows.
Обсуждается реализация PSL и Reduce для семейства 64-битовых операционных систем Windows. Основным недостатком 32-битовых реализаций были ограничения на максимальный объем используемой оперативной памяти (не
более 128M). В предлагаемой реализации таких ограничений нет.
А.А. Гусев, С.И. Виницкий, В.П. Гердт, В.А. Ростовцев, О. Чулуунбаатар (ОИЯИ и Международный университет "Дубна"; gooseff@ jinr.ru, vinitsky@thsun1.jinr.ru, gerdt@jinr.ru, rost@jinr.ru, ehuka@jinr.ru), Т.А. Толстова (Тверской ГУ; tana0731@mail.ru) Символьно-численный алгоритм редукции двумерной краевой задачи с применением параметрических функций.
Представлен символьно-численный алгоритм редукции эллиптической двумерной краевой задачи к системе обыкновенных дифференциальных уравнений второго порядка. Используется разложение решения по набору функций одной переменной и зависящих от второй переменной как от параметра. Алгоритм реализован в среде Maple-Fortran и применен для построения асимптотических разложений рассматриваемой краевой задачи.
М.Г. Кокотчикова, Д.С. Кулябов, Л.А. Севастьянов (РУДН; mgkokotchikova@ gmail.com, yamadharma@gmail.com, leonid. sevast@gmail.com) Применение регуляри-зованного метода восстановления функции для задач оптики.
Продолжение предыдущего доклада этих же авторов (см. раздел "Регулярные собрания семинара").
В силу оптической специфики задачи для восстановления функции предлагается воспользоваться полиномами Цернике, образующими ортонормированный базис в гильбертовом пространстве L2(Q). Для регуляризованного восстановления матрицы дискретного преобразования гартманограмм в ве
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.