Cистема компьютерной алгебры GAP 4.4.7
на CHIP-CD 9/2006


1. Краткое знакомство с системой GAP
2. Возможности работы с алгебраическими объектами
3. Инсталляция системы с помощью CHIP-CD
4. С чего начать работу с системой

1. Краткое знакомство с системой GAP

Система компьютерной алгебры GAP, название которой расшифровывается как "Groups, Algorithms and Programming", была задумана около 20 лет назад как инструмент комбинаторной теории групп - раздела алгебры, изучающего группы, заданные порождающими элементами и определяющими соотношениями. C выходом каждой новой версии программы сфера ее применения охватывала все новые и новые разделы алгебры.

Разработка системы была начата в 1986 г. в Высшей Технической Школе Рейн-Вестфалии (г.Аахен, Германия). В 1997 г. центр координации разработки и технической поддержки пользователей переместился в Университет г.Сент-Эндрюс, Шотландия. В настоящее время GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Основные центры разработки системы находятся в университетах г.Сент-Эндрюс (Шотландия), гг. Аахен, Брауншвейг (Германия), Университете штата Колорадо (США). Текущая версия системы - GAP 4.4.7 - была выпущена в марте 2006 г.

Изначально система GAP разрабатывалась под Unix, а затем была портирована для работы в других операционных системах. В настоящее время она работает в разнообразных версиях Unix/Linux, а также в Windows и MacOS. Некоторые пакеты, такие как, например, графический интерфейс XGAP, функционируют только в системах семейства Unix/Linux.

GAP является свободно распространяемой, открытой и расширяемой системой. Она распространяется в соответствии с GNU Public License. Cистема поставляется вместе с исходными текстами, которые написаны на двух языках: ядро системы написано на Си, а библиотека функций - на специальном языке, также называемом GAP, который по синтаксису напоминает Pascal, однако является объектно-ориентированным языком. Пользователи могут создавать свои собственные программы на этом языке, и здесь исходные тексты являются незаменимым наглядным пособием. Наконец, разработчики программ для GAP могут оформить свои разработки в виде пакета для системы GAP и представить их на рассмотрение в Совет GAP. Принятая в Совете GAP процедура рецензирования позволяет приравнивать принятые Советом GAP пакеты к научной публикации, и ссылаться на них наравне с другими источниками. Пакеты для системы GAP представлены на данной странице на сайте системы.

Помимо уже упомянутых пакетов, система состоит из следующих четырех основных компонент:

2. Возможности работы с алгебраическими объектами

В разнообразии областей алгебры, охватываемых GAP, можно убедиться, даже только лишь прочитав названия разделов обширнейшей документации по системе, занимающей около 1500 страниц (которая, кстати, не только входит в состав дистрибутива, но и доступна через Интернет). Вычислительная мощь системы может быть продемонстрирована находящимся на ее сайте примером определения того, что кубик Рубика имеет 43252003274489856000 различных состояний, и сборки кубика Рубика из произвольного начального состояния в среднем за 100 ходов.

GAP дает возможность производить вычисления с гигантскими целыми и рациональными числами, допустимые значения которых ограничены только объемом доступной памяти. Далее, система работает с циклотомическими полями, конечными полями, р-адическими числами, многочленами от многих переменных, рациональными функциями, векторами и матрицами. Пользователю доступны различные комбинаторные функции, элементарные теоретико-числовые функции, разнообразные функции для работы с множествами и списками.

Группы могут быть заданы в различной форме, например, как группы подстановок, матричные группы, группы, заданные порождающими элементами и определяющими соотношениями. Более того, построив, например, групповую алгебру, можно вычислить ее мультипликативную группу, и даже задать ее подгруппу, порожденную конкретными обратимыми элементами групповой алгебры. Ряд групп может быть задан непосредственным обращением к библиотечным функциям (например, симметрическая и знакопеременная группы, группа диэдра, циклическая группа и др.).

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

Теория представлений групп также входит в область применения системы GAP. Здесь имеются инструменты для вычисления таблиц характеров конкретных групп, действий над характерами и интерактивного построения таблиц характеров, определения теоретико-групповых свойств на основании свойств таблицы характеров группы. Модулярные представления групп (т.е. представления над полем, характеристика которого делит порядок группы) также могут быть исследованы с помощью GAP.

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

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

Кроме новых алгоритмов и функций, в GAP 4.4 усовершенствована производительность многих уже существовавших ранее алгоритмов, в т.ч. для вычисления неприводимых представлений и их характеров, вычисления нормализаторов и сопряженных подгрупп в симметрических группах подстановок, вычисления системы представителей смежных классов в группах подстановок. Разложение подстановки в произведение порождающих элементов теперь вовзращает существенно более короткие слова (например, длины около 100 для группы кубика Рубика). Усовершенствования также коснулись списков, многочленов, матриц и матричных групп, расширений конечных групп, конечномерных алгебр.

В вышедшей в  мае 2005 г. версии GAP 4.4.5, в библиотеку конечных групп были добавлены следующие группы:
Также в ней была введена новая функция StructureDescription для вычисления структурных описаний конечных групп, например:
gap> l := AllSmallGroups( Size, 8 );;
gap> List( l, StructureDescription );
[ "C8", "C4 x C2", "D8", "Q8", "C2 x C2 x C2" ]
На сайте системы Вы можете ознакомиться с нововведениями, появившимися в версиях 4.4.6 и 4.4.7.

3. Инсталляция системы с помощью CHIP-CD

На CHIP-CD 9/2006 помещен экспериментальный дистрибутив системы GAP для Windows.
Его разработку и поддержку осуществляет автор данной статьи с помощью NSIS (Nullsoft Scriptable Install System) - свободно распространяемого и открытого программного продукта для создания инсталляторов для Windows.

Для установки системы GAP и пакетов для GAP нужно сначала проинсталлировать файлgap4r4p7.exe (основные компоненты системы, а также опциональные компоненты tools, htmie и xtom<>), а затем файл пакетов для системы GAP packages-<timestamp>.exe.

Инсталляция производится стандартным для Windows способом:
Скриншоты, демонстрирующие процесс инсталляции, помещены на странице экспериментального дистрибутива. Оттуда же можно загрузить его новые версии (наиболее часто обновляется архив пакетов).

После инсталляции для быстрой проверки работоспособности системы Вы можете запустить ее и ввести несколько команд, например:

gap> 3^80;
147808829414345923316083210206383297601
gap> G:=SymmetricGroup(10); 
Sym( [ 1 .. 10 ] )
gap> Size(G);
3628800


Затем Вы можете запустить более обширный тест (занимает несколько минут на современных компьютерах):
gap> tst := Filename( DirectoriesLibrary("tst"), "testall.g" );;
gap> Read(tst);
You should start GAP4 using: `gap -N -A -x 80 -r -m 100m'. The more
GAP4stones you get, the faster your system is. The runtime of
the following tests (in general) increases. You should expect
about 100000 GAP4stones on a Pentium 3, 1GHz.
The `next' time is an approximation of the running time for the next test.

Architecture: i686-pc-linux-gnu-gcc

test file GAP4stones time(msec)
-------------------------------------------
testing: /cygdrive/d/GAP4R4/tst/zlattice.tst

zlattice.tst 0 219

[ ... много строк вывода ... ]

grppcnrm.tst 40534 37795 (next ~ 39 sec)
testing: /cygdrive/d/GAP4R4/tst/grpmat.tst
grpmat.tst 40783 38251
-------------------------------------------
total 37223 229058
gap> quit;
После успешной инсталляции системы сообщите, пожалуйста, об этом в GAP Group, в соответствии с пожеланиями, находящимися здесь.

В случае возникновения проблем технического характера, если решить проблему самостоятельно не удается, Вы можете сообщить о ней (на английском языке) в группу поддержки пользователей GAP по адресу support <at> gap-system <dot> org или (на украинском, русском или английском языке) в Украинскую группу пользователей GAP по адресу konovalov <at> member <dot> ams <dot> org.

Если Вы воспользовались CHIP-CD 9/2006 для установки системы GAP, мы также будем благодарны за краткое сообщение об этом по адресу konovalov <at> member <dot> ams <dot> org.

Если Вы использовали систему GAP в Вашем исследовании, просим Вас включить ее в библиографию и ссылаться на нее так же, как Вы ссылаетесь на книги и статьи (рекомендации по оформлению ссылок приводятся здесь).



4. С чего начать работу с системой

Запустив систему, Вы увидите на экране нечто подобное:

            #########           ######         ###########           ### 
         #############          ######         ############         #### 
        ##############         ########        #############       ##### 
       ###############         ########        #####   ######      ##### 
      ######         #         #########       #####    #####     ###### 
     ######                   ##########       #####    #####    ####### 
     #####                    ##### ####       #####   ######   ######## 
     ####                    #####  #####      #############   ###  #### 
     #####     #######       ####    ####      ###########    ####  #### 
     #####     #######      #####    #####     ######        ####   #### 
     #####     #######      #####    #####     #####         #############
      #####      #####     ################    #####         #############
      ######     #####     ################    #####         #############
      ################    ##################   #####                #### 
       ###############    #####        #####   #####                #### 
         #############    #####        #####   #####                #### 
          #########      #####          #####  #####                ####   

     Information at:  http://www.gap-system.org
     Try '?help' for help. See also  '?copyright' and  '?authors'
    
   Loading the library. Please be patient, this may take a while.
GAP4, Version: 4.4.7 of 17-Mar-2006, i686-pc-cygwin-gcc
Components:  small 2.1, small2 2.0, small3 2.0, small4 1.0, small5 1.0,
             small6 1.0, small7 1.0, small8 1.0, small9 1.0, small10 0.2,
             id2 3.0, id3 2.1, id4 1.0, id5 1.0, id6 1.0, id9 1.0, id10 0.1,
             trans 1.0, prim 2.1  loaded.
Packages:    AClib 1.1, Polycyclic 1.1, Alnuth 2.1.1, CrystCat 1.1.2,
             Cryst 4.1.4, AutPGrp 1.2, CRISP 1.2.1, CTblLib 1.1.3,
             FactInt 1.4.8, GAPDoc 0.9999, LAGUNA 3.3.3, Sophus 1.12,
             Polenta 1.2, ResClasses 2.0.5  loaded.
gap>


Под эмблемой GAP4 Вы видите приглашение системы, после которого будут отображаться вводимые с клавиатуры символы:

gap>

Для выхода из системы применяется команда quit;  (заметим, что любая команда завершается точкой с запятой, после чего нужно нажать <Enter>).

Если Вы впервые работаете с системой, Вы можете попробовать начать читать и вводить (в т.ч. через копирование и вставку) примеры из первых глав Введения в GAP (HTML, PDF). В частности, там рассказывается, как пользоваться обширнейшей документацией по системе.

Вы можете попробовать, например, использовать GAP как простейший калькулятор:

gap> (9 - 7) * (5 + 6);
22
gap> 2^64;
18446744073709551616
gap> 3^132;
955004950796825236893190701774414011919935138974343129836853841

Определить последние пять из 9152052 цифр 43-го числа Мерсенна 230402457-1, найденного в декабре 2005 г. в ходе проекта GIMPS (Great Internet Mersenne Prime Search), и являющегося на сегодня самым большим из известных науке простых чисел:

gap> a:=2^30402457;
<<an integer too large to be printed>>
gap> a mod 100000;
43872


Вычислить наибольший общий делитель двух целых чисел и найти его линейное представление:

gap> Gcd(100, 48);
4
gap> Gcdex(100, 48);
rec( gcd := 4, coeff1 := 1, coeff2 := -2, coeff3 := -12, coeff4 := 25 )
gap> 100*1+48*-2;
4
gap> 100*-12+48*25;
0


Разложить целое число на множители с помощью функции FactorsInt:

gap> FactorsInt(2^64-1);
[3, 5, 17, 257, 641, 65537, 6700417]
gap> FactorsInt(2^128-1);
[3, 5, 17, 257, 641, 65537, 274177, 6700417, 67280421310721]
gap> FactorsInt(2^200-1);
[3, 5, 5, 5, 11, 17, 31, 41, 101, 251, 401, 601, 1801, 4051, 8101, 61681, 268501, 340801, 2787601, 3173389601]


GAP предоставляет разнообразные возможности для работы с множествами, списками, матрицами. Например, список квадратов натуральных чисел от 1 до 10 можно получить так:

gap> List([1..10], x -> x^2);
[ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 ]


А список натуральных чисел, не превосходящих 100 и являющихся произведением трех простых чисел (не обязательно различных), можно получить следующим образом:

gap> Filtered([1..100], x -> Length(Factors(x))=3 );
[ 8, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52, 63, 66, 68, 70, 75, 76, 78,
  92, 98, 99 ]


Теперь зададим матрицу следующим образом:

gap> A:=[[1,2,3,4],[4,2,1,5],[-1,10,0,0],[2,-4,7,0]];
[ [ 1, 2, 3, 4 ], [ 4, 2, 1, 5 ], [ -1, 10, 0, 0 ], [ 2, -4, 7, 0 ] ]


Для того, чтобы вывести ее на экран в удобочитаемой форме, используется команда Display:

gap> Display(A);
[ [   1,   2,   3,   4 ],
  [   4,   2,   1,   5 ],
  [  -1,  10,   0,   0 ],
  [   2,  -4,   7,   0 ] ]


Вычислим определитель этой матрицы:

gap> DeterminantMat(A);
-932

Таким образом, данная матрица является невырожденной, и система линейных уравнений с данной матрицей должна иметь единственное решение. Его можно найти с помощью функции SolutionMat( mat, vec ), которая возвращает вектор-строку x такую, что x * mat = vec (обратите внимание, что умножается вектор-строка на матрицу, а не матрица на вектор-столбец!). Пусть vec=[1,-1,0,3], тогда

gap> v:=SolutionMat(A,[1,-1,0,3]);
[ 519/932, 36/233, -323/932, -243/932 ]


Проверим, что действительно было найдено решение системы:

gap> v*A;
[ 1, -1, 0, 3 ]

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

Можно задать подстановки и вычислить их произведение:

gap> (1,2,3);
(1,2,3)
gap> (1,2,3) * (1,2);
(2,3)


Найти подстановку, обратную к данной:

gap> (1,2,3)^-1;
(1,3,2)


Найти образ точки под действием данной подстановки:

gap> 2^(1,2,3);
3


Вычислить подстановку, сопряженную с данной с помощью другой подстановки:

gap> (1,2,3)^(1,2);
(1,3,2)


Теперь зададим группу, порожденную двумя подстановками:

gap> s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );
Group( [ (1,2), (1,2,3,4,5,6,7,8) ] )


Как известно, это есть не что иное, как симметрическая группа подстановок 8-й степени. Теперь мы можем вычислить ее коммутант:

gap> a8 := DerivedSubgroup( s8 );
Group([(1,2,3),(2,3,4),(2,4)(3,5),(2,6,4),(2,4)(5,7),(2,8,6,4)(3,5)])


Исследуем свойства коммутанта - найдем его порядок, проверим его коммутативность:

gap> Size( a8 ); IsAbelian( a8 );
20160
false


Более нетривиальные примеры применения GAP Вы сможете найти в документации к системе, содержащейся в подкаталоге gap4r4\doc или на сайте системы GAP.

Материалы о системе компьютерной алгебры GAP на русском языке Вы можете найти, посетив сайт Украинской группы пользователей GAP. В частности, в разделе "Изучаем алгебру с GAP" этого сайта содержится серия примеров к курсу алгебры и теории чисел, а в разделе "Подробнее..." - методическое пособие по системе GAP.

Рекомендуем также подписаться на GAP Forum - англоязычный форум для обсуждения связанных с GAP вопросов, сообщений об обновлениях, новых версиях, пакетах, конференциях и др. связанных с GAP событиях.

Желаем Вам приятной работы с системой GAP!


С уважением,
Александр Борисович Коновалов
председатель Украинской группы пользователей GAP
доцент кафедры алгебры и геометрии Запорожского государственного университета
E-mail: konovalov <at> member <dot> ams <dot> org