Из истории отечественной компьютерной алгебры

Ефимов Г.Б., Грошева М.В., efimov@keldysh.ru

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

Компьютерная алгебра, история науки, механика

G.B. Efimov, M.V.Grosheva.

In the paper we briefly discuss some stages of development and application of Computer Algebra (CA) and CA systems. The list of known Russian CA systems is presented. We also give the list of Conferences, Seminars and Books of papers in this branch of informatics. See also http://www.keldysh.ru

Computer algebra, mechanic, history of science.

Г.Б.Ефимов, М.В.Грошева.

ИПМ им. М.В. Келдыша РАН, НИИ Механики МГУ им. М.В. Ломоносова, Москва

Efimov@keldysh.ru
1. Введение.

Истории развития Символьных, Аналитических преобразований или Вычислений на ЭВМ и Систем для Аналитических Вычислений (САВ) или Компьютерной Алгебре и системам для нее (СКА) в нашей стране, а также обзорам по различным приложениям КА и программным системам СКА посвящено уже немало работ [ ]. Мы хотели остановиться на некоторых моментах этой истории, – на роли конференций, семинаров в развитии отечественных исследований по КА и их использования, а также напомнить об отечественных системах КА, в том числе разработанных для задач механики.

В истории развития и применения КА в Советском Союзе можно отметить несколько этапов. После первых, весьма интересных, но немногочисленных экспериментов по преобразованию символьных (формульных) выражений на компьютере, выяснилось, что для дальнейшего их развития требуются большие ресурсы и затраты труда. Исследования продолжались небольшими коллективами в крупных научных центрах в Ленинграде, Киеве, Новосибирске, Москве, Харькове и др. Существенным прорывом явилось создание СКА АНАЛИТИК в Институте кибернетики Украинской Академии наук в Киеве. АНАЛИТИК был аппаратно реализован на машине МИР-2, небольшой и поэтому достаточно доступной, с языком пользователя по тому времени весьма высокого уровня. На АНАЛИТИК-е было выполнено немало прикладных работ, была организована ассоциация пользователей МИР-а, активно работавшая.

В следующий период, после появления БЭСМ-6 и машин ряда ЕС и языков достаточно высокого уровня на них, было создано большое число СКА, очень различных по объему и возможностям, разнородных по областям применения. Они отличались по степени универсальности, по набору и совершенству реализованных в них алгоритмов КА, как общих математических, так и проблемно ориентированных. Многочисленность СКА определялась рядом обстоятельств. Ограниченность ресурсов компьютеров затрудняла использование и развитие языков высокого уровня, удобного сервиса и средств взаимодействия различных систем, в частности СКА и численных пакетов и комплексов программ. Из-за этого затруднялось использование уже существующих СКА для задач другого типа и стыковка их с существующими комплексами численных вычислений. Отсутствовали и объединяющие проекты по развитию КА и СКА, в программировании на повестке дня стояли другие задачи. Поэтому создавались все новые СКА, каждая для своей группы задач.

Можно отметить еще одно обстоятельство общего характера. Серьезные ресурсы, и компьютеров, и исследователей были сосредоточены на больших ВЦ, специализированных на решении важных прикладных задач и сильно загруженных. ВУЗы имели, как правило, весьма ограниченные ресурсы современных компьютеров. Мировой опыт показал, что широкое распространение получили те СКА, которые были широко доступны. Так система Reduce, первоначально специализированная, активно развивалась и стала универсальной благодаря тому, что была доступна в университетах. Открытость обеспечила ей быстроту развития, рост числа и совершенствование качества новых алгоритмов КА. Специфика ситуации у нас не создало такой возможности.

Объединяющим центром по работам в КА в этот период явился Объединенный институт ядерных исследований в Дубне. В нем смогли получить и адоптировать Reduce, активно способствовали его распространению. Кроме собственных больших работ на этой системе, проводилось сотрудничество с исследователями других организаций, стажировка в ОИЯИ, что способствовало освоению Reduce-а во многих центрах. Большую роль в объединении научных сил Совещания по КА, регулярно проводившиеся в Дубне, с публикацией их трудов. Были налажены контакты с ведущими специалистами за рубежом. Дополнением к организующей работе в Дубне служил Семинар по КА под руководством Д.В. Ширкова на физическом факультете МГУ. С появлением у нас персональных компьютеров, широких возможностей для международных контактов ситуация в исследованиях по КА существенно изменилась, но мы остановимся в основном на описании предыдущих этапов нашей истории.

Многочисленность отечественных СКА заставляла собирать информацию об имевшихся в то время системах, что предпринималось авторами в ряде обзоров. Несомненно, ряд систем остались за их рамками, но собранный материал дает большую информацию о разработанных СКА. Часть ее мы представляем ниже. Более полная, – в монографии авторов [1].

Приводим список наиболее ряда известных СКА. В конце списка даны СКА для задач механики системы тел, по некоторым СКА данные не полны. В описание входит: название, город, фамилии авторов, язык реализации, ЭВМ (литературу по ним см. [1] на фамилии авторов).

АВТО-АНАЛИТИК - Томск, Е.А.Арайс, Б.Ш.Гельфман, В.М.Зюзьков, А.В.Шутенков; БЭСМ-6, язык Автоаналитик; ЕС, ПК.

АНАЛИЗ Москва, Ю.А.Герасимов, А.А.Красилов; БЭСМ-6, Алгол-60.

АНАЛИТИК-74, -79 - Киев, В.М.Глушков, С.Б.Погребинский, В.П.Клименко, Ю.С. Фишман и др.; МИР-2, язык Аналитик-74. СМ-1410,

АНАЛИТИК-89, -91 - Киев, В.П.Клименко, С.Б.Погребинский, Ю.С. Фишман и др.; программная реализация, язык АНАЛИТИК-89, -91.

АНАЛИТИК-93, -2000 - Киев, В.П.Клименко, А.А.Морозов, Ю.С.Фишман, А.Л.Ляхов и др.; программная реализация с новыми языковыми возможностями

АЛГЕБРА-0.5 - Горький, М.А.Чубаров, Г.А.Долгов и др.; ЕС, Фортран.

АЛЬКОР - Москва, Л.В.Проворов; ЕС, БЭСМ-6, СМ-4, ПК, Рефал.

АРАП - Новосибирск, А.Л.Семенов; БЭСМ-6, ЯРМО; "Эльбрус" Автокод-Эльбрус.

АУМ - Новосибирск, Н.А.Калинина, И.В.Поттосин, А.Л.Семенов; БЭСМ-6, ЯРМО; "Эльбрус", Автокод-Эльбрус.

БОРА - Томск, Ю.Б.Шмидт; БЭСМ-6, машинные коды.

ВИБРАН - Вильнюс, Р.В.Кульветене, Г.П.Кульветис; ЕС, СМ, ПК, Фортран.

ВФЛ-1 - Иркутск, В.М.Матросов, С.Н.Васильев, В.Г.Каратуев, Е.А.Суменков; БЭСМ-6, "Эльбрус", Паскаль.

ДИНАМИКА - Иркутск, В.Д.Иртегов, Л.А.Бурлаков, М.В.Почтаренко; БЭСМ-6, Алг-ГДР.

ДИРАК - Новосибирск, А.Г.Грозин; "Одра", ЕС, "Электроника 100-25", Паскаль.

КЕНТАВР - Минск, В.Л.Катков, М.Д.Попов; БЭСМ-6, ЯРМО.

КИДИМ - Харьков, Л.И.Штейнвольф, В.Н.Митин; ЕС, Алгол-68.

МАРС - Томск, Е.А.Арайс, В.М.Дмитриев, В.Ф.Шадрин, А.В.Шутенков и др.; БЭСМ-6, ЕС, Автоаналитик, Фортран.

МЕХАНИК Ирк., А.В.Банщиков, Л.А.Бурлакова, Г.Н.Иванова, С.С.Смирнов; ЕС, PL-1.

MLR - Иркутск, М.В.Почтаренко; БЭСМ-6, Алгол-ГДР.

MMANG - Гродно, О.М.Городецкий; ЕС, Рефал.

МОДЕЛЬ - Ташкент, В.Бузурханов, М.Музафаров; БЭСМ-6, Паскаль.

НОРМАЛИЗАЦИЯ - Иркутск, В.Д.Иртегов, М.А.Новиков; БЭСМ-6, Алгол-ГДР.

ПАС - Москва, Г.Б.Ефимов, БЭСМ-6, Фортран.

ПЛ-ОСИАЛ - Ташкент, Т.Т.Имамов, Б.Курманбаев; ЕС, ПЛ/1.

ПЛЭНЕР-АНАЛИТИК - Москва, В.А.Эльтеков; БЭСМ-6, язык Плэнер.

ПОЛИНАЛ - Москва, А.Б.Константинов; БЭСМ-6, Алгол-ГДР.

САВАГ - Ленинград, Ю.К.Демьянович; БЭСМ-6, Алгол-ГДР.

САНТ - Дмитровград, Ю.В.Марков; БЭСМ-6, Макро-ассемблер БЭМШ.

САНТРА - Москва, И.Б.Щенков, ЕС, Рефал.

СИРИУС-СПУТНИК - Харьков, И.Р.Аксельрод, Л.Ф.Белоус; ЕС, М-222, Спутник.

СИРИУС-2.1 - Харьков, И.Р.Аксельрод, Л.Ф.Белоус; ЕС, Спутник, Рефал.

СПРИНТ - Ленинград, Н.Н.Васильев; БЭСМ-6, Фортран.

СТР - Ленинград, Н.Н.Васильев; БЭСМ-6, "Эльбрус", Фортран.

СРМ - Москва, В.Л.Топунов, И.Г.Резников, В.И.Стеллецкий; БЭСМ-6, ЕС, Рефал.

УПП - Ленинград, В.А.Брумберг, С.В.Тарасевич, Т.В.Иванова, Н.Н.Васильев, В.И. Скрипниченко, И.О.Бабаев; БЭСМ-6, ЕС, "Эльбрус", Фортран.

CATA - Вильнюс, В.В.Тумасонис; БЭСМ-6, ЕС, Лисп.

GRATOS - Ленинград, С.В.Тарасевич; БЭСМ-6, ЕС, "Эльбрус", Фортран.

SASM - Ленинград, А.В.Кузьмин; БЭСМ-6, Фортран, Автокод Мадлен.

SATURN - Москва, Д.В.Куликов; ЕС, Рефал.

- Чебоксары, Б.В.Алексеев; БЭСМ-6, Фортран, машинрые коды.

- Ленинград, П.И.Бегун, Г.А.Водень и др.; БЭСМ-6, Алгол-60, ЕС, Фортран.

- Новосибирск, В.Г.Ганжа, С.И.Мазурик, В.П.Шапеев; БЭСМ-6, ЕС, Рефал.

- Москва, Е.В.Панкратьев, Р.Е.Серов, С.Г.Хлебутин; СМ-4, Рефал.

- Ташкент, Т.Фархадов, Т.Юлдашев; БЭСМ-6, Алгол-60.

Устойчивость-1 - Горький,Г.А.Долгов,Д.Н.Макарычева,М.А.Чубаров; ЕС, Фортран.

CompHEP - Э.Э.Боос, М.Н.Дубинин,В.Ф.Еднерал и др., ИЯФ МГУ.

АЛМАК, Тула - Ю.Б. Подчуфаров, А.П.Матвеев, АНАЛИТИК, СМ-1410.

СПИН - Ленинград, Р.И.Сольницев, И.В.Ковтун, Фортран, ЕС.

ANTRA-VEKTRA - Ленинград, А.Б.Кикин, З.Е.Пейсах, Фортран, ЕС.

MMT-1/V2 - Киев, С.Я. Свиситунов и др., РL-1, ЕС.

SYMA - Москва, А.В.Яценко, РL-1, ЕС.

- Пермь, А.Б.Бячков, В.А.Иванов и др., М.Ю.Дроздов, В.В.Маланин, Лисп-Reduce, ЕС, ПК.

Полимех-символ - Москва, Д.М. Климов и В.М.Руденко, Редьюс, ЕС, ПК.

Универсальный процессор – Брянск, Д.Ю.Погорелов, Фортран.

КАПСУЛА – Москва, М.Г.Зотов, М.М.Востостряков и П.В.Киргизбаев.

АММУСТ – Ленинград, В.А.Коноплев, численная с СКА САВАГ (В.П.Червонных).

Авторы принимали участие в рабочей группе по СКА для исследования динамики системы тел, к которым относятся СКА: АВТО-АНАЛИТИК, АЛГЕБРА-0.5, (также - УСТОЙЧИВОСТЬ, АНФОР той же группы), ВИБРАН, КИДИМ, иркутские ДИНАМИКА, MLR и МЕХАНИК, ANTRA-VEKTRA, MMANG, MMT-1/V2, АЛМАК, СПИН, SYMA, КАПСУЛА, Плимех-символ, Универсальный процессор, СКА Пермского университета, ПАС и ряд других. (По этим СКА см. Горький-84, Информатор-83, Ленинград-88,89, Вильнюс-84,90, Севастополь-91 и по фамилиям авторов в [ ]).

Обсуждение СКА для исследования динамики системы тел, (см. Ленинград-88, Ленинград-89-II, Вильнюс-90) показало дифференциацию внутри этой группы СКА – по сходным задачам и режимам работы. Назовем три группы с достаточно выраженной спецификой. Первая группа (задачи типа "проектирования") имеет дело с большим числом вариантов-моделей, среди которых производится выбор, оптимизация параметров. Важна формализация модели для общения пользователя с системой (этапы 1, 2, 3 цикла А.А.Самарского), далее работа ведется численно. Во второй группе (моделирование в громоздких и сложных случаях) СКА выполняет этапы 1-4 цикла, в центре внимания оказывается эффективность счета – вид уравнений движения, представление данных и их преобразований, организация счета, контроль точности и т.п. Третья подгруппа – качественные исследования свойств уравнений и решений: нормализация, линеаризация, устойчивость, поиск стационарных решений и т.п. СКА используется на многих этапах. Главное – богатство и совершенство алгоритмов, в том числе специальных, их развитие. Каждая группа имеет ярких представителей, имеются и промежуточные случаи.

К первой группе относим КИДИМ, КАПСУЛА (в задачах управления), CompHEP. Последняя СКА, для моделирования и оптимизации физического эксперимента ярко демонстрирует роль СКА при формализации задачи, поэтому мы ее рассмотрели с механическими СКА. Ко второй группе относится АММУСТ (с СКА САВАГ), MMANG, АНФОР. К третьей группе – иркутские МЕХАНИК и ДИНАМИКА, Полимех-символ Института проблем механики АН, на которой отрабатывались механические алгоритмы. Система Универсальный Процессор первоначально можно было отнести к первой группе, но ее более современный комплекс соответствовал группе второй.

Большую роль в развитии КА и систем КА играли конференции, семинары разного масштаба и уровня. При том что большая часть публикаций по КА и ее применениям находилась в малодоступных сборниках трудов вузов, редко попадали в крупные журналы, роль обмена информацией на научных собраниях трудно переоценить. Отечественные разработки по КА опубликованы весьма неравномерно, многие из них труднодоступны и нередко отражены лишь в материалах конференций, семинаров и совещаний. Приводим список значительной части научных конференций и сборников их материалов, в том числе, специально с механическим уклоном. Сюда же отнесены некоторые публикации специально посвященные КА и СКА. Перед каждым из них приводим его сокращенное обозначение – для удобства ориентации в их множестве. Естественно, не все конференции, где присутствовала тема КА, попали в наш список: на многих из них, особенно в ранние годы, КА занимала скромное место, хотя для развития КА они могли играть заметную роль. В качестве примеров можно назвать конференции «Методы трансляции» (Новосибирск, 1981 г.), «Диалог Человек-ЭВМ» (Протвино, 1983 г.) или 3-ю Четавескую конференцию по устойчивости движения и механике (Иркутск, 1975 г.). Многие работы по применению КА докладывались на конференциях и семинарах по математике, механике или физике, где КА была представлена слабо, и терялись в общей массе работ.

Харьков-72 – Bычислительная математика и вычислительная техника. Всес. семинар. Харьков, 1979. - Xарьков: ФTИHT AH УCCP, 1972, N 3, 152 с.

Дубна-80 – Aналитические вычисления на ЭBM и их применение в теоретической физике. Mатериалы междунар.совещ. Дубна, 1979 - Дубна: OИЯИ, 1980, 187 с.

Дубна-83 – Aналитические вычисления на ЭBM и их применение в теоретической физике. Mатериалы междунар.совещ. Дубна, 1983. - Дубна: OИЯИ, 1983, 260 с.

Информатор-83 – Системы аналитических вычислений на ЭВМ (Аналитические пакеты прикладных программ). М.В. Грошева, Г.Б. Ефимов, В.А. Брумберг, И.О. Бабаев, Н.Н. Васильев, Т.В. Иванова, В.И. Скрипниченко, С.В. Тарасевич, И.Р. Аксельрод, Л.Ф. Белоус, Г.А. Долгов, А.В. Кузьмин, Р.В. Кульветене, Г.П. Кульветис, М.В. Почтаренко, М.А. Чубаров. Материалы семинара ИМеханики МГУ, 1981. - Информатор. ИПМ АН СССР, 1983, N 1, 65 с.

Вильнюс-84 – Теория и практика автоматизированных систем аналитических преобразований. Тез. респ. совещ. Вильнюс, 1984. - Вильнюс: ИПК СНХ Лит. ССР, 1984, 93 с.

Горький-84 – Системы для аналитических преобразований в механике. Тез. докл. Всес. конф. Горький, 1984. - Горький: ГГУ, 1984, 147 с.

Дубна-85 – Aналитические вычисления на ЭBM и их применение в теоретической физике. Материалы междунар. совещания. Дубна, 1985. - Дубна: OИЯИ, 1985, 420 с.

Аналитические ППП-88 – Пакеты прикладных программ. Аналитические преобразования. - M., Наука, 1988, 156 с.

Ленинград-88 – Методы компьютерного конструирования моделей механики систем твердых тел. Материалы Всес. рабочего совещ. Л., 1988.- Препр. Ленингр. фил. Ин-та машиновед. АН СССР, 1989, N 16, 32 с.

Киев-88 – Системы аналитических вычислений (методы компьютерной алгебры) в механике деформируемого твердого тела. Докл. Всес. совещ. Киев, 1988. - КГУ. Киев, 1990, (168с.) Деп. УкрНИИНТИ 17.04.90, №732, - Ук90.

Ленинград-89: I,II – Методы компьютерного конструирования моделей классической и небесной механики-89. Секция I: Небесная механика. Тез. докл. Всес. совещ. Л., 1989. - Ин-т теор. астрон. АН СССР, 1989, 67 с. Секция II: Теория и практика компьютерного конструирования моделей механики многозвенных технических систем. Материалы Всес. совещ. Л., 1989. - Препр. Ленингр. фил. Ин-та машиновед. АН СССР, 1989, N 32, 83 с.

Вильнюс-90 – Aналитические преобразования на ЭBM в автоматизации научно-исследовательских работ. Всес. конф. Вильнюс, 1990. - Вильнюс: ИПК СНХ ЛитССР, 1990, 94 с.

Ленинград-90 – Алгоритмы и программы небесной механики. Всес. совещ. Л. 1990. - Л., Ин-т теор. астрон. АН СССР, 1990, 80 с.

Дубна-90 – Computer Algebra in Physical Research. Int. Conf. Computer Algebra Phys. Res., Dubna, USSR, 1990. Memorial Volume for N.N.Govorun. - Singapore; New Jersey; London; Hong Kong: - World Scientific, 1991, 453 p. Сб. аннот., Дубна, ОИЯИ, 1990, 96 с.

Севастополь-91 – Применение ЭВМ для решения задач механики. Тез. научно техн. конф. Севастополь, 1991. - Киев: общ. "Знание" Украины, 1991, 55 с.

С.-Петербург-91,-92,-95 – Компьютерные методы небесной механики.Тез.докл. Всес. совещ. с международным участием. С.-Пб.,1991. - Инст теор. астрон. АН СССР, 1991, 101 с.; - ИТА РАН, 1992, 95 с.; 1995, 208 с.

Киев-93 – International Symposium on Symbolic and Algebraic Computation (ISSAC'93). July 6-8, 1993, Kiev, Ukraine. Abstracts, 1993, 321 p. + International Workshop "Computer Algebra Application". July 9, 1993, Kiev, Ukraine. Extended Abstracts, S-Petersburg, 1993, 55 p.

St.-Pеtеrsburg-93, -94 – International Congress on Computer Systems and Applied Mathematics (CSAM'93). 19-23July, 1993. Abstr., 1993, 278 p. Section: "Computer Algebra Applications". International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL'94). 7-10 March, 1994. Abstracts, 1994, 266 p.

Переславль Залесский -94, -95 – International Workshop "New Computer Technologies in Controll Systems", Pereslavl-Zalessky. 11-15 July, 1994; Abstracts, 1994, 99 p. 13-19 August, 1995; Abstracts, 81 p.

Bucharest-95 – International Conference "Symbolic Calculations and Their Application in Fundamental Reasearches", Bucharest, 5-11 September, 1995. Abstracts, ITA RAS, St.-Petersburg, 1995, 48 p.

Инфосфера-95 - Международная конференция "Эволюция инфосферы" ("Информатика-95"), Москва, 21-23 ноября 1995.

Москва, Институт механики МГУ - 1978, 1981, 1986-1990 гг. – Всесоюзные совещания по использованию САВ в задачах механики. (По материалам первого из них подготовлен Информатор-83).

Минск-97. – Компьютерная алгебра в фундаментальных и прикладных исследованиях. Междунар. конфер.1997. – Тезисы. Белорусск. ГУ. Минск. 1997.

Pragua-98 – 4-th Intern. IMACS conference on Applications of Computer Algebra - IMACS ACA’98, Prage, Aug.9-11, 1998. – The History of Computer Algebra Applications. Session. Theses of Report. - Moscow, 1998. 36 p.

Минск-99. – Компьютерная алгебра в фундаментальных и прикладных исследованиях и образовании. 2 Междун. конф. сент.1999.Тез. Минск.1999. 108 с.

St-Petersburg-2000. – 6 Intern. IMACS confer. on Applications of Computer Algebra - IMACS ACA’ 2000, St-Petersburg, July-2000. – Theses. St-Petersburg.2000.

Dubna-2001 – Computer Algebra and it’s Application to Physics. - CAAP-2001. Dubna, JINR. 2001.

6. Заключение.

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