- PVSM.RU - https://www.pvsm.ru -
PARI/GP [1] — это система компьютерной математики с собственным C-подобным интерпретируемым языком, ориентированная на вычислительную теорию чисел. Система пользуется популярностью в научной среде: согласно Google Scholar только за 2014 год порядка 100 тематических статей, использующих PARI/GP, были опубликованы в реферируемых журналах/конференциях.
В моём диссертационном исследовании мне требовалось часто решать традиционные задачи линейной алгебры (например, для матрицы большой размерности вычислить её ядро и ранг), но только над конечными полями (например, или ). Если бы у нас были просто комплексные матрицы, то эффективно справились бы все хоть сколько-нибудь известные системы символьной математики: например, в любимой мною Wolfram Mathematica [2] достаточно использовать функции NullSpace и MatrixRank соответственно. Вот было бы здорово, если эти же функции враз заработали и для матриц над конечными полями, пусть и с потерей в производительности из-за неэффективности общих алгоритмов линейной алгебры для них… Увы, я получил экспоненциальный рост (вплоть до часов на моём бедном нетоповом ноутбуке) времени вычислений от размерности матриц (см. мой вопрос [3] на профильном форуме по Wolfram Mathematica). Правда, справедливости ради, это было вызвано не столько проблемами реализации алгоритмов линейной алгебры, сколько проблемами самого процессора символьных вычислений.
К моей великой радости PARI/GP предназачается именно для расчётов в различных алгебраических системах (кольцах, полях), оперируя их элементами как «атомарными» числами, а не как символьными структурами над встроенными типами. По моему эмпирическому наблюдению, PARI/GP имеет непревзойдённую скорость таких вычислений. К тому же есть возможность трансляции интерпретируемого кода в чистый C.
Описание далее достаточно «высокоуровневое», без отсылки к алгоритмам и структурам данных, используемым внутри PARI/GP (темы будущих постов).
Как было уже сказано, PARI/GP использует свой C-подобный язык. Подробное руководство можно посмотреть тут [4]. Далее следует небольшое описание, поясняющее отдельные моменты примера ниже (и даже больше):
x = 12;
type(x)
>"t_INT"
type('x)
>"t_POL"
{ x = 12; }
x
>12
{ my(y = -13.2); }
y
>y
createField = (q, n, var) -> ffgen(minpoly(ffprimroot(ffgen(ffinit(q, n, var), var))), var);
a = createField(2, 4, 'x)
>x
fforder(a) \ вычисляет мулььтипликативный порядок элемента
>15
allocatemem(2^27); \ аллоцирует 128Мб памяти под внутренний стек PARI/GP
M = matrix(1000, 1000, i,j, random(a)); \ создает случайную 1000х1000 матрицу над полем GF(16)
{gettime(); matrank(M); gettime()} \ вернет время (мс) на расчёт ранга этой матрицы
>34209
{gettime(); kernel(M~); gettime()} \ время на расчёт ядра пространства строк этой матрицы
>88425
Конфигурация моего ноутбука — Intel® Core(TM) i7-4702M CPU @ 2.20GHz 2.20GHz, 32kB L1 cache, 8Gb DDR3. Использовался PARI/GP 2.7.2 (32bit, single thread) — это последний на момент публикации этого текста релиз, «работающий из коробки» под ОС Windows.
Автор: semenovp
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/81745
Ссылки в тексте:
[1] PARI/GP: http://pari.math.u-bordeaux.fr/
[2] Wolfram Mathematica: http://www.wolfram.com/mathematica/
[3] вопрос: http://mathematica.stackexchange.com/questions/15140/finitefields-package-is-very-slow-any-fast-substitute-for-mathematica
[4] тут: http://www.math.uiuc.edu/~r-ash/GPTutorial.pdf
[5] Источник: http://habrahabr.ru/post/249785/
Нажмите здесь для печати.