Система компьютерной
алгебры GAP
Система компьютерной алгебры
GAP
( http://www-gap.dcs.st-and.ac.uk/~gap
), название которой расшифровывается как "Groups, Algorithms and
Programming", была задумана около 15 лет назад как инструмент комбинаторной
теории групп - раздела алгебры, изучающего группы, заданные порождающими
элементами и определяющими соотношениями. Однако с выходом каждой новой
версии программы сфера ее применения охватывала все новые и новые разделы
алгебры, и сейчас это довольно масштабная по своему охвату система. Каждая
из систем такого рода, будь то MathCAD, Maple, Mathematica или Statistica,
имеет свои преимущества для представителей той или иной области математики,
и GAP наиболее привлекателен для исследований в области абстрактной алгебры.
Разработка системы была начата в
1986 г. в г.Аахен, Германия ( http://www.math.rwth-aachen.de/LDFM/
). В 1997 г. центр, который осуществляет координацию разработки и техническую
поддержку пользователей, переместился в Университет г.Сент-Эндрюс (Шотландия).
Текущая версия системы - GAP 4.2 - вышла в свет в феврале 2000 г.
Изначально система GAP разрабатывалась
под Unix, а затем была портирована для работы в других операционных системах.
В настоящее время она работает под разнообразными версиями Unix/Linux,
а также под Windows 9x, Windows NT, MacOS. Заметим, что производительность
системы под Unix/Linux возрастает на 20-40% по сравнению с Windows.
GAP является свободно распространяемой,
открытой и расширяемой системой. Она распространяется бесплатно (исключение
могут составлять только накладные расходы), и пользователи могут свободно
передавать ее другим пользователям (с некоторыми ограничениями, касающимися
модификации системы или ее частей). Далее, система поставляется вместе
с исходными текстами, которые написаны на двух языках: ядро системы написано
на Си, а библиотека функций - на специальном языке, также называемом GAP,
который напоминает Pascal. Пользователи могут создавать свои собственные
программы на этом языке, и здесь исходные тексты являются незаменимым наглядным
пособием. Наконец, разработчики программ для GAP могут оформить свои разработки
в стандарте share package и представить их на рассмотрение в совет GAP.
После прохождения процедуры рецензирования и одобрения советом GAP эта
разработка включается в приложение к дистрибутиву GAP для распространения
вместе с ним, и приравнивается к научной публикации.
Помимо уже упомянутых share packages,
система состоит из следующих четырех основных компонент:
-
ядра системы, обеспечивающего интерпретацию
языка GAP, работу с системой в программном и интерактивном режиме;
-
библиотеки функций, в которой реализованы
разнообразные алгебраические алгоритмы (более 4000 пользовательских функций,
более 140000 строк программ на языке GAP);
-
библиотеки данных, включая, например,
библиотеку всех групп порядка не более 2000 (за исключением 49487365422
групп порядка 1024), библиотеку примитивных групп подстановок, таблицы
характеров конечных групп и т.д., что в совокупности составляет эффективное
средство для выдвижения и тестирования научных гипотез;
-
обширной (около полутора тысяч страниц)
документации, доступной в разнообразных форматах (tex, ps, pdf, htm), а
также через Интернет.
Краткий обзор возможностей
GAP
для работы с различными видами
алгебраических объектов
Прежде всего, это возможность производить
вычисления с гигантскими целыми и рациональными числами, допустимые значения
которых ограничены только объемом доступной памяти. Далее, система работает
с циклотомическими полями, конечными полями, р-адическими числами,
многочленами от многих переменных, рациональными функциями, векторами и
матрицами. Пользователю доступны различные комбинаторные функции, элементарные
теоретико-числовые функции, разнообразные функции для работы с множествами
и списками.
Группы могут быть заданы в различной
форме, например, как группы подстановок, матричные группы, группы, заданные
порождающими элементами и определяющими соотношениями. Более того, построив,
например, групповую алгебру, можно вычислить ее мультипликативную группу,
и даже задать ее подгруппу, порожденную конкретными обратимыми элементами
групповой алгебры. Ряд групп может быть задан непосредственным обращением
к библиотечным функциям (например, симметрическая и знакопеременная группы,
группа диэдра, циклическая группа и др.).
Функции для работы с группами включают
определение порядка группы, вычисление классов сопряженных элементов, центра
и коммутанта группы, верхнего и нижнего центрального рядов, ряда коммутантов,
Силовских подгрупп, максимальных подгрупп, нормальных подгрупп, решеток
подгрупп, групп автоморфизмов, и т.д. Для ряда конечных групп доступно
определение их типа изоморфизма.
Интересная демонстрация возможностей
системы на примере построения математической модели кубика Рубика и исследования
описывающей его группы подстановок с помощью системы GAP может быть найдена
на сайте GAP по адресу http://www-history.mcs.st-and.ac.uk/~gap/Intro/rubik.html
Теория представлений групп также
входит в область применения системы GAP. Здесь имеются инструменты для
вычисления таблиц характеров конкретных групп, действий над характерами
и интерактивного построения таблиц характеров, определения теоретико-групповых
свойств на основании свойств таблицы характеров группы. Модулярные представления
групп (т.е. представления над полем, характеристика которого делит порядок
группы) также могут быть исследованы с помощью GAP.
В последней версии системы существенным
образом расширены возможности для работы с векторными пространствами, алгебрами
и модулями. В системе могут быть определены векторные пространства над
всеми доступными полями и модули над всеми доступными кольцами. Имеются
алгоритмы для вычисления структуры конечномерных алгебр Ли, которые могут
быть, например, заданы структурными константами или порождающими элементами,
вычисления различных их Лиевских подалгебр и идеалов.
Среди других областей применения
системы - теория графов и их автоморфизмов, теория кодирования, группы
Галуа, полугруппы, кристаллографические группы, и многое другое. Существует
графический интерфейс XGAP, который работает под OC Linux или Unix и позволяет,
например, графически изобразить решетку подгрупп группы. Информация о существующих
разработках для применения в той или проблемной области может быть найдена
на сайте GAP ( http://www-gap.dcs.st-and.ac.uk/~gap
) в разделе "share packages".
Получение и инсталляция системы
Дистрибутив системы может быть загружен
с одного из четырех сайтов, главным из которых является сайт GAP Group
http://www-history.mcs.st-and.ac.uk/~gap/
. Остальные три находятся в г.Аахен (Германия), г.Бостон (США), г.Канберра
(Австралия). Ссылки на них могут быть найдены на сайте GAP Group. Описание
дистрибутива находится по адресу http://www-history.mcs.st-and.ac.uk/~gap/Info4/distrib.html.
Каталог, содержащий дистрибутив GAP 4.2 на FTP-сервере - ftp://ftp-gap.dcs.st-and.ac.uk/pub/gap/gap4/
.
Дистрибутив занимает порядка 40 MB,
в развернутом виде полная версия требует около 156 МВ (без некоторых специальных
инструментов теории представлений групп, которые требуют еще 130 МВ). Для
экономии места можно сначала установить частичную версию, а затем по мере
необходимости дополнять ее новыми модулями. GAP вполне нормально работает
на ПК Pentium 166-MMX, RAM 32 MB, но рекомендуется RAM 64 MB.
Сначала с помощью описания дистрибутива
необходимо определить, какой набор файлов необходим для Вашей операционной
системы. На самом деле, различия между дистрибутивами (как по размеру,
так и по содержанию) очень невелики. GAP разработан таким образом, что
при переходе от одной операционной системы к другой меняется только его
ядро, написанное на Си, и способ запуска программы. Основная же часть информации
(библиотеки функций и данных), имеющие формат текстовых файлов √ программ
на языке GAP или специальным образом представленных данных √ остается неизменной,
а ядро уже, в свою очередь, обращается к ним.
С учетом незначительного различия
состава дистрибутива для разных систем можно рекомендовать вариант загрузки
полной версии дистрибутива (т.е. для Unix/Linux-систем), после чего пользователям
Windows нужно добавить всего несколько файлов, чтобы система могла работать
и под Windows. Это даст им возможность ознакомиться с перспективами использования
системы под Linux, и, возможно, приведет их к решению о переходе к ее использованию,
например, в случае большого объема вычислений, или необходимости использовать
некоторые share packages, работающие только под Unix/Linux.
В общем случае для инсталляции
понадобятся следующие файлы:
Итак, необходимые файлы получены. Начнем
с инсталляции под Linux. Автор лично инсталлировал GAP под Linux Red Hat
5.2, Linux Black Cat 6.2, Linux Red Hat 7.0, и должен заметить, что это
происходит даже более отлаженно, чем под Windows, в полном соответствии
с инструкциями из файла INSTALL. Вы компилируете unzoo, распаковываете
дистрибутив, bugfixes и share packages, а затем запускаете configure и
make для сборки ядра системы. GAP запускается файлом gap4r2/bin/gap.sh
после, может быть, его небольшого редактирования. Процедура инсталляции
графического интерфейса XGAP аналогична. При инсталляции под Windows сборка
ядра не производится. Вместо этого необходимо распаковать файл wbin4r2n5.zoo.
Система запускается файлом Gap4r2\bin\gap.bat, отредактированным согласно
содержащимся в нем инструкциям. Запустив GAP (во всех системах), Вы должны
увидеть на экране нечто подобное:
#########
###### ###########
###
#############
###### ############
####
##############
######## #############
#####
###############
######## ##### ######
#####
######
# #########
##### ##### ######
######
########## #####
##### #######
#####
##### #### ##### ######
########
####
##### ##### #############
### ####
##### #######
#### #### ###########
#### ####
##### #######
##### ##### ######
#### ####
##### #######
##### ##### #####
#############
##### #####
################ #####
#############
###### #####
################ #####
#############
################ ##################
#####
####
###############
##### ##### #####
####
#############
##### ##### #####
####
#########
##### #####
#####
####
Information at: http://www-gap.dcs.st-and.ac.uk/~gap
? for help. Copyright and authors list by ?copyright,
?authors
Loading the library. Please be patient, this may take
a while.
GAP4, Version: 4r2 fix5 of 26-September-2000, i586-pc-cygwin-gcc
Components: small, small2, small3, small4, small5, small6,
small7,
small8, id2, id3, id4, id5, id6, trans, prim, tbl,
tom installed.
gap>
Если это так √ поздравляем с успешным
завершением инсталляции! Кстати, стартовая страница руководства в формате
html находится в файле GAP4r2/doc/htm/INDEX.HTM
На русском языке доступно разработанное
автором методическое пособие по предыдущей версии системы - GAP 3.4.4.
Особенности системы, описанные в нем, незначительно изменились при переходе
к новой версии 4.2, поэтому его можно использовать для получения общего
представления о системе. Текст пособия помещен на сайте GAP Group по адресам
http://www-history.mcs.st-and.ac.uk/~gap/Deposit/GAP-rus.htm
и ftp://ftp-gap.dcs.st-and.ac.uk/pub/gap/gap4/deposit/teaching/GAP-rus.zip
, а также на сайте Exponenta.ru по адресу http://www.exponenta.ru/SOFT/OTHERS/gap/0.asp
Дальнейшая информация о системе GAP
может быть найдена на сайте GAP Group по адресу http://www-gap.dcs.st-and.ac.uk/~gap
. Там же можно подписаться на GAP-Forum - список рассылки новостей системы
GAP.
Коновалов А.Б.,
доцент кафедры алгебры и геометрии
Запорожского государственного университета
E-mail: konovalov@member.ams.org
10 декабря 2000 г.
