1.3 Системы компьютерной алгебры

Имеется несколько доступных систем компьютерной алгебры, большинство из которых разработано в США; в СССР имеется система, называемая аналитик, реализованная аппаратным образом. Прекрасным источником информации об этих системах являются периодически проводимые конференции, симпозиумы и т.д. по символьным и алгебраическим преобразованиям, SYMSAC — в США и EUROCAL или EUROSAM — в Европе. Труды этих конференций содержат как обзоры текущего состояния, так и направления дальнейшего развития; см. например, (Petricle (ed), 1971). Кроме того, ежеквартальный бюллетень публикует группа SIGSAM (Special interest Group on Symbolic and Algebraic Manipulation) ассоциации ACM (Association for Computing Machinery). Также ежеквартально выходит Journal of Symbolic Computation.

Стандартным тестом для любой системы компьютерной алгебры является вычисление Делоне движения Луны. Нахождение точного положения Луны в любой данный момент чрезвычайно важно для навигации и астрономии и удивительно сложно; это вычисление было начато в 1847 г. французским астрономом Делоне и заняло у него 10 лет, плюс еще 10 лет заняла проверка. Полученная формула занимает целую книгу. В 1970 г. три исследователя лаборатории Боинг в Сиэтле проверили работу Делоне на компьютере, что заняло 20 часов. Они обнаружили только три незначительные ошибки, что кажется почти невероятным.

Системы компьютерной алгебры демонстрируют великую изощренность и разнообразие проектов и могут быть разбиты на две основные группы в соответствии с их развитием.

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

данных. В следующем списке приводятся примеры таких систем: carnal — британская система для небесной механики и общей теории относительности; schoonship — для физики высоких энергий; altran, sac-1 и sac-2 - для полиномиальной арифметики.

Из чисто сентиментальных побуждений мы кратко опишем возможности системы sac-1 (symbolic and algebraic cakulatioa - версия 1), являющейся высоко переносимой системой.

Sac-1 — переносимая система на базе Фортрана для выполнения разнообразных заданий на многих различных алгебраических структурах. В действительности это — иерархия подсистем или модулей, состоящих из некоторого числа подпрограмм, выполняющих последовательность заданий. Каждый модуль непосредственно зависит от одного или нескольких (а неявно может зависеть от многих) предшествующих модулей системы, кроме стоящей особняком системы обработки списков. Следующий список указывает взаимозависимость различных подсистем (т.е. из приведенного ниже списка видно, например, что полиномиальная система зависит как от системы обработки списков, так и от системы целочисленной арифметики): (1) обработка списков; (2) целочисленная арифметика; (3) полиномиальная арифметика; (4) модулярная арифметика; (5) наибольший общий делитель и результант; (6) линейная алгебра, разложение на множители полиномов, рациональные функции, гауссовы полиномы; (7) интегрирование рациональных функций, вещественные нули; (8) вещественные алгебраические числа, комплексные нули.

Чтобы воспользоваться системой sac-1, нужно написать программу на Фортране, которая выполняет обычные фортрановские вызовы подпрограмм и функций для обращения к требуемым процедурам системы следовательно, пользователю, знакомому с Фортраном, не придется учить нового синтаксиса. Имена алгоритмов в sac-1 указывают на их функции; например, PSUM означает сложение полиномов (polynomial summation), в то время как ISUM — сложение целых чисел (integer summation).

Системы из второй группы являются программами общего назначения, снабжающими пользователя как можно более широкими математическими возможностями. Большая часть из них доступна через различные компьютерные сети. Основные представители этой группы — macsyma, reduce, schratchpad, maple (канадская система).

Например, reduce — система на базе языка Лисп. Ниже перечислены некоторые из ее возможностей: (1) разложения и упорядочение полиномов и рациональных функций; (2) символьное

дифференцирование; (3) символьное интегрирование; (4) подстановки и поиск по образцу; (5) вычисление наибольшего общего делителя двух полиномов; (6) автоматическое и контролируемое пользователем упрощение выражений; (7) полный язык для символьных вычислений, на котором написана сама программа reduce.

Новейшей и, по-видимому, лучшей для использования системой компьютерной алгебры является maple. Она была разработана в 1980-х гг. и вобрала в себя лучшие черты других систем, разработанных в конце 1960-х гг. Для пользователя имеется язык высокого уровня с современным синтаксисом, более подходящий для описания алгебраических алгоритмов.

Системы компьютерной алгебры общего назначения были разработаны также и для микрокомпьютеров, но обычно они более медленные и менее понятливые, чем их сородичи, спроектированные для больших ЭВМ; наиболее распространенной из таких систем является .

В прошлом системы компьютерной алгебры в общем не получали широкого распространения, во-первых, из-за медлительности, поскольку основные арифметические операции должны были быть в явном виде запрограммированы, а не реализованы на уровне аппаратного обеспечения, а во-вторых, из-за быстрого истощения пространства памяти, отводимого для хранения символьных выражений, в силу роста результирующих и промежуточных вычисляемых выражений. Сегодня, однако, с развитием недорогих компьютеров системы компьютерной алгебры стали значительно более доступными для обучения и исследований. Во время написания этой книги (начало 1987 г.) фирма Hewlett-Packard поставляла карманный калькулятор НР-28с для компьютерной алгебры стоимостью приблизительно 200 долларов.