автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Параллельные полиномиальные алгоритмы в компьютерной алгебре

Тамбовский государственный университет имени Г Р Державина

На правах рукописи

Валеев Юрий Дамирович

ПАРАЛЛЕЛЬНЫЕ ПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ В КОМПЬЮТЕРНОЙ АЛГЕБРЕ

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

0031Т80и г

Тамбов 2007

003178007

Работа выполнена в лаборатории алгебраических вычислений Тамбовского государственного университета им Г Р Державина

Научный руководитель доктор физико-математических наук,

профессор

Малашонок Геннадий Иванович

Официальные оппоненты доктор физико-математических наук,

старший научный сотрудник Корняк Владимир Васильевич

кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович

Ведущая организация Тамбовский государственный технический университет

Защита диссертации состоится "21" декабря 2007 г в 15 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, г Москва, ул Большая Коммунистическая, 25, Институт системного программирования РАН, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан "20" ноября 2007 г

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

/Прохоров СП/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы

С появлением параллельных компьютеров возникла потребность в программах, максимально использующих их возможности Одни технологии параллельного программирования требуют от программиста явного описания какие части программы и данных буд^т распределены на конкретные процессоры Это может быть как распределение витков циклов, разделение главной программы на части и указание с помощью директив какие части должны быть вычислены на других процессорах Другие технологии оформлены в виде параллельных языков программирования, но существующие реализации их пока далеки от оптимальной эффективности Одни технологии являются дополнительными библиотеками, которые расширяют стандартные языки программирования специальными командами пересылки данных межд} процессорами Испотьзуя их, пользователям приходится" описывать все обмены данными между процессорами, следить за тем, чтобы не было длительных остановок в вычислениях

Программы, написанные с использованием этих технологий, требуют дополнительных усилий по отладке и оптимизации, тк нужно учитывать большое число факторов Это, во-первых, однородность данных задачи Если данные неоднородны, то некоторые процессоры мог} т вычислить свои подзадачи быстрее, таким образом они будут простаивать пока другие процессоры не вычислят свои части Для устранения этой проблемы приходится применять специальные методы для исправления неоднородности или менять исходный алгоритм Получающиеся при этом программы могут работать менее эффективно на других конфигурациях параллельных компьютеров Учет всех этих дополнительных нюансов для достижения оптимальной масштабируемости программы требует дополнительного времени на разработку Поэтому требуются системы автоматического распараллеливания, которые могут сами перераспределять данные и вычисления на свободные процессоры Эти системы должны отслеживать свободные и занятые процессоры и автоматически вызывать ф> нкции для пересылки этих данных Пользователю требуется лишь описать граф своего алгоритма и производимые в вершинах графа вычисле-

ния

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

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

Цель работы.

Цель диссертационной работы состоит в разработке способа организации параллельных вычислений для решения задач компьютерной алгебры Задачи работы

• Разработка способа организации параллельных вычислений для рекурсивных последовательных алгоритмов

• Разработка параллельных алгоритмов для полиномиальных операций

• Разработка способа организации параллельных вычислений для операций над полиномиальными матрицами

Методы исследования. В работе используются методы компьютерной алгебры, теории графов, теории вероятностей Для экспериментов используется язык программирования Java, для организации параллельных вычислений - среда ParJava ИСП РАН

Научная новизна.

• Разработан новый способ организации параллельных вычислений для рекурсивных алгоритмов Он включает в себя систему динамического распределения заданий и позволяет решать задачи как с однородными, так и с неоднородными данными В каждый момент времени отслеживаются свободные процессоры и размеры подзадач, вычисляемые процессорами Используется крупноблочное распараллеливание, т е освободившимся процессорам выделяется наибольшая связная компонента задачи для минимизации числа пересылок между процессорами

• В зависимости от входных данных автоматически выбирается лучший алгоритм умножения полиномов

• Разработаны новые форматы хранения полиномов многих переменных векторный формат и формат двоичного дерева (бидерева) Разработаны алгоритмы для операций над ними Оба формата ориентированы на применение в параллельных вычислительных системах и допускают эффективное разделение полиномов на части и пересылку частей

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

Апробация работы.

Результаты исследований в рамках данной работы докладывались на следующих конференциях

- Международная конференция "Алгебра и анализ" (Казань, 2-9 июля 2004),

- 6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),

- IX Международная конференция "Проблемы теоретической кибернетики" (Пенза, 23-28 мая 2005),

- 12-я международная конференция, посвященная приложениям компьютерной алгебры (Варна, Болгария, 26-29 июня 2006),

- Державинские чтения (Тамбов, 2004-2007),

- научные семинары в Тамбовском университете

Публикации автора. Основные результаты диссертации опубликованы в 13 работах

Структура и объем работы .Диссертация состоит из введения, 3 глав, списка литературы и приложения

СОДЕРЖАНИЕ РАБОТЫ

В 1-й главе описывается способ организации параллельных вычислений, который называется схемой LLP(Low Level Parallelization) В 1-м разделе описываются принципы функционирования и организация данных, а во 2-м разделе приводится детальное описание алгоритмов, применяемых в схеме LLP

Пусть в вычислениях участвуют п компьютерных модулей (КМ) КМ с номером 0 будет называться главным, т к он получает все задание и в него возвращается результат вычислений, а КМ с номером 1 будет называться диспетчером, он играет роль основного управляющего модуля

Характеристики схемы LLP:

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

2 Наличие планировщика (диспетчера), который следит за работой всех КМ Если некоторый КМ освобождается, то диспетчер находит один из наиболее загруженных процессоров и разрешает ему передать часть своего задания свободному процессору За счет такого перераспределения заданий достигается равномерная нагрузка всех процессоров системы

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

4. Повторное использование готовых схем параллельных вычислений, они включаются как подсхемы

5. Предлагаемая предполагает использование интерфейса MPI, а, следовательно, может использоваться на всех параллельных системах, поддерживающих MPI

веса О веса 1 веса 2 веса 3

Рис. 1. Представление графа в виде одноуровнего взвешенного дерева

Сначала могут быть распределены и обрабатываться параллельно вершины веса 0, затем веса 1 и т д Каждый вычислительный блок в вершине является вычислительным алгоритмом, который может быть представлен своим взвешенным деревом Поэтому граф всего вычислительного алгоритма разворачивается в многоуровневое дерево

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

В 1-м разделе описывается векторный формат хранения полиномов и рассматриваются алгоритмы дтя основных операций с полиномами в этом формате Основная идея векторного формата заключается в следующем Пусть полином нескольких переменных представлен в виде вектора, элементами которого являются мономы Мономы в векторе расположены в некотором порядке Полином / € Я[х1,х2, хранится в виде (/1,

/2, , /т), где - мономы полинома / и /1 > /2 > > /т (запись /г > /; означает, что моном /, старше монома согласно заданному порядку)

В памяти компьютера данный вектор хранится в виде 2-х векторов информационного и вектора коэффициентов В информационном векторе записаны степени всех мономов в том порядке, в котором они перечислены в векторе, по р степеней на каждый моном, где р - номер самой старшей переменной, которая присутствует в полиноме, из заданного полиномиального кольца В.[х 1,2:2, ,х„] Информационный вектор представляет из себя вектор

кц,к\2, , &21) ,кт1,кт2, ,ктр,

где к,1,кг2, ,кгр - степени монома /, при переменных х\,Х2, ,хр В векторе коэффициентов хранятся коэффициенты мономов полинома в порядке их перечисления в векторе

Достоинствами хранения полиномов в векторном формате являются

1. Компактность, те при хранении используется малый объем памяти

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

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

Недостатком является сложность умножения полинома на моном, т к нужно умножить его на каждый моном полинома

Во 2-м разделе описывается формат хранения полиномов в виде би-

дерева и приводятся алгоритмы, предназначенные для операции с полиномами, записанными в данном формате

Предлагаемый формат основан на идее дихотомического деления полинома Для полинома Г(х) одной переменной происходит разделение на старшую ¡\(х) и младшую /г(х) части так, что /(ж) = /1(2;) + /2(ж), ¿ед{/2{х)) < 2к~г ^ йед{/(х)) = йед{Д(аг)) < 2к Таким образом, /(ж) = /{(х)х2 + /2(2:) Для полиномов многих переменных вводится порядок на переменных и выделяется старшая переменная Затем полином рассматривается как полином от одной старшей переменной над кольцом полиномов от остальных переменных Эта процедура повторяется по всем переменным

Рассмотрим подробнее формат для полинома одной переменной над числовым кольцом Пусть задан полином / 6 2[х] /(х) = апхп+ап-1хп~1 + + а о, 2к~1 < с1ед(/(х)) < 2к Полином хранится в виде бинарного дерева (бидерева) высотой к Мономы соответствуют концевым вершинам Путь от корня до концевой вершины, соответствующей моному агхг, кодируется двоичной записью числа г, г = (Ьк,Ьк-1, ,61) Каждый бит Ь3 определяет одно из двух возможных направлений для исходящего ребра

1 - левое, 0 - правое

В строении полинома многих переменных эта конструкция повторяется Пусть / 6 Я[х 1,Х2, ,гт] = 2[х1,Х2, ,хт-1}[хт} Запишем полином f в виде /(хт) = апХт + ап-гх^1 + + ао, где а} е г[х1,х2, , хт-1] Построим бидерево, соответствующее полиному одной переменной хт Его концевые вершины указывают на полиномы т — 1 переменной а} Аналогично строятся бидеревья, соответствующие этим полиномам, и так продолжается далее до XI, концевым вершинам последних бидере-вьев соответствуют числовые коэффициенты Полученное бидерево для

полинома т переменных естественным образом распадается на т слоев слой ] образован бидеревьями _/-той переменной

Достоинствами хранения полиномов в этом формате являются

- быстрое разделение на старшую и младшую часть

- быстрое умножение полинома на мономы

Эти 2 свойства бидеревьев делают алгоритм Карацубы очень эффективным

Недостатком этого формата являются дополнительные накладные расходы

В 3-м разделе рассматриваются теоретические оценки сложности стандартного алгоритма умножения полиномов и алгоритма умножения Карацубы для разреженных полиномов

Пусть Ш - область, каждый элемент которой может быть записан в одном машинном слове

Определение 1. Назовем полиномом типа (т,аг) случайный полином ЕГ=1 Сгх'-1 из Ш[:г] коэффициент Сг которого отличен от нуля с вероятностью ач (1 ^ г ^ го)

Если а, = а для всех г, то будем записывать тип полинома в виде (т,а), а число а будем называть плотностью полинома

Для области характеристики 0 справедливы следующие равенства (слева типы операндов, а справа типы результата)

(т,а) + (го,/3) = (го, 1 - (1 - а)( 1 - /3)), (1)

{т,а) х (го,/3) = (2т — 1,7ггт) (2)

Здесь и далее используются обозначения

= г, при 1 < г < гтг, = 2тгс — г, при т ^ г ^ 2т — 1, (3)

тгГ = 1 - (1 - <*/3)С при 1 ^ г < 2т - 1 (4)

Будем обозначать, соответственно, Е.А и ЕМ. математические ожидания числа операций сложения и числа операций умножения в алгоритме Предложение 1. При вычислении произведения полиномов типов (ш, а) и (го,/3), с помощью стандартного алгоритма имеем

е м = £Л = т2ар

Обозначим = (1 — а)2 , <7(в) = 1 —

Рассмотрим алгоритм Карацубы (5) для случая, когда т = 2м, ¡3 = 7 = сг(в), где г и в - могут быть любыми неотрицательными целыми

Предложение 2. При вычислении произведения полиномов типов (т, ст(г)) и (m,a(s)), г, s ^ 0, с помощью алгоритма Карацубы имеем

Предложение 3 При вычислении произведения полиномов типа (тп,

сг(г)) и (m,a(s)), г, s ^ 0, т = 2м с помощью алгоритма Карацубы имеем

М-1 к /,\

SAZ, = £ £ ( ) 2к-'СР(2м-к-\г + г,в + г)

к=0 1=0 V /

Алгоритмы умножения полиномов в области Z[x] Целое число имеет тип (w), если оно хранится в w машинных словах Примем следующую модель вычислителя (w) + (v) = (max(v,w)), (w) x (и) = (w+v) Для алгоритма суммирования типа (w)+(w) число сложений положим равным w, а для стандартного алгоритма умножения (w) х (v) количество умножений и количество сложений положим равными vw

Для умножения чисел из Z[x] по алгоритму Карацубы число операций умножения равно N™K = u>'°S23, а число операций сложения равно N«K = J^tZo 3'(2 28-1-1 + 4 2s-t) = 3 - w)

Для стандартного умножения чисел типа (w) число операций сложения и умножения обозначим, соответственно, = w2 и N™s = w2

Определение 2. Назовем полиномом типа (тп, аг,гс) случайный полином 1 с'х'~1 из W[x] коэффициент с, которого отличен от нуля с вероятностью а, (1 ^ г < т) и все ненулевые коэффициенты имеют тип

И

Предложение 4. При вычислении произведения полиномов типов (т, cr(r),w) и (m,a(s),w), г, s ^ 0, с помощью стандартного алгоритма умножения полиномов, получим

£M™r¡StW = т2 a(r)cr{s)N™, (12)

£J&Sr,s,w = m2c(r)a(s)(K + 2u>) (13)

Предложение 5. При вычислении произведения полиномов типов (т, <r(r),w) и (m,a(s),w), г, s ^ 0, т = 2м с помощью алгоритма Карацубы имеем

= (14)

м-1 к /,\

еAÍKr¡s,w = кем™.,. + £ £ , (15)

k=О 1=0 \г/

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

В 3-й главе рассматривается применение LLP схемы для вычисления произведения матриц и для вычисления обратной матрицы 1

В 1-м разделе приводится реализация схемы LLP для блочного алгоритма умножения матриц

Во 2-м разделе приводится реализация LLP схемы для обращения матриц

Алгоритм обращения матриц заключается в следующем Пусть F -поле, полугруппа Рп образована матрицами над F порядка п, у которых число единичных элементов совпадает с рангом матрицы, а остальные элементы равны нулю Полугруппа Dn образована диагональными матрицами порядка п с элементами 0 и 1 на диагонали, |Z?n|=2n и единичная матрица I - единица в Dn и в Рп Чертой обозначается инволюция на Dn 1 = 1 — 1 Для матрицы Е Е Рп единичные элементы на диагонали I = ЕЕТ € Dn соответствуют ненулевым строкам матрицы Е Аналогично для диагонали J = ЕТЕ е Dn Запись А = IA, (А = AJ), I,J е Dn используется для указания на все нулевые строки (столбцы) матрицы А Вычислим две обратимые матрицы Ли С для произвольной матрицы А £ такие что RAC = Е 6 Рп, R - нижняя треугольная и С -

верхняя треугольная, причем, если А = IAJ и/, J £ Dn, то матрицы R и С имеют вид R = I + IRI, С = J + JRJ Отметим, что при этом

1 Рекурсивный шаг вычисляются такие обратимые матрицы Ли и Си , что -Яп-АпСп — Ец 6 Рп Находим К\АС\ = А1, где

1Малашонок Г.И , Зуев М. С. Обобщенный алгоритм вычисления обратной матрицы //XI Державинские чтения Тезисы докладов Тамбов Изд-во ТГУ им Г Р Державина, 2006 - С 48-50

Е = IE J

Если А - обратима, то ЕТЕ = I и А 1 = СЕТР Пусть матрица А порядка 2п, разбита на равные блоки

Здесь /1_= ЕцЯп, Л = ЕпЕп, а = Я11А12, /3 = АпСи, А^ = Ей, = /ЗЛ, = 1ю, А\2 = Л22 - РЕ^а

2 Параллельно выполняемые рекурсивные шаги вычисляются такие обратимые матрицы Й12, С12, Я21, С21, что Д12А12С12 = £12 _

Я21Л21С21 = £21 При этом Д12 = /1_+ /1Я12/1, С21 = Л + а

матрицы £12 и £21 имеют вид Е12 = 1\Е\2 € Рп, Е21 = E2\J\ £ Рп Находим Д2А1С2 = А2, где

С21

д2

= / Й12 О ^ -7^2^12 Я21

\ с / С21 -СиЕ^Лз \

у ' 2 \ О С12 у

Здесь обозначено = Е^Еи, {21 = £21 £21, 7 = Д21Л22С12, А21 -= Е\2, А221 = £п, А\2 = /217^12

£11 = (^п)Г

=

= К

= СпЕтп

Ч

У!1 = - гетр

12

Ет 21

Рис. 2 Граф алгоритма с двухсторонним разложением 3 Рекурсивный шаг вычисляются такие обратимые матрицы Я22 и С22, что Д22А22С22 = Е22, при этом Е22 = /21^22 Jl2 £ Рп, Р-22 = /21 +

/21^22/21 и С22 = Лг +

Находим, ПзА2С'з = Е Перемножим найденные матрицы, в результате получим RАС = Я, где

R-.

RnRu О

-R22(fE'[2Ri2 + R2ipE'[1)Rn R22R21 J'

c=f СпСл -Cii{C2iE%ijJi2 + EmaCu)C22

C12C22

Рис. 3. Граф алгоритма с двухсторонним разложением (Продолжение)

На рисунке 3 вершины разного типа обозначены различными фигурами Каждая вершина обозначает задание в LLP, которое имеет свой номер и свой граф Квадраты обозначают тот же алгоритм, что и весь

граф, т е алгоритм обращения матрицы Обозначим это задание константой MATR_INV, которая имеет значение отличное от номеров других заданий

Два задания на графе обозначены большими эллипсами Задание, вычисляющее А21, имеет номер MATR_INV1, а задание, вычисляющее А^, - номер MATR_INV2

Круги обозначают вершины типа MATR_MUL - умножение матриц по модулю

Треугольники - умножение по модулю А на (-В), где А и В - матрицы Задание для него имеет номер MATR_AMB

Трапеции - это задания, вычисляющие выражения вида AB+CD, где умножение производится без модуля, а сложение по модулю Эти задания имеют номер MATR_AB_CD

В приложении приведены реализации на языке Java заданий LLP для блочного алгоритма умножения матриц и для двустороннего алгоритма обращения матриц

В работе получены следующие результаты

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

• Разработана LLP схема для умножения полиномов Разработаны новые форматы хранения полиномов многих переменных векторный формат и формат двоичного дерева и алгоритмы для операций над ними Форматы предназначены для разреженных полиномов Они ориентированы на применение в параллельных вычислительных системах и допускают эффективное разделение полиномов на части и пересылку частей В зависимости от входных данных автоматически выбирается лучший алгоритм умножения полиномов

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

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

• Разработана LLP схема для умножения матриц

• Разработана LLP схема для обращения матриц

Основные публикации по теме диссертации:

Статьи в изданиях по перечню ВАК'

1 Малашонок Г И , Валеев Ю Д Об одном формате полиномов для параллельных вычислений // Вестн Тамб ун-та Сер Естеств и техн науки Тамбов, 2004 Т 9, вып 1 С 149-150

2 Малашонок Г И , Валеев Ю Д , Зуев М С О параллельных матричных алгоритмах в компьютерной алгебре // Вестн Тамб ун-та Сер Естеств и техн науки Тамбов, 2005 Т 10, вып 1 С 102-104

3 Малашонок Г И , Валеев Ю Д О некоторых подходах к построению параллельных программ // Вестн Тамб ун-та Сер

Естеств и техн науки Тамбов, 2005 Т 10, вып 1 С 154-156

4 Малашонок Г И , Валеев Ю Д Рекурсивное распараллеливание символьно-численных алгоритмов//Вестн Тамб ун-та Сер Естеств и техн науки Тамбов, 2006 Т 11, вып 4 С 536-549

Учебные пособия

5 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельная компьютерная алгебра Введение Тамбов Изд-во ТГУ им Г Р Державина, 2006 102 с

6 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры Тамбов Изд-во ТГУ им Г Р Державина, 2006 122 с

Прочие публикации

7 Валеев Ю Д Параллельные схемы умножения полиномов // Труды Математического центра им Н И Лобачевского, том 23 Казань Изд-во Казанского математического общества, 2004 С 47

8 Валеев Ю Д , Малашонок Г И О сложности алгоритмов умножения полиномов // Труды 6 Международной конференции "Дискретные модели в теории управляющих систем" М Изд-во ВМиК МГУ, 2004 С 32-40

9 Малашонок Г И , Аветисян А И , Валеев Ю Д , Зуев М С Параллельные алгоритмы компьютерной алгебры // Труды института системного программирования /под ред В П Иванникова М ИСП РАН, 2004 С 169-180

>ъ

10 Валеев Ю Д О сложности алгоритмов для разреженных полиномов//Проблемы теоретической кибернетики Тез докл XIV Междунар конф M Изд-во механико-математического факультета МГУ, 2005 С 52

11 Малашонок Г И , Валеев Ю Д Динамическое распределение заданий в вычислительном кластере по графу алгоритма //XI Державинские чтения Тезисы докладов Тамбов Изд-во ТГУ им Г Р Державина, 2006 С 38-47

12 Валеев Ю Д К истории параллельных вычислений // Современное математическое образование и проблемы истории и методологии науки Тамбов Изд-во Першина Р В , 2006 С 125-130

13 Malaschonok G I, Valeev Y D , Zuyev M S , Kazakov V N On the parallel computer algebra // АСА 2006 12th International Conference on Applications of Computer Algebra Institute of Mathematics and Informatics Bulgarian Academy of Sciences (June 26-29, 2006, Varna, Bulgaria ) Sofia, 2006 P 52

Подписано в печать 15 11 2007 г Формат 60 X 48/16 Объем 1,0 п л Тираж 100 экз Заказ № 1155 Бесплатно 392008, г Тамбов, Советская, 1£Юг Издательство ТГУ им Г Р Державина