Эксперименты с параллельным алгоритмом вычисления характеристических полиномов матриц в кольце полиномов

Как видно из таблицы, при увеличении количества процессоров с 2 до 4 время уменьшилось в 1,9 раза, при увеличении с 2 до 8 — в 3,34 раза. Следовательно, для данного эксперимента эффективно использовать рассмотренный параллельный алгоритм для вычисления базиса Гребнера полиномиальных идеалов на 8 процессорах.

ЛИТЕРАТУРА

1. Г.И. Малашонок, М.В. Старое, А.А. Бетин, О.Н. Переславцева, А.Г. Поздникин Параллельная компьютерная алгебра. Часть 1. Учебное пособие. Тамбов: Издательский дом ТГУ им. Г.Р. Державина, 2009.

2. Faugere J.-C. A new efficient algorithm for computing Groebner bases (F4), J. Pure Appl. Algebra, 139:1-3 (1999), 61-88.

Starov M.V. Realization of Fougere’s method for calculation of polynomial basis. Experiments with a parallel algorithm for calculation for ideals of polynomial basis are stated.

Key words: calculation of a Groebner basis, parallel algorithm, algorithm F4, Faugere’s method, cluster.

Поступила в редакцию 20 ноября 2009г.

УДК 004.421

ЭКСПЕРИМЕНТЫ С ПАРАЛЛЕЛЬНЫМ АЛГОРИТМОМ ВЫЧИСЛЕНИЯ ХАРАКТЕРИСТИЧЕСКИХ ПОЛИНОМОВ МАТРИЦ В

КОЛЬЦЕ ПОЛИНОМОВ1

© О. Н. Переславцева

Ключевые слова: вычисление характеристического полинома, параллельный алгоритм, кластер.

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

В работе [1] был рассмотрен параллельный алгоритм вычисления характеристических полиномов матриц, основанный на методе гомоморфных образов [2] в кольце полиномов с целочисленными коэффициентами. На основе приведённого алгоритма был разработан программный комплекс для параллельного вычисления характеристических полиномов

1 Работа выполнена при поддержке программы «Развитие потенциала высшей школы» (проект 2.1.1/1853) и Темплана 1.12.09.

матриц в кольце полиномов, с которым были проведены эксперименты на кластере ТГУ им. Г.Р. Державина и на кластере МСЦ РАН.

Для оценки эффективности параллельного алгоритма введем понятие ускорения. Обозначим через Ьк время вычисления задачи на кластере с к процессорами. При переходе от кластера с п процессорами к кластеру с к процессорами, к > п, ускорение достигает 100%, когда £„/£*,. = к/п. Ускорение равно нулю, когда ^ = tn . Чтобы определить ускорение вычислений при других значениях £„/£*; определим ускорение как функцию времени •

Определение. Ускорением вычислений при переходе от п -процессорного кластера, где время вычислений равно , к к -процессорному кластеру, где время вычислений равно Ьк, к > п, называется функция ап^ = {К/^к ~ 1 )/(к/п — 1) • 100%.

Эксперимент 1 проводился на кластере ТГУ им. Г.Р. Державина. В эксперименте использовались плотные полиномиальные матрицы размера 40 х 40 над полиномами от двух переменных с 10-разрядными коэффициентами, старшая степень каждой переменной равна 2.

Зависимость времени вычисления от количества процессоров и ускорение вычислений при переходе от 2-процессорного кластера к 4-процессорному и 8-процессорному кластерам приведены в табл. 1.

Таблица 1

Время и ускорение вычислений характеристического полинома полиномиальной матрицы с использованием алгоритма, основанного на методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского; порядок матрицы п = 40, разрядность числовых коэффициентов Ь = 10 бит, старшие степени переменных (1ед = [2,2].

Количество процессоров к 2 4 8

Время £*;, с 4480 2424 1631

Ускорение «2,к 85% 58%

Как показывают эксперименты, результаты которых приведены в табл. 1, ускорение вычислений составило 85% при переходе от 2 -процессорного кластера к 4 -процессорному кластеру и 58% при переходе к 8 -процессорному кластеру.

Эксперимент 2 проводился на кластере МВС-100К в МСЦ РАН. В эксперименте использовались плотные полиномиальные матрицы размера 50 х 50 над полиномами от двух переменных с 10-разрядными коэффициентами. Старшие степени переменных равны 2: Лед =[2,2].

График зависимости времени вычисления от количества процессоров приведён на рис. 1. В табл. 2 приведено ускорение вычислений при переходе от 1-процессорного кластера.

Тип«

Рис. 1. Зависимость времени вычисления характеристического полинома с использованием алгоритма, основанного на методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского [3], от количества процессоров пРгос \ порядок матрицы п — 50, разрядность числовых коэффициентов Ъ = 10 бит, старшие степени переменных <1ед = [2,2].

Таблица 2

Время и ускорение вычислений характеристического полинома полиномиальной матрицы с использованием алгоритма, основанного на методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского; порядок матрицы п = 50, разрядность числовых коэффициентов Ь = 10 бит, старшие степени переменных <1ед = [2,2].

Количество процессоров к 1 2 4 8 16 32 64 128 256

Время с 16558 8676 4548 2651 1626 1146 748 513 510

Ускорение о:х>. 91% 88% 75% 61% 43% 34% 25% 12%

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

Проведённые эксперименты показали, что для полиномиальных матриц для некоторого числа процессоров пересылаемые блоки становятся на столько малыми, что время пересылки приближается к времени вычислений. Поэтому при увеличении количества процессоров ускорение вычислений становится близким к 0, начиная с некоторого числа процессоров. Это говорит о том, что дальнейшее распараллеливание не выгодно. Так, лучшее время вычисления характеристических полиномов матриц размера 50 х 50 над полиномами от двух переменных, старшие степени которых равны 2, с 10-разрядными коэффициентами на кластере МВС-100К в МСЦ РАН будет около 10 минут.

ЛИТЕРАТУРА

1. Переславцева О.Н. Параллельное вычисление характеристического полинома матрицы // Параллельные вычислительные технологии (ПаВТ’2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009 г.). Челябинск: Изд. ЮУрГУ, 2009. С. 817-821.

2. Компьютерная алгебра: Символьные и алгебраические вычисления. Пер. с англ./ Под ред. Б. Бух-бергера, Дж. Коллинза, Р. Лооса. М.: Мир, 1986.

3. Данилевский А.М. О численном решении векового уравнения // Матем. сб. 1937. Т.2(44). N1. 169-

172.

Pereslavtseva O.N. Experiments with a parallel algorithm for calculation of the characteristic polynomial for polynomials matrixes. Experiments with a parallel algorithm for calculation of the characteristic polynomial for polynomials matrixes on the MVS and TSU clusters are stated and discussed.

Key words: calculation of a characteristic polynomial, parallel algorithm.

Поступила в редакцию 20 ноября 2009г.

УДК 004.421

УМНОЖЕНИЕ ФАЙЛОВЫХ ПОЛИНОМОВ1

© А. Г. Поздникин

Ключевые слова: файловый полином, умножение файловых полиномов, параллельный алгоритм.

Предлагается параллельный алгоритм умножения полиномов, которые не помещаются в оперативную память. Такие полиномы назовём файловыми полиномами, т. к. они хранятся в файлах на жёстком диске. Приводятся и обсуждаются результаты с параллельным алгоритмом вычисления произведения файловых полиномов.

1 Введение

Большинство математических систем позволяют производить операции с полиномами, которые хранятся в оперативной памяти компьютера. А когда полином не помещается в оперативную пямять, такие системы оказываются непригодными. Так как объёмы используемой оперативной памяти обычно меньше дисковой, то можно хранить полиномы в файлах на жёстком диске. Полином, записанный в файл на жёстком диске в определённом формате, будем называть файловым.

1 Работа выполнена при поддержке программы «Развитие потенциала высшей школы»